Matthew van Eerde's web log
I am a Software Development Engineer in Test working for the Windows Sound team. You can contact me via email: mateer at microsoft dot com
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:
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:
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:)
The optimality of the moves assumes both players play perfectly from the current board position