m,n,k-game

m,n,k-game

An m,n,k-game is an abstract board game in which two players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally.[1][2] Thus, tic-tac-toe is the 3,3,3-game and free-style gomoku is the 19,19,5-game. m,n,k-game is also called as k-in-a-row game on m×n board.

m,n,k-games are mainly of mathematical interest. One seeks to find the game-theoretic value, which is the result of the game with perfect play. This is known as solving the game.

Contents

Strategy stealing argument

A standard strategy stealing argument from combinatorial game theory 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, he or she pretends that he or she is the second player and adopts the second player's winning strategy. He or she 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, he or she can again play an arbitrary move and continue as before with the second player's winning strategy. Since an extra stone cannot hurt him or her, this is a winning strategy for the first player. The contradiction implies that the original assumption is false, and the second player cannot have a winning strategy.

This argument tells us 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

If an (m,n,k) game is a draw, a smaller game (that is, one with lower m and n) is also a draw. This means that if an (m,n,k) game is a win, then any larger game must also be a win.

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 any smaller (in m and n) normal and weak (m,n,k) games are also a draw.

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, assuming that both players use an optimal strategy.

  • 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.[citation needed]
  • k ≥ 8 is a draw on an infinite board. It is not clear if this strategy applies to any finite board sizes.[2] 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)[citation needed]
  • (k,k,k) is a draw if and only if k ≥ 2 (pairing strategies for k ≥ 6, special cases otherwise)[citation needed]

Specific results

  • k = 1 and k = 2 are trivial wins, except for (1,1,2) and (2,1,2)
  • k = 3 is a draw for (3,3,3) (see Tic-tac-toe) or if m < 3 or n < 3. It is a win otherwise.
  • (m,4,4) is a win for m = 30 (Lustenberger, 1967) and a draw for m ≤ 8.[1] In 2003, it was shown to be a win for m = 9 (Sobotovych, see external link W.J. Ma).
  • (5,5,4) is a draw.
  • (6,5,4) is a win.
  • (6,6,5) is a draw.
  • Computer search by L. Victor Allis has shown that (15,15,5) is a win, even with one of the restrictive rules of Gomoku.

Multidimensional variant

It is possible to consider variants played on a multidimensional instead of a bidimensional board.

For the case of k-in-a-row where the board is an n-dimensional hypercube with all edges with length k , Hales and Jewett proved[3] 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 that the game is a draw also when the number of cell is at least twice the number of lines, which happens if and only if 2 k^n ≥ (k + 2)^n.

See also

References

  1. ^ a b J. W. H. M. Uiterwijk and H. J van der Herik, The advantage of the initiative, Information Sciences 122 (1) (2000) 43-58.
  2. ^ a b H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence.
  3. ^ Elwyn R. Berlekamp, John Horton Conway, Richard K. Guy. "Winning ways for your mathematical plays, Volume 3", A K Peters (2003)

External links

  • W.J. Ma, Generalizations of tic-tac-toe, [1].

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Game theory — is a branch of applied mathematics that is used in the social sciences (most notably economics), biology, engineering, political science, computer science (mainly for artificial intelligence), and philosophy. Game theory attempts to… …   Wikipedia

  • Game Boy Color — Atomic Purple version of the Game Boy Color. Manufacturer Nintendo …   Wikipedia

  • Game development — is the process by which a game is produced. Today this term most commonly refers to the development of video games.OverviewDevelopment of video games is undertaken by a developer, which may be a single person or a large business. Typically, large …   Wikipedia

  • Game Boy Micro — Manufacturer Nintendo Product family Game Boy line Generation Sixth generation era …   Wikipedia

  • Game Boy — Game Boy …   Deutsch Wikipedia

  • Game Boy Color — Game Boy Hersteller Nintendo Typ Handheld Konsole Generation 3. Generation …   Deutsch Wikipedia

  • Game Boy Light — Game Boy Hersteller Nintendo Typ Handheld Konsole Generation 3. Generation …   Deutsch Wikipedia

  • Game Boy Pocket — Game Boy Hersteller Nintendo Typ Handheld Konsole Generation 3. Generation …   Deutsch Wikipedia

  • Game-Boy —  Ne doit pas être confondu avec Game Boy Color, Game Boy Advance, Game Boy Advance SP ou Game Boy Micro. Pour les articles homonymes, voir GB et Game Boy (homonymie) …   Wikipédia en Français

  • Game Boy (console) — Game Boy  Ne doit pas être confondu avec Game Boy Color, Game Boy Advance, Game Boy Advance SP ou Game Boy Micro. Pour les articles homonymes, voir GB et Game Boy (homonymie) …   Wikipédia en Français

  • Game Boy Light — Game Boy  Ne doit pas être confondu avec Game Boy Color, Game Boy Advance, Game Boy Advance SP ou Game Boy Micro. Pour les articles homonymes, voir GB et Game Boy (homonymie) …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”