Monte Carlo Tree Search in Hex
Authors:
- 19 August 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Intelligence and AI in Games
- Vol. 2 (4) , 251-258
Abstract
Hex, the classic board game invented by Piet Hein in 1942 and independently by John Nash in 1948, has been a domain of AI research since Claude Shannon's seminal work in the 1950s. Until the Monte Carlo Go revolution a few years ago, the best computer Hex players used knowledge-intensive alpha-beta search. Since that time, strong Monte Carlo Hex players have appeared that are on par with the best alpha-beta Hex players. In this paper, we describe MoHex, the Monte Carlo tree search Hex player that won gold at the 2009 Computer Olympiad. Our main contributions to Monte Carlo tree search include using inferior cell analysis and connection strategy computation to prune the search tree. In particular, we run our random game simulations not on the actual game position, but on a reduced equivalent board.Keywords
This publication has 11 references indexed in Scilit:
- Solving Hex: Beyond Humans2011
- Hex, Braids, the Crossing Rule, and XH-SearchLecture Notes in Computer Science, 2010
- Monte-Carlo Tree Search Solver2008
- Probing the 4-3-2 Edge Template in Hex2008
- Combining online and offline knowledge in UCT2007
- Hex and combinatoricsDiscrete Mathematics, 2006
- Solving 7×7 Hex with domination, fill-in, and virtual connectionsTheoretical Computer Science, 2005
- An Extension of the H-Search Algorithm for Artificial Hex PlayersLecture Notes in Computer Science, 2004
- A hierarchical approach to computer HexArtificial Intelligence, 2001
- Computers and AutomataProceedings of the IRE, 1953