Difference between revisions of "Captured cell"

From HexWiki
Jump to: navigation, search
(Expanded section "Captured is not connected" to include 3 other templates.)
(More examples of generous capture: Simplified this section.)
Line 79: Line 79:
 
== More examples of generous capture ==
 
== More examples of generous capture ==
  
Consider the [[Box|box template]].
+
We've seen [[#Captured is not the same as connected|above]] that many templates, such as 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 "*":
<hexboard size="5x6" contents="R c2 R b4 R e2 R d4 E *:d2 E *:b3 *:c3 *:d3 *:e3 *:c4"/>
+
The carrier of this template consists of the cells marked "*". One may ask whether the area marked "*" is Red-captured. The answer is no. To see why, consider, for example, the following position, with Blue to move:
+
<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"/>
+
It is easy to check that this position is winning for Blue with e3 being the winning move. In fact, Blue's connection will typically pass through the interior of the template. On the other hand, if just one of the cells marked "*" were occupied by Red (it does not matter which cell), the position would be winning for Red. This shows that Red has in fact not captured any of the cells marked "*".
+
  
However, the cells marked "*" are generous-captured via blue pieces at a3 and f3.
+
The [[bridge]]:
 +
<hexboard coords="show" size="5x4" contents="R c2 R b4 E *:b3 E *:c3 B a3 B d3" />
 +
 
 +
The [[mouth]]:
 +
<hexboard size="5x5" contents="R b4 R b2 R d2 R c4 E *:c2 *:b3 *:c3 *:d3 B e3" />
 +
 
 +
The [[box]]:
 
<hexboard size="5x6" contents="R c2 R b4 R e2 R d4 E *:d2 E *:b3 *:c3 *:d3 *:e3 *:c4 B a3 B f3"/>
 
<hexboard size="5x6" contents="R c2 R b4 R e2 R d4 E *:d2 E *:b3 *:c3 *:d3 *:e3 *:c4 B a3 B f3"/>
It is easy to see that in this case, Red can kill any blue pieces within the marked area by following a pairing strategy: if Blue plays at one of {b3, c3}, Red plays at the other, and similarly for {d3, e3} and {d2, c4}.
 
  
Similar arguments work for other templates too. As another example, consider the "open box" template, with carrier as shown:
+
The [[open box]]:
<hexboard size="5x6" contents="R c2 R b3 R e2 R d4 E *:d2 E *:b4 *:c3 *:d3 *:e3 *:c4"/>
+
None of the cells marked "*" are captured, as the following position demonstrates. With Blue to move, the position is winning for Blue, but if any one of the cells marked "*" is occupied by Red, the position becomes winning for Red.
+
<hexboard size="6x6" contents="R c2 R b3 R e2 R d4 E *:d2 E *:b4 *:c3 *:d3 *:e3 *:c4 B a4 R a5 R c5 B e1 B f1 R a6 B b6 B c6 B d6 B e6 B f6" />
+
However, the cells marked "*" are generous-captured via blue pieces at a5, b5 and f3. This can again be shown by a pairing strategy, pairing {b4, c3}, {c4, d2}, and {d3, e3}.
+
 
<hexboard size="5x6" contents="R c2 R b3 R e2 R d4 E *:d2 E *:b4 *:c3 *:d3 *:e3 *:c4 B a5 B b5 B f3"/>
 
<hexboard size="5x6" contents="R c2 R b3 R e2 R d4 E *:d2 E *:b4 *:c3 *:d3 *:e3 *:c4 B a5 B b5 B f3"/>
  

Revision as of 14:13, 16 August 2020

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

abcde12345

The two cells marked "*" are captured by Red. If Blue plays at b5, Red can play at c5, killing b5. 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.

abcde12345

For a more complex example, consider the following position, with Blue to move:

abcdefg1234567

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 template V2a, even though Red does not have an actual piece at f3.

Here are some other examples of cells captured by Red:

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:

abcd12345

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 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 a situation like this, 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 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:

abcd12345

The mouth:

abcde12345

The box:

abcdef12345

The open box:

abcdef12345

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.