Generalized Tic-tac-toe

(n-in-a-row on a p-by-q board)

Wei Ji Ma, 2005  

Contents
  1. Introduction
  2. Systematic exploration
  3. Four-in-a-row
  4. Five-in-a-row
  5. More-than-five-in-a-row
  6. Summary and rambling
  7. Higher dimensions
    • Hales-Jewett theorem
  8. Rule variations
    1. Misere n-in-a-row
    2. Revenge n-in-a-row
    3. Treblecross
    4. Two-directional tic-tac-toe
    5. Five-in-a-row with capture
    6. Periodic n-in-a-row
  9. References and further reading

Introduction

Tic-Tac-Toe (or noughts-and-crosses) is an ancient game with simple rules which is played all over the world. There are two players, who alternately occupy empty squares on a rectangular board with their pieces. In the standard version of the game, a player wins as soon as he has three of his pieces in a horizontal, vertical, or diagonal line on a 3x3 board. If neither player wins, it is a draw.

It can be found quickly that this game is a draw with best play. (Most kids who end up becoming mathematicians find this out.) You can also easily figure out that on a 3x4 board it is, with best play, won for the first player. What most players of the standard game do not know is that the general version of the game, n-in-a-row on a rectangular board, can be highly nontrivial and is partially unsolved. This website describes what people know nowadays about these generalizations, also called m,n,k-games. We also give some rule variations.

Systematic exploration

The central question is: when is n-in-a-row on a given rectangular board won, and when drawn? With "won" we now mean that there exists a winning strategy for the first player against any possible defense. There is an elegant argument proving that if there can never be such a winning strategy for the second player: if there would be a winning strategy for the second player, the first player could just "steal" this strategy after his first move. Since an extra move never hurts, he would win. It follows that there cannot be such a strategy. This is called the strategy-stealing argument. The game is drawn if there does not exist a winning strategy for the first player. There are some other general observations:
  1. If n-in-a-row is won on a board of a certain size, it is also won on any larger board. (Although this is generally believed to be true, I am not aware of a proof. Simple arguments fail, as was pointed out to me by Mateusz Kwasnicki.)
  2. If n-in-a-row is drawn on a board of a certain size, it is also drawn on any smaller board.
  3. If n-in-a-row is won on a certain board, m-in-a-row with k < n also is.
  4. If n-in-a-row is drawn on a certain board, m-in-a-row with m > n also is.
Without loss of generality, we will consider n-in-a-row on board size pxq, with n <= p <= q. If p < n <= q (for instance 4-in-a-row on a 3x100 board), the game reduces to n-in-a-row on 1xq, which is a draw unless k = 1 or (k = 2 and q > 2).

1-in-a-row is obviously won on any board.

2-in-a-row is won on any board of more than 2 squares (q>2).

3-in-a-row is drawn on 3x3 and smaller and won on 3x4 and larger (p >= 3, q > 3). It is also won on 3x3 with just one square augmented; you can try this yourself.

Four-in-a-row

A special section because this is going to be quite a long story. The good news that it is appears almost solved. An old result is that 4-in-a-row is a draw on 5x5 (C.Y. Lee). Berlekamp, Conway, and Guy (2001) do not give any minimum q for which it is won on 5xq. However, it is straightforward to show that it is won on 5x6 and larger (p>=5, q>5). A simple variation tree does the job. Start in one of both central squares: 
4-in-a-row on 5x6
Board coordinates: a-e and 1-6.

Variations can end in two ways. The first way is by two simultaneous threats 
of 4-in-a-row, only one of which can be defended. The second way is by two 
simultaneous threats of creating 3-in-a-row with open ends, while the second 
player cannot generate any useful threats. 
Notation for a threat is *; / just means "or". Moves are numbered: odd 
for the first player, even for the second player. When there are several ways to 
win, we give one which uses the smallest possible board.

1.c3
Given the symmetry, we restrict ourselves to replies in the right half and the 
center line.

2.c6/d6/e6/c5/d5/d3/c1/d1 3.b4 (*d2) 4.a5/d2/e1 5.d4 (*b2,*c4)
2.c4/e5 3.b4 (*d2) 4.a5/d2/e1 5.b3 (*b2,*b5,*d3)
2.c2/e1 3.b2 (*d4) 4.a1/d4/e5 5.b3 (*b4,*d3)
2.e2 3.b4 (*d2) 4.a5/d2/e1 5.b2 (*b3,*d4)
2.e4 (/e3 resp.) 3.b4 (*d2)
   4.a5 or 4.d2 5.b2 (*b3,*d4)
   4.e1 5.b2 (*b3,*d4) 6.e3 (/e4 resp.) 7.e2 8.e5 9.e6 10.b3 11.d2 
2.d2 3.d3 (*b3) 4.a3/b3/e3 5.c4 (*b5,*c2,*c5)
2.d4 3.c4 (*c2,*c5) 
   4.c2 5.b3 (*d3,*d5)
   4.c5 5.b3 (*d3,*d5) 6.e3 7.b6 8.a2/d5/e6 9.b5 10.b4 11.d3

Only the last two variations (2.d2 and 2.d4) need the sixth row for winning.
It even seems won on 5x5 with a single square augmented, provided the extra square is attached to a corner square or to the center square of an edge.

What if p = 4? It was shown to be a win on 4x30 by C. Lustenberger and on 4x27 by Selfridge, but it long remained unsolved on 4xq with 5 < q < 30. In December 2004, I received an email from Volodymyr Sobotovych, claiming that he had proved a win on 4x11 in 2003, and probably on 4x9 as well. He has done this using variation trees. Below are a few of his variations. Moves are numbered starting with 3 (the raster somehow does not appear fully):

I have checked all variations and they seem correct and complete. Some of them are very elegant or involved. No computer algorithm is available yet. It is harder to prove that it is a draw for q < 9, but his work firmly puts the best guess for the minimum q for which 4xq is won at 9. Since it does not seem that all variations which use the full width of the board can be improved, it is highly unlikely that there is a win for q < 9.
The original claim (July 2003) and a few exercises are posted on http://www.renju.net/media/news/news03.htm#33 (or click here for the text file). His full analysis file (Renlib format) used to be available at http://www.renju.nu/four_in_a_row/analysis_4_11.lib, but that site seems to be defunct now.

Five-in-a-row

Five-in-a-row is drawn on 5x5, either because 4-in-a-row already is, or using a pairing strategy. It is won on 15x15 and larger. This game has a history as a game played by ordinary people (that is, people not obsessed by mathematical games). The version of the game which is played on 19x19 (a Go board) is called Go-Moku, on 15x15 it is called Go-Moku or Renju (another name is Go-bang). Renju has somewhat different opening rules than Go-moku. Even the latter is so "easily" won that players of these games have imposed many restrictions on the first players, so as to make winning chances more equal. In Renju, many winning patterns, such as "double three" and "more-than-5-in-a-row", are forbidden for the first player. Allis, van den Herik, and Huntjens have proved that Go-Moku on 15x15 with restrictive rules is a win for the first player. Given that the win is so "easy", it is expected that the smallest board on which 5-in-a-row withour restrictions is won is much smaller than 15x15. As far as i know, 5-in-a-row has never been studied on non-square boards. An interesting question would be:
What is the smallest p such that there exists a q>=p for which 5-in-a-row is a win on a pxq board?

More-than-five-in-a-row

6-in-a-row is a draw on 6x6 (by a pairing strategy) but completely mysterious otherwise. It is not even known if there is any board size on which it is won! Ando Meritee (the world's strongest Renju player) thinks it is a draw on any board.

There are indications that 7-in-a-row is drawn even on infinite x infinite, but there is no proof.

8-in-a-row and more-in-a-row are always drawn; the drawing strategy has been proven on infinite x infinite (T.G.L. Zetters).

9-in-a-row is drawn on infinite x infinite using a Hales-Jewett pairing strategy:

(Figure from Berlekamp, Conway, Guy.) The pattern is periodic. Wherever the first player moves, the second player moves in the square connected to it with a line segment. In this way, 9-in-a-row can be prevented in any direction.

Summary

We call n-in-a-row "solved" if it is known on what board sizes it is won (and thus also on which it is drawn). n-in-a-row is solved for n = 1, 2, 3, and n > 7. It is close to being solved for n = 4 and n = 7. For n = 5 it is known that there are board sizes for which it is won.

nWin on p x q board (p <= q)
1always
2if and only if q > 2
3if and only if p >= 3 and q >= 4
4if and only if (p >= 5 and q >= 6) or (p = 4 and q >= 9 (?))
5if p = q >= 15; not if q <= 6
6not if p = q = 6 (conjecture: never)
7never (?)
>= 8never

The most challenging problems are to solve 5-in-a-row and 6-in-a-row. Where is the borderline between winnable (on sufficiently large boards) and drawn (on any board) - is it between 5 and 6, between 6 and 7, or even between 7 and 8? Another question is whether there is some underlying logic in all this.

Personally, I find 4-in-a-row on 4x9 and 5-in-a-row on diverse boards (such as 10x10) most fun to play. Also consider playing the capture variation of 5-in-a-row (see below).

Higher dimensions

Tic-tac-toe becomes mind-boggling when you start considering higher-dimensional "boards". For instance, a 3x3x3 "board" would be a cube, and your task is still to get a line or diagonal filled with your pieces.

Three-dimensional: 3-in-a-row is trivially won on 3x3x3. The game called Qubic, 4-in-a-row on 4x4x4, was weakly solved by Patashnik (1980) and strongly solved by Victor Allis (1994). There are 76 winning lines. For humans it is still interesting to play. You can play it by drawing the four layers of the cube.
4-in-a-row on 4x4xq with q < 4 is not interesting, because it reduces to 4-in-a-row on 4x4 (which is drawn). S.W. Golumb has found a Hales-Jewett pairing strategy for 8-in-a-row on 8x8x8.

Higher dimensions: The Hales-Jewett Theorem states that:

When playing n-in-a-row on a board of size nxnx..xn (d dimensions), for every n there exists some d such that it is won, no matter how many players there are.
For n = 3 and n = 4 this d should be 3 or higher, for general n there are various upper bounds on d. For d>3 these games are practically unplayable but mathematically fascinating.
Hales and Jewett also showed that if n is large enough with respect to d, n-in-a-row on a board of size nxnx..xn (d dimensions) is drawn. A lower bound is n>=3^d-1 if n is odd and n>=2^(n+1)-2 if n is even.

Surprisingly enough, this kind of mathematics is not completely useless. The Hales-Jewett theorem is central to Ramsey theory, the mathematical study of combinatorial objects in which a certain degree of order must occur as the scale of the object becomes large.
For computer scientists, coming up with a winning algorithm for won positions and with a defense algorithm in other cases, is a great challenge.

Rule variations

There are plenty of variations of tic-tac-toe on general pxq boards. Here we mention a few. Other variations can be found on this page by James Yolkowski.

References and further reading

Wei Ji Ma