Developments on Product Propagation

Abdallah Saffidine, Tristan Cazenave, Lamsade Université Paris-dauphine2016

TL;DR

This paper introduces and evaluates Product Propagation (PP), an algorithm for solving abstract two-player games. The authors demonstrate that PP, especially with extensions for handling transpositions and reducing memory usage, can outperform established algorithms like Alpha-Beta search and Monte Carlo Tree Search in specific game domains.

What Problem Does This Paper Address?

The paper tackles the challenge of efficiently solving abstract two-player games, a fundamental problem in artificial intelligence and game theory. While algorithms like Alpha-Beta search and Proof Number Search (PNS) are well-established, they have limitations. The authors propose Product Propagation (PP) as a novel approach that, by backing up probabilistic evaluations, offers an alternative to traditional minimaxing and can potentially overcome some of its pathologies. They aim to show that PP, particularly with practical improvements, can be a competitive or even superior algorithm for game solving in certain scenarios.

Methods

The core of the paper revolves around the Product Propagation (PP) algorithm. PP associates a "probability propagation number" (PPN) to each node in a game tree, representing the likelihood of a win for one player. The PPN is calculated based on the PPNs of its children, using a product rule for Min nodes and a related rule for Max nodes, assuming independence.

The authors also introduce several practical improvements and extensions to PP:

  • Mobility Heuristic: A more sophisticated initialization for non-terminal leaves, which considers the number of legal moves.
  • PP2 Algorithm: An adaptation inspired by PN2, which uses a bound on the number of nodes for sub-searches to manage memory consumption and improve efficiency.
  • Transpositions: The paper implicitly discusses the importance of transpositions (handling repeated game states) for improving performance, particularly in the context of DOMINEERING.

The paper compares PP and its variants against established algorithms like Alpha-Beta search (αβ), Proof Number Search (PNS), and Monte Carlo Tree Search (MCTS), including a variant called MCTS-E (using evaluation functions instead of random playouts).

Datasets

The paper evaluates the algorithms on three specific games:

  • Y: A game played on a triangular board with a hexagonal paving, known for its no-draw property. The experiments used 77,012 opening positions.
  • DOMINEERING: A game played on a rectangular board where players place dominoes. The experiments were conducted on 5x6, 6x6, and 7x6 board sizes.
  • NOGO: The misere version of GO, where the first player to capture loses. Experiments were performed on various board sizes, including 4x4, 18x1, 20x1, and 22x1.

No new benchmarks were introduced; the focus was on evaluating existing algorithms on established game domains.

Key Insights and Ideas

  • PP's Probabilistic Foundation: The core idea of backing up probabilistic evaluations, even with the simplifying assumption of independence, proves surprisingly effective in game solving. This offers a different perspective compared to deterministic game tree search.
  • PP's Domain-Specific Strengths: While PP might not universally outperform other algorithms, it demonstrates significant advantages in specific domains like Y and DOMINEERING, suggesting that its probabilistic approach is well-suited for certain game structures.
  • Importance of Practical Improvements: The extensions to PP, particularly PP2 for memory management and the implicit handling of transpositions, are crucial for making it competitive with highly optimized classical algorithms. This highlights that algorithmic elegance needs to be paired with practical engineering.
  • Trade-offs in Game Solving: The results for Y suggest a trade-off between time and iteration efficiency. PP is faster overall, while MCTS might require fewer iterations but takes longer per iteration, making PP preferable when time is the primary constraint.

Key Results

  • Game of Y: PP solved 77,010 out of 77,012 positions within 60 seconds. For 68,477 of these positions, PP was the fastest algorithm.
  • DOMINEERING: For the 6x6 board, PPT (PP with transpositions) was the best algorithm by far. On the 7x6 board, PPT outperformed both αβ and PN2, even when other algorithms ran out of memory.
  • NOGO: For NOGO, PP variants outperformed PNS variants on all tested sizes. αβ was better on standard sizes, but PPT became competitive on N x 1 boards for N > 18.

Limitations and Future Work

  • Independence Assumption: The paper acknowledges that the independence assumption used in PP's PPN calculation is not formally justified and often incorrect in practice. However, it is retained due to its simplicity and effectiveness.
  • Non-Optimized Implementations: The authors emphasize that they used generic, non-optimized implementations of PP and its competitors. This suggests that further optimization could yield even better results.
  • Future Work: The authors suggest adapting PP to handle multiple-outcome games (beyond two-outcome games) and exploring more elaborate schemes for transpositions to further enhance its performance. They also note the potential for adapting ideas from Multiple-Outcome PNS to PP for more general games.

Summary updated

Abstract

Product Propagation (PP) is an algorithm to backup proba-bilistic evaluations for abstract two-player games. It was shown that PP could solve go problems as efficiently as Proof Number Search (PNS). In this paper, we exhibit a few domains where, for generic non-optimized versions, PP performs better than previously known algorithms for solv-ing games. The compared approaches include alpha-beta search, PNS, and Monte Carlo Tree Search. We also extend PP to deal with its mem-ory consumption and to improve its solving time. 1
BibTeX
@misc{saffidine2016developments,
  author = {Abdallah Saffidine and Tristan Cazenave and Lamsade Université Paris-dauphine},
  title = {{Developments on Product Propagation}},
  year = {2016},
}
Figure