Tic Tac Toe (noughts and crosses) is always such a nice example.
I was thinking about strategies and decided to implement a program that plays Tic Tac Toe according to John von Neumann’s minimax. This is a kind of 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.
The algorithm works recursively by looking for the move that will let an optimally playing opponent inflict the least damage. The opponent’s strategy is calculated by way of the same algorithm, and so on. This means that on the first move, the computer investigates the entire game tree – it considers every single possible Tic Tac Toe game and then choses randomly among the best (least dangerous) moves.
Have a go at http://www.half-real.net/tictactoe/
- Here’s a document with every single game of Tic Tac Toe. It 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 adding some amount of randomness in algorithm would probably make it a better player against human opponents.
- 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.
