Find winning Strategy for 4 celled animals of Harary’s generalized tic tac toe

algorithmic-game-theorycombinatorial-game-theorycombinatoricspolyomino

A polyomino is a structure made of unit squares joined along their sides. A single square is called a monomino. Two make a domino. Three join in two different ways to make two trominoes.
Let's call the polyominoes as n celled animals. The question is about the 5 possible 4 celled animals which are named Skinny, Fatty, Elly, Knobby and Tippy. See image
These animals can be used to play tic tac toe. The basic idea is for two players to take turns marking the cells of a square matrix with zeros and crosses, but instead of trying to get three of their marks in a row, they try to form a specified animal or its mirror image.

For example, assume that the game's animal is Tippy, and that the game is played on an order 3 (three by three) square field. The first player to form Tippy, in either of its mirror image forms, wins.
What's the winning strategy for the first player?

To win Tippy tictactoe first take the center cell. Thereafter always play directly opposite your opponent's last move. You won't win until you take the last cell, but that move will always form Tippy. (Of course if your opponent makes an error, and you see a chance to win on your next move, you can shorten the game.)

How about the other four cell animals? The smallest boards on which Elly, Knobby, and Skinny are wins (for the first player; the second player can never win because of strategy stealing argument), have orders 4, 5, and 7, respectively. Fatty, surprisingly, is a tie on all boards.

My question is what is the winning strategy for each of the remaining other 4 celled animals namely Skinny, Elly and Knobby? Why is fatty a tie on all boards?

If there are some facts/results/theorems that go deeper into the game please feel free to share.

Best Answer

Jaap has already demonstrated why Fatty is a tie in his answer. Here are the winning strategies for the remaining animals.

Winning strategy for Elly on a $4\times 4$ board

As long as $X$ gets an orthogonal three-in-a-row in their first three moves, then they win, since such a three-in-a-row gives four threats, only three of which can be blocked by O's first thee moves. To claim a three-in-a-row in three moves, X need only claim a central square, then claim an adjacent central square such that the line containing these two X's avoids O's first move.

Winning strategy for Knobby on a $5\times 5$ board

X claims the center square on their first move, and then plays diagonally adjacent on their second move, such that their second X is as far as possible from O's first move. For their third move, X should play such that their first three moves form an L-tromino. There are two ways X can do this; no matter where O's second move is, one of these plays will give a double-threat, securing a win on move four.

Winning strategy for Skinny on $7\times 7$ board

X starts by claiming the center. Up to symmetry, O's response is one of the nine squares below: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&& \\\hline &&&&&& \\\hline &&&&&& \\\hline &&&X_1&&& \\\hline &&\color{gray}{O_1}&\color{gray}{O_1}&\;\;\;\;&\;\;\;\;&\;\;\; \\\hline &\color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&&& \\\hline \color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&&& \\\hline \end{array} $$ Below are winning strategies for seven of these responses. On turns two and three, X creates a situation like $\begin{array}{|c|c|c|c|c|}\hline \;\;&\mathsf{X}&\mathsf{X}&\;\;&\;\;\\\hline\end{array}$ or $\begin{array}{|c|c|c|c|c|}\hline \;\;&\mathsf{X}&\;\;&\mathsf{X}&\;\;\\\hline\end{array}$. O must respond in one of the empty squares, else X could create a three-in-a-row which is unobstructed on both ends on their subsequent move. On turn four, X creates two such threats; O cannot block both. $$ \begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&\color{gray}{O_3}& \\\hline &&&X_4&\color{gray}{X_5}&X_3& \\\hline &&&\color{gray}{X_5}&&\color{gray}{O_3}& \\\hline &&\color{gray}{O_2}&X_1&\color{gray}{O_2}&X_2&\color{gray}{O_2} \\\hline &&&&\;\;\;\;&\color{gray}{O_3}&\;\;\; \\\hline &\color{gray}{O_1}&&\color{gray}{O_1}&&& \\\hline \color{gray}{O_1}&\color{gray}{O_1}&&\color{gray}{O_1}&&& \\\hline \end{array}\qquad \begin{array}{|c|c|c|c|c|c|c|} \hline &&\color{gray}{O_3}&&&& \\\hline &&\color{gray}{O_3}&\color{gray}{X_5}&&& \\\hline &&X_3&X_4&\color{gray}{X_5}&& \\\hline &\color{gray}{O_2}&X_2&X_1&\color{gray}{O_2}&& \\\hline &&\color{gray}{O_3}&&&\;\;\;\;&\;\;\; \\\hline &&\color{gray}{O_1}&&&& \\\hline \;\;\;\;&&\color{gray}{O_1}&&&& \\\hline \end{array} $$ All that remains are when O responds orthogonally adjacent or diagonally adjacent to the center square. These lines of play were figured out by Daniel Mathias.

First suppose O responds adjacent to the center (WLOG, directly below). X then plays horizontally next to their first move, which forces O to play horizontally next to one of these X's (else, X can set up a three-in-a-row double-threat). There are two ways O can respond. So far, we are at $$ \begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&& \\\hline &&&&&& \\\hline &&&&&& \\\hline \;\;\;\;&\;\;\;\;&\color{gray}{O_2}&X_1&X_2&\color{gray}{O_2}&\;\;\;\; \\\hline &&&O_1&&& \\\hline &&&&&& \\\hline &&&&&& \\\hline \end{array} $$ For the remaining moves:

  • Place $X_3$ to create a three in a row with the first two moves. O must block.

  • Place $X_4$ just below $X_2$. O must respond just above $X_2$ or just below $X_4$.

  • Place $X_5$ to create a three-in-a-row with $X_2$ and $X_4$. O must block.

  • Place $X_6$ so that $X_2,X_3,X_5$ and $X_6$ are the vertices of a rectangle.

  • Place $X_7$ to create a three-in-a-row with an empty space on each side with either $X_6$ and $X_3$, or with $X_6$ and $X_5$. At least one will be possible, regardless of where O's sixth move was. This guarantees a win on the next move.

Finally, suppose O's second move is diagonally adjacent to the center. X should play adjacent to both this O and his first X, forcing O to play at either end of the pair of X's, as shown below. This is exactly like the diagram above for the previous line of play, just shifted one cell to the left! Therefore, the same strategy there works here. $$ \begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&& \\\hline &&&&&& \\\hline &&&&&& \\\hline \;\;\;\;&\color{gray}{O_2}&X_2&X_1&\color{gray}{O_2}&\;\;\;\;&\;\;\;\; \\\hline &&O_1&&&& \\\hline &&&&&& \\\hline &&&&&& \\\hline \end{array} $$