This program plays Tic Tac Toe according to John von Neumann's minimax algorithm. This is a meta-strategy that can be used for playing any game: Always chose the move that will minimize the maximum damage that your opponent can do to you.
Have a go. The computer should always achieve draw or win - otherwise there is a bug.
(Press the hint button to see the program's evaluation of each possible move.)
Some observations from this:
- Here's a document with every
single game of Tic Tac Toe, which gives the following numbers.
- 255,168 unique games of Tic Tac Toe to be played. Of these, 131,184 are won by the first player, 77,904 are won by the second player, and 46,080 are drawn.
- This supports the intuition that it is an advantage to begin the game.
- These numbers do not take similar board positions into account - rotating the board, mirroring it and so on. It does not matter which corner you place the first piece in, but this is not taken into account here.
- If neither player makes a mistake, the game is drawn (but we knew that already).
- This is an exercise in examining the objective properties of a game. There are two interesting sides to this:
- 1) The objective properties of Tic Tac Toe really matter for our enjoyment of it: It is a boring game because there are so relatively few combinations.
- 2) On the other hand, humans clearly play the game in a different way than the computer. The computer's playing style lets us make some observations about how humans play games.
- To the computer, the first move is the most complicated (takes around a second on my 2ghz machine). This is unlike human players who seldomly have any problem deciding what to do on the first move.
- The program assumes that the opponent does not make any mistakes. Humans do make
mistakes, of course, so in actuality the program isn't playing optimally.
- The number of possible unique games is larger than I would have guessed, but this indicates how we humans are very good at identifying patterns. Faced with the huge number of variations in a game like this, we simply identify some general properties of Tic Tac Toe: Beginning in the middle is a good thing; if your opponent begins in the middle, you must pick the corner; a good way of winning is to threaten two squares simultaneously.
- We think about games like this in fuzzy and chaotic ways - this gives us a lot of flexibility.
- It is the same fuzziness that leads us into making stupid mistakes.
- On some level, it is our fuzzy way of playing games that allows us to have fun. If we simply played with the unimaginative brute force strategy that the computer uses, it would definitely be work rather than play - and nobody would have any fun playing against us, for that matter.
Half-Real, chapter 3.