
An ''m'',''n'',''k''-game is an abstract
board game
A board game is a type of tabletop game that involves small objects () that are placed and moved in particular ways on a specially designed patterned game board, potentially including other components, e.g. dice. The earliest known uses of the ...
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 i ...
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, 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 (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...
is the 3,3,3-game and free-style
gomoku
''Gomoku'', also called ''five in a row'', is an Abstract strategy game, abstract strategy board game. It is traditionally played with Go (game), Go pieces (black and white stones) on a 15×15 Go board while in the past a 19×19 board was standa ...
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 a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
interest. One seeks to find the
game-theoretic value, the result of the game with
perfect play
Perfect commonly refers to:
* Perfection; completeness, and excellence
* Perfect (grammar), a grammatical category in some languages
Perfect may also refer to:
Film and television
* ''Perfect'' (1985 film), a romantic drama
* ''Perfect'' ( ...
. 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. Research in this field has primarily focused on two-player games in which a ''position'' ev ...
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). 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 involves a proposition conflicting 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 the second player cannot win but may only draw (by preventing the first player from playing ''k''-in-a-row). The weak version of a game then has just two possible outcomes ("win" and "draw") instead of three.
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''
0, ''n''
0, ''k''
0) is a draw, then (''m''
0, ''n''
0, ''k'') with ''k'' ≥ ''k''
0 is a draw, and (''m'', ''n'', ''k''
0) with ''m'' ≤ ''m''
0 and ''n'' ≤ ''n''
0 is a draw. Likewise, if (''m''
0, ''n''
0, ''k''
0) is a win, then (''m''
0, ''n''
0, ''k'') with ''k'' ≤ ''k''
0 is a win, and (''m'', ''n'', ''k''
0) with ''m'' ≥ ''m''
0 and ''n'' ≥ ''n''
0 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 (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...
), 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. And the first general result means that (''m'', ''n'', ''k'') is a draw for ''m'' = ''n'' = ''k'' if ''k'' ≥ 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'' ≥ 9 and a draw for ''m'' ≤ 8.
* 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 game, abstract strategy board game. It is traditionally played with Go (game), Go pieces (black and white stones) on a 15×15 Go board while in the past a 19×19 board was standa ...
.
* (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 ( ); the special case for is known as a ''tesseract''. It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel l ...
with all edges with length ''k'' (an
nk game), Hales and Jewett proved
[Elwyn 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 and
:''k'' ≥ 3
''n'' − 1
or if ''k'' is
even 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 or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
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" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
:2 ''k''
''n'' ≥ (''k'' + 2)
''n''.
See also
*
Connect Four
*
Connect6
Connect6 (; Pinyin: liùzǐqí; ;; ) introduced in 2003 by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University in Taiwan, is a two-player strategy game similar to Gomoku.
Two player ...
*
Gomoku
''Gomoku'', also called ''five in a row'', is an Abstract strategy game, abstract strategy board game. It is traditionally played with Go (game), Go pieces (black and white stones) on a 15×15 Go board while in the past a 19×19 board was standa ...
*
Harary's generalized tictactoe
*
Kaplansky's game
*
''nd'' game
*
Pente
Pente is an Abstract strategy game, abstract strategy board game for two or more players, created in 1977 by Gary Gabrel. A member of the M,n,k-game, m,n,k game family, Pente stands out for its Custodian capture, custodial capture mechanic, which ...
*
Qubic
*
Score Four
*
Eternas
References
{{Tic-Tac-Toe
Abstract strategy games
In-a-row games
Partially solved games