Difference between revisions of "Dead cell"

From HexWiki
Jump to: navigation, search
(2x2 is less confusing than 1x1)
m (typo)
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A dead cell is a cell whose colour does not affect the outcome of the game.  
+
A dead cell is a cell whose colour does not affect the outcome of the game. More formally, in a given Hex position, a cell is ''dead'' if for every way of filling all empty cells of the board with red and blue pieces, the winner remains the same when the colour of the dead cell is changed from red to blue or vice versa.
  
More formally, in a given Hex position, a cell is ''dead'' if for every way of filling all empty cells of the board with red and black pieces, the winner remains the same when the colour of the dead cell is changed from red to blue or vice versa.
+
A cell that is not dead is ''alive''.
 +
 
 +
== Examples ==
  
 
[[Useless triangle]]s are examples of dead cells.
 
[[Useless triangle]]s are examples of dead cells.
  
In the following [[pattern]]s, the dead cell is labelled with a star.
+
In the following [[pattern]]s, the dead cell is labelled with a star. Some patterns include empty cells; however, these cells have only been included for context; they do not need to be empty. They can be occupied by stones of either color or even be outside the board.
<hex>R4 C5 Q0
+
 
    Hc2 Hd2
+
=== Dead cells in the interior ===
Hb3 Sc3 Hd3</hex>
+
 
 +
<hexboard size="2x3"
 +
  coords="none"
 +
  edges="none"
 +
  visible="-a1"
 +
  contents="R a2 b1 c1 c2 E *:b2"
 +
  />
 +
 
 +
<hexboard size="3x3"
 +
  coords="none"
 +
  edges="none"
 +
  visible="-a1 a2 b3 c3"
 +
  contents="B a3 R b1 c1 c2 E *:b2"
 +
  />
  
<hex>R5 C5 Q0
+
<hexboard size="3x3"
  Hc2 Hd2
+
  coords="none"
    Sc3 Hd3
+
  edges="none"
Vb4</hex>
+
  visible="-a1 b1 b3 c3"
 +
  contents="B a2 a3 R c1 c2 E *:b2"
 +
  />
  
<hex>R5 C5 Q0
+
=== Dead cells near edges and corners ===
        Hd2
+
Vb3 Sc3 Hd3
+
  Vb4</hex>
+
  
<hex>R5 C5 He2 Hd3 Se3</hex>
+
<hexboard size="3x4"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="-a1 a2 b1"
 +
  contents="R c2 b3 E *:c3"
 +
  />
  
<hex>R5 C5 He2 Se3 He4</hex>
+
<hexboard size="2x5"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="-a1"
 +
  contents="R b2 d2 E *:c2"
 +
  />
  
<hex>R5 C5 He2 Se3 Vd4</hex>
+
<hexboard size="3x5"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="-a1 a2 b1"
 +
  contents="B c2 R d3 E *:c3"
 +
  />
  
<hex>R5 C5 Se3 Vd3 Vd4</hex>
+
<hexboard size="3x5"
 +
  coords="none"
 +
  edges="bottom"
 +
  visible="-a1 a2 b1"
 +
  contents="B c2 d2 E *:c3"
 +
  />
  
<hex>R5 C5 He4 Se5</hex>
+
<hexboard size="3x4"
 +
  coords="none"
 +
  edges="bottom right"
 +
  visible="-a1 a2 b1"
 +
  contents="R c3 E *:d3"
 +
  />
  
 
== Usage ==
 
== Usage ==
  
Because the colour does not affect the result of the game, dead cells can be treated as if they contained a blue piece or a red piece, without changing the strategic value of the position. This often simplifies the analysis of Hex positions. In particular, dead cells as [[captured cell|captured]] by both players.
+
Because the colour does not affect the result of the game, dead cells can be treated as if they contained a blue piece or a red piece, without changing the strategic value of the position. This often simplifies the analysis of Hex positions. In particular, dead cells are [[captured cell|captured]] by both players.
  
 
For example, in the following hypothetical situation (with Red to move), Red might wonder whether the piece at e2 could somehow be useful as a [[ladder escape]].
 
For example, in the following hypothetical situation (with Red to move), Red might wonder whether the piece at e2 could somehow be useful as a [[ladder escape]].
Line 41: Line 80:
 
However, the cell e2 is dead, and therefore the position is strategically equivalent to the one where e2 is blue. It follows that e2 cannot possibly be useful to Red as a ladder escape, or for any other purpose.
 
However, the cell e2 is dead, and therefore the position is strategically equivalent to the one where e2 is blue. It follows that e2 cannot possibly be useful to Red as a ladder escape, or for any other purpose.
  
It is never advantageous to move in a dead cell. It is also never advantageous to move in a cell that the opponent can kill (i.e., turn into a dead cell) with the next move. Such a cell is called ''vulnerable'' for the player who should not move there.
+
It is never advantageous to move in a dead empty cell. It is also never advantageous to move in a cell that the opponent can kill (i.e., turn into a dead cell) with the next move. Such a cell is called ''vulnerable'' for the player who should not move there.
  
This concept can be useful in determining which side of a [[bridge]] it is better to intrude upon. In the following example, b3 is vulnerable for Blue. If Blue plays b3, Red can respond at c3, killing b3. Since b3 is now dead, it can be treated as a red piece. Effectively, Blue has gained nothing, and Red has gained two new pieces at b3 and c3. It follows that if Blue wants to invade the bridge, she should do so at c3.
+
This concept can be useful in determining which side of a [[bridge]] it is better to intrude upon. In the following example, b3 is vulnerable for Blue. If Blue plays b3, Red can respond at c3, killing b3. Since b3 is now dead, it can be treated as a red piece. Effectively, Blue has gained nothing, and Red has gained two new pieces at b3 and c3. It follows that if Blue wants to intrude into the bridge, she should do so at c3. See also the article on [[bolstered template]]s.
  
 
<hex>R5 C5 Q1 Ha3 Vb4 Vc2</hex>
 
<hex>R5 C5 Q1 Ha3 Vb4 Vc2</hex>
Line 57: Line 96:
 
While the colour of a dead cell does not affect whether a position is winning or losing, it can affect whether other cells are dead. For example, in the following position, both c3 and d3 are dead.
 
While the colour of a dead cell does not affect whether a position is winning or losing, it can affect whether other cells are dead. For example, in the following position, both c3 and d3 are dead.
  
<hexboard size="4x6" coords="show" contents="B a4 B b4 B d4 B e4 R c2 R d2 R e2 R c3 R d3"/>
+
<hexboard size="4x6" coords="show" contents="B a4 b4 d4 e4 f4 R c2 c3 d2 d3 e2"/>
  
 
Therefore we can colour c3 blue without changing the strategic value of the position. Alternatively, we can colour d3 blue without changing its value. However, we cannot colour ''both'' c3 and d3 blue, as this would actually change the outcome of the game. In other words, if we change the colour of c3, then d3 is no longer dead, and vice versa.
 
Therefore we can colour c3 blue without changing the strategic value of the position. Alternatively, we can colour d3 blue without changing its value. However, we cannot colour ''both'' c3 and d3 blue, as this would actually change the outcome of the game. In other words, if we change the colour of c3, then d3 is no longer dead, and vice versa.
Line 63: Line 102:
 
An extreme example of this is the position where the entire Hex board is filled with red pieces. This is obviously a win for Red. Also, assuming the board size is at least 2x2, every single cell on the board is dead. However, if we were to change all of them to blue, it would clearly change the winner of the game.
 
An extreme example of this is the position where the entire Hex board is filled with red pieces. This is obviously a win for Red. Also, assuming the board size is at least 2x2, every single cell on the board is dead. However, if we were to change all of them to blue, it would clearly change the winner of the game.
  
However, if a dead cell is currently empty, they it will remain dead no matter what colour it or other empty dead cells are filled with. In particular, a set of several empty dead cells is captured, as a whole, by both players.
+
However, if a dead cell is currently empty, then it will remain dead no matter what colour it or other empty dead cells are filled with. In particular, a set of several empty dead cells is captured, as a whole, by both players.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 16:30, 25 May 2023

A dead cell is a cell whose colour does not affect the outcome of the game. More formally, in a given Hex position, a cell is dead if for every way of filling all empty cells of the board with red and blue pieces, the winner remains the same when the colour of the dead cell is changed from red to blue or vice versa.

A cell that is not dead is alive.

Examples

Useless triangles are examples of dead cells.

In the following patterns, the dead cell is labelled with a star. Some patterns include empty cells; however, these cells have only been included for context; they do not need to be empty. They can be occupied by stones of either color or even be outside the board.

Dead cells in the interior

Dead cells near edges and corners

Usage

Because the colour does not affect the result of the game, dead cells can be treated as if they contained a blue piece or a red piece, without changing the strategic value of the position. This often simplifies the analysis of Hex positions. In particular, dead cells are captured by both players.

For example, in the following hypothetical situation (with Red to move), Red might wonder whether the piece at e2 could somehow be useful as a ladder escape.

abcde12345

However, the cell e2 is dead, and therefore the position is strategically equivalent to the one where e2 is blue. It follows that e2 cannot possibly be useful to Red as a ladder escape, or for any other purpose.

It is never advantageous to move in a dead empty cell. It is also never advantageous to move in a cell that the opponent can kill (i.e., turn into a dead cell) with the next move. Such a cell is called vulnerable for the player who should not move there.

This concept can be useful in determining which side of a bridge it is better to intrude upon. In the following example, b3 is vulnerable for Blue. If Blue plays b3, Red can respond at c3, killing b3. Since b3 is now dead, it can be treated as a red piece. Effectively, Blue has gained nothing, and Red has gained two new pieces at b3 and c3. It follows that if Blue wants to intrude into the bridge, she should do so at c3. See also the article on bolstered templates.

abcde12345

Dead cell analysis often plays a role in determining cells that are captured or dominated.

Since dead cells, vulnerable cells, captured cells, and dominated cells are never good candiates for a player's next move, dead cell analysis can significantly speed up computer Hex algorithms, since it can reduce the number of possibilities that must be explored.

Dead cell analysis is also used in the proof that a1 is a losing opening.

Interaction between multiple dead cells

While the colour of a dead cell does not affect whether a position is winning or losing, it can affect whether other cells are dead. For example, in the following position, both c3 and d3 are dead.

abcdef1234

Therefore we can colour c3 blue without changing the strategic value of the position. Alternatively, we can colour d3 blue without changing its value. However, we cannot colour both c3 and d3 blue, as this would actually change the outcome of the game. In other words, if we change the colour of c3, then d3 is no longer dead, and vice versa.

An extreme example of this is the position where the entire Hex board is filled with red pieces. This is obviously a win for Red. Also, assuming the board size is at least 2x2, every single cell on the board is dead. However, if we were to change all of them to blue, it would clearly change the winner of the game.

However, if a dead cell is currently empty, then it will remain dead no matter what colour it or other empty dead cells are filled with. In particular, a set of several empty dead cells is captured, as a whole, by both players.

See Also

External link

Ryan Hayward's publication page contains research articles on dead cells.