Difference between revisions of "Dead cell"
m (cat. intermediate) |
(Expanded the article on dead cells.) |
||
| Line 1: | Line 1: | ||
| − | A dead cell is a cell | + | 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 black pieces, the winner remains the same when the colour of the dead cell is changed from red to blue or vice versa. | |
| + | |||
| + | [[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. | ||
| Line 17: | Line 19: | ||
Vb3 Sc3 Hd3 | Vb3 Sc3 Hd3 | ||
Vb4</hex> | Vb4</hex> | ||
| + | |||
| + | <hex>R5 C5 He2 Hd3 Se3</hex> | ||
| + | |||
| + | <hex>R5 C5 He2 Se3 He4</hex> | ||
| + | |||
| + | <hex>R5 C5 He2 Se3 Vd4</hex> | ||
| + | |||
| + | <hex>R5 C5 Se3 Vd3 Vd4</hex> | ||
| + | |||
| + | <hex>R5 C5 He4 Se5</hex> | ||
== Usage == | == Usage == | ||
| − | Because the colour does not affect the result of the game, dead cells can be | + | 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. |
| − | + | 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]]. | |
| + | <hexboard size="5x5" | ||
| + | coords="show" | ||
| + | contents="R a2 R a3 R a4 B a5 B c3 B d2 B e1 R e2" | ||
| + | /> | ||
| + | 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. | ||
| + | |||
| + | 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. | ||
<hex>R5 C5 Q1 Ha3 Vb4 Vc2</hex> | <hex>R5 C5 Q1 Ha3 Vb4 Vc2</hex> | ||
| + | |||
| + | Dead cell analysis often plays a role in determining cells that are [[captured cell|captured]] or [[dominated cell|dominated]]. | ||
| + | |||
| + | Since dead cells, vulnerable cells, captured cells, and [[dominated cell]]s are never good candiates for a player's next move, dead cell analysis can significantely 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 opening|a1 is a losing opening]]. | ||
== See Also == | == See Also == | ||
Revision as of 17:05, 13 June 2020
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 black pieces, the winner remains the same when the colour of the dead cell is changed from red to blue or vice versa.
Useless triangles are examples of dead cells.
In the following patterns, the dead cell is labelled with a star.
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 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.
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.
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.
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 significantely 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.
See Also
External link
Ryan Hayward's publication page contains research articles on dead cells.
