From:  (Chris Thompson)
Date:           14 Oct 1996 00:00:30 GMT
Newsgroups:     sci.math
Subject:        Harary's animal-achievement game - some questions

Yet Another Posting arising from browsing old SciAm issues...

[MG1] Martin Gardner, "Mathematical Games"
      Scientific American 240:4 (April 1979) pp. 18-21

[MG2] Martin Gardner, "Mathematical Games"
      Scientific American 241:3 (September 1979) p. 26

[WW]  Elwyn Berlekamp, John Conway & Richard Guy, "Winning Ways"
      (Academic Press, 1982) [vol 2] pp. 684-685

[MG1] and [WW] describe a class of two-person games invented by 
Frank Harary. They are played on a square matrix and the players 
alternately mark a previously unmarked cell with a player-specific 
symbol [as in noughts-and-crosses = tick-tack-toe]. A player wins if
he forms a congruent copy [reflections are allowed] of a specified 
"animal" [a.k.a. "polyomino"] of cells all marked with his symbol.

By the usual strategy-stealing argument, with optimal play the game
must be either a first-player win or a draw, so it's only fair to
count a draw as a second-player win. In fact there's a variant in
which all the second player does is to try to stop the first player 
forming the animal: she doesn't win by forming one herself. An animal
which can be achieved by the first player on a sufficiently large 
board is a "winner", one that he cannot form is a "loser".

The main result mentioned in [MG1] and [WW] is that there are just
twelve animals that are winners:

  *    *-*   *-*-*   *-*   *-*-*-*   *-*-*    *-*-*   *-*
                       *                 *      *       *-*

  *-*-*-*    *-*-*-*   *-*-*      *-*-*-*
        *        *         *-*          *-*

Well, maybe "result" isn't quite the right word, as although the
Hales-Jewett pairings shown in [MG1] and [WW] certainly prove all
other animals losers [although note that both these specify the
same wrong pairing for demonstrating that

      *     *

is a loser - e.g. see [MG2]], the status of the final hexomino
(named "Snaky" by Harary) is admitted to be uncertain, [MG1]
saying that it is "believed" that a first-player win in 13 moves 
on a 15x15 board is possible, and [WW] giving the same numbers
but succinctly adding the caveat "but Snaky is a bit shaky".

Q1. Surely someone has settled this one way or the other by now,
    if only by brute force computation? 

[MG1] and [WW] both give minimum numbers of moves (m) and minimum
board sizes (b for a bxb board) for the winners. These don't agree,
for at least two reasons: 

 1. There is a difference between 
    a) m_1, the minimum number of moves to win on an infinite board, 
       and b_1, the minimum size of board in which one can win in 
       m_1 moves; and
    b) b_2, the minimum size of board on which it is possible to win,
       and m_2, the minimum number of moves necessary to win on such
       a board.
    [MG1] is trying to give (b); [WW] (without making it very clear)
    seems to be attempting (a).
 2. Some entries are just wrong. E.g. [MG1] gives (b=4,m=5) for the
    Z-shaped tetromino, [WW] correctly gives (b=3,m=5) [correctly
    according to either (a) or (b), in this case]. To add to the
    confusion, in [MG2] Gardner writes "for the 4-cell animal Knobby
    [the T-shaped tetromino] the move number is 4, not 5" -- but
    [MG1] already correctly [I think] gave (b=5,m=4) for this animal!

Q2. Has anyone worked out the correct optimal (boardsize,moves) values
    for each winning animal?

There are all sorts of potential variations: triangular or hexagonal
grids, 3-dimensional grids, games in which the players try to make
different animals, games in which they try to avoid making specific
animals, etc., etc. In [MG1] Gardner writes "Harary is planning a book
on achievement and avoidance games in which all these generalisations
of ticktacktoe and many other closely related games will be explored".

Q3. Did this book ever appear? What other work has been done in this 
    area in the last 15 years?

With thanks in advance for any information on this subject.

Chris Thompson