Hello, my name is Jeremiah Hockaday. I am pursuing my Masters
degree at Dalhousie University under the guidance of
Peter Selinger and Svenja Huntemann. Together we have developed a
combinatorial game theory for Reverse Hex, which allows us to
compare game values, achieve canonical forms, and enumerate positions.
Imagine that you and your friend have been kidnapped by the nefarious
Dr. Nim. He has strapped the two of you to electric chairs, and he
intends to let whoever survives his deadly game go free.
The board pictured is the intersection of two open circuits,
one black and one white. You both take turns placing down conductive
tiles of your respective color until one of the circuits are closed and...
(cue lightning)
This is the game of Reverse Hex.
You do not want to die: you still have a master's thesis to write!
What you need is a way to compare your options to find which is the best.
You recall a talk given by Peter Selinger at CanaDAM (2025):
In Hex, the outcome of a filled board depends on which terminals are connected.
In Rex, we dont want terminals to be connected,
so we associate top with nothing being connected
and bottom with everything beight connected.
(show examples on presentation).
Naturally, we say that two games are equivalent if, for any outside
position X, the outcome of G+X is less than or equal to the outcome of H+X.
This is similar to the ordering on games in normal play.
You do not want to die: you still have a master's thesis to write!
What you need is a way to tell whether one position is better than
another position. You start with what you know:
having more of your pieces connected is worse than having less connected
at the end of the game. Let's look at one section of a larger board.
Ignorant of the hidden context in grey, we can say that
connecting none is better than
connecting one is better than
connecting all of your terminals.
We can express this as a partially ordered set,
with top always representing the best outcome and
bottom representing the worst outcome.
The Rex board itself is a two terminal position, so its outcome poset
is always Bool {top,bot}. the chunk of board shown below is a 3-terminal
position, so it has 5 possible outcomes, ordered thusly (shown on board).
Now we have a way to compare outcomes, but what should it mean to compare
two games?
Well look again at this board. You want to say that a middle position G is
worse than a middle position H when, given any way of filling the outside
region, the outcome of G+X is less than or equal to the outcome of H+X.
(State this more formally on the slide itself, but say it casually aloud.)
Here, the outcome of a game over Bool is determined by the existence of a
first/second player strategy to acheive top. This is called the contextual
relation, and it will be the basis for our intrinsic relation.
UNfortunately, just like in normal play, there are infinitely many contexts (X's)
that we must use to compare G and H.
Since we are only mortal, this relation is difficult for us to use.
In order to make our relation useful, we need to look at
some properties that Rex has and create an intrinsic relation on
Rex positions.
Take this Rex position, G. Let's duplicate the position and play a game on
the sum: Left will play white stones on board L and black stones on
board R, and right will behave dually. At the end of the game,
left wins if the atomic value of board L is less than or equal to
the atomic value of board R.
If Right makes the first move on one board, Left can simply copy Right's move
on the other board. This means Left has a second player strategy that guarantees
the boards are identical at the end of the game, a win for Left.
Right says this is unfair, and makes Left go first. Left still wants to use her
old strategy, so she numbers the cells arbitrarily and plays to cell 0.
If Right plays in cell 0 on the opposing board,
then left plays to the next available cell.
If Right plays to a cell n neq 0 on either board,
then Left plays to cell n on the opposing board.
If right ever plays in cell 0,
then by induction Left has a first player winning strategy.
Because there is an even number of cells total, Right will make the last move.
Then Right cannot force Left to play anywhere, and Right will have
to play in cell 0 at some point.
Then left has a fisrt player strategy for ensuring the boards are identical at the end.
We say that a game G has Property X if Left has a first player winning strategy
in the comparison game of G, and we have just shown that all games of Rex have
property X.
We have the following intrinsic relation on games:
G is less than or equal to H when Left can win the comparison game as second player
and make the last move.
As you can see here, (relation pictured)
This relation is very similar to the Hex relation and to the relation of normal play.
Yay, we can finally compare things! Let's try it out:
⊥ ≅ { { ⊥ | ⊥ } | { ⊤ | ⊤ } } ≅ ⊤
uh oh...
The problem here is that this relation is not transitive
unless we restrict it to games that have property X.
The game in the middle here is the earliest S.A.M. game that does not have property X.
In Rex, I would always rather play a game in which my opponent just moved
rather than play a game in which I just moved.
Because of this, if I could pass at any point, I would.
This is where dead cells come in.
A dead cell is a cell whose state does not affect the final outcome of the game.
If there is a dead cell on the board, it is the same as passing.
Dead cells serve to change the order of play:
If Left goes first and plays in a dead cell, it's as if Right was going first all along.
If we take the addition G plus a dead cell:
G + ⬡ = { ⬡+Gl , G | G , ⬡+Gr}
We should have that moving to G dominates all other options:
{ G | G }
We call this property Star Anti Monotonicity (SAM).
∀ Gl, ∀ Gr : Gl+⬡ ≤ G ≤ Gr+⬡