Tic Tac Toe Random AI

Question

I am working on building a Tic Tac Toe game with varying AI implementations for a computer opponent for the sake of learning different algorithms and how to implement them. The first I am trying which should be the easiest is just having the computer choose a random space each time.

This is working for me to a certain extent, the issue becomes run time. Every time the aiRandMove() method is called, it takes longer and longer to pick a move to the point where after 5 moves have been made on board (cpu + user combined) the program appears to hang (although this isn't technically the case).

Upon further debugging on my part I realize that this should be expected as the aiRandMove() method is randomly choosing an X and Y coordinate and then the move is tested to see if it is legal. As less and less spaces are open, there are fewer and fewer legal moves, thus many more failed attempts by the randomizer to generate a legal move.

My questions is, Is there any way I can modify this that would at least reduce the time taken by the function? As far as I can tell from googling and just running through the problem myself, I cannot think of a way to optimize this without compromising the "randomness" of the function. I thought about keeping an array of moves the computer attempted but that would not resolve the problem because that would not affect the amount of times rand() generated duplicate numbers. Here is the code for this function which is all that is really relevant to this issue:

//Function which handles the AI making a random move requires a board
//object to test moves legality and player object to make a move with
//both are passed by reference because changes to board state and the player's
//evaluation arrays must be saved
char aiRandMove(Player &ai, Board &game){
   int tryX;
   int tryY; //Variables to store computer's attempted moves
   bool moveMade = false;
   char winner;
   while(!moveMade){
      srand(time(NULL));//Randomizes the seed for rand()
      tryX = rand() % 3;
      tryY = rand() % 3; //coordinates are random numbers between X and Y
      cout << "Trying move " << tryX << ", " << tryY << endl;
      if(game.isLegalMove(tryX, tryY)){
         winner = game.makeMove(tryX, tryY, ai);
         moveMade = true;
      }
   }
   return winner;
}

I have also tried moving the seed function out of the while loop (this was put inside the while to "increase randomness" even though that is something of a logical folly and this has also not improved results.

If all else fails I may just label this method "Easy" and only have random moves until I can tell if I need to block or make the winning move. But perhaps there are other random functions which may assist in this endeavor. Any and all thoughts and comments are more than appreciated!

Answer 1

You need to remove the invalid moves from the equation, such as with the following pseudo-code, using an array to collect valid moves:

possibleMoves = []
for each move in allMoves:
    if move is valid:
        add move to possibleMoves
move = possibleMoves[random (possibleMoves.length)]

That removes the possibility that you will call random more than once per attempted move since all possibilities in the array are valid.

Alternatively, you can start the game with all moves in the possibleMoves array and remove each possibility as it's used.

You also need to learn that it's better to seed a random number generator once and then just use the numbers it generates. Seeding it with time(0) every time you try to get a random number will ensure that you get the same number for an entire second.