Skip to 0 minutes and 0 seconds 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!

Skip to 0 minutes and 54 seconds 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.

Skip to 1 minute and 42 seconds 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.

Skip to 2 minutes and 25 seconds 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.

Skip to 3 minutes and 16 seconds 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!

# Analyzing tic-tac-toe

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?

© Davidson Institute of Science Education, Weizmann Institute of Science