Temperature Discovery Search

TO DO: this needs to be extended with examples, and ideas for future work.

Temperature Discovery Search (TDS) is a minimax- based game tree search method designed to compute or approximate the temperature of a combinatorial game. TDS is based on Berlekamp's concept of an enriched environment, where a combinatorial game G is embedded in an environment consisting of a large set of simple "switch" games of decreasing temperature.

Optimal play starts in the environment, but eventually must switch to G. TDS finds the temperature of G by determining the lowest possible temperature at which this switch must happen in order to preserve the minimax score.

Both exact and heuristic versions of TDS are described and evaluated experimentally. In experiments with sum games in Amazons, TDS greatly outperforms a full board alphabeta searcher.


TDS+ is a strongly improved version of the TDS algorithm, with five enhancements.


Y. Zhang. TDS+: Improving Temperature Discovery Search. MSc thesis, University of Alberta, 2014.

Y. Zhang and M. Müller. TDS+: Improving Temperature Discovery Search. AAAI 2015, pages 1241-1247.

M. Müller, M. Enzenberger, and J. Schaeffer. Temperature discovery search. AAAI 2004, pages 658-663, San Jose, CA, 2004.

Created on: Jun 19, 2009 Last modified: May 18, 2015

Martin Müller