Construction d'un joueur artificiel pour Tetris

Christophe Thiery, Bruno ScherrerRev. d'Intelligence Artif 2009 · DOI

TL;DR

This paper tackles the challenge of creating a high-performing Tetris AI by exploring the cross-entropy method for optimizing evaluation functions. The authors demonstrate that by combining carefully selected features with this optimization technique, they can achieve state-of-the-art performance, significantly outperforming previous Tetris bots.

What Problem Does This Paper Address?

Creating an effective AI for games like Tetris is a complex problem. Tetris, despite its simple appearance, presents a significant challenge due to the vast number of possible game states and the inherent randomness of piece generation. Comparing the performance of different AI agents is also tricky, as scores can vary wildly, and subtle implementation details can have a large impact. Previous research has focused on designing "evaluation functions" that assign a score to a given game state, aiming to guide the AI towards better decisions. However, finding the optimal set of features (or "base functions") and their corresponding weights for these evaluation functions has been a persistent challenge.

Methods

The core of this paper lies in applying and refining the cross-entropy method for optimizing the weights of Tetris AI's evaluation functions. The cross-entropy method is an iterative optimization algorithm that works by maintaining a distribution of potential solutions (in this case, weight vectors) and progressively refining it to focus on better-performing solutions.

Key aspects of their approach include:

  • Feature Engineering: The authors leverage existing feature sets from prior work (e.g., Bertsekas and Tsitsiklis) and introduce their own novel features, such as "hole depth" and "lines with holes," to better capture important game dynamics.
  • Cross-Entropy Method: This iterative process involves:
  • Generating a set of candidate weight vectors from a Gaussian distribution.
  • Evaluating each candidate by playing a Tetris game with it.
  • Selecting the top-performing candidates.
  • Updating the Gaussian distribution to better represent these high-performing candidates.
  • Noisy Cross-Entropy: A crucial addition is the use of "noise" in the cross-entropy method. This noise, added to the variance of the distribution, helps prevent the algorithm from converging too quickly to a suboptimal solution and encourages exploration. They investigate different noise strategies (constant, linearly decreasing, and no noise).
  • Tetris Simplification: For most experiments, they use a simplified version of Tetris where the current piece appears at the desired drop location, simplifying the decision-making process.

Datasets

The paper does not introduce new datasets for training. Instead, it uses the game of Tetris itself as the benchmark. They evaluate their AI on two configurations:

  • Standard 10x20 grid: This is the commonly used configuration in Tetris research.
  • 10x16 grid: This smaller grid is used to provide a lower bound on performance for the original Tetris game, which is more difficult due to the piece-by-piece movement.

Key Insights and Ideas

  • Subtle Implementation Details Matter: The authors highlight that seemingly minor differences in game rules or AI implementation can drastically affect performance scores, making direct comparisons between studies challenging.
  • Noise is Crucial for Cross-Entropy: Introducing noise into the cross-entropy method significantly improves the performance of the Tetris AI, preventing premature convergence and leading to better final results.
  • Feature Engineering is Key: The performance of the AI is highly dependent on the quality of the features used in the evaluation function. Their novel features, like "hole depth," proved to be highly effective.
  • Combining Expertise and Optimization: The most successful approach was to combine expert-designed features (from Dellacherie) with an automated optimization method (cross-entropy) to find the optimal weights.
  • Simplicity Can Be Better: Their best-performing AI (DN) uses a relatively small set of features (8) compared to some other approaches, suggesting that a well-chosen, concise set of features can be more effective than a large, potentially redundant one.

Key Results

  • The authors' best Tetris AI (DN), using their novel features and the cross-entropy method with constant noise, achieved an average score of 35,000,000 ± 20% lines on the standard 10x20 Tetris grid. This significantly outperforms previous state-of-the-art results.
  • On the simplified 10x16 grid, their AI achieved 910,000 ± 5% lines, which serves as a lower bound for its performance on the more difficult original Tetris.
  • They found that a constant noise strategy in the cross-entropy method was more reliable than a linearly decreasing noise strategy for achieving consistent high performance.
  • Their novel features ("hole depth" and "lines with holes") had a significant positive impact on performance.

Limitations and Future Work

  • Computational Cost: Evaluating AI performance requires playing a large number of games, which is computationally intensive. The authors suggest exploring ways to reduce this cost, such as using smaller game grids for training or estimating game duration from early moves.
  • Noise Strategy Refinement: While constant noise proved effective, they suggest exploring other noise decay strategies, like geometric decay, to potentially improve convergence.
  • More Complex Features: The authors propose investigating more complex or expressive feature functions, potentially drawing from other Tetris AI research or using techniques like genetic programming for automatic feature discovery.
  • Alternative Optimization: They are currently investigating the CMA-ES (Covariance Matrix Adaptation Evolution Strategy) algorithm as an alternative to the cross-entropy method, as it offers a more expressive search space for the distribution.

Summary updated

BibTeX
@article{thiery2009construction,
  author = {Christophe Thiery and Bruno Scherrer},
  title = {{Construction d'un joueur artificiel pour Tetris}},
  journal = {Rev. d'Intelligence Artif.},
  year = {2009},
  doi = {10.3166/ria.23.387-407},
}
Figure