Theory of 1-2-2 Hex

Dear Hex community,

I would like to know whether there is a general theory for multi-move combinatorial games, specifically monotone connection games like 1-2-2 Hex. I apologize in advance if this is well known, but I have not been able to find any relevant papers.

If I understand this paper correctly, J. H. Conway's surreal numbers can be adapted for Hex by defining outcomes to be the connectivity of a region's boundary: On the combinatorial value of Hex positions (arxiv) However, multiple-move games allow a player to play in more than one component at once, so the very definitions of Left and Right options are unclear to me, if they work at all.

Therefore, I would like to share a simple, sufficient condition for a 1-2-2 Hex position to be winning, which generalizes to the n-move Shannon switching game, as well as some interesting consequences of my analysis of a lone 3rd row stone.

Consider a region with two marked Black cells. We call it "good" if and only if either:

1. there is an unbroken path of Black cells joining them; or

2. for every White intrusion into the region with k pieces (1<=k<=2), there is a Black response with no more than k pieces that results in a good position (with fewer empty cells).

Good regions guarantee a connection between the marked stones, and they can be composed (attached) to form new good regions, thanks to the k=1 case. Moreover, we can use them within other templates in the same way as in regular Hex. *1

I posted in Mason Mackaman's Hex discord a proof that goodness is equivalent to "joinability," meaning the positions that are winning when composed f(# empty cells) times upon themselves, where f is an effectively computable function. The proof can be adapted to the n-move Shannon switching game. *2

The theory's main significance is its ability to positively decide many large positions by composing small joinable regions. For instance, the following are minimal 2nd and 3rd row templates, a 3-stone internal template (essentially the 2nd row edge template), and an example of region composition: diagram (trmph)

Moreover, in 2-move Hex, goodness is equivalent to connectedness in composition in series with several 3-stone "bridges." *3 Therefore, perhaps a non-joinable template should not be considered weakly connected (indeed many such templates fail in conjunction with a single bridge), which, combined with the equivalence to joinability, in my humble opinion justifies my criterion as the simplest extension of Hex templates to 2-move Hex.

However, non-joinable templates are meaningful because they can operate in parallel, etc... The smallest example is that Black b1 is connected to b3 via b2, a2a3, or c1c2; intruding at b2 forces a 2-move response. *4

With insights from this theory, I conducted an analysis of connecting a 3rd row piece (Black a3) with essentially minimal space; specifically, there is no empty space to the left of the a1-a3-c1 triangle. diagram (trmph) Consider only the top Black stone for now. Some key lines are listed below. If there is additional space on the third row, the ladder can be played in even more ways; that is beyond my analysis capabilities.

b1 c2 1-0

b2 a2 b1b2 b3c2 1-0

c1 b2 b1 c2 ... (note b2 dominates b3)

c1 c2 ... (note c1 c2 b1 d1 1-0)

The incomplete lines optimally continue d1 d2 e1 e2 ... as a 2nd row ladder in Hex! Basically, White cannot afford to play 2 moves or Black connects easily; blocking near a3 is bad for the same reason.

In the full position with two debatable regions, the top 3rd row stone has more space while the bottom is escaped. White must force both ladders, and Black still wins since the bottom connects shortly so White can no longer use the k=1 clause to play the top ladder. However, I suspect there are even more tricks with just a3: the players might try to play the ladder quickly or slowly, which might matter in more complex situations when the ladder escape is nontrivial, or even use the area near the initial stone as an in-between move. *5

Thank you very much for reading my work. I believe my definition of weak connections might be helpful in practice because it can reduce the search space of good intrusions. Please let me know if this is all trivial, known, or wrong.

Warren Bei

Notes

*1 For instance, this justifies the b1 c2 intrusion to a3: we do not need to worry about c2, and may pretend it is part of the edge.

*2 Proof sketch for general case: suppose some t-stone intrusion requires a t+1-stone response to maintain goodness. Let White repeatedly find n-t+1 fresh components, playing those t cells in one component and just one of the t cells in the other n-t components (n = no. moves per turn). WLOG Black blocks the t-stone intrusion, which costs t+1 stones; then one of the n-t components will be left alone. Repeat until White has created a large supply of components with one intrusion already done. Then repeat this process on only those components, etc; basically Black's slight inefficiency introduced at each turn allows White to build potential.

*3 Proof: if a 2-stone intrusion leads to a non-good position, play it; else play the 1-stone intrusion and spend the other stone in a bridge. The opponent has to save the bridge, therefore only getting 1 stone left, which is not good. The number of bridges needed does not exceed half the number of blank cells.

*4 In this case, adding one bridge destroys the connection. I have not yet found a non-joinable template that takes two bridges to disconnect.

*5 Yes, I mean 1-2-2 Hex can be a race! I doubt a zwischenzug can be played near a3, since a2 prevents White 2-move intrusions like d1d2 after the ladder.