Difference between revisions of "Captured cell"

From HexWiki
Jump to: navigation, search
m (Captured cells and dead cells: Copy-editing)
(mouth -> trapezoid)
 
(32 intermediate revisions by 3 users not shown)
Line 1: Line 1:
An area of the board (empty or not) has been ''captured'' by a player if all of the opponent's pieces in that area are dead, and for any possible move by the opponent in the area, the player has a counter-strategy that kills all of the opponent's pieces in that area.  
+
An area of the board (empty or not) has been ''captured'' by a player if all of the opponent's pieces in that area are [[dead cell|dead]], and for any possible move by the opponent in the area, the player has a counter-strategy that kills all of the opponent's pieces in that area.  
  
 
It is never advantageous for a player to move in an area that has been captured by the opponent. A captured area may as well be assumed to have been filled with the capturing player's pieces, as this does not change the strategic value of the position.
 
It is never advantageous for a player to move in an area that has been captured by the opponent. A captured area may as well be assumed to have been filled with the capturing player's pieces, as this does not change the strategic value of the position.
Line 7: Line 7:
 
The most common example of capture is the second row edge template
 
The most common example of capture is the second row edge template
  
<hexboard size="5x5" contents="R c4 E *:b5 c5"/>
+
<hexboard size="5x5"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="area(c3,a5,d5,d3)"
 +
  contents="R c4 S red:(b5 c5) E a:b5 b:c5"/>
  
The two cells marked "*" are captured by Red. If Blue plays at b5, Red can play at c5, killing b5.  
+
The two shaded cells are captured by Red. If Blue plays at a, Red can play at b, [[dead cell|killing]] a.  
Conversely, if Blue plays at c5, Red can play at b5, killing c5. Therefore, both cells are captured and the above position is strategically equivalent to the following.
+
Conversely, if Blue plays at b, Red can play at a, killing b. Therefore, both cells are captured and the above position is strategically equivalent to the following.
  
<hexboard size="5x5" contents="R c4 R b5 c5"/>
+
<hexboard size="5x5"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="area(c3,a5,d5,d3)"
 +
  contents="R c4 R b5 c5"/>
  
For a more complex example, consider the following position, with Blue to move:
+
Note that we are not saying that if Blue plays at a, Red ''should'' move at b. It may well be the case that Red [[Minimax#Intrusion_into_edge_template_II|has a better move elsewhere]]. Specifically what the above example demonstrates is that the cells a and b are captured by Red.
  
<hexboard size="7x7" contents="R f2 g2 g3 B d3 d4 E *:e3 f3"/>
+
Here are some other examples of cells captured by Red:
  
The two cells marked "*" are captured by Red, because if Blue plays at either one of them, Red can play the other, killing Blue's piece. Since each Red-captured cell can be treated as a red piece, it follows that Red is connected to the bottom edge by [[Edge_templates_with_two_adjacent_stones#edge_template_V2a|edge template V2a]], even though Red does not have an actual piece at f3.
+
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b4 c4 d4 d2 c3 d3"
 +
  contents="R b4 c4 d4 d2 S red:(c3 d3)"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b4 c4 e2 d2 c3 d3"
 +
  contents="R b4 c4 e2 d2 S red:(c3 d3)"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b4 c4 d2 e3 c3 d3"
 +
  contents="R b4 c4 d2 B e3 S red:(c3 d3)"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b3 c4 d2 e3 c3 d3"
 +
  contents="R c4 d2 B e3 b3 S red:(c3 d3)"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b4 c4 d4 b3 e3 c3 d3"
 +
  contents="R b4 c4 d4 b3 e3 S red:(c3 d3)"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b4 c4 d4 e3 c2 c3 d3"
 +
  contents="R b4 c4 d4 e3 B c2 S red:(c3 d3)"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b3 c4 d4 e3 c2 c3 d3"
 +
  contents="R c4 d4 e3 B b3 c2 S red:(c3 d3)"
 +
  />
 +
<hexboard size="5x6"
 +
  coords="hide"
 +
  visible="b4 c4 d4 e2 c2 c3 d3"
 +
  contents="R c4 d4 b4 B c2 e2 S red:(c3 d3)"
 +
  />
 +
 
 +
== Usage ==
 +
 
 +
Consider the following position, with Blue to move:
 +
 
 +
<hexboard size="7x7"
 +
  contents="R f2 g2 g3 B d3 d4 S red:(e3 f3)"
 +
  />
 +
 
 +
The two shaded cells are captured by Red, because if Blue plays at either one of them, Red can play the other, killing Blue's piece. Since each Red-captured cell can be treated as a red piece, it follows that Red is connected to the bottom edge by [[Edge_templates_with_two_adjacent_stones#edge_template_V2a|edge template V2a]], even though Red does not have an actual piece at f3.
  
 
== Captured cells and dead cells ==
 
== Captured cells and dead cells ==
Line 28: Line 85:
 
For example, consider the effect of a red piece at b2:
 
For example, consider the effect of a red piece at b2:
  
<hexboard size="5x5" contents="R b2 E +:a1 +:a2 *:b1 *:c1"/>
+
<hexboard size="5x5"
 +
  edges="top left"
 +
  visible="area(a1,a5,c5,e1)"
 +
  contents="R b2 E +:a1 +:a2 *:b1 *:c1 S red:(a1,a2,b1,c1)"
 +
  />
  
 
First, b2 captures the two cells marked "*". Then, because the cells marked "*" can be treated as if they were red pieces, the cells marked "+" become dead, and therefore also captured. Thus, a single red piece at b2 has captured four other cells.
 
First, b2 captures the two cells marked "*". Then, because the cells marked "*" can be treated as if they were red pieces, the cells marked "+" become dead, and therefore also captured. Thus, a single red piece at b2 has captured four other cells.
Line 34: Line 95:
 
Moreover, if there is an additional blue piece at a4, Red b2 actually captures five cells:
 
Moreover, if there is an additional blue piece at a4, Red b2 actually captures five cells:
 
   
 
   
<hexboard size="5x5" contents="R b2 B a4 E +:a1 +:a2 *:b1 *:c1 +:a3"/>
+
<hexboard size="5x5"  
 +
  edges="top left"
 +
  visible="area(a1,a5,c5,e1)"
 +
  contents="R b2 B a4 E +:a1 +:a2 *:b1 *:c1 +:a3 S red:(a1,a2,b1,c1,a3)"
 +
  />
  
 
First, b1 and c1 are Red-captured and a1 and a2 are dead as in the previous example. Finally, since a2 can be treated as a red piece, it also kills a3.
 
First, b1 and c1 are Red-captured and a1 and a2 are dead as in the previous example. Finally, since a2 can be treated as a red piece, it also kills a3.
Line 40: Line 105:
 
== Captured is not the same as connected ==
 
== Captured is not the same as connected ==
  
Based on the example of the 2nd row template above, one may wonder whether cells that are part of a template are automatically captured. This is not the case. To see why not, consider an interior bridge template:
+
Based on the example of the 2nd row edge template above, one may wonder whether cells that are part of a template are automatically captured. This is not the case. To see why not, consider the following position containing an interior bridge template, with Blue to move:
  
<hexboard coords="show" size="6x6" contents="R c4 d2 e4 e5 B a6 b6 c6 f2 E *:c3 *:d3"/>
+
<hexboard coords="show" size="4x4" contents="R c1 b3 d3 E *:b2 *:c2 B a4 b4"/>
  
The two cells marked "*" form part of a bridge, but they are not captured. Indeed, if Blue intrudes into the bridge at d3, Red will lose because she cannot simultaneously defend the bridge and prevent Blue from connecting at d4. On the other hand, had the cells marked "*" been red pieces, the position would have been winning for Red.  
+
The two cells marked "*" form part of a bridge, but they are not captured. Indeed, if Blue intrudes into the bridge at c2, Red will lose because Red cannot simultaneously defend the bridge and prevent Blue from connecting at c3. On the other hand, had even one of the cells marked "*" been occupied by Red (it does not matter which one), the position would have been winning for Red. This shows that neither of the cells marked "*" is captured by Red.
 +
 
 +
Analogous things can be said about other interior templates as well. Each of the following positions contains an interior template whose [[carrier]] is marked "*". With Blue to move, each position is winning for Blue. But if any one of the cells marked "*" is replaced by a red piece, the position becomes winning for Red.
 +
 
 +
The [[trapezoid]]:
 +
<hexboard size="5x5" contents="R b4 R b2 R d2 R c4 E *:c2 *:b3 *:c3 *:d3 B a5 B b5 B c5 B a1 B b1 B c1 R e4" />
 +
 
 +
The [[box]]:
 +
<hexboard size="5x6" contents="R c2 R b4 R e2 R d4 E *:d2 E *:b3 *:c3 *:d3 *:e3 *:c4 R f4 B c1 B d1 B a5 B b5 B c5 B d5"/>
 +
 
 +
The [[Interior_template#The shopping cart|shopping cart]]:
 +
<hexboard size="5x6" contents="R b4 R b3 R e2 R d4 E *:d2 E *:c2 *:c3 *:d3 *:e3 *:c4 B a5 B b5 B c5 B d5 B b1 R f4" />
 +
 
 +
== Generous capture ==
 +
 
 +
In some situations, it can happen that an area is not technically captured by a player, but the area ''would'' be captured if the ''opponent'' had additional pieces on the board.  For example, consider the following situation:
 +
<hexboard size="7x7" contents="R f2 g2 g3 E *:e3 *:f3 E +:d3 E +:d4"/>
 +
The two cells marked "*" are not captured by Red. However, as we already saw above, they would become captured (by Red) if Blue occupied the cells marked "+". Red can sometimes take advantage of such a situation by mentally "giving" the additional cells to Blue, i.e., playing as if Blue already had pieces there. In other words, if Red promises never to move in the cells marked "+", then she can treat the cells marked "*" as captured. We refer to this as "generous" capture, because to capture the cells, the player must generously (albeit only mentally) give additional cells to the opponent.
 +
 
 +
In the above example, the red group is connected to the bottom edge by generous capture and  [[Edge_templates_with_two_adjacent_stones#edge_template_V2a|edge template V2a]]. Note that it is important that this template does not overlap the "generous" cells d3 and d4, i.e., it would still be valid if Blue actually occupied these cells.
 +
 
 +
It may seem paradoxical that Red can gain an advantage by mentally surrendering some cells to Blue. Normally, additional Blue pieces can only be bad for Red. So what is the catch? Why can't we just consider the cells marked "*" above as captured without the mental contortion of giving additional pieces to Blue? The answer is that in some situations, generous capture may help Red connect in one direction, while interfering with Red's connection in the other. As an example of this, consider the following position, with Blue to move:
 +
<hexboard size="7x7" contents="R b4 c3 c2 c1 d1 f2 g2 g3 E *:e3 *:f3 E +:d3 B a6 b5 c4 d4 d2 e1 g1"/>
 +
Red is connected to the top edge via [[double threat]] at f1 and d3. Red is also connected to the bottom edge by generous capture: a generous blue piece at d3 captures f3 for Red, and therefore Red is connected down by [[Edge_templates_with_two_adjacent_stones#edge_template_V2a|edge template V2a]]. However, the catch is that Red cannot achieve both of these things simultaneously: the generous blue piece at d3 invalidates Red's connection to the top &mdash; even though this piece only exists in Red's imagination! And indeed, this position is winning for Blue: a possible winning move for Blue is e3, which requires Red to defend the upward and downward connections at the same time.
 +
 
 +
== More examples of generous capture ==
 +
 
 +
We've seen [[#Captured is not the same as connected|above]] that many templates, such as the bridge, the trapezoid, the box, and the shopping cart, do not capture any of the cells in their carrier. However, all of these templates ''generously'' capture their carrier if certain blue pieces are added. The following diagrams show which blue pieces can be added to each template to capture the cells marked "*":
 +
 
 +
The [[bridge]]:
 +
<hexboard size="5x4"
 +
  coords="none"
 +
  edges="none"
 +
  visible="c2 b4 b3 c3 a3 d3"
 +
  contents="R c2 R b4 E *:b3 E *:c3 B a3 B d3"
 +
  />
 +
 
 +
The [[trapezoid]]:
 +
<hexboard size="5x5"
 +
  coords="none"
 +
  edges="none"
 +
  visible="b4 b2 d2 c4 c2 b3 c3 d3 e3"
 +
  contents="R b4 R b2 R d2 R c4 E *:c2 *:b3 *:c3 *:d3 B e3"
 +
  />
 +
 
 +
The [[box]]:
 +
<hexboard size="5x6"
 +
  coords="none"
 +
  edges="none"
 +
  visible="c2 b4 e2 d4 d2 b3 c3 d3 e3 c4 a3 f3"
 +
  contents="R c2 R b4 R e2 R d4 E *:d2 E *:b3 *:c3 *:d3 *:e3 *:c4 B a3 B f3"
 +
  />
 +
 
 +
The [[Interior_template#The shopping cart|shopping cart]]:
 +
<hexboard size="5x6"
 +
  coords="none"
 +
  edges="none"
 +
  visible="c2 b3 e2 d4 d2 b4 c3 d3 e3 c4 a5 b5 f3"
 +
  contents="R c2 R b3 R e2 R d4 E *:d2 E *:b4 *:c3 *:d3 *:e3 *:c4 B a5 B b5 B f3"
 +
  />
 +
 
 +
== See also ==
  
 
*[[Equivalent patterns]]
 
*[[Equivalent patterns]]
Line 50: Line 176:
 
*[[Computer Hex]]
 
*[[Computer Hex]]
  
*[[Dominated cells]]
+
*[[Dominated cell]]s
 +
 
 +
*[[Dead cell]]s
  
*[[Dead cells]]
+
== External links ==
  
== External link ==
+
Henderson and Hayward, [https://webdocs.cs.ualberta.ca/~hayward/papers/revDom.pdf "Captured-reversible moves and star decomposition domination in Hex"].
  
 
[[Ryan Hayward]]'s [http://www.cs.ualberta.ca/~hayward/publications.html publication page] contains research articles on dead, vulnerable, captured, and dominated cells.
 
[[Ryan Hayward]]'s [http://www.cs.ualberta.ca/~hayward/publications.html publication page] contains research articles on dead, vulnerable, captured, and dominated cells.

Latest revision as of 23:42, 14 February 2024

An area of the board (empty or not) has been captured by a player if all of the opponent's pieces in that area are dead, and for any possible move by the opponent in the area, the player has a counter-strategy that kills all of the opponent's pieces in that area.

It is never advantageous for a player to move in an area that has been captured by the opponent. A captured area may as well be assumed to have been filled with the capturing player's pieces, as this does not change the strategic value of the position.

Examples

The most common example of capture is the second row edge template

ab

The two shaded cells are captured by Red. If Blue plays at a, Red can play at b, killing a. Conversely, if Blue plays at b, Red can play at a, killing b. Therefore, both cells are captured and the above position is strategically equivalent to the following.

Note that we are not saying that if Blue plays at a, Red should move at b. It may well be the case that Red has a better move elsewhere. Specifically what the above example demonstrates is that the cells a and b are captured by Red.

Here are some other examples of cells captured by Red:

Usage

Consider the following position, with Blue to move:

abcdefg1234567

The two shaded cells are captured by Red, because if Blue plays at either one of them, Red can play the other, killing Blue's piece. Since each Red-captured cell can be treated as a red piece, it follows that Red is connected to the bottom edge by edge template V2a, even though Red does not have an actual piece at f3.

Captured cells and dead cells

Any cell in which a player actually has a piece is trivially captured by that player. Moreover, since dead cells can be treated as cells of either color, an empty dead cell is captured by both players. (Dead cells containing an opponent's piece may also sometimes be captured, but when considering such cells as part of a captured area, beware of the interaction between multiple dead cells).

The analysis of dead cells and captured cells may sometimes go through multiple iterations: as some cells are discovered to be captured, they create other dead cells, which in turns may create additional captured cells, and so on.

For example, consider the effect of a red piece at b2:

abcde12345

First, b2 captures the two cells marked "*". Then, because the cells marked "*" can be treated as if they were red pieces, the cells marked "+" become dead, and therefore also captured. Thus, a single red piece at b2 has captured four other cells.

Moreover, if there is an additional blue piece at a4, Red b2 actually captures five cells:

abcde12345

First, b1 and c1 are Red-captured and a1 and a2 are dead as in the previous example. Finally, since a2 can be treated as a red piece, it also kills a3.

Captured is not the same as connected

Based on the example of the 2nd row edge template above, one may wonder whether cells that are part of a template are automatically captured. This is not the case. To see why not, consider the following position containing an interior bridge template, with Blue to move:

abcd1234

The two cells marked "*" form part of a bridge, but they are not captured. Indeed, if Blue intrudes into the bridge at c2, Red will lose because Red cannot simultaneously defend the bridge and prevent Blue from connecting at c3. On the other hand, had even one of the cells marked "*" been occupied by Red (it does not matter which one), the position would have been winning for Red. This shows that neither of the cells marked "*" is captured by Red.

Analogous things can be said about other interior templates as well. Each of the following positions contains an interior template whose carrier is marked "*". With Blue to move, each position is winning for Blue. But if any one of the cells marked "*" is replaced by a red piece, the position becomes winning for Red.

The trapezoid:

abcde12345

The box:

abcdef12345

The shopping cart:

abcdef12345

Generous capture

In some situations, it can happen that an area is not technically captured by a player, but the area would be captured if the opponent had additional pieces on the board. For example, consider the following situation:

abcdefg1234567

The two cells marked "*" are not captured by Red. However, as we already saw above, they would become captured (by Red) if Blue occupied the cells marked "+". Red can sometimes take advantage of such a situation by mentally "giving" the additional cells to Blue, i.e., playing as if Blue already had pieces there. In other words, if Red promises never to move in the cells marked "+", then she can treat the cells marked "*" as captured. We refer to this as "generous" capture, because to capture the cells, the player must generously (albeit only mentally) give additional cells to the opponent.

In the above example, the red group is connected to the bottom edge by generous capture and edge template V2a. Note that it is important that this template does not overlap the "generous" cells d3 and d4, i.e., it would still be valid if Blue actually occupied these cells.

It may seem paradoxical that Red can gain an advantage by mentally surrendering some cells to Blue. Normally, additional Blue pieces can only be bad for Red. So what is the catch? Why can't we just consider the cells marked "*" above as captured without the mental contortion of giving additional pieces to Blue? The answer is that in some situations, generous capture may help Red connect in one direction, while interfering with Red's connection in the other. As an example of this, consider the following position, with Blue to move:

abcdefg1234567

Red is connected to the top edge via double threat at f1 and d3. Red is also connected to the bottom edge by generous capture: a generous blue piece at d3 captures f3 for Red, and therefore Red is connected down by edge template V2a. However, the catch is that Red cannot achieve both of these things simultaneously: the generous blue piece at d3 invalidates Red's connection to the top — even though this piece only exists in Red's imagination! And indeed, this position is winning for Blue: a possible winning move for Blue is e3, which requires Red to defend the upward and downward connections at the same time.

More examples of generous capture

We've seen above that many templates, such as the bridge, the trapezoid, the box, and the shopping cart, do not capture any of the cells in their carrier. However, all of these templates generously capture their carrier if certain blue pieces are added. The following diagrams show which blue pieces can be added to each template to capture the cells marked "*":

The bridge:

The trapezoid:

The box:

The shopping cart:

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, vulnerable, captured, and dominated cells.