5
$\begingroup$

It is known that determining who wins Hex from an arbitrary position is PSPACE-vollständig but of course a strategy stealing argument guarantees that the first player wins on the empty board or, more generally, from any symmetric position.
The winning strategy, however, is not known at all.

How hard is it to find a winning move in Hex starting from a symmetric position?

It is known that determining who won a finished game is PPAD-complete on an exponentially large board.
Could finding a winning move be also PPAD-complete?
Has this problem been studied before for any notion of "symmetric"?

$\endgroup$
3
  • 2
    $\begingroup$ I'm pretty sure this is open, my intuition would be PSPACE-complete. This paper shows that the corresponding problem is PSPACE-complete for a more general class of problems that includes finding a winning move in Hex from a symmetric starting position: arxiv.org/pdf/1911.06907.pdf $\endgroup$
    – GMB
    Aug 28, 2022 at 16:57
  • 2
    $\begingroup$ Hey, I remember this result, we've even covered it on our reading seminar! It is indeed strongly related, yet I'm not convinced that symmetric Hex will be also PSPACE-complete, at least I don't think that the reductions in that paper would work so easily for it. $\endgroup$
    – domotorp
    Aug 28, 2022 at 19:25
  • 1
    $\begingroup$ Ah, neat! I definitely agree that a major new idea in the reduction would be needed to show PSPACE-completeness for symmetric hex. In any case, it's a nice question, I'll be very interested if you find an answer. $\endgroup$
    – GMB
    Aug 28, 2022 at 20:09

1 Answer 1

3
$\begingroup$

Finding a winning move in symmetric positions in Hex is PSPACE-complete

First, let's define our problem, and call it SYMHEXMOVE:
Take as an input: a symmetric Hex position
Output: any move which is winning for Player 1 (the player who moves next).

Here is a proof that it's PSPACE-hard. It's by reduction from the problem of deciding the winner in a (non-symmetric) Hex position. It's essentially an encoding of the reduction from the paper "Strategy-Stealing is Non-Constructive" into a symmetric Hex position. (The paper was mentioned in the comments by author @gmb, and can be found at https://arxiv.org/pdf/1911.06907.pdf)

Here's the problem we'll reduce, DECISIONHEX:
Take as an input: a Hex position
Output: whether Player 1 has a winning strategy or not.

DECISIONHEX is known to be PSPACE-hard.

I'll show how to take any instance of DECISIONHEX (i.e. an arbitrary Hex position $H$) and turn it into an instance of SYMHEXMOVE (i.e. a symmetric Hex position $H'$). Then, by solving the SYMHEXMOVE instance, we can answer the original DECISIONHEX instance.

We'll build $H'$ from the original DECISIONHEX instance $H$. The following illustration is a planar graph representation of $H'$:

enter image description here

  • We paste $H$ into $H'$ twice, side-by-side, represented as the nodes $G1$ in the illustration. Since $H'$ is symmetric, we also paste two inverted* $H$s into $H'$ on the other side of the line of symmetry, represented as the nodes $G2$.
    • If $H$ is winning for Player 1, then $G1$ is a win for Red when playing first, and $G2$ is a win for Blue when playing first.
    • If $H$ is winning for Player 2, then $G1$ is a win for Blue regardless of who goes first, and $G2$ is a win for red regardless of who goes first.
  • The yellow vertices $A$ and $B$ are empty tiles.
  • Colored edges represent a chain of filled tiles of that color.

*An inverted $H$ is $H$ but flipped across the line of symmetry, and where all blue pieces are turned red and vice-versa.

If a player can form a path of their color in the graph (both edges and vertices), then they win. If the player plays on $A$ or $B$, they color the vertex with their color. If a player wins (forms an unbroken chain between their sides) in a game $G$, they color the corresponding vertex with their color.

Red wins if they color A+B, A+one G1, or B+both G2s.
Blue wins if they color A+B, A+one G2, or B+both G1s.

This is the same as in "Strategy-Stealing is Non-Constructive", and the rest of the proof should be the same.

Red is first to play in $H'$. The following are equivalent:

  • Player 2 wins in $H$.
  • B is the only winning first move for Red in $H'$.

Proof of equivalence:

  1. When Player 2 wins in $H$, then B is a winning first move for Red:
    • Red plays B. Blue is forced to play A. Then, Red wins if they win both G2s, and Blue wins otherwise. From the argument in "Strategy-Stealing is Non-Constructive", Red can win both by executing the winning strategy for Player 2 in $H$ each turn, on whichever board Blue's last move was. (If Blue's last move was elsewhere, Red can play arbitrarily.)
  2. When Player 2 wins in $H$, then there is no other winning first move for Red.
    • Red plays X (something other than B), then Blue can play B. If X was not A, then Red must play A. Otherwise, Red gets to choose where to play next. Regardless, Red wins if they can win either of the $G1$s, and Blue wins otherwise. However, Blue can win both of the $G1$s, even when Red has the next move, by executing the winning $H$ strategy each turn on whichever board Red plays.
  3. When Player 1 wins in $H$, then B is a losing first move for Red.
    • Red plays B, and Blue is forced to play A. Then Red wins iff they win both $G2$s. Say Red plays in the upper $G2$. Then, Blue can ignore the upper $G2$ and play only in the lower $G2$, executing the winning $H$ strategy.

Thus, if we had an algorithm that could answer SYMHEXMOVE, we could run it on $H'$, and we could decide DECISIONHEX for $H$. (If the algorithm returns B, then Player 1 does not win $H$, otherwise Player 1 does win $H$.) So SYMHEXMOVE is PSPACE-hard.

Final step

The last step is to show that we can actually encode this planar graph into an actual hex position $H'$. This is pretty straightforward, since the graph is planar and each vertex has degree $\leq 6$.

If we define a symmetric Hex position as one for which the board is the same after flipping, and then inverting colors, then we can construct $H'$ like this:

enter image description here

$H'$ is unchanged after flipping across the long diagonal and then inverting colors. This, of course, also satisfies the more general definition of symmetry from "Strategy-Stealing is Non-Constructive": the players' sets of winning tiles are isomorphic to each other.

Also, the size of $H'$ is polynomial in the size of $H$.

(Edit) More specific classes of symmetric positions

We showed that the problem of finding a winning move for any symmetric Hex position is PSPACE-complete. We defined symmetric to be any position for which the strategy-stealing argument applies.

However, this does not preclude the possibility of an efficient algorithm for finding a winning move in specific classes of symmetric games.

The construction shown above is one where the board is symmetric over the long diagonal, so we already know it's still PSPACE-hard to find a winning move even if we restrict to that class.

What about when the board is symmetric over the short diagonal? Or, even more specifically, when the board is symmetric over both the short and the long diagonal? Perhaps if we restrict to such a setting, we could find an efficient algorithm for determining winning moves.

We may believe that if we keep restricting the class of positions further and further, we will eventually find some in which there exist efficient algorithms. For example, if we restrict to the class of completely empty odd-sized boards, we may conjecture that there is a constant-time algorithm (play in the center).

For Hex positions that are symmetric over both diagonals, I think I've proven that it is still PSPACE-hard to find a winning move:

My construction is more complicated than the one earlier, and actually uses the earlier one as a gadget. Here's a crazy-looking diagram that represents it:

enter image description here

Some intuitions for this construction:

As you can see, it has two copies of the earlier diagram $H'$ in it. We can kind of model each $H'$ as a single node that can be claimed by whichever player plays there first.

Then, playing any $H'$ or $D$ forces the next 3 moves, by forcing both players to claim alternating $H'$s and $D$s, so that one player owns both $H'$s and one player owns both $D$s.

If the original game $H$ was a win for player 1, then in order to claim an $H'$, players can play its $A$. In that case, the player with the $H'$s can win by connecting their $A$s to each other by using the $C$s, which form a bridge between the $A$s. Thus, when p1 wins $H$, claiming both $H'$s by playing $A$ is a winning strategy.

If the original game $H$ was a win for player 2, then in order to claim an $H'$, players can play its $B$. In that case, the $B$s and $C$s form a 2x2 game of Hex, in which Blue seeks to connect the top to bottom, and Red seeks to connect the left to right. The player with the next move can always accomplish their goal. Thus, when p2 wins $H$, claiming both $H'$s by playing $B$ is a winning strategy.

I'll try to edit this post with a more complete proof in a bit.

Even more specific?

However, you may note that this construction is on a board of even length. Then, one may wonder, can you prove that it's PSPACE-hard to find a winning move on an odd-sized board with both axes of symmetry? Or is there in fact an efficient algorithm? (Is playing in the center always winning?) I wasn't able to get this construction to work with an odd-sized board, so I'm not sure what the answer is.

Bodwin, Greg; Grossman, Ofer, Strategy-stealing is non-constructive, ZBL07650369.

$\endgroup$
8
  • $\begingroup$ Very nice! So either A or B is the winning move, and which depends on who wins the original game. Do you think that something similar could also work for a centrally symmetric board? $\endgroup$
    – domotorp
    Jun 30, 2023 at 4:15
  • $\begingroup$ A centrally symmetric board as in one that's symmetric across the long diagonal and across the short diagonal? The answer might be yes -- perhaps by building the same mechanism across the top two quadrants and by using some clever construction to render the bottom two quadrants moot? $\endgroup$
    – Kevin Wang
    Jun 30, 2023 at 15:34
  • $\begingroup$ For example, make a Hex board with odd side length. Then A is the middle tile. Fill the short diagonal with blue on top and red on bottom. Note that this makes the entire left and bottom quadrants irrelevant. Then, place $H'$ as shown above, on the long diagonal between the top and right quadrants. $\endgroup$
    – Kevin Wang
    Jun 30, 2023 at 21:31
  • 1
    $\begingroup$ @domotorp So, I think there are two ways to define "centrally symmetric". One is the way you propose, but it's not a good definition because it's not actually symmetric in the game theory sense. (For example, in a 3x3, a position in which Red has already won by picking the 3 hexes on the left could be symmetric by that definition, if Blue picks the 3 hexes on the right.) $\endgroup$
    – Kevin Wang
    Jul 1, 2023 at 18:43
  • 1
    $\begingroup$ The better definition is that the board is symmetric across two axes: whenever a hex is blue, its reflection across the long diagonal is red, and its reflection across the short diagonal is red, and its reflection across the center is also blue. This is the definition that I thought I had a construction for in the earlier comments, but I was actually wrong there -- my construction involved placing stones on a diagonal, but that violates symmetry (since its reflection across that diagonal is itself) and indeed if that were allowed then the game is not necessarily symmetric. $\endgroup$
    – Kevin Wang
    Jul 1, 2023 at 18:47

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.