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.

Answer 2

Given that there is only at most 9 choices, even using your random picking, this would not cause a long delay. What is causing the long delay is calling srand inside the loop. This is causing your program to get the same random numbers for the duration of a second. The loop is probably being executed millions of times in that second (or would be without the cout call)

Move the srand call outside of the loop (or better yet, just call it once at the start of your program).

That is not to say you shouldn't look at ways of removing the unavailable moves from the random selection, as it may make a difference for other types of games.

Answer 3

You could reduce that to very acceptable levels by creating a list of free coordinates and getting a random index in that collection. Conceptually:

#include <vector>

struct tictactoe_point
{
    int x, y;
};

vector<tictactoe_point> legal_points;
tictactoe_point point;
for (point.x = 0; point.x < 3; point.x++)
{
    for (point.y = 0; point.y < 3; point.y++)
    {
        if (game.isLegalMove(point.x, point.y))
        {
            legal_points.push_back(point);
        }
    }
}

point = legal_points[rand() % legal_points.size()];
game.makeMove(point.x, point.y, ai);
moveMade = true;

This solution is not optimal, but it's a significant improvement: now, the time it takes to make a move is fully predictable. This algorithm will complete with one single call to rand.

The fact that you call srand each time you pick a number makes the process even slower, but then again, the major problem is that your current solution has to try over and over again. It's not bounded: it may even never complete. Even if srand is considerably slow, if you know that it'll run just one time, and not an indefinite number of times, it should be viable (though not optimal either).

There are many ways to improve on this:

• Keep a list of valid coordinates to play, and remove the coordinates when either the player or the AI plays it. This way you don't have to rebuild the list at every turn. It won't make a big difference for a tic-tac-toe game, but it would make a big difference if you had a larger board.
• Use the standard C++ random function. This isn't really an algorithm improvement, but rand() in C is pretty crappy (I know, I know, it's a long video, but this guy really really knows his stuff).

Answer 4

The reason why it seems slower every move is because the AI is picking moves that have already been made so it randomly re-picks either another illegal move(Could be recurring) or it picks the correct square.

To speed this part of your program up you could have a collection(eg linkedlist) that contains the positions, use your random function over this list. When a move is picked by you or the AI remove the element from the list.

This will remove the recurring process of the AI picking the same squares.