Harary's generalized tic-tac-toe
From Wikipedia, the free encyclopedia
Harary's generalized tic-tac-toe is an even broader generalization of tic-tac-toe than m,n,k-games are. Instead of the goal being limited to "in a row" constructions, the goal can be any polyomino (Note that when this generalization is made diagonal constructions are not considered a win). It was devised by Frank Harary in March of 1977.
Like many other games, the second player cannot win (the reason is detailed on the m,n,k-game page). All that is left to study then is to determine if the first player can win, on what board sizes he may do so, and in how many moves it will take.
[edit] Results
[edit] 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.
- monomino: b = 1, m = 1
- domino: b = 2, m = 2
- straight tromino: b = 4, m = 3
- L-tromino: b = 3, m = 3
- square-tetromino: The first player cannot win
- straight-tetromino: b = 7, m = 8
- T-tetromino: b = 5, m = 4
- Z-tetromino: b = 3, m = 5
- L-tetromino: b = 4, m = 4
[edit] References
- 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.
