121 competition/games/go-moku.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
121 competition/games/go-moku.p
For a game of k in a row on an n x n board, for what values of k and n is
there a win? Is (the largest such) k eventually constant or does it increase
with n?
competition/games/go-moku.s
Berlekamp, Conway, and Guy's _Winning_Ways_ reports proof that the
maximum k is between 4 and 7 inclusive, and it appears to be 5 or 6.
They report:
. 4-in-a-row is a draw on a 5x5 board (C. Y. Lee), but not on a 4x30
board (C. Lustenberger).
. N-in-a-row is shown to be a draw on a NxN board for N>4, using a
general pairing technique devised by A. W. Hales and R. I. Jewett.
. 9-in-a-row is a draw even on an infinite board, a 1954 result of H. O.
Pollak and C. E. Shannon.
. More recently, the pseudonymous group T. G. L. Zetters showed that
8-in-a-row is a draw on an infinite board, and have made some
progress on showing infinite 7-in-a-row to be a draw.
Go-moku is 5-in-a-row played on a 19x19 go board. It is apparently a
win for the first player, and so the Japanese have introduced several
'handicaps' for the first player (e.g., he must win with _exactly_
five: 6-in-a-row doesn't count), but apparently the game is still a win
for the first player. None of these apparent results have been
proven.
Continue to:
My Books
