Domination - Revision history

Selinger: Added two links

2025-06-29T16:52:50Z

Added two links

Selinger: Neighborhood domination implies both switch-domination and capture-domination.

2023-11-18T22:37:16Z

Neighborhood domination implies both switch-domination and capture-domination.

Selinger: /* Types of domination */ clarification

2023-11-16T21:20:57Z

‎Types of domination: clarification

Selinger: /* Capture-domination */ missing word

2023-11-16T21:20:13Z

‎Capture-domination: missing word

Selinger: Selinger moved page Dominated cell to Domination: The title "dominated cell" was originally by analogy with "dead cell", but is confusing.

2023-11-16T21:19:11Z

Selinger moved page Dominated cell to Domination: The title "dominated cell" was originally by analogy with "dead cell", but is confusing.

Selinger: small clarification

2023-11-05T15:40:41Z

small clarification

Selinger: /* Kill-domination */ Added bridge peep as an example of kill-domination

2023-11-05T14:34:33Z

‎Kill-domination: Added bridge peep as an example of kill-domination

Selinger: /* External links */ Middle initial

2023-11-05T04:35:49Z

‎External links: Middle initial

Selinger: /* Path-domination */ Added equivalence between kill-domination and path-domination.

2023-11-05T04:20:20Z

‎Path-domination: Added equivalence between kill-domination and path-domination.

Selinger: /* External links */ Added journal and year to Henderson-Hayward citation.

2023-11-05T01:30:02Z

‎External links: Added journal and year to Henderson-Hayward citation.

@@ Line 228: / Line 228: @@
 === 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.
+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.
@@ Line 236: / Line 236: @@
 === 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.
+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.

@@ Line 225: / Line 225: @@
    />
 Here, Blue X would kill Y, and therefore from both Red and Blue's point of view, X dominates Y.
 === Path-domination ===
@@ Line 239: / Line 233: @@
 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.
 == Example: the 10-cell acute corner ==

@@ Line 111: / Line 111: @@
 == 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 are special cases of these.
+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.

@@ Line 9: / Line 9: @@
 In general, it can be [[Hex theory#Complexity|difficult]] to determine whether one move dominates another. But there are many situations where the concept of [[captured cell|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, i.e., by looking at a few nearby cells.
+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 ==

@@ Line 237: / Line 237: @@
 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 a 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.
+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.
 == Example: the 10-cell acute corner ==

← Older revision	Revision as of 21:19, 16 November 2023
(No difference)

@@ Line 214: / Line 214: @@
 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.
 === Neighborhood-domination ===

@@ Line 334: / Line 334: @@
 Philip T. Henderson. [https://era.library.ualberta.ca/items/dd8ce116-183f-4ad0-b7e6-618d38f132ff "Playing and solving the game of Hex"]. Ph.D. thesis, University of Alberta, 2010.
-Philip T. Henderson and Ryan Hayward, [https://webdocs.cs.ualberta.ca/~hayward/papers/revDom.pdf "Captured-reversible moves and star decomposition domination in Hex"]. Integers Journal, 2013.
+Philip T. Henderson and Ryan B. Hayward, [https://webdocs.cs.ualberta.ca/~hayward/papers/revDom.pdf "Captured-reversible moves and star decomposition domination in Hex"]. Integers Journal, 2013.
 [[Ryan Hayward]]'s [http://www.cs.ualberta.ca/~hayward/publications.html publication page] contains research articles on dead cells.