What is the hardest winnable tic-tac-toe-ish game?

430 Views Asked by At

A tic-tac-toe-ish game is a game on an infinite where the goal is to claim a specific set of cells reflected, rotated, or translated where each player takes turns claiming a cell. A winnable tic-tac-toe-ish game is such a game which the first player can win. How big can the winning set of cells be for the game to still be winnable?

1

There are 1 best solutions below

4
On BEST ANSWER

The case where target set is a polyomino was originally proposed by Harary, referred to as generalized tic-tac-toe or animal tic-tac-toe. Determining the largest polyomino which the first player can achieve is an open problem.

The situation for tetrominos is discussed here. The square tetromino is a loser, but all others are winners. We also know the entire story for pentominos; the Y, L, and N pentominos are winners, while all others are losers. Moving up to hexominos, we know that most of the shapes are losers, simply because they contain a smaller previously proven loser as a subset. However, for the hexomino shown below, lovingly dubbed "Snaky" by Martin Garder, it is an open problem to determine if it is a winner or a loser! This is only open case; every polyomino of size 7 or more contains a previously proven loser, so is a loser.

Therefore, it is unknown whether the largest winnable polyonimo has size five or six.

enter image description here

I do not know what happens for more general target sets, i.e. ones that are only diagonally connected, or not connected at all.


Below is a pictorial proof that all of the displayed shapes are actually losers. The second player forces a draw by using the pairing strategy described in the figure. This image was taken from

H. Harborth, M. Seemann, Snaky is a paving winner, Bull. Inst. Combin. Appl. 19 (1997), 71–78

Edit: As pointed out by Spitemaster in a comment, the picture in the original paper contained a mistake. I fixed this mistake, so the picture below is correct.

enter image description here