T-3PO — Tic-Tac-Toe Played Optimally (#166)

Tic-Tac-Toe, noughts and crosses, Xs and Os, three in a row or whatever you want to call it may be the simplest perfect in­for­ma­tion game that is enjoyable by humans. Two players set their pieces (X or O) on an 3 ⨉ 3 grid, alternating their turns. The first player to get three of their pieces in a line, wins. If no player succeeds to get a line, the game ends in a draw.

Tic-Tac-Toe’s simplicity may be­come clear, if you consider that skilled players — people who have played a few rounds — can reliably achieve a draw, thereby playing perfectly. Two perfect players playing Tic-Tac-Toe will — whoever starts — al­ways tie, so one may call the game virtually pointless, due to there practically never being a winner.
Because of its simple rules and short maximal num­ber of turns (nine) it is also a game that can be solved by a computer using brute-force and trees.

The first Tic-Tac-Toe-playing pro­gram I wrote is a Python shell script. It lets you, the human player, make the first move and then calculates the best possible move for itself, lead­ing to it never loosing. On its way it has a little chat whilst pretending to think about its next move. The Python source code can be seen below or downloaded here.

The second Tic-Tac-Toe-playing pro­gram I wrote uses the exact same meth­od of optimizing its play, though it lets you decide who should begin and is entirely writ­ten in Java­Script. You can play against it by following this link.

Both programs look at the en­tire space of possible games based on the cur­rent board’s status, assumes you want to win and ran­dom­ly picks be­tween the moves that ei­ther lead to a win for the computer or to a draw. I did not in­clude ran­dom mistakes to give the human player any chance of winning against the computer. Oth­er Tic-Tac-Toe-playing computers, such as Google’s (just google the game⁠¹), have this func­tion­al­i­ty.

Source code: t-3po.py