Using Payoff-Similarity to Speed Up Search

Furtak, Timothy; Buro, Michael

doi:10.5591/978-1-57735-516-8/IJCAI11-097

Using Payoff-Similarity to Speed Up Search

Timothy Furtak, Michael Buro

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 534-538.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-097

Abstract

Transposition tables are a powerful tool in search domains for avoiding duplicate effort and for guiding node expansions. Traditionally, however, they have only been applicable when the current state is exactly the same as a previously explored state. We consider a generalized transposition table, whereby a similarity metric that exploits local structure is used to compare the current state with a neighbourhood of previously seen states. We illustrate this concept and forward pruning based on function approximation in the domain of Skat, and show that we can achieve speedups of 16+ over standard methods.

Timothy Furtak, and Michael Buro. 2011. Using Payoff-Similarity to Speed Up Search. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 534–538. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-097

@inproceedings{ijcai2011p97,
  title     = {Using Payoff-Similarity to Speed Up Search},
  author    = {Furtak, Timothy and Buro, Michael},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {534--538},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-097},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-097},
}

TY  - CPAPER
TI  - Using Payoff-Similarity to Speed Up Search
AU  - Furtak, Timothy
AU  - Buro, Michael
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 534
EP  - 538
DO  - 10.5591/978-1-57735-516-8/IJCAI11-097
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-097
ER  -