TDS+: Improving Temperature Discovery Search

Authors

  • Yeqin Zhang University of Alberta
  • Martin Müller University of Alberta

DOI:

https://doi.org/10.1609/aaai.v29i1.9363

Keywords:

Temperature Discovery Search, TDS , combinatorial game theory, sum games, game tree search, Amazons

Abstract

Temperature Discovery Search (TDS) is a forward search method for computing or approximating the temperature of a combinatorial game. Temperature and mean are important concepts in combinatorial game theory, which can be used to develop efficient algorithms for playing well in a sum of subgames. A new algorithm TDS+ with five enhancements of TDS is developed, which greatly speeds up both exact and approximate versions of TDS. Means and temperatures can be computed faster, and fixed-time approximations which are important for practical play can be computed with higher accuracy than before.

Downloads

Published

2015-02-16

How to Cite

Zhang, Y., & Müller, M. (2015). TDS+: Improving Temperature Discovery Search. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9363

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization