What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?

Question

Consider the game of infinite Hex, where two players Red and Blue alternately place their stones on the infinite hex grid, each aiming to create a winning configuration.

Red wins after infinite play, for the standard winning condition, if there is a connected $\newcommand\Z{\mathbb{Z}}\Z$-chain of red stones, which travels from lower left at infinity to upper right at infinity, moving ultimately from quadrant III to quadrant I, for any choice of center. Equivalently, there is a $\Z$-chain of red stones crossing any given horizontal line only finitely many times, crossing ultimately from below to above, and also crossing every vertical line only finitely many times, crossing ultimately from left to right.

Similarly, Blue wins if there is a connected $\Z$-chain of blue stones connecting the upper left at infinity to the lower right at infinity.

Further background information about the game is available in my preprint:

• Joel David Hamkins and Davide Leonessi, Infinite Hex is a draw, arxiv:2201.06475.

My question is about the complexity of the standard winning condition.

Question 1. What is the precise complexity of the winning condition of infinite Hex?

More specifically, what is the descriptive set-theoretic complexity of the set of (partial) colorings of the hex board that exhibit a win for Red? That is, considering plays of the game as producing a partial coloring of the hex-tile grid with Red/Blue, what is the complexity of the set of such colorings for which Red fulfills the winning condition?

Clearly, the winning condition has complexity $\Sigma^1_1$ at worst, since Red wins if and only if there is a winning Red $\Z$-chain, which amounts to a second-order existential quantifier to get the $\Z$-chain, and to assert that a given $\Z$-chain is winning for Red involves only number quantifiers, since one needs only to say that it forms a connected chain, that it is entirely Red, and that it fulfills the infinite convergence property from lower left to upper right. On its face, therefore, infinite Hex is an analytic game, one whose winning condition has complexity $\Sigma^1_1$. But is the game truly $\Sigma^1_1$? I find it likely that the complexity bound can be improved.

Question 2. Is infinite Hex a Borel game? That is, is the set of (partial) colorings of the hex board that are winning for Red a Borel set?

I conjecture that infinite Hex is a Borel game. To prove this, it would suffice to find an existential characterization for Red NOT to have won a given position. For example, perhaps Red fails to win if and only if there is a series of Blue-or-noncolored tiles forming larger and larger obstacles, which would prevent a Red win. For example, perhaps Blue has downward sloping lines connecting the positive y-axis to the positive x-axis for some choice of center, as in the trapezoidal figures of our paper, or perhaps Blue has stones infinitely far into quadrant I that are connected to stones in quadrants II and IV, for any choice of center. (Note that the question whether any two Blue stones are connected is an arithmetic property, requiring the quantification only over finite sequences and not infinite sequences.) If there were always such an existential reason for Red to lose, this would show that the non-winning plays were also $\Sigma^1_1$, making the Red wins $\Delta^1_1$ and hence Borel. This seems to be a promising approach, but I don't yet grasp a full account of the details here.

Meanwhile, the centrality of the complexity question is that ZFC proves that all Borel games are determined, and one might hope to use this, if the winning condition were Borel, to prove that either one of the players has a winning strategy in infinite Hex or both players have drawing strategies. In fact, we already know (the main initial result of our paper above) that both players have drawing strategies in infinite Hex, starting from an empty board. But we don't have this result yet for the infinite Hex games arising from arbitrary finite positions, even ones with a single extra stone, and we actually have no proof that such games are determined. But surely they are determined!

Question 3. Can we prove in ZFC that the infinite Hex game proceeding from any given Borel position is determined, in that either one of the players has a winning strategy or both players have drawing strategies?

The point is that the answer would be affirmative if the collection of colorings fulfilling a win for Red were Borel, since this would follow from Borel determinacy, which is provable in ZFC. Note that Borel determinacy is usually formulated for won/loss games, without draws, but infinite Hex admits drawn outcomes. But one can easily modify the Borel determinacy result for won/loss/draw games.

If infinite Hex is indeed Borel, what is the Borel complexity? It doesn't seem to be arithmetic, but perhaps a clever argument would show that it is. Perhaps one need only say that Red wins, just in case Blue has not placed stones exhibiting certain finitary connectivity properties with respect to choices of center origin.

Question 4. Is infinite Hex an arithmetic game?

Meanwhile, some of the alternative winning conditions mentioned in our paper are indeed arithmetic, such as the winning-on-finite-boards condition.

Answer 1

The complexity is arithmetic, and at most $\Sigma^0_7$. The proof is based on showing that my counterexample to PyRulez's proposed formula is essentially the only one.

Let $G$ be the set of tiles of the infinite hexagonal grid, and let $R \subset G$ be the red tiles. For a tile $t \in G$ and subset $X \subset G$, let $C(X,t) \subset X$ be the connected component of $t$ in $X$. Let the quarter-plane $Q_n \subset G$ be the set of tiles contained in $\{(x,y) : x \geq n, y \geq n\}$.

Let $X \subset G$ be a set and $b \in X$ a tile. We say $X$ and $b$ are winning, if there exists a one-way infinite path in $X$ that starts from $b$ and lies eventually in every $Q_n$. We say $X$ and $b$ are nice if for all $m$, there exists $c \in Q_m \cap C(X, b)$, such that for all $n$, there exists $d \in Q_n \cap C(X \cap Q_m, c)$. We say a tile $a \in R$ is very nice if for all $k$, there exists $b \in Q_k \cap C(R, a)$ such that $Q_k \cap C(R, a)$ and $b$ are nice.

Note that PyRylez's condition is equivalent to $R$ and some red tile $b$ being nice.

Theorem. A red tile $a \in R$ is very nice if and only if $R$ and $a$ are winning.

Proof. It's clear that if $R$ and $a$ are winning, then $a$ is very nice, because we can just choose $b$, $c$ and $d$ from the path. For the converse, say that a set $X \subset G$ reaches to the northeast if it intersects $Q_j$ for all $j$. We need a couple of auxiliary results.

Lemma 1. Suppose that $X \subset G$ and $b \in X$ are nice, and that for all $i$, the number of connected components of $Q_i \cap C(X, b)$ that reach to the northeast is finite. Then $X$ and $b$ are winning.

Proof. For each $i$, let $A_i$ be the set of connected components of $Q_i \cap C(X, b)$ that reach to the northeast. Because $X$ and $b$ are nice, for each $i$ the set $A_i$ must be nonempty.

We define a tree by taking $\bigcup_{i \geq i_0} A_i$ as vertices, where $i_0$ is such that $b \in P$ for some $P \in A_i$. For each $P \in A_{i+1}$ there is a unique $Q \in A_i$ with $P \subset Q$, and we add an edge from $P$ to $Q$ to the tree.

Now we have a finitely branching infinite tree, so by König's lemma it has an infinite branch $(P_i)_{i \geq i_0}$ with $P_i \in A_i$ for each $i$. If we choose a tile $b_i$ from each $P_i$ with $b_{i_0} = b$, we can connect each $b_i$ to $b_{i+1}$ within $Q_i \cap X$, which gives us a winning path. QED.

Lemma 2. Suppose that $X$ and $b$ are nice but not winning, and for some $p$, infinitely many connected components of $Q_p \cap C(X, b)$ reach to the northeast. Then an infinite subset of those components is pairwise separated by bi-infinite paths in $G \setminus (Q_p \cap C(X, b))$ that visit each tile a finite number of times and return infinitely often to the same horizontal or vertical line in both directions.

Proof. WLOG we assume that there are infinitely many connected components that reach to the northeast and contain a tile that intersects the vertical half-line $V = \{(p,y):y \geq p\}$. The intersections of the components with $V$ are ordered in the sense that if two tiles of the same component $P$ intersect $V$, then the tiles in between them either are in $P$ or are not in any northeast-reaching component. We denote the induced order on the components as $(P_i)_{i \geq 0}$, where $P_0$ is the southernmost one.

For each $P_i$, define a bi-infinite path $(t_{i,j})_{j \in \mathbb{Z}}$ of tiles on $G \setminus (Q_p \cap C(X, b))$ as follows. The tile $t_{i,0}$ is the southeast neighbor of the southernmost tile of $P_i$ that intersects $V$. For $j < 0$ we continue the path directly to the west. For $j > 0$ we follow the outer border of $P_i$.

The path $(t_{i,j})_j$ separates $P_i$ from each $P_{i'}$ with $i' < i$. It's clear that $(t_{i,j})_j$ returns to the same horizontal line infinitely often in the negative direction. If it didn't do so for the positive direction, following the inner border of $P_i$ would give us a path in $Q_p \cap C(X, b)$ that proves $X$ and $b$ to be winning, contrary to our assumption. QED.

Assume that a red tile $a$ is very nice, but $R$ and $a$ are not winning. Choose some $k$ and $b \in Q_k \cap C(R, a)$ such that $Q_k \cap C(R, a)$ and $b$ are nice. By Lemmas 1 and 2, there exists $p$ such that $X := Q_p \cap C(R, a)$ contains an infinite number of connected components that reach to the northeast, which are separated by the bi-infinite paths.

Let $b'$ be given by the very-niceness of $a$ for $p$, so that $X$ and $b'$ are nice. Then $b'$ lies in some strongly connected component $P$ of $X$ that reaches to the northeast. Now, $P$ is separated from another such component $Q$ by a bi-infinite path $(t_i)$ that returns to the same line $L$ infinitely often, such that $Q$ lies to the north or east of $P$. Then $X$ and $b'$ can't be nice. Namely, if we choose $m$ so that $Q_m$ does not intersect $L$, then each connected component of $Q_m \cap P$ is finite, because it's restricted by the path $(t_i)$. We have to pick $c$ from one of these components, and then for large enough $n$, the tile $d$ does not exist. This is a contradiction, so $R$ and $a$ must be winning. QED.

It's maybe worth noting that this proof is not specific to the hexagonal grid, but should work for any periodic tiling of the plane, at least after only minor modifications.

Answer 2

The complexity is arithmetical (it is within $\Sigma^0_5$)

EDIT: a counterexample was found in the comments

Red wins if there exists a tile that connects lower left to upper right (with "connects" as defined by the original question). Without loss of generality we will show that the proposition "a tile is connected to upper right" is arithmetical.

Theorem: A tile $t$ is connected to the upper right iff for every vertical or horizontal line there is a $M$ such that for all $N$, there is a tile $s$ with coordinates both exceeding $N$ and a path of red tiles from $t$ to $s$, such that all tiles touching the line are among the first $M$ tiles of the path.

($\implies$) We can connect $t$ to $s$ using a prefix of the infinite chain connecting $t$ to the upper right. We let $M$ be the index of the last tile in the infinite path that touches the line.

($\impliedby$) (EDIT: As per @JoelDavidHamkins's comment, I flubbed the quantifier order in this part. I haven't found a counterexample though, so I'm still trying to think if this can be fixed. 🤔) Let $f$ be a function mapping lines to the $M$ described by the hypothesis. Let $N$ be an infinite hyperinteger. By the transfer principle, there is a hyperpath of red hypertiles connecting $t$ to a hypertile $s$ with coordinates both exceeding $N$ such that for any vertical or horizontal hyperline $l$, the hyperpath only crosses it in the first $f(l)$ hypertiles. (Note that the last such hypercrossing goes towards the side containing $s$, of course.) We truncate this hyperpath to an infinite path. This path only contains standard tiles because each nonstandard hypertile is an infinite hyperinteger $D$ distance away from $t$, and thus can not occur within the first $D$ tiles of a path starting at $t$. This path connects $t$ to the upper right since $f(l)$ is an integer for any horizontal or vertical line $l$.

$\Box$