Difference between revisions of "Domination"

Revision as of 15:23, 14 June 2020

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.

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. Namely, if moving at X would capture Y, then X always dominates Y. It is often possible to figure this out locally, i.e., by looking at a few nearby cells, rather than having to consider the whole board.

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 "*" dominates the moves marked "+", because moving at "*" would capture the cells marked "+". The cells that are left white can be any color.

Usage example

Red to move. Assume the cells marked "*" are empty; cells left white can contain any color. What is the best way for Red to connect her two groups?

The answer is d4. A move at c5 would also connect Red's groups, but d4 dominates c5. In fact, Red d4 captures c4, c5, d5, and e4, and therefore dominates all of these moves.

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.

Star decomposition domination

Sometimes it is possible to conclude that X dominates Y, even if moving at X would not exactly capture Y. One can reason as follows: suppose we can show that having two pieces at X and Y would be no better than just having a piece at X. Then X dominates Y, because moving at X is no worse than moving at X and Y, which in turns is at least as good as moving at Y alone.

As an example of this, consider the following position, with Blue to move. Which of the moves marked "*" dominates the others?

The answer is e4. For example, to see that e4 dominates d4, we reason as follows. Suppose there is a blue piece at e4.

Within the region marked "+", the only thing that can affect the game's outcome is whether d3 connects to the bottom edge or not. Red can achieve a connection in one move, and Blue can prevent a connection in one move. Now suppose that Blue also had a piece at d4.

In the region marked "+", the situation is exactly the same as before: Red can connect in one move, and Blue can disconnect Red in one move. Therefore, the additional piece at d4 is not helpful to Blue, provided Blue has a piece at e4. It follows that e4 dominates d4. A similar argument also shows that e4 dominates b5, c4, and d5 (but not c5).

This example is a special case of star decomposition domination. See Henderson and Hayward, "Captured-reversible moves and star decomposition domination in Hex".

See also

• Equivalent patterns

• Computer Hex

• Dead cell

• Captured cell

External links

Henderson and Hayward, "Captured-reversible moves and star decomposition domination in Hex".

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