You are currently browsing the tag archive for the ‘noughts and crosses’ tag.

**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^{ 9}= 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:

Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.

There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!

The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.

Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.

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.