Difference between revisions of "Domination"

Latest revision as of 22:37, 18 November 2023

In game theory, a move dominates another move if it is at least as good. In Hex, we say that a cell X dominates another cell Y in a given position (and from a particular player's point of view) if playing at X is at least as good as playing at Y for that player. If there is a set of cells in which one cell dominates all of the others, the player can eliminate the dominated cells from consideration, because moving in the dominating cell will be at least as good. This can often simplify the analysis of Hex positions.

Technically, every winning move dominates every other winning move (as well as every losing move), since any winning move is as good as any other. However, it is often possible to figure out domination locally, i.e., by looking at a few nearby cells, rather than having to consider the whole board. In particular, it is often possible to figure out whether one move dominates another without actually knowing whether either of these moves is winning or losing.

If a player already knows that they are winning, domination is no longer important. In that case, the player might prefer to play locally dominated moves that win efficiently, i.e., that minimize the number of remaining moves until the game is won.

Capture-domination

In general, it can be difficult to determine whether one move dominates another. But there are many situations where the concept of capturing can be used to reason about domination.

If moving at X would capture Y, then X always dominates Y. In this case, we say that X capture-dominates Y. It is often possible to figure this out locally, i.e., by looking at a few nearby cells.

Examples of dominated patterns

In all of the following examples, we assume that Red is the player to move. In each case, the move marked "*" capture-dominates the moves marked "+", because moving at "*" would capture the cells marked "+". The cells that are left white can be any color.

Mutually dominating moves

It is possible for two or more cells to dominate each other. In this case, they are all equally good moves. However, the player can still eliminate all but one of these moves from consideration.

For example, in the following position, each of the cells marked "*" dominates the other two. So any of these moves are equally good for Red (but of course there may be other moves on the board that are even better). When Red considers possible moves, she can concentrate on whichever of the three marked cells is the most convenient, and ignore the two others.

Usage examples

Example 1

Consider the following position, with Red to move. What is the best way for Red to connect her two groups?

The answer is c. A move at f would also connect Red's groups, but c dominates f. In fact, Red c captures b, d, f, and g, and therefore dominates all of these moves.

To see why c is strictly better than f, note that if Red connects using f, then Blue still has a forcing move at a; but if Red connects using c, Blue has no such forcing move.

Example 2

Consider the following position, where Red has captured cells a and b. If Blue actually plays in one of the cells a or b, what should Red do? Red could certainly play in the other of the two cells, enforcing the capture. However, it is better for Red to play at c, capturing all 5 cells. This response capture-dominates the solid connection at a or b.

In fact, if there is additional space, Red can even play at d, which captures all 7 cells and therefore dominates c (as well as a and b):

Types of domination

There are various different ways in which we can figure out that one move dominates another. Capture-domination, already discussed above, is by far the most common. However, there are many other kinds of domination. We list several of them here. Of these, fillin-domination and switch-domination are the most general; all of the other kinds of domination listed here are special cases of these.

Unless noted otherwise, we discuss all of the following types of domination from Red's point of view. Of course, the analogous notions also exist for Blue.

Fillin-domination

In a given position, we say that an empty cell Y can be filled-in by Red if having a red stone at Y does not help Red; in other words, if the position with Y being empty is equivalent to the position with Y being red. If Y can be filled-in by Red, we also say that Y is Red fillin.

Fillin is more general than capture: every captured cell is fillin, but not every fillin is captured. For example, it can be shown that in the following situation, Y is red fillin (see the 10-cell acute corner below). But Y is not red-captured.

We say that X fillin-dominates Y (for Red) if a red stone at X makes Y into fillin. In other words, if having a red stone at X and Y is no better for Red than just having red stone at X.

Proof of domination: suppose that X and Y are empty, and moving at Y is winning for Red. Then certainly occupying both X and Y in a single move would also be winning for Red. On the other hand, due to fillin, moving at X is just as good for Red as moving at both X and Y. Therefore, moving at X is also winning.

A note of caution about fillin: unlike capture, fillin is not closed under unions. In other words, if some set S of cells is fillin, and some other set T of cells is fillin, it does not follow that S ∪ T is fillin.

Capture-domination

Capture-domination was already described above. Since every captured cell is also fillin, capture-domination is a special case of fillin-domination.

Star decomposition domination

Suppose that some region of the Hex board is completely surrounded by red and blue stones (or board edges), in such a way that the boundary consists of exactly two groups of red stones and two groups of blue stones. Suppose, moreover, that the region is such that whoever moves next can connect their two groups. Henderson and Hayward call such a region a "star". If coloring some cell in the region does not alter the star-ness of the region, then that cell is fillin.

Star decomposition domination is the special case of fillin-domination where the fillin is due to a star region. As an example of this, consider the following position, with Blue to move. Which of the marked moves dominates the others?

The answer is c. We reason as follows. If Blue plays at c, then the shaded region is a star:

Moreover, each of a, b, d, e can be individually colored blue without changing that the region is a star. Therefore, each one of a, b, d, and e is individually fillin (note that not all of these cells can be filled-in simultaneously, or else the region would no longer be a star). It follows that c dominates each of a, b, d, and e (but not O).

Switch-domination

Consider a position with two empty cells X and Y. We say that X switch-dominates Y if the following holds: For every way of filling the remaining empty cells of the board with red and blue stones, if X=blue and Y=red is winning, then X=red and Y=blue is also winning.

Proof of domination: Suppose that in some position, X switch-dominates Y, and Red has a winning strategy S that starts by Red moving at Y. We claim that Red also has a winning strategy that starts by moving at X. In fact, let S' be the strategy that is exactly like S, but with the cells X and Y switched. In other words, every time Blue moves in one of X or Y, Red pretends that Blue has moved in the other of these cells. And every time the strategy S tells Red to move in X or Y, Red moves in the other of these cells. The strategy S' starts with Red moving at X. Assume that Red follows the strategy S' and that the game continues until the entire board is filled with stones (if the game finishes earlier, just let the players continue playing). At the end of the game, we reach a position where X=red. Case 1: Y=red. In that case, X and Y are the same color, so the position is exactly the same as would have been reached if Red had followed strategy S (and therefore a win for Red). Case 2: Y=blue. If Red had followed the strategy S, the game would have ended in exactly the same position, but with X=blue and Y=red. This would have been winning for Red. By the switch-domination assumption, X=red and Y=blue is then also a win for Red.

Here is an example:

We claim that X switch-dominates Y. To see why, fill the board with stones such that X=blue and Y=red and assume Red is the winner. Then the blue stone at X kills the red stone at Y, and therefore this position is equivalent to X=blue and Y=blue. Since it is winning for Red, it follows that X=red and Y=blue is also winning for Red, showing that X switch-dominates Y.

We note that switch-domination does not imply fillin-domination (and therefore does not imply capture-domination either). In fact, in the example we just gave, X does not fillin-dominate Y. To see why, consider X=red. Then with Blue to move, the left position is winning for Blue, and the right position is winning for Red. This shows that they are not equivalent, i.e., Y is not fillin.

Conversely, fillin-domination does not imply switch-domination. For example, consider the following 2x2 position with Red to move:

Here, X captures the entire bottom row, so X capture-dominates Y. But X does not switch-dominate Y; for example, if we fill the rest of the board like this,

then (X,Y)=(blue,red) is winning and (X,Y)=(red,blue) is losing for Red.

We also note that switch-domination is the same for both players: If X switch-dominates Y from Red's point of view, then X also switch-dominates Y from Blue's point of view. Fillin-domination does not have this property.

Kill-domination

From Red's point of view, we say that X kill-dominates Y if a blue stone at X would kill Y. In fact, the example of switch-domination we gave above was also an example of kill-domination.

Kill-domination is a special case of switch-domination. Proof: Suppose X kill-dominates Y. Consider a completely-filled board position with X=blue and Y=red that is winning for Red. Since Y is dead, X=blue and Y=blue is also winning for Red, therefore X=red and Y=blue is also winning for Red. Therefore X switch-dominates Y.

However, not every example of switch-domination arises from kill-domination. Switch-domination is the same from both players' point of view, but kill-domination is not.

An example of kill-domination is a bridge peep:

Here, Blue X would kill Y, and therefore from both Red and Blue's point of view, X dominates Y.

Path-domination

From Red's point of view, we say that X path-dominates Y if every minimal red winning path that passes though Y also passes through X. By a "minimal winning path", we mean a set of stones, added to the given position, that yields a chain between the player's edges, and such that no proper subset of the stones has this property.

Path-domination is a special case of switch-domination. Proof: Suppose X path-dominates Y. Consider a completely-filled board position with X=blue and Y=red that is winning for Red. Change the red stone at Y to a blue stone. If the resulting position is winning for Red, then so is X=red and Y=blue, because the extra red stone at X can only help Red. If the resulting position is losing, then Y must have been on some minimal red winning path. But we assumed that every such path contains X, a contradiction.

Perhaps surprisingly, path-domination and kill-domination are actually the same thing. To see why, it is helpful to know that an empty cell Y is dead if and only if there is no minimal winning path containing Y. Now X path-dominates Y from Red's point of view if and only if every minimal red winning path through Y also contains X. This is the case if and only if there is no minimal red winning path through Y when X is blue. But that is equivalent to saying that Y is dead when X is blue, i.e., X kill-dominates Y from Red's point of view.

Neighborhood-domination

From Red's point of view, define a neighbor of a cell X to be a cell that is either X itself, adjacent to X, or connected to X by an unbroken chain of red stones. We say that X neighborhood-dominates Y if both X and Y are empty, and every empty neighbor of Y is also an empty neighbor of X.

Neighborhood-domination is a special case of switch-domination. Proof: Suppose X neighborhood-dominates Y. Consider a completely-filled board position with X=blue and Y=red that is winning for Red. Consider a minimal winning path for Red. If the path does not pass through Y, then Y=blue would still be winning and there is nothing to show. If the path passes through Y, then the originally-empty cells on the path immediately before and after Y are neighbors of Y. By assumption, they are therefore also neighbors of X. Hence, the position with X=red and Y=blue is still winning for Red, with the winning path going through X instead of Y.

In fact, neighborhood-domination is also a special case of capture-domination. Proof: Suppose x neighborhood-dominates y from Red's point of view. Now put a red stone on x. Then all of y's neighbors are already connected to each other via the red stone on x, so that y can no longer be part of any minimal winning path. Therefore y is dead. Since dead cells are captured, y is captured by x, so that x captured-dominates y.

Example: the 10-cell acute corner

Consider the following cells in the acute corner:

Assume that the 10 indicated corner cells are still empty, and Red wants to make a move in the corner. Also assume that it is not the first move of the game (so Red does not need to worry about her move being swapped). Where should Red consider playing? It turns out that there are only 3 moves that dominate all other possibilities. Red should move at e, h, or j.

Caveat: Please note that this does not mean that Red should never make a move other than e, h, or j in the acute corner. It only means that if the corner is empty, Red's first move in the corner should be e, h, or j. In the presence of other (red or blue) stones, Red might of course need to move elsewhere in the corner. By symmetry, Blue's first move in the empty corner should be at a, e, or h.

Red's move at e

A red stone at e captures a, b, c, d, f, and g.

Therefore, e capture-dominates a, b, c, d, f, and g.

Red's move at h

Red's move at h fillin-dominates i. To show this, we must show that the following two corner positions are equivalent:

Clearly the right position is at least as good for Red as the left one, since Red has an additional stone. To see why the left position is at least as good as the right one, we consider two cases. Case 1: Red is the next player to make a move in the region. In this case, Red will play at e, capturing the entire region. Since the whole region (including i) is red-captured, the red stone at i no longer matters. Case 2: Blue is the next player to make a move in the region. If Blue moves anywhere other than e, Red responds at e, capturing the entire region (including i) and killing Blue's stone. If Blue moves at e, then the two positions are:

In this case, the only thing left to determine the outcome of the region {b,c,d,e,f,g,h,i} is whether Red connects h to the red edge or Blue connects e to the blue edge. In both the left and the right region, whichever player moves next achieves this outcome, so the two regions are equivalent.

Since having h is as good for Red as having both h and i, the move at h fillin-dominates i.

Red's move at j

The remaining possibility for Red in the empty 10-cell corner is to move at j.

e, h, and j are not dominated

We have seen above that all red moves other than e, h, and j in the corner are dominated. Could it be that one of these three remaining moves is also dominated? This is not the case. To see that e, h, and j are not dominated, it suffices to give examples of positions in which e (respectively h and j) is the only winning move.

Here are such positions. In each position, it is Red's turn, and the only winning move is indicated by the letter e, h, or j:

See also

• Equivalent patterns

• Computer Hex

• Dead cell

• Captured cell

External links

Philip T. Henderson. "Playing and solving the game of Hex". Ph.D. thesis, University of Alberta, 2010.

Philip T. Henderson and Ryan B. Hayward, "Captured-reversible moves and star decomposition domination in Hex". Integers Journal, 2013.

Ryan Hayward's publication page contains research articles on dead cells.