Learning of Resource Allocation Strategies for Game Playing

TL;DR

This paper tackles the under-explored problem of how game-playing AI should strategically allocate its limited computational resources (like search time) across different moves. They introduce a framework for learning "semi-dynamic" strategies that adapt resource allocation based on the current board state, demonstrating that such learned strategies can improve performance in checkers.

What Problem Does This Paper Address?

In complex games like Chess or Checkers, players don't spend equal time on every move. Crucial or complex positions demand more "thinking" time (resource allocation), while simpler ones can be handled quickly. This strategic allocation of resources significantly impacts game-playing quality. While much research focuses on which move to make (e.g., minimax, alpha-beta pruning), less attention has been paid to how much effort to invest in finding that move. This paper aims to bridge this gap by developing a method to automatically learn effective resource allocation strategies for game-playing AI.

Methods

The authors propose a framework for learning "semi-dynamic" resource allocation strategies. These strategies decide how much resource to allocate before each move calculation begins, but unlike "static" strategies, they can use information about the current board state. They frame this learning problem as a classification task: for a given board state, the AI needs to classify whether it should invest extra resources (a "positive" class) or not (a "negative" class).

Key methodological components include:

  • Strategy Types: They categorize strategies into static (pre-game allocation), semi-dynamic (per-move, board-dependent), and dynamic (can update mid-search). This work focuses on semi-dynamic.
  • Learning Framework: The core idea is to generate training examples by having a game-playing program play against itself. For each board encountered, they determine a "correct" resource allocation decision (the class) by comparing the outcome of a deeper search (e.g., depth k+n) versus a shallower search (depth k). If the deeper search yields a significantly better move, the board is labeled "positive."
  • Feature Extraction: Boards are represented by features (e.g., piece advantage, center control). They acknowledge the challenge of selecting relevant, cheap-to-compute features and mention using feature selection algorithms like RELIEF.
  • Classification Algorithm: They use a decision tree algorithm (a variant of ID3) to learn the classification rules from the generated examples.
  • Probabilistic Decision Trees: To address the issue of varying available resources, they extend their approach using probabilistic decision trees. This allows the strategy to be more or less selective based on the remaining search depth and number of moves left in the game.

Datasets

Not discussed in the paper. The paper describes generating training examples by having two instances of the game-playing program play against each other. The evaluation is done by measuring performance improvements in checkers.

Key Insights and Ideas

  • Resource Allocation is Crucial: The paper highlights that how an AI allocates its search effort is as important as the search algorithm itself for achieving strong performance.
  • Semi-Dynamic Strategies Offer a Sweet Spot: They strike a balance between the simplicity of static strategies and the computational cost of dynamic ones, making them practical for game AI.
  • Learning from Self-Play is Effective: Generating training data by having the AI play against itself is a viable method for creating realistic board states and determining optimal resource allocation decisions.
  • Decision Trees are Suitable Classifiers: Decision trees are computationally efficient for classifying board states, making them a good fit for real-time game-playing decisions.
  • Probabilistic Adaptation: The use of probabilistic decision trees allows the learned strategy to adapt its selectivity based on the overall resource budget remaining in the game, leading to more nuanced allocation.

Key Results

The paper reports that their implemented method, applied to the game of Checkers, was able to learn semi-dynamic strategies that improve game-playing performance. While specific quantitative improvements (e.g., win rate increase, Elo rating gain) are not detailed in the provided text, the authors state that experimental results demonstrate the effectiveness of their learned strategies.

Limitations and Future Work

  • Domain Specificity: While the framework is presented as general, the feature extraction and evaluation function are domain-specific (checkers). Extending this to other games would require adapting these components.
  • Feature Engineering: The paper acknowledges that feature selection is non-trivial and that ideally, features could be generated automatically (constructive induction).
  • Opponent Modeling: The current research does not consider opponent modeling, which human players often use to adjust their resource allocation (e.g., reacting to unexpected moves).
  • Future Work: The authors suggest exploring constructive induction for feature generation and incorporating opponent modeling into the resource allocation strategy. They also note the potential for using continuous class assignment algorithms if a more fine-grained utility measure is desired.

Summary updated

BibTeX
@inproceedings{1993learning,
  title = {{Learning of Resource Allocation Strategies for Game Playing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure