tic tac toe 2

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.

tic tac toe

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.

tic tac toe 3
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.

IB Revision

Screen Shot 2018-03-19 at 4.35.19 PM

If you’re already thinking about your coursework then it’s probably also time to start planning some revision, either for the end of Year 12 school exams or Year 13 final exams. There’s a really great website that I would strongly recommend students use – you choose your subject (HL/SL/Studies if your exam is in 2020 or Applications/Analysis if your exam is in 2021), and then have the following resources:

Screen Shot 2018-03-19 at 4.42.05 PM.pngThe Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and each area then has a number 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!

Screen Shot 2019-07-27 at 10.02.40 AM

The Practice Exams section takes you to ready made exams on each topic – again with worked solutions.  This also has some harder exams for those students aiming for 6s and 7s and the Past IB Exams section takes you to full video worked solutions to every question on every past paper – and you can also get a prediction exam for the upcoming year.

I would really recommend everyone making use of this – there is a mixture of a lot of free content as well as premium content so have a look and see what you think.