 # Shall We Play A Game?

### WE ARE THE NEWS NOW.

Qdrop 3019Q!!mG7VJxZNCI10 Mar 2019 – 8:09:20 PM

https://www.nsa.gov/News-Features/News-Stories/Article-View/Article/1624713/may-2018-puzzle-periodical-shall-we-play-a-game-computer-tic-tac-toe/📁
Shall We Play A Game?
How many Tweets has POTUS ‘forwarded’ in the past 12-hours?
Primary topic(s)?
Do you have your [ ] filled in?
Q

# May 2018 Puzzle Periodical – Shall We Play a Game? Computer Tic-Tac-Toe

By Stefan T., NSA Research Mathematician

Puzzle Periodical Logo45PRINT  |  E-MAILMay 15, 2018 —

Creator Challenge Difficulty Rating: Hard

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

 1 2 3 4 5 6 7 8 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

 X O O O X X O X X

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

 X X X O O O X O X

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:

• OXXXOOXOX
• XXOOOXXOX
• XOXOOXXXO
• XOXXOOOXX

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.

#WWG1WGA  #FactsMatter  #GreatAwakening
#TheStorm
#DigitalSoldier   #WeAreTheNewsNow

DOItQ.Media is the blog.
Official website is
DOItQ.News