Game Theory and Tic Tac Toe

Game Theory and Tic Tac Toe

The game of Noughts and Crosses or Tic Tac Toe is well known throughout the world and variants are thought to have been played over 2000 years ago in Rome. It’s a very simple game – the first person to get 3 in a row wins. In fact it’s so simple that it has been “solved” – before any move has been played we already know it should result in a draw (as long as the participants play optimal moves).

The way to solve Noughts and Crosses is to use combinatorial Game Theory – which is a branch of mathematics that allows us to analyses all different outcomes of an event.

This is the start of the game tree for Noughts and Crosses. We can expand this game tree to cover every possible outcome for the game. Once this complete tree is drawn, any participant can work through this tree to see what is their optimal move at any one time from any position.

An upper bound for the number of positions and number of different games is given by:

3 ⁹= 19,683.  This is the total number of possible game positions in a 3×3 grid – as every square will either be a O, X or blank.

9! = 362,880. This is the total number of ways that positions can be filled on the grid. (First you have 9 choices of squares, then there are 8 choices of squares etc).  This counts each X and O as distinct from other X and Os.

9 choose 5 = 126.  This is the number of different combinations of filling the grid with 5 Xs and 4 Os.

However the analysis of this game tree can be significantly simplified by realising that many different positions are simply reflections or rotations of each other. By looking only for distinct positions (positions that are isometric under refection and rotation) we can, for example, see that there are actually only three distinct starting moves – as shown in the diagram above.

James Grime from Numberphile takes us through how to answer a related question, “How many different ways are there to completely fill a Noughts and Crosses board with 5 Xs and 4 Os – not including rotations and reflections?”  The solution above is a little complicated (it makes uses of Group Theory) but it is an excellent introduction to some uses of higher level mathematics.

This somewhat horrendous looking graphic actually contains the solution to playing Noughts and Crosses. You can use it to always achieve the optimal outcome for X. It works as follows:
1) The big red X in the top left hand corner represents your best first move. So you make this move first.
2) Next, you see what your opponent does and choose the grid with the big black O in the position they have chosen.
3) This new grid will have a big red X – this is your next optimal move.
4) You then remain in your subsection of the larger grid – and repeat the process.

If you liked this you might also like:

Game Theory and Evolution – do nice guys always finish last?

Knight’s Tour – an exploration of this 1000 year old mathematical puzzle.

Essential resources for IB students

2) Exploration Guides and Paper 3 Resources

I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations.  The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.