Decaying simulation strategies

Mandy J.W. Tak, Mark H.M. Winands, Yngvi Björnsson

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

The aim of general game playing (GGP) is to create programs capable of playing a wide range of different games at an expert level, given only the rules of the game. The most successful GGP programs currently employ simulation-based Monte Carlo tree search (MCTS). The performance of MCTS depends heavily on the simulation strategy used. In this paper, we investigate the application of a decay factor for two domain-independent simulation strategies: the N-gram selection technique (NST) and the move-average sampling technique (MAST). Three decay factor methods, called move decay, batch decay, and simulation decay, are applied. Furthermore, a combination of move decay and simulation decay is also tested. The decay variants are implemented in the GGP program CadiaPlayer. Four types of games are used: turn taking, simultaneous move, one player, and multiplayer. Except for one-player games, experiments show that decaying can significantly improve the performance of both NST and MAST simulation strategies.

Original languageEnglish
Pages (from-to)395-406
Number of pages12
JournalIEEE Transactions on Computational Intelligence and AI in Games
Volume6
Issue number4
DOIs
Publication statusPublished - 1 Dec 2014

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Other keywords

  • Decay
  • general game playing (GGP)
  • Monte Carlo tree search (MCTS)
  • N-grams

Fingerprint

Dive into the research topics of 'Decaying simulation strategies'. Together they form a unique fingerprint.

Cite this