 Introduction
 Systematic exploration
 Fourinarow
 Fiveinarow
 Morethanfiveinarow
 Summary and rambling
 Higher dimensions
 Rule variations
 Misere ninarow
 Revenge ninarow
 Treblecross
 Twodirectional tictactoe
 Fiveinarow with capture
 Periodic ninarow
 References and further reading
Generalized Tictactoe (kinarow on an mbyn board) Introduction TicTacToe (or noughtsandcrosses) 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 tictactoe, kinarow on an mbyn 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,kgames. We also give some rule variations. Systematic exploration The central question is: when is kinarow 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 strategystealing argument. The game is drawn if there does not exist a winning strategy for the first player. There are some other general observations:
 If kinarow is drawn on a board of a certain size, it is also drawn on any smaller board.
 If kinarow is won on a certain board, hinarow with h<k is also won on that board.
 If kinarow is drawn on a certain board, hinarow with h>k is also drawn on that board.
 If kinarow 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 kinarow on a board of size mxn, with k <= m <= n. When m < k <= n (for instance 4inarow on a 3x100 board), the game reduces to kinarow on 1xn, which is a draw unless k = 1, or k = 2 and n > 2. 1inarow is trivially won on any board. 2inarow is trivially won on any board of more than 2 squares (n>2). 3inarow 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. Fourinarow Fourinarow turns out to be quite a long story, but it is appears almost solved. An old result is that 4inarow 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:  4inarow on 5x6
Board coordinates: ae and 16.
Variations can end in two ways. The first way is by two simultaneous threats of 4inarow, only one of which can be defended. The second way is by two simultaneous threats of creating 3inarow 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. Fiveinarow Fiveinarow is drawn on 5x5, either because 4inarow 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 GoMoku, on 15x15 it is called GoMoku or Renju (another name is Gobang). Renju has somewhat different opening rules than Gomoku. 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 "morethan5inarow", are forbidden for the first player. Allis, van den Herik, and Huntjens have proved that GoMoku 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 5inarow withour restrictions is won is much smaller than 15x15. As far as i know, 5inarow has never been studied on nonsquare boards. An interesting question would be:  What is the smallest m such that there exists a n>=m for which 5inarow is a win on a mxn board?
Morethanfiveinarow 6inarow 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 7inarow is drawn even on infinite x infinite, but there is no proof. 8inarow and moreinarow are always drawn; the drawing strategy has been proven on infinite x infinite (T.G.L. Zetters). 9inarow is drawn on infinite x infinite using a HalesJewett 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, 9inarow can be prevented in any direction. Summary We call kinarow "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. kinarow 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)  1  always  2  if and only if n > 2  3  if and only if m >= 3 and n >= 4  4  if and only if (m >= 5 and n >= 6) or (m = 4 and n >= 9 (?))  5  if m = n >= 15; not if n <= 6  6  not if m = n = 6 (conjecture: never)  7  never (?)  >= 8  never  The most challenging problems are to solve 5inarow and 6inarow. 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 4inarow on 4x9 and 5inarow on diverse boards (such as 10x10) most fun to play. Also consider playing the capture variation of 5inarow (see below). Higher dimensions Tictactoe becomes mindboggling when you start considering higherdimensional "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. Threedimensional: 3inarow is trivially won on 3x3x3. The game called Qubic, 4inarow 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. 4inarow on 4x4xn with n < 4 is not interesting, because it reduces to 4inarow on 4x4 (which is drawn). S.W. Golumb has found a HalesJewett pairing strategy for 8inarow on 8x8x8. Higher dimensions: The HalesJewett Theorem states that:  When playing kinarow 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, kinarow on a board of size kxkx..xk (d dimensions) is drawn. A lower bound is k>=3^d1 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 HalesJewett 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 exist several variations of tictactoe on general mxn boards. Here we mention a few. Inverse (also called "misere") kinarow: you win if your opponent gets kinarow. 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 3inarow is a draw on 3x3 by starting in the middle. Remarkably, inverse 2inarow 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 xplayer and the second player the oplayer. Let's define an xoarea as a space of empty squares between x and o (or o and x), and an xxarea as a space between two x's, e.g.: oAAAAxBBBxCCCCo  A and C are xoareas, B is an xxarea. Let's define a position as an Oposition if the xplayer 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 xplayer in an Oposition, the oplayer always can return to an Oposition: x....o > x..x.o > xo.x.o; x.....x > x..x..x > x..xo.x (an empty area between xo is also an xoarea). Let's return to our game on a 1xq board, where q is odd. The xplayer makes his first move, the oplayer occupies an end square with his second move, and after the next move of the xplayer there are two possible situations:  The oplayer can occupy the second end square and we have two xoareas and one xxarea; this is an Oposition.
 The players have occupied opposite end squares and the oplayer can build an Oposition with 3 xoareas. Hence, by induction, the final position will be an Oposition. In view of the definition of Oposition, this gives the oplayer 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 oplayer.
 Revenge kinarow: 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 (onedimensional), then the game is nontrivial. 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 tictactoe (thanks to Volodymyr Sobotovych). Let us define k&hinarow 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&hinarow and 2&hinarow are always won. 3&3inarow is a draw on 3x3 and a win on 3x4, 4x3, and larger. 3&4inarow is a draw on 3x4 and a win on 4x4 and larger. It is unsolved on general 3xn. 3&hinarow with h>=5 is a draw on all 3xn boards and won on 4xh and larger. 4&4inarow is a win on boards 7x7 and larger. However, it is unclear and interesting on mxn with m = 4,5,6. 5&5inarow is a sure draw for any board, through a pairing strategy. 4&5inarow is unsolved even on an infinite board. Is it a win or a draw?
 A morefun and less mathematical variation of 5inarow is 5inarow 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. NinukiRenju has the same rules as pente but also some additional ones.
 Periodic (or torus) kinarow: 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. 3inarow on periodic 3x3 is a win! Periodic kinarow on mxn is possible and interesting even with m < k (We define that a ring with m of the same symbols is only minarow, not kinarow.) Periodic 3inarow on 2xn is a win if and only if n >= 3. Periodic 4inarow on 2xn is a win if n >= 7. Periodic 5inarow is a sure draw on 2xn for any n (pairing strategy), but it seems nontrivial on other boards.
Other variations can be found on this page by James Yolkowski. References and further reading
