From:cet1@cus.cam.ac.uk (Chris Thompson)Date:14 Oct 1996 00:00:30 GMTNewsgroups:sci.mathSubject: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 Email: cet1@cam.ac.uk