Games: Tic-Tac-Toe

The game of tic-tac-toe (TTT) is used to illustrate how an AI program searches for an answer. It’s all about choosing amongst alternatives, taking into consideration what your opponent might do. Its moves, counter moves, counter-counter moves, and so on. Game programs build a search “tree”: from a given start position (root), consider all moves (branches) leading to new positions, and opponent responses from those positions, and so on. Eventually, a search sequence of moves stops in a position (leaf). A search tree can enumerate all scenarios, even to the end of the game. But which move choice do you make at the root? Each line of play gets a value. The value could be determined by the rules (win, loss, draw) or using human knowledge (e.g., the player with the white pieces has an advantage). The player to move chooses the move with the maximum value. The opponent chooses the move with the minimum value. Propagating values from the leaf positions back to the root will determine the value of the position and the best move to choose. This is called minimax search. Unfortunately, this approach can result in an enormously large search tree, even for a game as simple as tic-tac-toe. A little knowledge can go a long way to eliminate large parts of the search that are irrelevant.