Difference between revisions of "Domination"

From HexWiki
Jump to: navigation, search
m (minor typo)
(Moved Tompo1's example of domination from the page on capture to here, as Example 2.)
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
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 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 [[captured cell|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.
+
== Capture-domination ==
 +
 
 +
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 ''locally'', i.e., by looking at a few nearby cells, rather than having to consider the whole board.
  
 
== Examples of dominated patterns ==
 
== 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 [[captured cell|capture]] the cells marked "+". The cells that are left white can be any color.
+
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 [[captured cell|capture]] the cells marked "+". The cells that are left white can be any color.
  
<hexboard size="4x5" contents="E +:b4 *:c3 +:c4"/>
+
<hexboard size="4x5"  
<hexboard size="5x6" contents="R b4 c4 d4 E +:c3 +:d3 *:d2"/>
+
  coords="none"
<hexboard size="5x6" contents="R b4 c4 e2 E +:c3 +:d3 *:d2"/>
+
  edges="bottom"
<hexboard size="5x6" contents="R c4 d2 B e3 E +:c3 +:d3 *:b4"/>
+
  visible="area(c2,a4,d4,d2)"
<hexboard size="5x6" contents="R b3 b4 d4 e3 E +:c3 +:d3 *:c4"/>
+
  contents="E +:b4 *:c3 +:c4"
<hexboard size="5x6" contents="R b4 c4 d4 B c2 E +:c3 +:d3 *:e3"/>
+
  />
<hexboard size="5x6" contents="R c4 d4 B c2 b3 E +:c3 +:d3 *:e3"/>
+
<hexboard size="5x6"
<hexboard size="5x6" contents="R c4 d4 B b3 E +:c3 +:d3 *:d2"/>
+
  coords="none"
 +
  edges="none"
 +
  visible="area(c1,a3,a5,d5,f3,f1)"
 +
  contents="R b4 c4 d4 E +:c3 +:d3 *:d2"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(c1,a3,a5,d5,f3,f1)"
 +
  contents="R b4 c4 e2 E +:c3 +:d3 *:d2"
 +
  />
 +
<hexboard size="5x6"  
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(c1,a3,a5,d5,f3,f1)"
 +
  contents="R c4 d2 B e3 E +:c3 +:d3 *:b4"
 +
  />
 +
<hexboard size="5x6"  
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(c1,a3,a5,d5,f3,f1)"
 +
  contents="R b4 c4 d4 B c2 E +:c3 +:d3 *:e3"
 +
  />
 +
<hexboard size="5x6"  
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(c1,a3,a5,d5,f3,f1)"
 +
  contents="R c4 d4 B c2 b3 E +:c3 +:d3 *:e3"
 +
  />
 +
<hexboard size="5x6"  
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(c1,a3,a5,d5,f3,f1)"
 +
  contents="R c4 d4 B b3 E +:c3 +:d3 *:d2"/>
  
== Usage example ==
+
== Mutually dominating moves ==
  
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?
+
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.
  
<hexboard size="7x7" contents="R b4 b5 e5 f4 e3 B e2 d3 c6 E *:c4 c5 d4 d5 e4 f3"/>
+
For example, in the following position, each of the cells marked "*" dominates the two others. 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.
  
The answer is d4. A move at c5 would also connect Red's groups, but d4 dominates c5. In fact, Red d4 [[captured cell|captures]] c4, c5, d5, and e4, and therefore dominates all of these moves.
+
<hexboard size="5x6"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(c1,a3,a5,d5,f3,f1)"
 +
  contents="R b3 b4 d4 e3 E *:c3 *:d3 *:c4"
 +
  />
  
<hexboard size="7x7" contents="R b4 b5 e5 f4 e3 B e2 d3 c6 E +:c4 +:c5 *:d4 +:d5 +:e4"/>
+
== Usage examples ==
  
== Mutually dominating moves ==
+
=== Example 1 ===
  
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.
+
Consider the following position, with Red to move. What is the best way for Red to connect her two groups?
 +
 
 +
<hexboard size="7x7"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(e2,c4,b4,b5,c6,e5,f4,f3)"
 +
  contents="R b4 b5 e5 f4 e3 B e2 d3 c6 E a:f3 b:c4 c:d4 d:e4 f:c5 g:d5"
 +
  />
 +
 
 +
The answer is c. A move at f would also connect Red's groups, but c dominates f. In fact, Red c [[captured cell|captures]] b, d, f, and g, and therefore dominates all of these moves.
 +
 
 +
<hexboard size="7x7"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(e2,c4,b4,b5,c6,e5,f4,f3)"
 +
  contents="R b4 b5 e5 f4 e3 B e2 d3 c6 E +:c4 +:c5 *:d4 +:d5 +:e4"
 +
  />
 +
 
 +
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 cell|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, [[captured cell|capturing]] all 5 cells. This response capture-dominates the solid connection at a or b (although it may in some cases be inferior with regard to the secondary objective of minimizing the number of moves needed to win).
 +
 
 +
<hexboard size="3x3"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="area(b2,a3,c3,c2)"
 +
  contents="R b2 S red:(a3 b3) E a:a3 b:b3 c:c2"/>
  
 
== Star decomposition domination ==
 
== Star decomposition domination ==
Line 34: Line 104:
 
Sometimes it is possible to conclude that X dominates Y, even if moving at X would not exactly [[captured cell|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 turn is at least as good as moving at Y alone.
 
Sometimes it is possible to conclude that X dominates Y, even if moving at X would not exactly [[captured cell|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 turn 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?
+
As an example of this, consider the following position, with Blue to move. Which of the marked moves dominates the others?
<hexboard size="5x6" contents="B b4 R d3 E *:b5 c4 d4 d5 e4"/>
+
<hexboard size="5x6"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="area(c2,a4,a5,e5,f4,f2)"
 +
  contents="B b4 R d3 E d:b5 a:c4 b:d4 e:d5 c:e4"
 +
  />
  
The answer is e4. For example, to see that e4 dominates d4, we reason as follows. Suppose there is a blue piece at e4.
+
The answer is c. For example, to see that c dominates b, we reason as follows. Suppose there is a blue piece at c.
<hexboard size="5x6" contents="B b4 R d3 E +:b5 +:c4 +:d4 +:d5 +:c5 B e4"/>
+
<hexboard size="5x6"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="area(c2,a4,a5,e5,f4,f2)"
 +
  contents="B b4 R d3 S b5 c4 d4 d5 c5 B 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.
+
Within the shaded region, the only thing that can affect the game's outcome is whether Red's piece 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 b.
<hexboard size="5x6" contents="B b4 R d3 E +:b5 +:c4 +:d5 +:c5 B e4 d4"/>
+
<hexboard size="5x6"  
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="area(c2,a4,a5,e5,f4,f2)"
 +
  contents="B b4 R d3 S b5 c4 d4 d5 c5 B e4 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).
+
In the shaded region, 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 b is not helpful to Blue, provided Blue has a piece at c. It follows that c dominates b. A similar argument also shows that c dominates a, d, and e (but not O).
 +
<hexboard size="5x6"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="area(c2,a4,a5,e5,f4,f2)"
 +
  contents="B b4 R d3 E *:e4 +:(b5 c4 d4 d5) E O:c5"
 +
  />
  
 
This example is a special case of star decomposition domination. See Henderson and Hayward, [https://webdocs.cs.ualberta.ca/~hayward/papers/revDom.pdf "Captured-reversible moves and star decomposition domination in Hex"].
 
This example is a special case of star decomposition domination. See Henderson and Hayward, [https://webdocs.cs.ualberta.ca/~hayward/papers/revDom.pdf "Captured-reversible moves and star decomposition domination in Hex"].
 +
 +
== Path-domination ==
 +
 +
Another way to find dominated moves is by path-domination. We say that a cell X ''path-dominates'' a cell Y, from a player's point of view, if every minimal winning path for that player that passes though Y also passes through X. By a "minimal winning path", we mean a set of pieces, added to the given position, that yields a chain between the player's edges, and such that no proper subset of the pieces has this property. If X path-dominates Y, then X dominates Y.
 +
 +
To prove it, assume the player in question is Red. Consider all ways of completely filling all cells of the board, starting from the given position. For each such completely-filled board, there are four possiblities: (1) X and Y are both red; (2) X is red and Y is blue; (3) X is blue and Y is red; (4) X and Y are both blue. They key observation is that if (3) is winning for Red, then so is (2). Consider a position where (3) is winning for Red. Change the red piece at Y to a blue piece. If the resulting position is winning, then so is (2), because the extra red piece at X can only help Red. If the resulting position is losing, then Y must have been on some winning red path. But we assumed that every such path contains X, a contradiction.
 +
 +
Now given any winning strategy for Red that starts by putting a red piece at Y, we can obtain another winning strategy by simply exchanging the roles of X and Y. I.e., whenever the original strategy said to move at X, move at Y instead and vice versa. Therefore, moving at X is at least as good as moving at Y for Red, i.e., X dominates Y.
 +
 +
=== Examples of path-domination ===
 +
 +
To do.
  
 
== See also ==
 
== See also ==

Revision as of 02:01, 19 January 2021

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.

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, 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 "*" 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 two others. 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?

abcdfg

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 (although it may in some cases be inferior with regard to the secondary objective of minimizing the number of moves needed to win).

cab

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 turn 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 marked moves dominates the others?

abcde

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

Within the shaded region, the only thing that can affect the game's outcome is whether Red's piece 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 b.

In the shaded region, 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 b is not helpful to Blue, provided Blue has a piece at c. It follows that c dominates b. A similar argument also shows that c dominates a, d, and e (but not O).

O

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

Path-domination

Another way to find dominated moves is by path-domination. We say that a cell X path-dominates a cell Y, from a player's point of view, if every minimal winning path for that player that passes though Y also passes through X. By a "minimal winning path", we mean a set of pieces, added to the given position, that yields a chain between the player's edges, and such that no proper subset of the pieces has this property. If X path-dominates Y, then X dominates Y.

To prove it, assume the player in question is Red. Consider all ways of completely filling all cells of the board, starting from the given position. For each such completely-filled board, there are four possiblities: (1) X and Y are both red; (2) X is red and Y is blue; (3) X is blue and Y is red; (4) X and Y are both blue. They key observation is that if (3) is winning for Red, then so is (2). Consider a position where (3) is winning for Red. Change the red piece at Y to a blue piece. If the resulting position is winning, then so is (2), because the extra red piece at X can only help Red. If the resulting position is losing, then Y must have been on some winning red path. But we assumed that every such path contains X, a contradiction.

Now given any winning strategy for Red that starts by putting a red piece at Y, we can obtain another winning strategy by simply exchanging the roles of X and Y. I.e., whenever the original strategy said to move at X, move at Y instead and vice versa. Therefore, moving at X is at least as good as moving at Y for Red, i.e., X dominates Y.

Examples of path-domination

To do.

See also

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.