Newsgroups: rec.puzzles
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 8 Jan 92 23:58:24 GMT
Subject: Re: Noughts and crosses

se...@fid.morgan.com (Seth Breidbart) writes:

>The more interesting question is 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?

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.

cos...@cosell.bbn.com (Bernie Cosell) writes:

>Well, there is always go-moku, which is 5-in-a-row played on a 19x19
>go board.  It is a known 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.

Apparently, yes, but I don't know if even the plain 5-in-a-row has
been _proven_ to be a win, even on an infinite board.  I haven't been
through the _Winning_Ways_ bibliography yet, but I think they would
have mentioned such a result.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil