Harary's generalized tic-tac-toe

Harary's generalized tic-tac-toe

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.

Results

quare 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

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Harary — is a popular last name of Jews of Moroccan and Syrian descent. Many Moroccan Jews upon emigration to Israel in the 1950 s hebraicised the original surname, Elharar, to Harary. Harary may refer to:* Frank Harary ** Harary s generalized tic tac toe …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • M,n,k-game — An m,n,k game is an abstract board game in which two players take turns in placing a stone of their color on an m times; n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or… …   Wikipedia

  • m,n,k-game — An m,n,k game is an abstract board game in which two players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”