Monte Carlo Tree Search in Hex

Author

Arneson, Broderick ; Hayward, Ryan B. ; Henderson, Philip

Author_Institution

Dept. of Comput. Sci., Univ. of Alberta, Edmonton, AB, Canada

Volume

2

Issue

4

fYear

2010

Firstpage

251

Lastpage

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

Monte Carlo methods; artificial intelligence; computer games; tree searching; AI research; Claude Shannon´s seminal work; John Nash; MoHex; Monte Carlo tree search; Piet Hein; classic board game; computer olympiad; connection strategy computation; inferior cell analysis; knowledge-intensive alpha-beta search; random game simulations; Computational modeling; Decision trees; Games; Monte Carlo methods; Simulation; Artificial intelligence; Hex; computational and artificial intelligence; computational intelligence; games;

fLanguage

English

Journal_Title

Computational Intelligence and AI in Games, IEEE Transactions on

Publisher

ieee

ISSN

1943-068X

Type

jour

DOI

10.1109/TCIAIG.2010.2067212

Filename

5551182