Aswin F. van Woudenberg

Computer programs playing two-persons games like Chess, or Go usually use a search algorithm like minimax possibly with alpha-beta pruning. The simplicity of the game Tic-tac-toe however, makes a search algorithm unnecessary. The number of possible board situations is very limited and a better option in this case is to use a lookup table.

I started by generating all possible board situations and placing them all in a database. After that, calculating for every position the best possible move or moves that should follow to minimize the chance of losing and maximize the chance of winning was straitforward. I used the result to make a lookup table to be used in a C++ program that plays Tic-tac-toe perfectly. Because of the 8-fold symmetry of  the board the lookup table does not include too many elements.