Tie Fighters

Noughts and crosses (tic-tac-toe) is quite a boring game. The two main reasons for this are:

  1. Most games end in a draw or tie.
  2. The optimal strategy is too obvious (the first player wants to start in the middle).
With an ulterior mathematical motive in mind, I’d like to introduce you to two games that avoid the first complaint. Whether they address the second is up to you: I’d argue that only Game B, called Sim, does.
Game A 
Let’s call the game triangle-tac-toe. Draw a grid in the shape of a right-angled isosceles triangle whose sides are five squares across (giving 15 squares in total). A board-drawing hint: draw five rectangles.
Starting grid
Take turns to add noughts or crosses as in traditional tic-tac-toe. A player wins when three of their marks form the corners of a right-angled isosceles triangle of any size in the same orientation as the board (the corners may be touching or spread out).
Some of the possible ways for Crosses to win.
Game B (Sim)
Draw six points in a hexagonal arrangement. Optionally, lightly join each possible pair of points (a total of 15 lines) with dotted lines—don’t worry whether three cross lines in the middle or not, but double check that each point has five lines coming out of it.
Sim starting layout
Players pick their favourite colours (we’ll use the traditional Red and Blue), and take turns drawing a straight line in their chosen hue between two points (that haven’t already been connected). A player loses if they form a triangle of their colour between any three of the hexagon’s vertices.
End of a sample game—Red loses due to the highlighted triangle
Animation of the sample game above (click if not playing)
Analysis of Games
It’s not clear why neither game can end in a draw for the players. But it’s possible to prove that this is the case for both. I find it easiest to think of the process as trying to construct a counterexample, and failing. That is, you rigourously try to create a game that has ended in a tie, and so prove along the way that this is impossible.
Game B (Sim)
What would a counterexample look like? Let’s first find one for a smaller version of the same game played on a pentagon (let’s call it ‘Sim 5’). If we draw a blue pentagon with a red pentagram inside, this is the final appearance of a game that results in a draw.
A tied game played on five points
You can also find a similar counterexample for a square ‘Sim 4’ version much more easily from scratch, or you could remove from the ‘Sim 5’ dead-heat above, any of the points and the coloured lines emanating from it. For ‘Sim 3’ it is trivial: it’s actually impossible when playing properly for anyone to lose.
Returning to Sim 6, let’s think how the game might look like at the end, when all the lines have been coloured in. For our purposes, let’s ignore the fact that each player will take nearly the same number of moves (eight and seven)—I think it’s conceptually simpler to show the more general fact that it’s impossible to tie whatever number of moves the players have taken (it includes the eight-seven case, which is also the worst-case scenario).
Pick any one of the points (the vertex labelled ‘p’ in the palm of the hand in the diagram below), and look at the five lines extending out to the fingers. At least three of these lines must be red, or at least three must be blue. Let’s say, for the sake of argument, that it was red (the three fingers are circled below).
A visual aide to the proof from the paper ‘Graph Ramsey games
by Wolfgang Slanyattributed to Ranan Banerji.
Then, look at the vertices at the other end of these lines: what colours are the lines between them? If any are red, then we’ve made a red triangle; otherwise, all of them must be blue, which makes a blue triangle (see image below). So any way you try to colour the lines, you will make either a red triangle or a blue triangle.
Either Blue wins (left) or else at least one must be red, so Red wins (eg. right).
Note that, for a counterexample in Sim 5, we needed exactly two of each colour coming off each vertex, which is why the above proof doesn’t carry over. In fact, the pentagrammy picture above is the only example of a tie—can you explain why? Here, two examples are the same if we can change one into the other by keeping the line colours the same, but dragging points to a new location, or by simply swapping red for blue everywhere.
Now we’ve seen that it’s impossible to tie in ‘Sim 6’: how about in ‘Sim 7’? To get a tie, we would have to fill in all the lines. But if we ignore all the lines from the extra point, we have a copy of ‘Sim 6’ which must contain a triangle: so no tie here either. Or, by the same reasoning, for any larger game.
Game A
Let’s start in the same way: to get a tie we must have no triangles of Crosses or triangles of Noughts which are the same shape and facing the same direction as the triangular grid. So, again, if filling up the board always leads to someone winning, then we’ve proved there’s no way to tie.
An initial observation: of the five cells along the largest diagonal, at least three must be one or other of the markings. Let’s say they are Noughts. This is the same requirement we used in our analysis of Sim above.
If we get three Noughts in a row along the diagonal, or evenly spaced as in the diagram below, then we must have a pair of Crosses below to prevent Noughts winning. But then one or other must have their symbol as the corner piece, and that player would have won.
Three evenly spaced symbols of the same sort always leads to a win. Start with the lightest symbols, adding darker ones later to avoid a tie. The hybrid Noughts/Cross symbol shows a position where either player wins.
Eliminating these cases leaves only a four more more to check. Unfortunately, we more or less have to play the whole game through.
Four remaining cases to check. As above, start with the lightest symbols, adding darker ones later to avoid a tie. Again, the hybrid Noughts/Cross symbol shows a position where either player wins.
So we’ve proved that, by the time the board is filled up, someone must have won.
One difference over traditional tic-tac-toe is that each cell is part of four winning triangles. This means that every square is equally strong. In tic-tac-toe, the central square has four winning lines through it, but the others have either two or three. However, this seems to make the game too easy: the starting player should be able to win on their fourth move. Can you see how?
Again, we needed the whole playing area for the argument above to work. A board with smaller sides wouldn’t always end in a tie. However, though it could potentially end in a tie, optimal play on a triangle with sides four squares long should again lead to the first player winning on their fourth move. Any larger board would necessarily contain our triangle with sides of five cells, so any game would have to end in a draw.
Given that it’s such a biased game, why have I included it? It’s actually a mathematical lemma in disguise, a self-contained argument in a proof relating to Rado’s theorem. The game may be found in ‘Ramsey Theory on the Integers‘ by Bruce M. Landman and Aaron Robertson, page 245, Exercise 9.14; and it relates to Theorem 9.12 just beforehand.
If you’ve been paying close attention, my ulterior motive which links the two games is an area of mathematics, which I enjoy, called Ramsey theory.
Advertisements

2 Comments

Filed under Accessible

2 responses to “Tie Fighters

  1. Pingback: Planes, manes and pigeonholes | Out of the Norm

  2. Pingback: London MathsJam February Recap | Out of the Norm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s