N-Grams and the Last-Good-Reply Policy Applied in General Game Playing
- 21 May 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Intelligence and AI in Games
- Vol. 4 (2) , 73-83
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 introduce improved simulation strategies for GGP that we implement and test in the GGP agent CADIAPLAYER, which won the International GGP competition in both 2007 and 2008. There are two aspects to the improvements: first, we show that a simple ϵ-greedy exploration strategy works better in the simulation play-outs than the softmax-based Gibbs measure currently used in CADIAPLAYER and, second, we introduce a general framework based on N-grams for learning promising move sequences. Collectively, these enhancements result in a much improved performance of CADIAPLAYER. For example, in our test suite consisting of five different two-player turn-based games, they led to an impressive average win rate of approximately 70%. The enhancements are also shown to be effective in multiplayer and simultaneous-move games. We additionally perform experiments with the last-good-reply policy (LGRP). The LGRP combined with N-grams is also tested. The LGRP has already been shown to be successful in Go programs and we demonstrate that it also has promise in GGP.Keywords
This publication has 11 references indexed in Scilit:
- Monte-Carlo Tree Search Enhancements for HavannahLecture Notes in Computer Science, 2012
- CadiaPlayer: Search-Control TechniquesKI - Künstliche Intelligenz, 2011
- Node-Expansion Operators for the UCT Algorithm2011
- The Power of Forgetting: Improving the Last-Good-Reply Policy in Monte Carlo GoIEEE Transactions on Computational Intelligence and AI in Games, 2010
- Combining UCT and Nested Monte Carlo Search for Single-Player General Game PlayingIEEE Transactions on Computational Intelligence and AI in Games, 2010
- Multiple Overlapping Tiles for Contextual Monte Carlo Tree SearchLecture Notes in Computer Science, 2010
- CadiaPlayer: A Simulation-Based General Game PlayerIEEE Transactions on Computational Intelligence and AI in Games, 2009
- PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCHNew Mathematics and Natural Computation, 2008
- Combining online and offline knowledge in UCT2007
- The history heuristic and alpha-beta search enhancements in practiceIEEE Transactions on Pattern Analysis and Machine Intelligence, 1989