Monte Carlo tree search in lines of action

Mark H.M. Winands, Yngvi Björnsson, Jahn Takeshi Saito

Research output: Contribution to journalArticlepeer-review

46 Citations (Scopus)

Abstract

The success of Monte Carlo tree search (MCTS) in many games, where αβ-based search has failed, naturally raises the question whether Monte Carlo simulations will eventually also outperform traditional game-tree search in game domains where αβ -based search is now successful. The forte of αβ-based search are highly tactical deterministic game domains with a small to moderate branching factor, where efficient yet knowledge-rich evaluation functions can be applied effectively. In this paper, we describe an MCTS-based program for playing the game Lines of Action (LOA), which is a highly tactical slow-progression game exhibiting many of the properties difficult for MCTS. The program uses an improved MCTS variant that allows it to both prove the game-theoretical value of nodes in a search tree and to focus its simulations better using domain knowledge. This results in simulations superior in both handling tactics and ensuring game progression. Using the improved MCTS variant, our program is able to outperform even the world's strongest αβ-based LOA program. This is an important milestone for MCTS because the traditional game-tree search approach has been considered to be the better suited for playing LOA.

Original languageEnglish
Article number5523941
Pages (from-to)239-250
Number of pages12
JournalIEEE Transactions on Computational Intelligence and AI in Games
Volume2
Issue number4
DOIs
Publication statusPublished - Dec 2010

Bibliographical note

Funding Information:
Manuscript received March 15, 2010; revised June 08, 2010; accepted July 14, 2010. Date of publication July 26, 2010; date of current version January 19, 2011. This work was supported in part by the NWO Go for Go project under Grant 612.066.409 and by a grant from The Icelandic Centre for Research (RANNIS).

Other keywords

  • Game-tree solver
  • Lines of Action (LOA)
  • Monte Carlo tree search (MCTS)

Fingerprint

Dive into the research topics of 'Monte Carlo tree search in lines of action'. Together they form a unique fingerprint.

Cite this