Squic Squac Squo

Question

Two players take turns writing an X (first player) or an O (second player) in a 9 by 9 grid of cells.

A player wins if they manage to occupy four cells which form the vertices of a square of any size with horizontal and vertical sides. If this doesn't happen before the board is filled, then O wins.

Whom does this game favor?

Answer 1

My answer is that

X can force a win on his 8th move.

Proof outline:

By his 3rd move, X can put an L-shape on the board (three quarters of a square). From this point on, O is no longer free to move but forced to try and block X completing a square. Assuming O is trying to block X from winning, X's 4th move extends the L to a T-shape, which on move 5 he then either expands to a +-shape (to win on his 6th move) or to a new L-shape of double size (based on the T-shape's crossbar). If he doubles the scale, moves 6 and 7 again respectively make up a T-shape and a +-shape, after which he wins.

So, only O's first two moves are free for him to determine. The first move determines the initial scale of the L/T/+. The second move determines the orientation of the L- and T-shape or whether X has to double the scale on move 5. X moves in such a way that O never gets an L-shape of his own, except on his last move, just before X wins.

Depending on O's first move, X will try to either build a 2-by-2 or a 3-by-3 square. Doubling scale thus results in either a 3-by-3 or a 5-by-5 square, potentially making use of the full size of the board.

I find it hard to make this really rigorous without constructing a full decision tree, but here are some worked examples that I believe to cover all possibilities:

X starts in the centre (marked as 1 below). His next move (2) depends on whether O puts his first move (a) inside the 3-by-3 centre square (depicted on the left) or anywhere else on the board (depicted on the right). The situation after X's 2nd move is then one of the following (up to mirroring and rotation):

             .........              |              aaaaa....
             .........              |              .aaaa....
             .........              |              ..aaa....
             ...aa....              |              .........
             ....1....              |              ....1....
             .........              |              ....2....
             ....2....              |              .........
             .........              |              .........
             .........              |              .........

Player O can now follow one of three strategies, roughly:
1. Try to block the +-shape that X is trying to form: X doubles scale on his 4th move and wins on his 8th move.
2. Prevent X from making cell 2 the centre of his +-shape: X instead centres it around 1 and wins on his 6th move.
3. Anything else: X builds a +-shape centred around cell 2 and wins on his 6th move.

I have tried to depict what each of these looks like in the six figures below (extended from the two figures above). Note that I have indicated some of O's possible moves with b but symmetric possibilities exist. For example, in the leftmost figure, O can pick the spot marked 3 and then X will simply pick the cell marked b on the same row.

 f...6...g   .........   .........  |  aaaaa....   aaaaa....   aaaaa....
 .........   .........   .........  |  .aaaa....   .aaaa....   .aaaa....
 ..b...b..   ..e.5.6..   ....b....  |  ..aaa....   ..aaa....   ..aaa....
 ...aa....   ...aa....   ...aa....  |  ..8.4de..   ...e4d...   ....b....
 5...1.c.7   ..4.1.3..   ..6.1.c..  |  ...b13...   ...513...   ...61c...
 .........   .........   .........  |  ..7b2c5..   ...62c...   ...523...
 ..b.2.3..   ..d.2.c..   ..5.2.3..  |  .....d...   ....b....   ...e4d...
 .........   .........   .........  |  ..g.6.f..   .........   .........
 e...4.d.8   ....b....   ..e.4.d..  |  .........   .........   .........

The figures feel a little clumsy and not very elegant. If I come up with a way to make the argument more insightful, I will edit.