On the beach, scratching marks in the sand with a stick, my 4-year-old son was already good enough to force a draw in noughts and crosses, also known as tic-tac-toe.
In case there is anyone on the planet unfamiliar with this game, it is played on a 3 × 3 grid, with players taking turns to add their symbol – an X or an O – in one of the spaces. The winner is the first to place three of their symbols in a row horizontally, vertically or diagonally.
We can prove that two good players will always end the game in a draw by using an algorithm called an exhaustive search that examines all possibilities to come to a conclusion. In this case, we can use it to work out all the moves that each player could make in turn, until we get to a series of possible future endgames. These are evaluated as either a win, loss or draw. Then we work backwards, looking at the decisions that led to those endgames. At each decision point, we look at which player will be offered the choice and assume they will act in their own best interest, until we find out the optimal next move.
Advertisement
On a blank board, there are nine spaces in which the first symbol can be placed. For each of these possibilities, there are eight places where the second symbol can go, and for each of those, there are seven ways for the first player to respond, and so on. This leads to almost a million positions, which isn’t very many for a computer to search. Doing this analysis starting from a blank board, we find that, if both players play perfectly, the outcome is always a draw.
Knowing that you can only win if your opponent does something silly can make the game somewhat boring to play. However, some fun twists can spice things up.
A simple tweak is to reverse the game’s goal. Here, players place Os and Xs in the usual way, but the first to get three in a row loses. Have a go! You might be surprised that such a simple change results in really quite different gameplay.
Another twist is to play the game wild. This means that, each turn, players choose whether to place an X or an O, with the person who adds the third matching symbol in a row declared the victor, whichever symbol that is. It can be really hard to get into the mindset that your opponent can win using the line you are starting to create.
You can also enlarge the grid – try four in a row on a 4 × 4 grid. Or play on a larger grid than the winning line, like the classic game Connect 4, which requires four in a row, but is played on a 7 × 6 grid, with the added twist of gravity. You can even play on an infinite board. Take turns to place your symbol, aiming to get five in a row, enlarging the grid as needed.
There are many more varieties – maybe you can think of your own. For me, tweaking the rules and examining the result is the creative heart of mathematical thinking, and it is lovely to find so much to explore in this simple game.
Peter Rowlett is a mathematics lecturer, podcaster and author based at Sheffield Hallam University in the UK. Follow him @peterrowlett
For other projects visit newscientist.com/maker
