Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Dead Cell Analysis in Hex and the Shannon Game
verfasst von : Yngvi Björnsson, Ryan Hayward, Michael Johanson, Jack van Rijswijck
Erschienen in: Graph Theory in Paris
Verlag: Birkhäuser Basel
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In 1981 Claude Berge asked about combinatorial properties that might be used to solve Hex puzzles. In response, we establish properties of dead, or negligible, cells in Hex and the Shannon game.
A cell is dead if the colour of any stone placed there is irrelevant to the theoretical outcome of the game. We show that dead cell recognition is NPcomplete for the Shannon game; we also introduce two broader classifications of ignorable cells and present a localized method for recognizing some such cells. We illustrate our methods on Hex puzzles created by Berge.