Tic-tac-toe is a very popular game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a vertical, horizontal or diagonal row wins the game.
Mathematical properties of the game
From a mathematical point of view the game has two very important properties.
Property 1: The game admits an optimal strategy. A player that uses this optimal strategy will win or draw, but will never lose.
Property 2: The number of possible different matches is relatively small. At the start, the first player can mark any of the 9 spaces. On the following turn the second player can mark one of the remaining 8 spaces, and so on. The game continues until all the spaces are marked or one of the players wins.
It is then easy to see that the total number of different matches is lower than 9 × 8 × 7 × ... × 1 = 9! = 362880. That is a reasonably small number for a computer.
The algorithm: alpha-beta search
From properties 1 and 2 it follows that a practical and general algorithm to win or draw the game is to use the alpha-beta search. At each turn the algorithm evaluates all the possible consequences of each move (possible because of property 2) and chooses the one that will ensure a victory or a draw (possible because of property 1).
An AI player that chooses each move with the alpha-beta search algorithm will never lose.
Adding realism with a stochastic factor
To make the game more realistic it helps to introduce a stochastic factor, so that each turn, with a predefined probability, the AI player moves randomly rather than following the alpha-beta algorithm. This makes the AI player more human, and means that sometimes it will lose.
Alpha-beta search is one way to explore a space of possible moves. For a very different search and optimization approach, see how a genetic algorithm works.
