Editing 832: Tic-Tac-Toe

{{comic
| number    = 832
| date      = December 10, 2010
| title     = Tic-Tac-Toe
| image     = tic_tac_toe.png
| titletext = The only winning move is to play, perfectly, waiting for your opponent to make a mistake.
}}

==Explanation==
In what follows we will use numpad notation for tic-tac-toe, i.e.:
 7|8|9
 -+-+- 
 4|5|6
 -+-+- 
 1|2|3

Pixel values are taken from http://xkcd.com/832_large/.

Each map shows every possible combination of moves which will result in that side winning or tying. It assumes that X moves first, and its optimal move is X7. Any corner would do, so X1, X3 and X9 are also optimal moves. The map for X has a big red X7 (650&times;650 pixels), and the 8 remaining grids have a smaller (210&times;210) black X7.

The map for O has more combinations, because in this case X is not assumed to be optimal. All 9 subgrids have one big (210&times;210) black X and one big red O.

Note that only optimal moves are shown. For example, you can't find a grid beginning with X2 in Map of X, because X2 is not an optimal move.

In map for O you can find a 660&times;660 grid beginning with X2. Since the optimal answer is O5, you won't find X2, O8, for example.

;Example 1
The largest red X in Map for X is X7. This means that O must go to cell 7 in  Map for O. The largest red O in this subgrid is the center cell O5. Therefore X must magnify cell 5 in the map for X and look for a big red X, which is X3, i.e. in the cell (6, 4) in a 9&times;9 grid. This can be repeated until one of the players wins or there is a tie.

;Example 2
Download http://xkcd.com/832_large/ and edit it. Delete the upper part. Now you have a picture sized 2040&times;2150 pixels, with title MAP FOR O.

Assume X used the center cell, X5. You as O must magnify the center cell in the 3&times;3 map for O. Better still, select that cell and delete everything else. Now you have a picture sized 670&times;670 pixels, with a big red O7 and a big black X5. You must move O7 this time.
 O| |
 -+-+-
  |X| 
 -+-+-
  | |

Assume X moves X9. 
 O| |X
 -+-+-
  |X| 
 -+-+-
  | |

In your drawing program you select cell 9, which is 220&times;220 pixels. Look for the biggest red O, which is O1. You can see you blocked a winning move.
 O| |X
 -+-+-
  |X| 
 -+-+-
 O| |

Now X, naively, plays X3
 O| |X
 -+-+-
  |X| 
 -+-+-
 O| |X

You select cell 3 in your drawing program, which is 73&times;73 pixels and looks like this
 O| |X
 -+-+-
 O|X| 
 -+-+-
 O| |X
The O in cell 4 is red, which is your winning move.

;Title text
The title text is a reference to the 1983 movie ''{{w|WarGames}}''. In that movie, by playing Tic-Tac-Toe the AI realizes that some games cannot be won when all the players play flawlessly, and subsequently concludes that the only way to win at the nuclear warfare "game" is not to play.

==Errors==
1)&nbsp;In Map for X, the grid for X7, O9, X1, O4, X3 (i.e. go to Map for X, select cell 9, and then select cell 4) shows the same picture for O5 and O6. Those pictures belong to O6. 

[[Image:Tic-Tac-Toe-X-1-8.png]]

The correct pictures should be:
 X| |O    X| |O
 -+-+-    -+-+-
 O|O|     O| |O
 -+-+-    -+-+-
 X|<font color=red><strong>X</strong></font>|X    X|<font color=red><strong>X</strong></font>|X

2)&nbsp;In Map for X, the grid for X7, O1, X9, O8, X3  (i.e. go to Map for X, select cell 1, and then select cell 8) shows the same picture for O2 and O5. Those pictures belong to O2. The correct pictures should be:
 X|O|X
 -+-+-
  |O|X
 -+-+-
 O| |X
 =====
 X|O|X
 -+-+-
  | |X
 -+-+-
 O|O|X

3)&nbsp;In Map for O, the grid for X8, O5, X2, O6 (i.e. go to Map for O, select cell 8, and then select cell 2) shows the same picture for X1 and X3. Those pictures belong to X3. The correct pictures should be:
  |X|    \   /    |X| 
 -+-+-    \ /    -+-+-
 O|O|O     X     O|O|O
 -+-+-    / \    -+-+-
 X| |X   /   \    |X|X

4)&nbsp;In Map for O, the grid for X2, O5, X8, O4 (i.e. go to Map for O, select cell 2, and then select cell 8) shows the same picture for X7 and X9. Those pictures belong to X7. The correct pictures should be:
 X|X|    \   /    |X|X 
 -+-+-    \ /    -+-+-
 O|O|O     X     O|O|O
 -+-+-    / \    -+-+-
  |X|    /   \    |X|

5)&nbsp;In Map for O, the grid for X6, O5, X4, O2 (i.e. go to Map for O, select cell 6, and then select cell 4) shows the same picture for X1 and X7. Those pictures belong to X1. 

[[Image:Tic_Tac_Toe-O-6-4.png]]

The correct pictures should be:
 X|<font color=red><strong>O</strong></font>|
 -+-+-
 X|O|X
 -+-+-
  |O|
 =====
 \   /
  \ / 
   X  
  / \ 
 /   \
 =====
  |<font color=red><strong>O</strong></font>|
 -+-+-
 X|O|X
 -+-+-
 X|O|

6)&nbsp;Typography coloring issue: in Map for O, X5, O7, X3, O1, X4, O6,  the O6 should be red to show that it's the latest move, instead of black.

7)&nbsp;Another typography coloring issue: in Map for O, X1, O5, X4, O7, X3, O2, X6, O9, X8,  the X8 is red, but in Map for O all X should be black.

8)&nbsp;In Map for O, there are eight "strategy" mistakes, when the O player could have won the game but doesn't. These can be found on:
* X3, O5, X4, O7, X6, O9, X1 (winning move would be O8, but Map says O2);
* X3, O5, X8, O7, X2, O1, X9 (winning move would be O4, Map says O6);
The same on six other symmetrical games to the above.

9)&nbsp;In Map for O, there are four further "strategy" mistakes, when the O player could have won the game but doesn't. These can be found on:
* X7, O5, X8, O9, X1, O4: the small squares for X6 and X2 are identical, but only the one for X6 is correct. In case of either X2 or X3, O has the the winning move O6.
The squares for X2 and X3 should be:
 X|X|O
 -+-+-
 O|O|<font color=red><strong>O</strong></font>
 -+-+-
 X|X|

and
 X|X|O
 -+-+-
 O|O|<font color=red><strong>O</strong></font>
 -+-+-
 X| |X

respectively. The same on three other symmetrical games to the above.

10) &nbsp;In the map for O, center panel (first move X5), in the third level nested panel for X5, O7, X2, O8, X9, O1, move X2 from the second level "parent" panel is missing. The panel is depicted as:

  O|O|X
  -+-+-
 []|X|[]
  -+-+-
  O| |[]

where [] are the fourth-level nested panels, but should be:
  O|O|X
  -+-+-
 []|X|[]
  -+-+-
  O|X|[]

Same for the symmetrical game X5, O7, X6, O4, X1, O9, where X6 is missing.

==See also==
http://xkcd.com/832_large/

==Transcript==
:[The comic comprises two large square maps, each divided into nine sections, some of which are further subdivided in the same way. The subdivisions continue down for up to five levels, and the lower map has more tiny diagrams than the upper. The smallest divisions at every scale are completed tic-tac-toe games. At the smallest divisions some of the moves are too small to see.]

:Complete map of optimal Tic-Tac-Toe moves

:Your move is given by the position of the largest red symbol on the grid. When your opponent picks a move, zoom in on the region of the grid where they went. Repeat.

:Map for X:
:[The first square map.]

:Map for O:
:[The second square map.]

{{comic discussion}}
[[Category:Logic]]
[[Category:Comics with color]]