Difference between revisions of "Dead cell"

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.

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.

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.

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

• Equivalent patterns

• Computer Hex

• Dominated cells

• Captured cells

External link

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