24
$\begingroup$

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.

Infinite Hex

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.

Winning red path

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.

$\endgroup$
11
  • $\begingroup$ What if we just try to embed a tree $T\subseteq\omega^{<\omega}$ into the hex plane directly? This is a bit messy to do (in order to accommodate infinite branching, everything has to space out a lot) but I don't see a real obstacle to doing it. If this works, this gives $\Sigma^1_1$-completeness immediately. $\endgroup$ Nov 30, 2022 at 2:10
  • 1
    $\begingroup$ Ah, I see, it's much trickier than I thought. $\endgroup$ Nov 30, 2022 at 2:31
  • 1
    $\begingroup$ The way it works is that Red wins the finite rhombus boards, but with different chains depending on the center. No one chain fulfills the infinite winning condition. $\endgroup$ Nov 30, 2022 at 4:05
  • 2
    $\begingroup$ If someone could help me understand the close/down votes, I'd be grateful. Is the question unsuitable in some way? $\endgroup$ Dec 1, 2022 at 14:20
  • 4
    $\begingroup$ FWIW I think this is in the top 3 of questions this year, and the downvote and close vote baffle me. $\endgroup$
    – Ville Salo
    Dec 2, 2022 at 7:32

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is fantastic! I need some time to digest it fully, but your basic idea seems very sound. $\endgroup$ Jul 10, 2023 at 21:34
5
$\begingroup$

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$

$\endgroup$
15
  • 1
    $\begingroup$ I'm a little confused about your argument. In the theorem statement, you say that s and the path from t to s can depend on the lines, but in the converse direction of the proof, you seem to assume that s works for all lines. I guess you want to use a single pair of hyperlines that are further out than any standard line, and then argue that this also works for standard lines. But the problem then would be that the f(l) you get might itself be nonstandard, and so the truncated path might not go to infinty on the standard board. $\endgroup$ Jul 6, 2023 at 18:57
  • 1
    $\begingroup$ I looked at our paper again, and in the source file we proposed a candidate criterion: there is a Red stone such that for every choice of center it is connected to stones in the corresponding quadrants I and III, which are themselves connected to stones arbitrarily far out to infinity by finite paths that remain within the quadrant. I think this is equivalent to your characterization (so we did have the $\exists M\forall N$ idea). We had removed this comment, but I can't remember now whether that was because we had a counterexample or because we lacked proof. $\endgroup$ Jul 6, 2023 at 19:35
  • 3
    $\begingroup$ The direction ($\Longleftarrow$) is false, and I'll give a counterexample. Place a red tile $t$ somewhere, and place an infinite path of red tiles going directly to the north, starting from $t$. From this path, place an infinite number of finite branches $b$ directly to the east, so that for every choice of origin, at least one of them has an endpoint $s_b$ in quadrant I. From each $s_b$ continue the branch to the east and occasionally make a "detour" far north, east, and back south to the same horizontal line. The branches make these detours in unison to avoid collision. $\endgroup$ Jul 7, 2023 at 6:34
  • 1
    $\begingroup$ I drew a picture of Ilkka's counterexample here: twitter.com/JDHamkins/status/1677225988034265090. Very nice! This is similar to our double comb, as Davide mentioned, but the extra wiggles make it a counterexample to the PyRulez proposal. $\endgroup$ Jul 7, 2023 at 8:02
  • 3
    $\begingroup$ @JoelDavidHamkins I believe I can prove that my counterexample is in some sense the only one (all counterexamples must have a similar structure), and using this, that the complexity is at most $\Sigma^0_7$. It will take me some time to write the proof, though. $\endgroup$ Jul 8, 2023 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.