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
    • Misere n-in-a-row
    • Revenge n-in-a-row
    • Treblecross
    • Two-directional tic-tac-toe
    • Five-in-a-row with capture
    • Periodic n-in-a-row
  9. References and further reading

Generalized Tic-tac-toe    (k-in-a-row on an m-by-n board)

 

 Introduction      go up

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.

As many kids discover, this game is a draw with best play. You might think the game stops being interesting at that point. However, there is an interesting generalization of tic-tac-toe, k-in-a-row on an m-by-n rectangular board. Not for all combinations of k, m, n is it known whether the outcome under best play is a draw or not. This website describes what is known about these generalizations, also called m,n,k-games. We also give some rule variations.

 

Systematic exploration      go up

The central question is: when is k-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 a 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:
  • If k-in-a-row is drawn on a board of a certain size, it is also drawn on any smaller board.
  • If k-in-a-row is won on a certain board, h-in-a-row with h<k is also won on that board.
  • If k-in-a-row is drawn on a certain board, h-in-a-row with h>k is also drawn on that board.
  • If k-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.)
Without loss of generality, we will consider k-in-a-row on a board of size mxn, with k <= m <= n. When m < k <= n (for instance 4-in-a-row on a 3x100 board), the game reduces to k-in-a-row on 1xn, which is a draw unless k = 1, or k = 2 and n > 2.

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

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

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

 

Four-in-a-row      go up

Four-in-a-row turns out to be quite a long story, but 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 n for which it is won on 5xn. However, it is straightforward to show that it is won on 5x6 and larger (m>=5, n>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 m = 4? It was shown to be a win on 4x30 by C. Lustenberger and on 4x27 by Selfridge, but it long remained unsolved on 4xn with 5<n<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 n < 9, but his work firmly puts the best guess for the minimum n for which 4xn 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 n < 9.

The original claim by Sobotovych (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) is available at http://renju.se/rif/four_in_a_row.

 

Five-in-a-row      go up

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 for fun (that is, by 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 m such that there exists a n>=m for which 5-in-a-row is a win on a mxn board?

More-than-five-in-a-row      go up

6-in-a-row is a draw on 6x6 (by a pairing strategy) but nothing is known about it 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      go up

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

k
Win on m x n board (m <= n)
1always
2if and only if n > 2
3if and only if m >= 3 and n >= 4
4if and only if (m >= 5 and n >= 6) or (m = 4 and n >= 9 (?))
5if m = n >= 15; not if n <= 6
6not if m = n = 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.

 

For practical play, 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      go up

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 4x4xn with n < 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 k-in-a-row on a board of size kxkx..xk (d dimensions), for every k there exists some d such that it is won, no matter how many players there are.
For k = 3 and k = 4 this d must be 3 or higher. For general k there are various upper bounds on d. For d>3, these games are unplayable in practice but fascinating mathematically.
Hales and Jewett also showed that if k is large enough with respect to d, k-in-a-row on a board of size kxkx..xk (d dimensions) is drawn. A lower bound is k>=3^d-1 if k is odd and k>=2^(k+1)-2 if k 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      go up

There exist several variations of tic-tac-toe on general mxn boards. Here we mention a few.
  • Inverse (also called "misere") k-in-a-row: you win if your opponent gets k-in-a-row. Now, the first player is fighting for a draw and the second player is playing for a win. If m or n is even, then for any n the second player has as least a draw, using a mirror strategy. Inverse 3-in-a-row is a draw on 3x3 by starting in the middle. Remarkably, inverse 2-in-a-row is nontrivial. On 3x3, it is won for the second player. Let us consider k=2 on 1xn boards. It is drawn if n is even and won for the second player if n is odd. Volodymyr Sobotovych gives a winning strategy: 

Let's call the first player the x-player and the second player the o-player. Let's define an xo-area as a space of empty squares between x and o (or o and x), and an xx-area as a space between two x's, e.g.: oAAAAxBBBxCCCCo - A and C are xo-areas, B is an xx-area. Let's define a position as an O-position if the x-player is to move and the board contains only xo and xx areas, for instance: o....x....x....o.....x......o After any move by the x-player in an O-position, the o-player always can return to an O-position: x....o -> x..x.o -> xo.x.o; x.....x -> x..x..x -> x..xo.x (an empty area between xo is also an xo-area). Let's return to our game on a 1xq board, where q is odd. The x-player makes his first move, the o-player occupies an end square with his second move, and after the next move of the x-player there are two possible situations:

  • The o-player can occupy the second end square and we have two xo-areas and one xx-area; this is an O-position.
  • The players have occupied opposite end squares and the o-player can build an O-position with 3 xo-areas. Hence, by induction, the final position will be an O-position. In view of the definition of O-position, this gives the o-player at least a draw. However, the only possible drawing configuration on a full board has x's on both ends. In our strategy there is an o on at least one end, therefore it is a win for the o-player.
  • Revenge k-in-a-row: you win if you connect k, but you lose if your opponent can connect k immediately after that (the less interesting variation is with "draw" instead of "lose"). For k=3, this game is won on a 3x3 board. It is now not true anymore than a win on a certain board guarantees a win on any bigger board. If m or n is even, then for any k the second player has as least a draw, using a mirror strategy. Even if k=2 and the board size is 1xn (one-dimensional), then the game is non-trivial. For instance, k=2 on 1x5 is won for the first player if he starts in the second or fourth square, but not if he starts elsewhere.
  • A related game is played with k=3 on a 1xn board. However, both players play with the same pieces (say x). Whoever gets three x's in a row wins. This game is called treblecross. It is a typical example of an octal game and has been analyzed in detail.
  • Bidirectional tic-tac-toe (thanks to Volodymyr Sobotovych). Let us define k&h-in-a-row as game where a win is k in a horizontal line or h in vertical line. We play on boards mxn where m<=n, k<=m, and h<=n. 1&h-in-a-row and 2&h-in-a-row are always won. 3&3-in-a-row is a draw on 3x3 and a win on 3x4, 4x3, and larger. 3&4-in-a-row is a draw on 3x4 and a win on 4x4 and larger. It is unsolved on general 3xn. 3&h-in-a-row with h>=5 is a draw on all 3xn boards and won on 4xh and larger. 4&4-in-a-row is a win on boards 7x7 and larger. However, it is unclear and interesting on mxn with m = 4,5,6. 5&5-in-a-row is a sure draw for any board, through a pairing strategy. 4&5-in-a-row is unsolved even on an infinite board. Is it a win or a draw?
  • A more-fun and less mathematical variation of 5-in-a-row is 5-in-a-row with capture, on a Go board (19x19). When with your move you enclose precisely two of your opponent's adjacent pieces in a line or diagonal between a piece of yours which was already there and the one you just played, you can remove the opponent's pieces from the board. This can happen in more directions at the same time. With the extra rule that capturing five pairs of your opponent's pieces also wins the game, this game is called Pente. It was invented in 1973 by Gary Gabrel and is a registered game. Ninuki-Renju has the same rules as pente but also some additional ones.
  • Periodic (or torus) k-in-a-row: the top and bottom of the board are connected with each other, as well as the left and right. This means that in both directions you have a circular board (hence a torus). This makes all opening moves equivalent. It is rather difficult to play. 3-in-a-row on periodic 3x3 is a win! Periodic k-in-a-row on mxn is possible and interesting even with m < k (We define that a ring with m of the same symbols is only m-in-a-row, not k-in-a-row.) Periodic 3-in-a-row on 2xn is a win if and only if n >= 3. Periodic 4-in-a-row on 2xn is a win if n >= 7. Periodic 5-in-a-row is a sure draw on 2xn for any n (pairing strategy), but it seems non-trivial on other boards.

Other variations can be found on this page by James Yolkowski.

 

References and further reading      go up