# Tic-tac-toe AI Part 3: Game Tree for the Win

Writing a bot for a game as simple as tic-tac-toe is not that hard. As there are only 255,168 possible games, you can easily simulate all of them to search for good moves.

So the first thing the bot does is generating all possible game endings based on the current situation. The resulting situations can be stored in a so called Game Tree:

To generate the game tree, we will use a RecursiveAction to speed things up:

Each `SimulationTreeNode` starts a new thread to generate all possible moves. If less then 6 free fields are left, no new threads are started (wouldn’t improve performance anymore). The generated sub-situations are stored in an array.

Now when it is the computers turn, it can build the game tree or search for the new situation in the existing game tree (after players move):

# What should I do?

You may noticed the `getBestMove` call to the simulation tree. This method searches the best possible move. Often there are multiple moves with the same “score”. A random one is returned in that situation:

What does this “score” mean? The higher, the better: A defeat would be bad for us, so it has score -1. A draw would be OK, so it has score 0. Winning would be good, so it has score 1:

To calculate the score of situations which are not yet completed (no winner and still empty fields), we use the Minimax algorithm.

When it is the other players turn, we assume that he will try to do the best he can. So we must assume the lowest score of all possible moves for the situation. Because when we end up with that situation, the player could do this move that would hurt us.

When it is the computers turn, it will do the best it can. That’s why we can assume the highes score of all possible moves. Because when we end up with that situation, we may have a chance to do the move with that good score.

We end up with something like this: