An ''m'',''n'',''k''-game is an abstract

board game Board games are tabletop games that typically use . These pieces are moved or placed on a pre-marked board (playing surface) and often include elements of table, card, role-playing, and miniatures games as well. Many board games feature a comp ...

in which two

player Player may refer to: Role or adjective * Player (game), a participant in a game or sport ** Gamer, a player in video and tabletop games ** Athlete, a player in sports ** Player character, a character in a video game or role playing game who ...

s take turns in placing a stone of their color on an ''m''-by-''n'' board, the winner being the player who first gets ''k'' stones of their own color in a row, horizontally, vertically, or diagonally.J. W. H. M. Uiterwijk and H. J van der Herik, ''The advantage of the initiative'', Information Sciences 122 (1) (2000) 43-58.

Jaap van den Herik Hendrik Jacob (Jaap) van den Herik (born 8 October 1947 in Rotterdam) is a Dutch computer scientist, and professor at the University of Leiden, known for his contribution in the fields of computer chess and artificial intelligence. Biography ...

, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. Thus,

tic-tac-toe Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. T ...

is the 3,3,3-game and free-style

gomoku ''Gomoku'', also called ''Five in a Row'', is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a Go board. It is played using a 15×15 board while in the past a 19×19 board was standard. Be ...

is the 15,15,5-game. An ''m'',''n'',''k''-game is also called a ''k''-in-a-row game on an ''m''-by-''n'' board. The ''m'',''n'',''k''-games are mainly of

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

interest. One seeks to find the

game-theoretic Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has applic ...

value, the result of the game with

perfect play A solved game is a game whose outcome (win, lose or draw) can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full informa ...

. This is known as solving the game.

Strategy stealing argument

A standard strategy stealing argument from

combinatorial game theory Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...

shows that in no ''m'',''n'',''k''-game can there be a strategy that assures that the second player will win (a second-player

winning strategy Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and simil ...

). This is because an extra stone given to either player in any position can only improve that player's chances. The strategy stealing argument assumes that the second player has a winning strategy and demonstrates a winning strategy for the first player. The first player makes an arbitrary move, to begin with. After that, the player pretends that they are the second player and adopts the second player's winning strategy. They can do this as long as the strategy doesn't call for placing a stone on the 'arbitrary' square that is already occupied. If this happens, though, they can again play an arbitrary move and continue as before with the second player's winning strategy. Since an extra stone cannot hurt them, this is a winning strategy for the first player. The

contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

implies that the original assumption is false, and the second player cannot have a winning strategy. This argument tells nothing about whether a particular game is a draw or a win for the first player. Also, it does not actually give a strategy for the first player.

Applying results to different board sizes

A useful notion is a "weak (''m'',''n'',''k'') game", where ''k''-in-a-row by the second player does not end the game with a second player win. If weak (''m'',''n'',''k'') is a draw, then decreasing ''m'' or ''n'', or increasing ''k'' will also result in a drawn game. Conversely, if weak or normal (''m'',''n'',''k'') is a win, then any larger weak (''m'',''n'',''k'') is a win. Note that proofs of draws using pairing strategies also prove a draw for the weak version and thus for all smaller versions.

General results

The following statements refer to the first player in the weak game, assuming that both players use an optimal strategy. * If a particular (''m''₀, ''n''₀, ''k''₀) is a draw, then (''m''₀, ''n''₀, ''k'') with ''k'' ≥ ''k''₀ is a draw, and (''m'', ''n'', ''k''₀) with ''m'' ≤ ''m''₀ and ''n'' ≤ ''n''₀ is a draw. Likewise, if (''m''₀, ''n''₀, ''k''₀) is a win, then (''m''₀, ''n''₀, ''k'') with ''k'' ≤ ''k''₀ is a win, and (''m'', ''n'', ''k''₀) with ''m'' ≥ ''m''₀ and ''n'' ≥ ''n''₀ is a win. * ''k'' ≥ 9 is a draw: when ''k'' = 9 and the board is infinite, the second player can draw via a "pairing strategy". A draw on an infinite board means that the game will go on forever with perfect play. A pairing strategy involves dividing all the squares of the board into pairs in such a way that by always playing on the pair of the first player's square, the second player is ensured that the first player cannot get ''k'' in a line. A pairing strategy on an infinite board can be applied to any finite board as well – if the strategy calls for making a move outside the board, then the second player makes an arbitrary move inside the board. * ''k'' ≥ 8 is a draw on an infinite board. It is not clear if this strategy applies to any finite board sizes. It is not known if the second player can force a draw when ''k'' is 6 or 7 on an infinite board. * ''k'' ≥ 3 and either ''k'' > ''m'' or ''k'' > ''n'' is a draw, also by a pairing strategy in the dimension not smaller than ''k'' (or trivially impossible to win if both are smaller)

Specific results

* ''k'' = 1 and ''k'' = 2 are trivial wins, except for (1,1,2) and (2,1,2) * (3,3,3) is a draw (see

Tic-tac-toe Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. T ...

), and (''m'',''n'',3) is a draw if ''m'' < 3 or ''n'' < 3. (''m'',''n'',3) is a win if ''m'' ≥ 3 and ''n'' ≥ 4 or ''m'' ≥ 4 and ''n'' ≥ 3. * (5,5,4) is a draw, which means that (''m'',''n'',4) is a draw for ''m'' ≤ 5 and ''n'' ≤ 5, and (6,5,4) is a win, which means that (''m'',''n'',4) is a win for ''m'' ≥ 6 and ''n'' ≥ 5 or ''m'' ≥ 5 and ''n'' ≥ 6. (''m'',4,4) is a win for ''m'' ≥ 30 (Lustenberger, 1967) and a draw for ''m'' ≤ 8. It is unknown if (''m'',4,4) is a win or a draw for 9 ≤ ''m'' ≤ 29. * Computer search by Wei-Yuan Hsu and Chu-Ling Ko has shown that both (7,7,5) and (8,8,5) are draws, which means that (''m'',''n'',5) is a draw for ''m'' ≤ 8 and ''n'' ≤ 8. Computer search by L. Victor Allis has shown that (15,15,5) is a win, even with one of the restrictive rules of

Gomoku ''Gomoku'', also called ''Five in a Row'', is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a Go board. It is played using a 15×15 board while in the past a 19×19 board was standard. Be ...

. * (9,6,6) and (7,7,6) are both draws via pairings.

Multidimensional variant

It is possible to consider variants played on a multidimensional board instead of a bidimensional board. For the case of ''k''-in-a-row where the board is an ''n''-dimensional

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...

with all edges with length ''k'', Hales and Jewett provedElwyn R. Berlekamp, John Horton Conway, Richard K. Guy. "Winning ways for your mathematical plays, Volume 3", A K Peters (2003) that the game is a draw if ''k'' is

odd Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric. Odd may also refer to: Acronym * ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...

and :''k'' ≥ 3^''n'' − 1 or if ''k'' is

even Even may refer to: General * Even (given name), a Norwegian male personal name * Even (surname) * Even (people), an ethnic group from Siberia and Russian Far East ** Even language, a language spoken by the Evens * Odd and Even, a solitaire game w ...

and :''k'' ≥ 2^''n''+1 − 2. They

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...

that the game is a draw also when the number of cells is at least twice the number of lines, which happens

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...

:2 ''k''^''n'' ≥ (''k'' + 2)^''n''.

References