lotus

previous page: 120 geometry/coloring/cheese.cube.p
  
page up: Puzzles FAQ
  
next page: 122 competition/games/hi-q.p

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:













TOP
previous page: 120 geometry/coloring/cheese.cube.p
  
page up: Puzzles FAQ
  
next page: 122 competition/games/hi-q.p