Invited Speakers

Tristan Cazenave, Stefan EdelkampProceedings of the International Symposium on Combinatorial Search 2021 · DOI

Abstract

This document provides a summary of the invited talks presented at the Fifth Annual Symposium on Combinatorial Search (SoCS) held in 2012. The presentations by Tristan Cazenave and Stefan Edelkamp explore the frontiers of Monte-Carlo Tree Search in single-agent domains and the engineering challenges of high-performance heuristic search, respectively.

Introduction

The field of combinatorial search is characterized by a constant tension between algorithmic sophistication and computational efficiency. At the 2012 Symposium on Combinatorial Search, two keynote addresses highlighted distinct but complementary paths for the field. Tristan Cazenave discussed the adaptation of Monte-Carlo Tree Search (MCTS)—a technique popularized by its success in adversarial games—to single-agent puzzles and optimization. Simultaneously, Stefan Edelkamp addressed the practical engineering required to scale heuristic search to modern hardware, revealing surprising insights into the trade-offs between heuristic complexity and raw search speed.

Monte-Carlo Tree Search for Single-Agent Domains

Tristan Cazenave’s research addresses the challenge of applying probabilistic, simulation-based search to domains that lack an opponent. While MCTS revolutionized two-player games like Go by using random simulations to evaluate board states, its application to single-agent tasks requires a shift in perspective. In these domains, the "move" does not face a counter-move but must still navigate a massive state space to find an optimal or high-quality solution.

A primary method introduced for these tasks is Nested Monte-Carlo Search. By nesting the search process, the algorithm can discover complex sequences and mathematical formulas that standard MCTS might overlook in a non-adversarial setting. This approach allows the search to effectively "look deeper" into the state space by using the results of lower-level simulations to guide higher-level decisions.

Cazenave reported successful applications of this method in several challenging areas:

  • Puzzles: Achieving high performance in Morpion Solitaire and SameGame.
  • Optimization: Solving the Traveling Salesman Problem (TSP) with time windows.
  • Scientific Discovery: Automating the discovery of complex mathematical formulas across various scientific domains.

Stefan Edelkamp’s talk shifted the focus toward the practical bottlenecks of heuristic search algorithms like A*. As problem sizes grow, the limitations of physical hardware—specifically memory and processing power—become the primary constraints. Edelkamp detailed a comprehensive "toolbox" for modern search engineering designed to overcome these hurdles.

The Search Engineering Toolbox

To achieve high performance, Edelkamp emphasized several key strategies:

  • Memory Management: Utilizing External Memory Search (using SSDs and Hard Disks) to bypass RAM limitations, supported by perfect hashing to manage state lookups efficiently.
  • Hardware Acceleration: Leveraging the parallel processing power of multi-core CPUs and GPUs to accelerate state evaluations and expansions.
  • Symbolic Representations: Using compact data structures to represent and manipulate large sets of states simultaneously.
  • Machine Learning Integration: Incorporating ML methods to refine search priorities and improve the accuracy of heuristics.

Key Insights and the Blind Search Paradox

The symposium highlighted several counterintuitive findings in the realm of optimal planning. One of the most significant insights was the Blind Search Paradox: in certain scenarios, "blind" search strategies can outperform A* search equipped with state-of-the-art heuristics. This occurs when the computational overhead of calculating a complex heuristic outweighs the benefit of the reduction in the number of states explored. This suggests that for modern, large-scale problem solving, the synergy between hardware architecture and algorithmic simplicity is often more critical than heuristic complexity alone.

Conclusion and Future Directions

The 2012 invited talks underscored that the future of combinatorial search lies in both algorithmic versatility and rigorous engineering. While Nested MCTS proves to be a powerful tool for finding "needles in haystacks" in optimization and puzzles, the engineering of search algorithms must continue to evolve to address memory latency and the effective use of parallel hardware. Future research is directed toward developing "cheaper" heuristics and better criteria for determining when to rely on complex guidance versus raw computational power.

Summary updated

Abstract

Abstracts of the invited talks presented at the Fifth Annual Symposium on Combinatorial Search held in 2012.
BibTeX
@inproceedings{cazenave2021invited,
  author = {Tristan Cazenave and Stefan Edelkamp},
  title = {{Invited Speakers}},
  booktitle = {Proceedings of the International Symposium on Combinatorial Search},
  year = {2021},
  doi = {10.1609/socs.v3i1.18229},
}
Figure