Solving 7×7 Hex: Virtual Connections and Game-State Reduction
作者： R. Hayward , Y. Björnsson , M. Johanson , M. Kan , N. Po
DOI: 10.1007/978-0-387-35706-5_17
关键词: State (computer science) 、 Case finding 、 Reduction (complexity) 、 Algorithm 、 Virtual circuit 、 Outcome (game theory) 、 Recursive descent parser 、 Mathematics 、 Theoretical computer science
摘要: We present an algorithm which determines the outcome of arbitrary Hex game-state by finding a winning virtual connection for player. Our performs recursive descent search game-tree, combining fixed and dynamic composition rules with some new reduction results based on move domination. The is powerful enough to solve 7×7 game-states; in particular, we use it determine game after each 49 possible opening moves, case explicit proof-tree
springer.com
sci-hub.st 参考文章(9)
Cameron Browne, Hex Strategy: Making the Right Connections ,(2000)
Jing Yang, Simon Liao, Miroslaw Pawlak, New Winning and Losing Positions for 7×7 Hex annual conference on computers. pp. 230- 248 ,(2002) , 10.1007/978-3-540-40031-8_16
Stefan Reisch, Hex ist PSPACE-vollständig Acta Informatica. ,vol. 15, pp. 167- 191 ,(1981) , 10.1007/BF00288964
Aaron Bakst, Martin Gardner, The Second Scientific American Book of Mathematical Puzzles and Diversions. The American Mathematical Monthly. ,vol. 69, pp. 455- ,(1962) , 10.2307/2312171
David Gale, The Game of Hex and the Brouwer Fixed-Point Theorem American Mathematical Monthly. ,vol. 86, pp. 818- 827 ,(1979) , 10.1080/00029890.1979.11994922
Richard M. Karp, Reducibility Among Combinatorial Problems Journal of Symbolic Logic. ,vol. 40, pp. 219- 241 ,(2010) , 10.1007/978-3-540-68279-0_8
Michael N. Bleicher, Donald W. Crowe, Anatole Beck, Excursions into Mathematics ,(1969)
Vadim V. Anshelevich, A hierarchical approach to computer Hex Artificial Intelligence. ,vol. 134, pp. 101- 120 ,(2002) , 10.1016/S0004-3702(01)00154-0
S. Reisch, Hex ist PSPACE-vollstadig Acta Infomatica. ,vol. 15, pp. 167- 191 ,(1981)