Solving 7×7 Hex: Virtual Connections and Game-State Reduction

Autor:	N. Po, Yngvi Björnsson, J. van Rijswijck, Morgan Kan, Ryan B. Hayward, Michael Johanson
Rok vydání:	2004
Předmět:	Reduction (complexity) Computer Science::Computer Science and Game Theory Theoretical computer science Virtual circuit ComputingMilieux_PERSONALCOMPUTING Case finding State (computer science) Recursive descent parser Outcome (game theory) Algorithm Mathematics
Zdroj:	Advances in Computer Games ISBN: 9781475744248 ACG
Popis:	We present an algorithm which determines the outcome of an arbitrary Hex game-state by finding a winning virtual connection for the winning player. Our algorithm performs a recursive descent search of the game-tree, combining fixed and dynamic game-state virtual connection composition rules with some new Hex game-state reduction results based on move domination. The algorithm is powerful enough to solve arbitrary 7×7 game-states; in particular, we use it to determine the outcome of a 7×7 Hex game after each of the 49 possible opening moves, in each case finding an explicit proof-tree for the winning player.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::799e91e49431ef5098449254f293506d https://doi.org/10.1007/978-0-387-35706-5_17 Zobrazit plný text záznamu