Information Set Monte Carlo Tree Search

Article English OPEN
Cowling, Peter I. ; Powley, Edward J. ; Whitehouse, Daniel (2012)
  • Subject: 1712 | 2207 | 1702 | 2208
    arxiv: Computer Science::Computer Science and Game Theory

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.
  • References (41)
    41 references, page 1 of 5

    [1] S. Gelly and D. Silver, “Monte-Carlo tree search and rapid action value estimation in computer Go,” Artif. Intell., vol. 175, no. 11, pp. 1856-1875, Jul. 2011.

    [2] L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning,” in Proc. Eur. Conf. Mach. Learn., J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, Eds., Berlin, Germany, 2006, pp. 282-293.

    [3] M. L. Ginsberg, “GIB: Imperfect information in a computationally challenging game,” J. Artif. Intell. Res., vol. 14, pp. 303-358, 2001.

    [4] R. Bjarnason, A. Fern, and P. Tadepalli, “Lower bounding Klondike Solitaire with Monte-Carlo planning,” in Proc. 19th Int. Conf. Autom. Plan. Sched., Thessaloniki, Greece, 2009, pp. 26-33.

    [5] I. Frank and D. Basin, “Search in games with incomplete information: A case study using Bridge card play,” Artif. Intell., vol. 100, no. 1-2, pp. 87-123, 1998.

    [6] BoardGameGeek, Lord of the Rings: The Confrontation, 2011 [Online]. Available: http://boardgamegeek.com/boardgame/3201/lord-ofthe-rings-the-confrontation

    [7] BoardGameGeek, Stratego, 2011 [Online]. Available: http:// boardgamegeek.com/boardgame/1917/stratego

    [8] J. W. H. M. Uiterwijk and H. J. van den Herik, “The advantage of the initiative,” Inf. Sci., vol. 122, no. 1, pp. 43-58, Jan. 2000.

    [9] E. J. Powley, D. Whitehouse, and P. I. Cowling, “Determinization in Monte-Carlo tree search for the card game Dou Di Zhu,” in Proc. Artif. Intell. Simul. Behav., York, U.K., 2011, pp. 17-24.

    [10] D. Whitehouse, E. J. Powley, and P. I. Cowling, “Determinization and information set Monte Carlo tree search for the card game Dou Di Zhu,” in Proc. IEEE Conf. Comput. Intell. Games, Seoul, Korea, 2011, pp. 87-94.

  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    569
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    White Rose Research Online - IRUS-UK 0 569
Share - Bookmark