Spatial state-action features for general games
From MaRDI portal
Abstract: In many board games and other abstract games, patterns have been used as features that can guide automated game-playing agents. Such patterns or features often represent particular configurations of pieces, empty positions, etc., which may be relevant for a game's strategies. Their use has been particularly prevalent in the game of Go, but also many other games used as benchmarks for AI research. In this paper, 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 around action variables. We provide extensive details on several design and implementation choices, with a primary focus on achieving a high degree of generality to support a wide variety of different games using different board geometries or other graphs. Secondly, we propose an efficient approach for evaluating active features for any given set of features. In this approach, we take inspiration from heuristics used in problems such as SAT to optimise the order in which parts of patterns are matched and prune unnecessary evaluations. This approach is defined for a highly general and abstract description of the problem -- phrased as optimising the order in which propositions of formulas in disjunctive normal form are evaluated -- and may therefore also be of interest to other types of problems than board games. An empirical evaluation on 33 distinct games in the Ludii general game system demonstrates the efficiency of this approach in comparison to a naive baseline, as well as a baseline based on prefix trees, and demonstrates that the additional efficiency significantly improves the playing strength of agents using the features to guide search.
Recommendations
Cites work
- A Computing Procedure for Quantification Theory
- A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play
- A Greedy Heuristic for the Set-Covering Problem
- A machine program for theorem-proving
- Classification with costly features as a sequential decision-making problem
- Computer Go
- Deep Blue
- Finite-time analysis of the multiarmed bandit problem
- Hex strategy: making the right connections
- scientific article; zbMATH DE number 3713199 (Why is no real title available?)
- scientific article; zbMATH DE number 1196641 (Why is no real title available?)
- scientific article; zbMATH DE number 2143606 (Why is no real title available?)
- scientific article; zbMATH DE number 956861 (Why is no real title available?)
- MoHex 2.0: a pattern-based MCTS hex player
- On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other
- Optimizing Expert Systems: Heuristics for Efficiently Generating Low-Cost Information Acquisition Strategies
- Reducibility among combinatorial problems
- Reinforcement learning. An introduction
- Solving propositional satisfiability problems
- Stochastic Dominance and Expected Utility: Survey and Analysis
This page was built for publication: Spatial state-action features for general games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6108764)
