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'$:
- 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:
- 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.)
- 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.
- 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:
$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:
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.
