This month's NSA Puzzle Periodical pays tribute to the 1983 motion picture "WarGames." In the movie a supercomputer is programmed to play Tic-Tac-Toe.
The computer plays itself with each X and O placed uniformly at random into any square (this means the computer plays without regard to strategy). What is the probability a game will end in a draw?
Assume perfect random number generation. The first X will be placed in any square with probability 1/9. The first O will go into any of the remaining squares with probability 1/8 and so on.
Solution
Answer: The probability of a draw is 8/63.
If we number the squares of the board 1 to 9
then every permutation of 1 through 9 defines a game. For instance the permutation 178294635 would be the game where X plays in square 1 then O plays in square 7 then X in square 8 and so forth. This would result in
which is a win for X. It follows that there are 9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 possible games. (Note the order is important in determining the winner. If the final layout were
then the winner would be the one who completed its row first.)
However we're interested in ties so we just need to count how many of these games result in no winner. All we need to do is consider the possible locations of the "O"s in a tie. There must be at least one O (but fewer than three!) in every row column and diagonal. Up to symmetry there are 3 distinct placements of the "O"s that will achieve this: (Here two positions of the board are considered related by symmetry if one can be obtained from the other by a combination of rotations by 90 degrees of the entire board and flipping the entire board around the vertical axis containing positions 2 5 and 8.)
-
-
-
For instance position 1 means O goes in squares 1 5 6 8 while X goes in squares 2 3 4 7 9. Because the order the "X"s and "O"s are placed doesn't matter there are 4! × 5! ways to arrive at this position. Then notice that position 1 has a 4-fold rotational symmetry:
so that there are actually 4 × 4! × 5! draws resulting in position 1. Position 2 has an 8-fold rotational/reflective symmetry so there are 8 × 4! × 5! ties resulting in position 2.
Finally position 3 has a 4-fold symmetry so there are 4 × 4! × 5! games that will end in a tie in position 3. All told there are 16 × 4! × 5! games that will end in a draw. Thus the probability of a draw is (16 × 4! × 5!)/9! = 8/63.
Did you enjoy this NSA Puzzle Periodical?
If your friends and family would also like to try this math and logic challenge look for NSA's Puzzle Periodical on the third Tuesday of every month on www.nsa.gov.
NSA's Puzzle Periodical is also Tweeted to more than 400 000 + followers.