Harary's generalized tic-tac-toe

Harary's generalized tic-tac-toe or animal tic-tac-toe is a generalization of the game tic-tac-toe, defining the game as a race to complete a particular polyomino on a square grid of varying size, rather than being limited to "in a row" constructions. It was devised by Frank Harary in March 1977, and is a broader definition than that of an m,n,k-game.

Harary's generalization does not include tic-tac-toe itself, as diagonal constructions are not considered a win.

Like many other two-player games, strategy stealing means that the second player can never win. All that is left to study is to determine whether the first player can win, on what board sizes he may do so, and in how many moves it will take.

Results

Square boards

Let b be the smallest size square board on which the first player can win, and let m be the smallest number of moves in which the first player can force a win, assuming perfect play by both sides.[1][2][3]

  • monomino: b = 1, m = 1
  • domino: b = 2, m = 2
  • I-tromino: b = 4, m = 3
  • V-tromino: b = 3, m = 3
  • I-tetromino: b = 7, m = 8
  • L-tetromino: b = 4, m = 4
  • O-tetromino: The first player cannot win
  • T-tetromino: b = 5, m = 4
  • Z-tetromino: b = 3, m = 5
  • F-pentomino: The first player cannot win
  • I-pentomino: The first player cannot win
  • L-pentomino: b = 7, m = 10
  • N-pentomino: b = 6, m = 6
  • P-pentomino: The first player cannot win
  • T-pentomino: The first player cannot win
  • U-pentomino: The first player cannot win
  • V-pentomino: The first player cannot win
  • W-pentomino: The first player cannot win
  • X-pentomino: The first player cannot win
  • Y-pentomino: b = 7, m = 9
  • Z-pentomino: The first player cannot win
  • All hexominoes (with a possible exception of the N-hexomino, which is still currently unsolved, may have b = 15 and m = 13): The first player cannot win
  • All heptominoes and above: The first player cannot win

References
  1. Tic-tac-toe
  2. QBF Encoding of Generalized Tic-Tac-Toe
  3. How to find winning Strategy for 4 celled animals of Harary's generalized tic tac toe
  • Beck, József (2008), "Harary's Animal Tic-Tac-Toe", Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge: Cambridge University Press, pp. 60–64, doi:10.1017/CBO9780511735202, MR 2402857
  • Gardner, Martin. The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems: Number Theory, Algebra, Geometry, Probability, Topology, Game Theory, Infinity, and Other Topics of Recreational Mathematics. 1st ed. New York: W. W. Norton & Company, 2001. 286-311.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.