Tic-tac-toe can be made more challenging for humans and AI-based machines by extending the 3 × 3 game to higher dimensions and array sizes, such as in this 4 × 4 × 4 version, and by introducing gravity effects, as each piece slides to the bottom available position.

c. 1300 BC

TIC-TAC-TOE

Archeologists can trace what appears to be “three-in-a-row games” to around 1300 BCE in ancient Egypt. For tic-tac-toe (TTT), two players, O and X, take turns marking their symbols in the spaces of a 3 × 3 grid. The player who first places three of his own marks in a horizontal, vertical, or diagonal row wins.

We’re interested in TTT for this book because it has often been used as an introduction to aspects of artificial intelligence and computer programming, due to the simplicity of searching its game trees (where nodes are positions in a game, and edges represent moves). TTT is a “perfect information” game, as all players know all the moves that have taken place. It is also a sequential game without randomization, with the players taking turns and avoiding the use of dice.

TTT may be considered an “atom” upon which the molecules of more advanced games of position were built through the centuries. With the slightest of variations and extensions, the simple game of TTT becomes a fantastic challenge, requiring significant time to master. Mathematicians and puzzle aficionados have extended TTT to larger boards, higher dimensions, and strange playing surfaces such as rectangular or square boards connected at their edges to form a torus (doughnut shape) or Klein bottle (a surface with just one side).

Consider some TTT curiosities. Players can place their Xs and Os to fill a TTT board in 362,880 (or 9!) ways. However, there are 255,168 possible games in TTT when considering all possible games that end in 5, 6, 7, 8, and 9 moves. In 1960, the MENACE AI system (a contraption of colored beads and matchboxes) learned to play TTT using reinforcement learning. In the early 1980s, computer geniuses Danny Hillis, Brian Silverman, and friends built a Tinkertoy^® computer that played TTT from 10,000 Tinkertoy pieces. In 1998, researchers and students at the University of Toronto created a robot to play three-dimensional (4 × 4 × 4) TTT with a human.