I saw the following image on Twitter and Reddit, an image suggesting an entire class of infinitary analogues of the game Connect-Four. What fun! Let’s figure it out!
I’m not sure to whom the image or the idea is due. Please comment if you have information. (See comments below for current information.)
The rules will naturally generalize those in Connect-Four. Namely, starting from an empty board, the players take turns placing their coins into the $\omega\times 4$ grid. When a coin is placed in a column, it falls down to occupy the lowest available cell. Let us assume for now that the game proceeds for $\omega$ many moves, whether or not the board becomes full, and the goal is to make a connected sequence in a 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 $\omega\times 6$ version of the game that is shown, and indeed in the $\omega\times n$ version for any finite $n$, I claim that neither player can force a win; both players have drawing strategies.
Theorem. In the game Connect-$\omega$ on a board of size $\omega\times n$, where $n$ is finite, neither player has a winning strategy; both players have drawing strategies.
Proof. For a concrete way to see this, observe that 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. This 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. $\Box$
Let me point out that on a board of size $\omega\times n$, where $n$ is odd, we can also make this conclusion by a strategy-stealing argument. Specifically, I argue first that the first player can have no winning strategy. Suppose $\sigma$ is a winning strategy for the first player on the $\omega\times n$ board, with $n$ odd, and let us describe a strategy for the second player. After the first move, the second player mentally ignores a finite left-initial segment of the playing board, which includes that first move and with a odd number of cells altogether in it (and hence an even number of empty cells remaining); the second player will now aim to win on the now-empty right-side of the board, by playing as though playing first in a new game, using strategy $\sigma$. If the first player should ever happen to play on the ignored left side of the board, then the second player can answer somewhere there (it doesn’t matter where). In this way, the second player plays with $\sigma$ as though he is the first player, and so $\sigma$ cannot be winning for the first player, since in this way the second player would win in this stolen manner.
Similarly, let us argue by strategy-stealing that the second player cannot have a winning strategy on the board $\omega\times n$ for odd finite $n$. Suppose that $\tau$ is a winning strategy for the second player on such a board. Let the first player always play at first in the left-most column. Because $n$ is odd, the second player will eventually have to play first in the second or later columns, leaving an even number of empty cells in the first column (perhaps zero). At this point, the first player can play as though he was the second player on the right-side board containing only that fresh move. If the opponent plays again to the left, then our player can also play in that region (since there were an even number of empty cells). Thus, the first player can steal the strategy $\tau$, and so it cannot be winning for the second player.
I am unsure about how to implement the strategy stealing arguments when $n$ is even. I shall give this more thought. In any case, the theorem for this case was already proved directly by the initial concrete argument, and in this sense we do not actually need the strategy stealing argument for this case.
Meanwhile, it is natural also to consider the $n\times\omega$ version of the game, which has only finitely many columns, each infinite. The players aim to get a sequence of $\omega$-many coins in a column. This is clearly impossible, as the opponent can prevent a win by always playing atop the most recent move. Thus:
Theorem. In the game Connect-$\omega$ on a board of size $n\times\omega$, where $n$ is finite, neither player has a winning strategy; both players have drawing strategies.
Perhaps the most natural variation of the game, however, occurs with a board of size $\omega\times\omega$. In this version, like the original Connect-Four, a player can win by either making a connected row of $\omega$ many coins, or a connected column or a connected diagonal of $\omega$ many coins. Note that we orient the $\omega$ size column upwards, so that there is no top cell, but rather, one plays by selecting a not-yet-filled column and then occupying the lowest available cell in that column.
Theorem. In the game Connect-$\omega$ on a board of size $\omega\times\omega$, neither player has a winning strategy. Both players have drawing strategies.
Proof. Consider the strategy-stealing arguments. If the first player has a winning strategy $\sigma$, then let us describe a strategy for the second player. After the first move, the second player will ignore finitely many columns at the left, including that first actual move, aiming to play on the empty right-side of the board as though the first player using stolen strategy $\sigma$ (but with colors swapped). This will work fine, as long as the first player also plays on that part of the board. Whenever the first player plays on the ignored left-most part, simply respond by playing atop. This prevents a win in that part of the part, and so the second player will win on the right-side by pretending to be first there. So there can be no such winning strategy $\sigma$ for the first player.
If the second player has a winning strategy $\tau$, then as before let the first player always play in the first column, until $\tau$ directs the second player to play in another column, which must eventually happen if $\tau$ is winning. At that moment, the first player can pretend to be second on the subboard omitting the first column. So $\tau$ cannot have been winning after all for the second player. $\Box$
In the analysis above, I was considering the game that proceeded in time $\omega$, with $\omega$ many moves. But such a play of the game may not actually have filled the board completely. So it is natural to consider a version of the game where the players continue to play transfinitely, if the board is not yet full.
So let us consider now the transfinite-play version of the game, where play proceeds transfinitely through the ordinals, until either the board is filled or one of the players has achieved the winning goal. Let us assume that the first player also plays first at limit stages, at $\omega$ and $\omega\cdot 2$ and $\omega^2$, and so on, if game play should happen to proceed for that long.
The concrete arguments that I gave above continue to work for the transfinite-play game on the boards of size $\omega\times n$ and $n\times\omega$.
Theorem. In the transfinite-play version of Connect-$\omega$ on boards of size $\omega\times n$ or $n\times\omega$, where $n$ is finite, neither player can have a winning strategy. Indeed, both players can force a draw while also filling the board in $\omega$ moves.
Proof. It is clear that on the $n\times\omega$ board, either player can force each column to have infinitely many coins of their color, and this fills the board, while also preventing a win for the opponent, as desired.
On the $\omega\times n$ board, consider a variation of the strategy I described above. I shall simply always play in the first available empty column, thereby placing my coin on the bottom row, until the opponent also plays in a fresh column. At that moment, I shall play atop his coin, thereby placing another coin in the second row; immediately after this, I also play subsequently in the left-most available column (so as to force the board to be filled). I then continue playing in the bottom row, until the opponent also does, which she must, and then I can add another coin to the second row and so on. By always playing the first-available second-row slot with all-empty second rows to the right, I can ensure that the opponent will eventually also make a second-row play (since otherwise I will have a winning condition on the second row), and at such a moment, I can also make a third-row play. By continuing in this way, I am able to place infinitely many coins on each row, while also forcing that the board becomes filled. $\Box$
Unfortunately, the transfinite-play game seems to break the strategy-stealing arguments, since the play is not symmetric for the players, as the first player plays first at limit stages.
Nevertheless, following some ideas of Timothy Gowers in the comments below, let me show that the second player has a drawing strategy.
Theorem. In the transfinite-play version of Connect-$\omega$ on a board of size $\omega\times\omega$, the second player has a drawing strategy.
Proof. We shall arrange that the second player will block all possible winning configurations for the first player, or to have column wins for each player. To block all row wins, the second player will arrange to occupy infinitely many cells in each row; to block all diagonal wins, the second player will aim to occupy infinitely many cells on each possible diagonal; and to block the column wins, the second player will aim either to have infinitely many cells on each column or to copy a winning column of the opponent on another column.
To achieve these things, we simply play as follows. Take the columns in successive groups of three. On the first column in each block of three, that is on the columns indexed $3m$, the second player will always answer a move by the first player on this column. In this way, the second player occupies every other cell on these columns—all at the same height. This will block all diagonal wins, because every diagonal winning configuration will need to go through such a cell.
On the remaining two columns in each group of three, columns $3m+1$ and $3m+2$, let the second player simply copy moves of the opponent on one of these columns by playing on the other. These moves will therefore be opposite colors, but at the same height. In this way, the second player ensures that he has infinitely many coins on each row, blocking the row wins. And also, this strategy ensures that in these two columns, at any limit stage, either neither player has achieved a winning configuration or both have.
Thus, we have produced a drawing strategy for the second player. $\Box$
Thus, there is no advantage to going first. What remains is to determine if the first player also has a drawing strategy, or whether the second player can actually force a win.
Gowers explains in the comments below also how to achieve such a copying mechanism to work on a diagonal, instead of just on a column.
I find it also fascinating to consider the natural generalizations of the game to larger ordinals. We may consider the game of Connect-$\alpha$ on a board of size $\kappa\times\lambda$, for any ordinals $\alpha,\kappa,\lambda$, with transfinite play, proceeding until the board is filled or the winning conditions are achieved. Clearly, there are some instances of this game where a player has a winning strategy, such as the original Connect-Four configuration, where the first player wins, and presumably many other instances.
Question. In which instances of Connect-$\alpha$ on a board of size $\kappa\times\lambda$ does one of the players have a winning strategy?
It seems to me that the groups-of-three-columns strategy described above generalizes to show that the second player has at least a drawing strategy in Connect-$\alpha$ on board $\kappa\times\lambda$, whenever $\alpha$ is infinite.
Stay tuned…
In the original 7 x 6 version, the starting player has a winning strategy. I don’t know of any infinite ordinals \kappa, \lambda for which one of the players has a winning strategy.
Nice article!
I’m glad you enjoyed it.
It would seem natural to suppose that the first player should still win for Connect-Four on a much larger board, even an infinite board; that is, where the winning goal is still just four-in-a-row. But I would need to think more about this. I think that the proof that the first player wins on the $7\times 6$ board is a finicky analysis. I don’t know of any abstract general argument.
Here’s an idea for the second player in the transfinite omega-by-omega game. It isn’t a full winning strategy, for reasons that I’ll make clear, but it is a strategy for getting a diagonal. The first player plays a point (n,1). Then the second player plays (n+1,1) and aims for the diagonal that goes up from that point. The strategy for doing so is as follows. If the first player ever places a piece down that allows the second player to fill a point in that diagonal, then the second player does so. Otherwise, the second player makes sure that everything is filled up to and including the diagonal that starts at (n+3,1) — that is, the one two below the target. That is easily done, and by the end of stage omega the result will be that all places will be filled up to that lower diagonal, and if ever there is a point above that diagonal, then the second player will occupy the position in that column in the target diagonal. Actually, let’s also add that the second player will make sure that all such columns are completely filled. Again, that’s easy to do.
We now get to stage omega+1. If there are any empty spaces, then the first player is forced to play one below the target diagonal, and the second player can then add the corresponding target point. So basically the second player can do the same strategy and by the end of it will have gained at least one more point.
So at each stage, the second player gets to place at least one more point in the target diagonal. The first player can spin this out up to an arbitrary countable ordinal (simply by bijecting that ordinal with the unfilled columns) but being forced to go first is a crippling disadvantage when it comes to trying to stop the second player adding points to the target diagonal.
The reason this isn’t a winning strategy is that the first player might make some other diagonal that’s lower than the target one, but actually I think with a small modification to the above strategy one can stop that. We just choose in each diagonal below the target one an infinite set of target points and apply a similar strategy to ensure that the second player will occupy all of them.
But now I’ve noticed a significant flaw with my proposed strategy above, which is that in order to get the target diagonal, the second player is forcing the first player to occupy the diagonal one below it. What’s interesting about that is that since the diagonal one below can be completed only at a limit ordinal, and since the second player will always occupy a point in the target diagonal when possible, it looks as though the two players will complete diagonals at the same limit ordinal.
This is a kind of draw that doesn’t exist when the thing you are trying to make is finite, so it’s an added dimension to the infinite game.
I think I’ve just proved that the second player has a strategy that stops the first player winning, assuming that getting diagonals at the same time counts as a draw. But I’d need to check the details to be sure.
Thanks very much for this. I had come to essentially the same idea while walking to college this morning. It seems very difficult to set up your diagonal in a way that doesn’t also allow the opponent to build a diagonal at the same time.
I think your final conclusion is not quite right, since it could be that the opponent has already won at an earlier stage, before you get set up to complete your diagonal. That is, couldn’t it be that before the penultimate points are played below the diagonal at which you are aimed, that your opponent has already won? (And yes, if both players succeed in building a row, column or diagonal, then it is a draw.)
It isn’t clear to me whether we should look upon going first at limits as an advantage or a disadvantage.
I would be very intrigued if it came out that one of the players could have a winning strategy.
Meanwhile, one way to imagine arguing against this would be to diagonalize against all possible rows, columns and diagonals. There are only countably many ways to win, and any of them can be spoiled by a single well-placed coin. The rows and columns can be each easily refuted in finitely many moves each. For the diagonals, one wants to try to refute a given diagonal, perhaps in the way you describe, but one cannot allow that the play proceeds transfinitely, for then perhaps there is a win on another lower diagonal. Perhaps one can try to kill all the diagonals in such a way that if one doesn’t get a chance to kill a given diagonal, then it doesn’t matter, because it means that play hadn’t proceeded far enough for it to need to be killed.
Let me try to flesh out what I was saying (with no guarantee of success). I want, as the second player, to stop you, as first player, from winning outright. So as above, after your first move I shall nominate a diagonal that I promise to occupy in its entirety.
That means you won’t get a full row, and it will be easy for me to stop you getting one of the first few columns, so it remains for me to ensure that you don’t get any diagonals that are lower than my target diagonal, apart from the one directly below.
To do this, I choose a fairly sparse set of points such that each of those lower diagonals contains at least one of those points, and there is only one point in each column. And I’ll make sure that each point from that set is at even height and is a lot lower than the target diagonal. Let’s call these blocking points.
I will now apply the following strategy. Every time you play in a column below a blocking point, I will immediately play directly above you. That guarantees that I will get all blocking points, unless I am forced at some point to play directly above myself, before having reached the blocking point. Let’s call a column safe if I’m allowed to play there. Then if all columns are unsafe, there must be a first moment when that happened, and that can’t be at a successor ordinal because then there is a safe column somewhere and that takes infinitely many moves to fill up. So it’s at a limit ordinal, which means that you have to make the next move at that danger moment for me.
So I think I can get all the blocking points.
Ah but that doesn’t quite work, since if you fill up all columns apart from two that contain two blocking points for which the parities of the distances from the target diagonal are different, then you will end up occupying a point in my target diagonal if I apply the strategy.
But I think I can at least stop you winning, by applying the same proof but to a set of points that blocks all rows, all columns and all diagonals. I think all I need is that all the blocking points in any column have even parity.
OK here’s a quick version of the argument. I nominate an infinite set of columns where you will be the first to play and where the play thereafter will alternate between us (because whenever you play there I will go straight on top). Assuming I succeed, and choose the columns sensibly, I can rule out all diagonals this way, as well as all rows of even height.
In fact, let me be a bit more concrete. My strategy is as follows. If you play in a column with x-coordinate zero mod 3, then I’ll play on top of you immediately afterwards. If you play in column with x-coordinate 2m+1, then the first time you do so I’ll play in the column 2m+2, and vice versa. Otherwise, whenever you play in one of those columns I’ll play on top immediately afterwards.
I claim that at the end of the game, all the 0-mod-3 columns will be filled you-me-you-me-you-me etc., and for each m, at least one of the 2m+1 and the 2m+2 columns will be filled me-you-me-you etc. (that one being the one you didn’t go in first), while the other will alternate either straight away or after starting you-you. Note that this stops you occupying any row, column or diagonal.
If I fail in that objective, there will have to be a first moment when I fail. It can’t be at a successor ordinal, since all I have to do is stick to that strategy. And at a limit ordinal your options are to play above one of my pieces, in which case I can happily continue, or to occupy an unoccupied column. If the unoccupied column is 0-mod-3 I’m happy, and if it’s 1 or 2, then the other must also be unoccupied (or I would have contributed to the first one) so again I’m happy.
Thanks very much for this. I want to digest it further, but one issue to address at the start is that to win with a row, you don’t need the whole row, but only a final segment—a connected $\omega$-length piece of it. So you have to pay attention to blocking the rows beneath your target diagonal.
But I think your blocking squares and mod 3 ideas are very good. Let me think more about it.
My comment was a bit of a stream of consciousness and I recommend ignoring everything up to “In fact I’ll be a bit more concrete.” From there I think what I offer, which doesn’t involve target diagonals, is a simple strategy for the second player to stop the first player obtaining any row (by which I mean final segment, but in fact not even more than three consecutive points I think), column or diagonal. At the moment I don’t see any way for the second player to win or for the first player to stop the second player winning, so the question is still interesting!
Yes, I think the argument is right, and I have written about it in the main post.
The strategy doesn’t seem, however, to prevent a column win for the first player, but rather ensures that any such winning configuration is duplicated for the second player, forcing the draw. If the first player always plays on one of the paired columns, and you copy on the other, then both will make the winning configuration.
Incidentally, I think you probably mean $3m+1$, $3m+2$, instead of $2m+1$, etc. I’m not sure if users can edit comments here, but if you are not able to edit, I think I can change this for you.
I am wondering whether we might be able to make a drawing strategy for the first player using a similar idea. My proposal is that player one will aim to complete the board by time $\omega^2$, which means he has $\omega$ many limits at which he must go first, and he will use these to ensure that the board becomes filled in some systematic manner, while on the rest of the moves trying to undertake a version of the copying strategy we described for the second player. At any limit before $\omega^2$, there will have been only finitely many extraneous limit moves, and so we might hope that they’ve been fairly harmless. And then the copying strategy will rule out row, column and diagonal wins for the opponent. I don’t quite see all the details, but perhaps something like this can work.
I am the person who posted this on reddit. However, I am not the person who made the image. One of my friends sent it to me a while back, but it said connect pi instead, so I just changed the symbol. I think I found the person who posted this originally on pinterest. https://pin.it/xcmg3fvhb6gzkj
Thanks very much for this information! I’m not on pinterest, but I’d like to contact that person about using this image. Is it alright with you that I have used your modified version?
The Pi version seems to be: https://www.pinterest.com/pin/380413499768691503.
It is perfectly fine that you used it. I actually think it’s really cool!
Thanks for the vote of confidence.
One key difference to the finite game is that a different sort of draw is possible. Each player may obtain a wining arrangement at the same limit ordinal time. Perhaps there is some pleasing, if not natural, ordering of winning arrangements that could serve as a tie breaker?
Hey Jeff! How nice to have a comment from you.
I agree about your remark. Since there are only countably many different winning “reasons”, one can impose a priority on them and use this to break ties. For example, we could say that it is better to start your row, column or diagonal closer to the origin, or if the same distance, then rows are better than columns are better than diagonals.
I think it would be nice to let the second player start a series of omega moves sometimes, to make the game more symmetric. I would write the move index in the Cantor normal form, and player 1 moves iff the sum of the coefficients is even.
Maybe the players can force draw already when it is sufficient to arrange k number of coins in a row, where k is finite? If the board is Z^2 without gravity and the winning configuration is a 2×2 square, there is an easy proof that both players can force a draw (arrange cells in pairs like bricks, if the first player plays X, the second player plays its pair). Similarly, if the winning configuration is a vertical or horizontal line of five. I think this is also the case for a vertical or horizontal or diagonal line for some k, but I do not remember the details. With gravity it could be similar.
I spent a bit of time thinking about this, and it seems to me that one probably can’t formulate a sensible notion of fairness that survives once the ordinals stop being describable. (In particular, the game can go on way beyond the point where Cantor normal form doesn’t exist any more.) But it would be interesting to know whether this intuition is correct.
I don’t have much to say about math that wasn’t already said but I will say I very much appreciate your choice in memes.
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.Filmplus