Skip main navigation

Analyzing tic-tac-toe

Watch Yossi Elran explain tic-tac-toe
0
Tic Tac Toe, or, Noughts and Crosses has been around for years. There is some uncertainty about who actually invented the game. It obviously existed in England for hundreds of years. Historians think that the game was invented much earlier. Archeologists, studying the Roman Empire, found hundreds of empty tic-tac-toe boards engraved on different artifacts, implying that the game existed 2000 years ago! Historians claim that the boards actually belonged to a game called (in Latin) “Terni Lapilli”. The 19’th century engineer and mathematician Charles Babbage was the first person to design a mechanical “computer game” for tic-tac-toe – long before electricity was invented. In fact, the first computer game in the world was tic-tac-toe!
54
The game was played on the world’s first electric computer, which was called EDSAC, and was constructed in Cambridge, England in 1949. The first player in tic tac toe always is at an advantage, but if the second player is clever enough, he can always enforce a draw, no matter how the first player plays. Where should the first player draw his ‘X’, to maximise his advantage? Should it be on the center square? A middle side square? Or perhaps the corner square? For each of these first player beginning moves, we can analyse the possible responses of the second player to see whether he can force a draw.
102.2
We only need to check these three possible beginning moves, because of the symmetry of the board. If the first player begins by drawing his ‘X’ in a middle side square, The second player can force a draw by responding with an ‘O’ in any of the four squares marked by the question marks. Here is an example of one of these responses. No matter how X responds to this situation, as long as O continues playing cleverly, he can force a draw. These are the moves if X responds in the center square. You can see from that from this state, ‘X’ has no way to devise a trap for O.
144.9
O will always be able to block any row that ‘X’ tries to make. Like this. Or like this. And so on. We saw that if the first player responds by drawing an X in the centre square O can force a draw. Using similar analysis, we can show that if X responds in any other square, O can always force a draw. If the first player begins by drawing his ‘X’ in the center square, The second player can force a draw by responding with an ‘O’ in any of the four corner squares. You can try to prove this for yourself.
195.7
It turns out that if the first player begins by drawing his ‘X’ in a corner square, the only possible second player response that will avoid him losing, is to draw his ‘O’ in the center square. The first player can force his own win, if the second player responds any other place on the board, as we can see in this example. Analysing tic tac toe is really fun! Now you know the tricks, you can become, a tic tac toe expert!

Tic-tac-toe, or, as it is known in England, Noughts and Crosses, is an intriguing game. The rules are quite simple. The first player is ‘X’. The second ‘O’ and they take turns drawing ‘X’’s and ‘O’s on the 3 x 3 grid. The winner is the player who succeeds in completing a row, column or diagonal of his three marks, three ‘X’s or three ‘O’s.

Watch the video, to see a short analysis of some of the moves in the game. In game theory, mathematicians are interested in finding out if one of the players has an advantage on the other. We usually assume that both players are ‘clever’ and don’t make ‘silly’ mistakes, meaning, that they play the best possible available response to the other players moves.

Tic-tac-toe always ends in a draw under these condition. However, although the first player does not have a decisive advantage, meaning that if both players are clever the game cannot end with a win for him, he does has an advantage over the second player in that he has many more possible moves to achieve a win if the second player isn’t careful.

Discussion

Could you figure out how the second player can draw from all his possible responses to the first player’s moves? Why is it important that both players are considered good players? How would we analyze games where one of the players is a random player?

This article is from the free online

An Introduction to Recreational Math: Fun, Games, and Puzzles

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education