Today's XKCD strip purports to show a complete map of tic-tac-toe including optimal moves.
I'm guessing the optimality of the move takes into account both the game-theoretic value of the move, assuming a perfect opponent:
- Good moves
- Preserves the win
- Preserves the draw
- "Preserves the loss" (every move in a lost position is of this type)
- "Bad" moves
- Converts won position to drawn position
- Converts drawn position to lost position
- "Very bad" moves
- Converts won position to lost position
And the practical value of the move, which allows for the possibility of error either on the player's part or the opponent's part.
In particular, I'm guessing that at each level Randall eliminated all the "bad" (and "very bad") moves, then broke the "well, all these moves are 'good'" tie by looking at some aggregation of the values of all following positions. The idea is, you want to pick the "good move" which:
- In a won position: minimizes the chance that you'll make a "bad" move (or a "very bad" move) later
- In a drawn position: maximizes the chance that your opponent will make a "bad" move
- Further ties broken by minimizing the chance that you'll make a "bad" move later
- In a lost position: maximizes the chance that your opponent will make a "bad" move (or a "very bad" move)
If there are still ties, I am guessing that Randall invoked a randomizer. For example, X's first move (in the top left corner) is tied in every possible respect with the other three corners.
I object to this approach because humans don't always pick moves randomly. They learn. They make rules for themselves, some of which are fallible, and can be exploited. For example, "move in the center if you can" is a typical rule, followed by "if you can't move in the center, move in a corner." Also, I think information is lost by hiding the other "good" moves.
So, here's my version. I don't go into nearly as much depth, but here is the game-theoretic value of all of X's first moves (W = win; D = draw; L = loss:)
Not very exciting... a nine-way tie.
And for each first move for X, here is the game-theoretic value of all of O's first moves (I only show three, the others can be inferred by symmetry:)
For an example of a "very bad" move, consider the position after X moves in the top left corner (a good move) and O moves in the lower left corner (a bad move, after which X has a won position:)