Open problems
Contents
[hide]Currently open problems
- Are there cells other than a1 and b1 which are theoretically losing first moves?
- Is it true that for every cell (defined in terms of direction and distance from an acute corner) there is an n such that for any Board of size at least n that cell is a losing opening move?
- Conversely, is it true that, for example, c3 is a winning first move on every Hex board of size at least 5?
- Is the center hex on every Hex board of odd size a winning opening move?
- On boards of all sizes, is every opening move on the short diagonal winning?
- Is the following true? Assume one player is in a winning position (will win with optimal play) and the opponent plays in a hex X. Let the set A consist of all empty hexes that are members of any path between opponents edges that uses the stone at X. If A is non-empty, A contains a winning move. Otherwise any move is winning, even passing the turn. (This problem was posed by Jory in the Little Golem forum.)
- The generalization of the above statement to monotone set-coloring games is false, as shown in section 3 below.
Formerly open problems
Sixth row template problem
Does there exist an edge template which guarantees a secure connection for a piece on the sixth row?
Answer: Yes, edge template VI1a is such a template.
Triangle template problem
Are the templates below valid in their generalization to larger sizes? (This problem was posed by Jory in the Little Golem forum.)
Answer: No. The first one in the sequence that is not connected is the one of height 8.
In fact, using a variant of Tom's move, it is easy to see that even the following triangle, which has more red stones, is not an edge template:
To see why, imagine that the right edge is a blue edge and that all cells outside the carrier are occupied by Blue. Note that Blue gets a 2nd-and-4th row parallel ladder. Blue wins by playing the tall variant of Tom's move:
There is in fact a template of height 8 continuing the above sequence, but it requires slightly more space:
The corresponding template of height 9 requires this much space:
Seventh row template problem
Does there exist an edge template which guarantees a secure connection for a piece on the seventh row?
Answer: Yes. See Seventh row edge templates.
Failure for maker-breaker games
This section contains two counterexamples to a generalization of the following problem.
- Is the following true? Assume one player is in a winning position (will win with optimal play) and the opponent plays in a hex X. Let the set A consist of all empty hexes that are members of any path between opponents edges that uses the stone at X. If A is non-empty, A contains a winning move. Otherwise any move is winning, even passing the turn.
The generalization is to maker-breaker games. In these games, the players alternatively color a cell. Some subsets of the cells are designated as winning sets. One player is called the Maker and the other the Breaker. The Maker's goal is to color all of the cells in a winning set, and the Breaker's goal is to prevent this. Hex is a maker-breaker game, where the winning sets are exactly the paths connecting Maker's edges.
I give two examples. The first is simple and highly-symmetric. The second goes 3-of-3: There are exactly 3 legal moves outside the set, and all 3 of them win.
simple and highly-symmetric:
Take a hexagonal bipyramid, and give each equatorial edge an arrow pointing to a pole, such that the directions of the arrows alternate. Consider the maker-breaker game on the vertices of the resulting object, where the winning sets are the vertices of faces such that the equatorial edge's arrow points to the face's polar vertex.
Breaker is in a winning position: No matter what Maker's first move is, Breaker's first move is a pole. (If Maker's was not a pole, then there is symmetry between the poles until Breaker chooses one.) If neither of Maker's first two moves was a pole, then Breaker's second move is the other pole, winning for Breaker. Otherwise, Breaker pretends Maker's pole move was Maker's first move, and wins by pairing using the equatorial edges whose arrows point to the pole Maker played.
Now, assume Maker plays a pole X. The analogue to the set A, is the set of vertices that are members of any minimal winning set which uses the vertex X. These are exactly the equatorial vertices, so in particular this set is non-empty.
However, if Breaker responds on the equator, then Breaker loses: Let Y be where Breaker just played. Maker responds on the equator, either opposite of Y, or the cell 120 degrees from Y whose immediate threat is adjacent to - rather than opposite from - Y. Breaker must defend against that threat, after which Maker plays the other equatorial vertex adjacent to where Maker just played. Lastly, Maker wins by playing either the pole Maker didn't already play, or continuing in the same direction on the equator.
going three-of-three:
This one is a maker-breaker game whose underlying set is {0,1L,1R,2L,2R,3L,3R,4}. There are exactly 6 minimal winning sets, and they are {0,1L,2L},{2L,3L,3R},{2L,3L,4} and the three formed by interchanging L with R.
Breaker is in a winning position: By symmetry, assume Maker does not play a R element. 0 and 2L each switch-dominate 1L, so this leaves 0,2L,3L,4 as candidates for Maker's first move. If Maker's first move is 3L or 4, then Breaker can play 2L and win with the pairing {0,1R},{2R,3R}. If Maker's first move is 2L or 0, then Breaker wins by playing any of 3L,3R,4 and using the pairs {0,1L} and {1R,2R} and whichever of {3L,3R,4} Breaker hasn't yet played.
Now, assume Maker plays 0. The analogue to the set A, is the set of vertices that are members of any minimal winning set which uses the element 0. This is exactly {1L,1R,2L,2R}.
If Breaker responds in {1L,1R,2L,2R}, then Breaker loses: By symmetry, assume Breaker plays 1L or 2L. Maker responds at 2R, threatening to win immediately with 1R. Breaker must defend against that threat, after which Maker plays 3R, and wins with 3L or 4.
(As noted in the "Breaker is in a winning position" part here, all three of Breaker's moves outside of the analogue-of-A win for Breaker.)
