Domination - Revision history

Hexanna: /* Fillin with concessions */ clarify

2026-09-14T03:18:53Z

‎Fillin with concessions: clarify

Hexanna: /* Fillin with concessions */ add IV2d example

2026-09-14T02:15:39Z

‎Fillin with concessions: add IV2d example

Hexanna: fillin with concessions

2026-09-14T00:39:51Z

fillin with concessions

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

@@ Line 137: / Line 137: @@
 ==== Fillin with concessions ====
-In a given position, we say that X is ''Red fillin with concession Y'' if filling X red and Y blue gives a position no better for Red than the original. Here X and Y are sets of empty cells. Ordinary Red fillin is the case where Y is empty.
+In a given position, we say that X is ''Red fillin with concession Y'' if filling X red and Y blue gives a position no better for Red than the original. Here X and Y are sets of empty cells. Ordinary Red fillin is the case where Y is empty. Any superset of Y is also a concession, so we are mainly interested in minimal concession sets.
-[[Captured cell#Generous capture|Generous capture]] is a special case: giving Y to Blue captures X for Red, allowing Red to fill X. Giving Blue extra stones can only hurt Red, and filling captured cells preserves the winner.
+[[Captured cell#Generous capture|Generous capture]] is a special case: after giving Y to Blue, X is captured by Red and can therefore be filled without changing the winner.
 In the examples below, X (the fillin) is shaded red and Y (the concession) is shaded blue.
@@ Line 147: / Line 147: @@
 <hexboard size="3x3" float="inline" coords="none" edges="none" visible="-(a1 b1 a3 c3)"
    contents="R c1 b3 B a2 S red:b2 blue:c2" />
-<hexboard size="2x3" float="inline" coords="none" edges="none" visible="-c2"
+<hexboard size="3x3" float="inline" coords="none" edges="none" visible="c1 c2 b2 a3 b3"
-   contents="R a1 c1 b2 S red:b1 blue:a2" />
+   contents="R c1 a3 b3 S red:b2 blue:c2" />
 In the [[crescent]] below, Red can fill a and c by conceding d. Red a kills c, and Red b captures a/c. If Blue takes b, Red answers a; the remaining d is at least as good for Red as b in the shaded position. If Blue takes a, Red answers b and pairs c with d.

@@ Line 159: / Line 159: @@
 <hexboard size="3x3" coords="none" edges="none" visible="-c3"
    contents="R a1 a3 c1 b3 S red:(a2 b1 b2) blue:c2 E a:a2 b:b1 c:b2 d:c2" />
 === Capture-domination ===

← Older revision		Revision as of 00:39, 14 September 2026
Line 134:		Line 134:

	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.		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.
		+
		+	==== Fillin with concessions ====
		+
		+	In a given position, we say that X is ''Red fillin with concession Y'' if filling X red and Y blue gives a position no better for Red than the original. Here X and Y are sets of empty cells. Ordinary Red fillin is the case where Y is empty.
		+
		+	[[Captured cell#Generous capture\|Generous capture]] is a special case: giving Y to Blue captures X for Red, allowing Red to fill X. Giving Blue extra stones can only hurt Red, and filling captured cells preserves the winner.
		+
		+	In the examples below, X (the fillin) is shaded red and Y (the concession) is shaded blue.
		+
		+	In the following two examples, Red answers a Blue move in either shaded cell by playing the other. The blue cell [[#Switch-domination\|switch-dominates]] the red cell, since a Red move in the blue cell kills the red cell. Thus either outcome is at least as good for Red as the shaded assignment.
		+
		+	<hexboard size="3x3" float="inline" coords="none" edges="none" visible="-(a1 b1 a3 c3)"
		+	contents="R c1 b3 B a2 S red:b2 blue:c2" />
		+	<hexboard size="2x3" float="inline" coords="none" edges="none" visible="-c2"
		+	contents="R a1 c1 b2 S red:b1 blue:a2" />
		+
		+	In the [[crescent]] below, Red can fill a and c by conceding d. Red a kills c, and Red b captures a/c. If Blue takes b, Red answers a; the remaining d is at least as good for Red as b in the shaded position. If Blue takes a, Red answers b and pairs c with d.
		+
		+	<hexboard size="3x3" coords="none" edges="none" visible="-c3"
		+	contents="R a1 a3 b3 c2 S red:(a2 b2) blue:c1 E a:a2 b:b1 c:b2 d:c1" />
		+
		+	In the [[trapezoid]] below, Red can fill a, b, and c by conceding d. Pair a with b, and c with d. Whichever cell Red gets from each pair, the four existing Red stones become connected.
		+
		+	<hexboard size="3x3" coords="none" edges="none" visible="-c3"
		+	contents="R a1 a3 c1 b3 S red:(a2 b1 b2) blue:c2 E a:a2 b:b1 c:b2 d:c2" />

	=== Capture-domination ===		=== Capture-domination ===

@@ 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 ==

← 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 ===