Optimised Playout Implementations for the Ludii General Game System

• URL: http://arxiv.org/abs/2111.02839v1
• Date: Thu, 4 Nov 2021 12:59:53 GMT
• Title: Optimised Playout Implementations for the Ludii General Game System
• Authors: Dennis J. N. J. Soemers and \'Eric Piette and Matthew Stephenson and Cameron Browne
• Abstract summary: The Ludii general game system can automatically infer, based on a game's description in its general game description language, whether any optimised implementations are applicable. An empirical evaluation demonstrates major speedups over a standard implementation, with a median result of running playouts 5.08 times as fast, over 145 different games in Ludii.
• Score: 8.344476599818828
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper describes three different optimised implementations of playouts, as commonly used by game-playing algorithms such as Monte-Carlo Tree Search. Each of the optimised implementations is applicable only to specific sets of games, based on their rules. The Ludii general game system can automatically infer, based on a game's description in its general game description language, whether any optimised implementations are applicable. An empirical evaluation demonstrates major speedups over a standard implementation, with a median result of running playouts 5.08 times as fast, over 145 different games in Ludii for which one of the optimised implementations is applicable.

Related papers

• A General Framework for User-Guided Bayesian Optimization [51.96352579696041]
  We propose ColaBO, the first Bayesian-principled framework for prior beliefs beyond the typical kernel structure. We empirically demonstrate ColaBO's ability to substantially accelerate optimization when the prior information is accurate, and to retain approximately default performance when it is misleading.
  arXiv  Detail & Related papers  (2023-11-24T18:27:26Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  We introduce an alternative framework for decision-time planning that is not based on solving subgames, but rather on update equivalence. We derive a provably sound search algorithm for fully cooperative games based on mirror descent and a search algorithm for adversarial games based on magnetic mirror descent.
  arXiv  Detail & Related papers  (2023-04-25T20:28:55Z)
• Spatial State-Action Features for General Games [5.849736173068868]
  We formulate a design and efficient implementation of spatial state-action features for general games. These are patterns that can be trained to incentivise or disincentivise actions based on whether or not they match variables of the state in a local area. We propose an efficient approach for evaluating active features for any given set of features.
  arXiv  Detail & Related papers  (2022-01-17T13:34:04Z)
• General Game Heuristic Prediction Based on Ludeme Descriptions [8.344476599818828]
  This paper investigates the performance of different general-game-playings for games in the Ludii general game. We train several regression learning models to predict the performance of these systems based on each game's description file.
  arXiv  Detail & Related papers  (2021-05-26T21:17:47Z)
• Portfolio Search and Optimization for General Strategy Game-Playing [58.896302717975445]
  We propose a new algorithm for optimization and action-selection based on the Rolling Horizon Evolutionary Algorithm. For the optimization of the agents' parameters and portfolio sets we study the use of the N-tuple Bandit Evolutionary Algorithm. An analysis of the agents' performance shows that the proposed algorithm generalizes well to all game-modes and is able to outperform other portfolio methods.
  arXiv  Detail & Related papers  (2021-04-21T09:28:28Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Deep Learning for General Game Playing with Ludii and Polygames [8.752301343910775]
  Combinations of Monte-Carlo tree search and Deep Neural Networks, trained through self-play, have produced state-of-the-art results for automated game-playing in many board games. This paper describes the implementation of a bridge between Ludii and Polygames, which enables Polygames to train and evaluate models for games that are implemented and run through Ludii.
  arXiv  Detail & Related papers  (2021-01-23T19:08:33Z)
• Ludii Game Logic Guide [7.444673919915048]
  Ludii is a general game system that can be used to play a wide variety of games. This report explains how general game states and equipment are represented in Ludii.
  arXiv  Detail & Related papers  (2021-01-06T16:22:37Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• Efficient Reasoning in Regular Boardgames [2.909363382704072]
  We present the technical side of reasoning in Regular Boardgames (RBG) language. RBG serves as a research tool that aims to aid in the development of generalized algorithms for knowledge inference, analysis, generation, learning, and playing games.
  arXiv  Detail & Related papers  (2020-06-15T11:42:08Z)
• Learning Dynamic Belief Graphs to Generalize on Text-Based Games [55.59741414135887]
  Playing text-based games requires skills in processing natural language and sequential decision making. In this work, we investigate how an agent can plan and generalize in text-based games using graph-structured representations learned end-to-end from raw text.
  arXiv  Detail & Related papers  (2020-02-21T04:38:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.