The Connect Infinity game

Question

Recently Joel David Hamkins posted an entry on the Connect Infinity game.
Connect-$\omega$ is Connect Four but played on an $\omega\times n$ grid ($n$ finite)! The above shows $n=6$. The difference is that Connect-$\omega$ proceeds in $\omega$-many moves and the goal is to make a connected sequence in any row, of $\omega$ many coins of your color (you don’t have to fill the whole row, but rather a connected infinite segment of it suffices). A draw occurs when neither or both players achieve their goals.

In the entry, there are proofs which I don't understand. Could someone explain them in detail?

Board size $\omega\times n$, $n$ finite: Neither player has a winning strategy; both players have drawing strategies.

Either player can ensure that there are infinitely many of their coins on the bottom row: they simply place a coin into some far-out empty column, which also blocks a win for the opponent on the bottom row. Next, observe that neither player can afford to follow the strategy of always answering those moves on top, since this would lead to a draw, with a mostly empty board. Thus, it must happen that infinitely often we are able to place a coin onto the second row. This blocks a win for the opponent on the second row. And so on. In this way, either players can achieve infinitely many of their coins on each row, thereby blocking any row as a win for their opponent. So both players have drawing strategies.

I can't see or visualize how IF either player follows the strategy of always answering those moves on top, it would lead to a draw with a mostly empty board. How exactly would this play out?

And why must it happen infinitely often that either player is able to place a coin on the second row, and how does this imply that either players can place infinite many of their coins on each row above the second row?

EDIT: Please see user326210's answer and my summary.

Answer 1

The proof on that page has sort of loose reasoning, but the result is correct. The following theorem establishes the result more precisely. In particular, in point (2), I clarify the answers to the bolded questions.

Theorem. You can force a draw.

We'll need the following results:

1. You can block a win in the bottom row: Note that you can always place an isolated piece in the bottom row, far to the right of any piece played so far. Because you can do this infinitely often, and your opponent cannot stop you, you can block a win in the bottom row.

2. You can block a win in the second row (or force a draw anyways): When it's your turn, if you don't have any isolated pieces, place an isolated piece in the bottom row as before. If you do have an isolated piece, stack a second piece on top of it. If you create infinitely many stacks of two in this way, you prevent a win in the second row.

   Your opponent may try to block you, of course, by stacking their own piece on top of your isolated pieces. But your pieces are all isolated, and responding to your isolated piece creates an isolated tower, yet your opponent needs to place infinitely many non-isolated pieces in order to create a contiguous row and win. Thus, your opponent can either commit to blocking all (but finitely many) of your two-towers, which means their own pieces will be isolated on top of your pieces and hence no one will win, or else place infinitely many pieces somewhere else, allowing you to create infinitely many two-towers to block a win in row two. It follows that you can always block a win in row two. You either build infinitely many two-towers, or your opponent spends every turn blocking you and no one wins.

3. You can block a win in any fixed higher row $k>2$. The strategy for such a higher row $k>2$ is slightly different—in order to build a tower of height $k>2$, your opponent needs your cooperation. To block a win in row $k$, you will simply refuse to cooperate, and block your opponent if they try to build a tower themselves.

   In particular, choose an infinite subset $T\subseteq \mathbb{N}$ whose complement is also infinite. You will generally refuse to place a piece in any column in $T$. (You can choose to avoid columns in $T$ because the complement of $T$ is infinite.) Thus the only way for your opponent to build a tower of height $k$ in $T$ is to build it exclusively using their own pieces. And if your opponent ever builds a tower of height $k-1$ in a column in $T$, you will make an exception and stack your piece on top of it. Your opponent cannot stop you from acting this way in all of your chosen columns, and therefore you can interrupt row $k$ infinitely many times, preventing a win in row $k$.

   For every column in $T$, either your opponent abandons that column (so the cell in row $k$ is blocked because it is empty), or your opponent builds a $k-1$ tower and you stack your piece on top (so the cell in row $k$ is blocked because you've filled it.)

This leads to the following global strategy:

4. You can force a draw. If there are $n$ rows in the board, choose infinite, distinct subsets[*] $S$ and $T_3, \ldots, T_n$ of $\mathbb{N}$. When it is your turn, check to see whether your opponent's previous move belongs to a particular $T_m$ ($m\geq 3$). If so, check whether your opponent has just built a tower of height $m-1$ and if so, stack a piece there, blocking the tower's completion. Otherwise, check whether you have an isolated piece. If you do, stack a second piece on top of it. If you don't, find an isolated column in $S$ far to the right of any piece placed so far by either player, and put an isolated piece there.

   By the preceding results, this strategy blocks each row infinitely often, and your opponent cannot interfere with any part of the process (except to block infinitely many two-towers, which results in a draw anyways.) Hence you can force a draw.

   An important aside: note that because your opponents' $k>2$ height towers take more than one turn to build, you can block them while still having time to place more isolated pieces (unlike with $k=2$ as we showed).

   [*] For a concrete example of such subsets, let $p_0, p_1,p_2,\ldots,$ denote the prime numbers. Let $S$ be the set of all powers of $p_0=2$. Let $T_3,\ldots, T_n$ be the set of all powers of the next primes. Then these are all infinite, disjoint subsets of $\mathbb{N}$.

Answer 2

This is a summary of user326210's earlier strategy. Nonempty columns are called towers and if a tower has $k$ coins, we say it has height $k$ and call it a $k$-tower. Your towers in particular are interpreted as walls. Player 1 has a drawing strategy, called Isolated Towers:

1. Always be on the right: On your first move, play anywhere. On your subsequent moves, if the rightmost tower (rmTow) does not consist of only your coins, place a coin in a column to the right and isolated to rmTow. Otherwise place a coin in rmTow.

This blocks a win on the bottom two rows:

• Your opponent cannot win on the bottom row as you block them on your moves. (Scenario 1)
• Your opponent cannot win on the 2nd row: If your opponent repeatedly places on top of your $1$-towers, they cannot form a $2$-sequence of 2nd row coins as your towers (and hence theirs) are isolated. (Scenario 2) If your opponent does not place on top of your $1$-tower, you block the 2nd row on your next move, forming a $2$-wall. (Scenario 3)

X=You, O=Opponent, _ represents a gap of 1 column for simplicity

1)               2)    O O O...    3)  O X
  XO_XO_XO... OR   X_O_X_X_X... OR   X_O_X

2. If your opponent tries to win on a row $k\ge3$, then they must place on top of your $k-1$-wall (placing on their tower is useless as you can block them as in Scenario 3).

The scenario is now (for k=3)

3)    O3O O...
    O X2X X...
  X_O_X1X_X...
       a b

But note that it costs you $k-1\ge2$ moves to build an incomplete $3$-wall, and your opponent only 1 move to complete it in their favor. They can then spend their surplus moves filling the gaps (columns a,b,...). In the scenario for $k=3$, in column a, your opponent would have filled 1 and 2 with O. After a long enough game, your opponent will fill an infinite number of gaps and form a $\omega$-sequence on the $k$th row.

But you can include in your strategy the following: "If your opponent tries to win on the $k$th row and has built a $k-1$-tower in between isolated towers, place a coin on top of it". So in the scenario for $k=3$, your next move would place a coin in column a, which would fill 3 and block any $2$-sequences on the $k$th row.

So your opponent cannot win on rows $k\ge3$, and hence on all rows. And this strategy can be played by your opponent, so both players have drawing strategies. I believe this also works for an $\omega\times\omega$ board.