16
$\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$
10
  • $\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
  • 1
    $\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
  • 2
    $\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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy