Information Set Monte Carlo Tree Search

Peter I. Cowling; Edward J. Powley; Daniel Whitehouse

doi:10.1109/TCIAIG.2012.2200894

Information Set Monte Carlo Tree Search

Peter I. Cowling, Edward J. Powley, Daniel Whitehouse

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Monte Carlo tree search (MCTS) is an AI technique
that has been successfully applied to many deterministic games
of perfect information. This paper investigates the application
of MCTS methods to games with hidden information and uncertainty.
In particular, three new information set MCTS (ISMCTS)
algorithms are presented which handle different sources of hidden
information and uncertainty in games. Instead of searching minimax
trees of game states, the ISMCTS algorithms search trees of
information sets, more directly analyzing the true structure of the
game. These algorithms are tested in three domains with different
characteristics, and it is demonstrated that our new algorithms
outperform existing approaches to handling hidden information
and uncertainty in games.
Index Terms—Artificial intelligence (AI), game tree search,
hidden information, Monte Carlo methods, Monte Carlo tree
search (MCTS), uncertainty.

Original language	English
Article number	6203567
Pages (from-to)	120-143
Number of pages	24
Journal	Computational Intelligence and AI in Games, IEEE Transactions on
Volume	4
Issue number	2
DOIs	https://doi.org/10.1109/TCIAIG.2012.2200894
Publication status	Published - 2012

Access to Document

10.1109/TCIAIG.2012.2200894

Information Set Monte Carlo Tree SearchSubmitted manuscript, 2.06 MB

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6203567

Cite this

@article{53f1d1918ab1497fbb4ce101f31c038b,

title = "Information Set Monte Carlo Tree Search",

abstract = "Monte Carlo tree search (MCTS) is an AI techniquethat has been successfully applied to many deterministic gamesof perfect information. This paper investigates the applicationof MCTS methods to games with hidden information and uncertainty.In particular, three new information set MCTS (ISMCTS)algorithms are presented which handle different sources of hiddeninformation and uncertainty in games. Instead of searching minimaxtrees of game states, the ISMCTS algorithms search trees ofinformation sets, more directly analyzing the true structure of thegame. These algorithms are tested in three domains with differentcharacteristics, and it is demonstrated that our new algorithmsoutperform existing approaches to handling hidden informationand uncertainty in games.Index Terms—Artificial intelligence (AI), game tree search,hidden information, Monte Carlo methods, Monte Carlo treesearch (MCTS), uncertainty.",

author = "Cowling, {Peter I.} and Powley, {Edward J.} and Daniel Whitehouse",

year = "2012",

doi = "10.1109/TCIAIG.2012.2200894",

language = "English",

volume = "4",

pages = "120--143",

journal = "Computational Intelligence and AI in Games, IEEE Transactions on",

issn = "1943-068X",

publisher = "IEEE",

number = "2",

}

TY - JOUR

T1 - Information Set Monte Carlo Tree Search

AU - Cowling, Peter I.

AU - Powley, Edward J.

AU - Whitehouse, Daniel

PY - 2012

Y1 - 2012

N2 - Monte Carlo tree search (MCTS) is an AI techniquethat has been successfully applied to many deterministic gamesof perfect information. This paper investigates the applicationof MCTS methods to games with hidden information and uncertainty.In particular, three new information set MCTS (ISMCTS)algorithms are presented which handle different sources of hiddeninformation and uncertainty in games. Instead of searching minimaxtrees of game states, the ISMCTS algorithms search trees ofinformation sets, more directly analyzing the true structure of thegame. These algorithms are tested in three domains with differentcharacteristics, and it is demonstrated that our new algorithmsoutperform existing approaches to handling hidden informationand uncertainty in games.Index Terms—Artificial intelligence (AI), game tree search,hidden information, Monte Carlo methods, Monte Carlo treesearch (MCTS), uncertainty.

AB - Monte Carlo tree search (MCTS) is an AI techniquethat has been successfully applied to many deterministic gamesof perfect information. This paper investigates the applicationof MCTS methods to games with hidden information and uncertainty.In particular, three new information set MCTS (ISMCTS)algorithms are presented which handle different sources of hiddeninformation and uncertainty in games. Instead of searching minimaxtrees of game states, the ISMCTS algorithms search trees ofinformation sets, more directly analyzing the true structure of thegame. These algorithms are tested in three domains with differentcharacteristics, and it is demonstrated that our new algorithmsoutperform existing approaches to handling hidden informationand uncertainty in games.Index Terms—Artificial intelligence (AI), game tree search,hidden information, Monte Carlo methods, Monte Carlo treesearch (MCTS), uncertainty.

UR - http://www.scopus.com/inward/record.url?scp=84862586602&partnerID=8YFLogxK

U2 - 10.1109/TCIAIG.2012.2200894

DO - 10.1109/TCIAIG.2012.2200894

M3 - Article

SN - 1943-068X

VL - 4

SP - 120

EP - 143

JO - Computational Intelligence and AI in Games, IEEE Transactions on

JF - Computational Intelligence and AI in Games, IEEE Transactions on

IS - 2

M1 - 6203567

ER -

Information Set Monte Carlo Tree Search

Abstract

Access to Document

Other files and links

Cite this