Noughts and Crosses

In my menu, I have used OXO as and abbreviation for Noughts and Crosses (British) / Tic-Tac-Toe (American).  This is commonly the first strategy game a child plays.  Pencil and paper is mostly used, but there are commercial sets available.  2 players take turns to place their mark/counter in an empty cell on a 3x3 grid.  One player places O's and the other X's, and the winner is the first player to make 3 in a row with their symbol (horizontal, vertical, or diagonal).  The game can end in a draw - as in the diagram above.  From the British name, I think that O's should go first, but it doesn't really make any difference.

The player going first always has an extra symbol on the board after their turn, and that is a considerable advantage.  Apart from being careful, the main strategic idea is to sent up a double threat.  For example : -
   or    
In each case, X can only block one of the potential lines of O's, so O will win on their next turn.

Like 3,4,5 Nim, strategy is easily discovered by playing and spotting what works!  Even young players soon learn that you can avoid losing by playing in the centre at the first opportunity.  Between experienced players, the game is a theoretical draw, but Martin Gardner suggests that by playing their first move in the middle of a side, O has the best chance of catching out an unwary opponent. 

For such a simple 'child's' game the following game stats require larger numbers than might have been expected, especially as rotations and reflections of a position are only counted once: -

• 138 terminal board positions - 91 wins by O, 44 wins by X, but only 3 drawn positions (can you find them?).
• 765 possible different positions during a game.
• 26,830 possible different games - see calculations by Henry Bottomley.

I had fun programming my computer to find the game tree of 765 different positions.  I then used backtracking, from won positions, to label each position with the result of the game with optimal play from that point onwards.  For anyone interested, you can download the resulting OXO Data File.txt.  It is a simple text file that should load into any text editor / word processor / spreadsheet.  Each entry gives a position number, 9 character string for the state of the board and a single character O/X/d for O wins / X wins / drawn with rational play.  These are separated by commas.  So, position 34 gives the board as OO...X... and a win for X.  Split the board string into 3 groups of 3 characters, for the 3 rows of the board: -
O O .
. . X
. . .
X can now play in the top right corner, O must block the vertical line and then X can create a double threat for the win.
Please let me know if you find any errors in my data.

Further Noughts and Crosses information can be found at Tic-tac-toe - Wikipedia

The game Pick 15 is isomorphic (i.e. has the same structure) as OXO.  To play Pick 15, list the numbers from 1 to 9 on a piece of paper (or use playing cards 1-9 from a suit).  Players take turns to claim a number, say by writing their initial next to it, so that each number can only be chosen once.  A player wins if any three of their claimed numbers sum to 15.  The equivalence with OXO is easily seen by marking the claimed numbers on a Magic Square, where all rows, columns and both diagonals sum to 15.  For example: -

Hence, a winning strategy for OXO can be used to win at Pick 15, where it is harder to spot double threats.

As with many simple abstract games, there are lots of variant games which share the basic concepts - see my article OXO Variants.
It can also be played in 3 or more dimensions - see the OXO 3-D article.