Difference between revisions of "Domination"

Revision as of 03:09, 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

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.

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

Blue to move. Which of the moves marked "*" dominates the others?

The answer is e4. See Henderson and Hayward, "Captured-reversible moves and star decomposition decomposition in Hex".

See also

• Equivalent patterns

• Computer Hex

• Dead cell

• Captured cell

External links

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

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