Difference between revisions of "Captured cell"

From HexWiki
Jump to: navigation, search
(Generous capture: fixed number of pieces and cleaned up diagram code)
(Captured is not the same as connected: cleaned up proof-position for bridge)
Line 97: Line 97:
 
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:
 
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="5x4" contents="R c2 R b4 E *:b3 E *:c3 B a5 B b5 R d4"/>
+
<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 c3, Red will lose because she cannot simultaneously defend the bridge and prevent Blue from connecting at c4. 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.
+
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.
 
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.

Revision as of 07:32, 19 January 2021

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 mouth:

abcde12345

The box:

abcdef12345

The open box:

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? Wny 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 mouth, the box, and the open box, 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 mouth:

The box:

The open box:

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.