Game tree search with adaptive resolution

Hung Jui Chang, Meng-Tsung Tsai, Tsan Sheng Hsu*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In this paper, we use an adaptive resolution R to enhance the min-max search with alpha-beta pruning technique, and show that the value returned by the modified algorithm, called Negascout-with-resolution, differs from that of the original version by at most R. Guidelines are given to explain how the resolution should be chosen to obtain the best possible outcome. Our experimental results demonstrate that Negascout-with-resolution yields a significant performance improvement over the original algorithm on the domains of random trees and real game trees in Chinese chess.

Original languageEnglish
Title of host publicationAdvances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers
Pages306-319
Number of pages14
DOIs
StatePublished - 20 Aug 2012
Event13th International Conference on Advances in Computer Games, ACG 2011 - Tilburg, Netherlands
Duration: 20 Nov 201122 Nov 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Advances in Computer Games, ACG 2011
CountryNetherlands
CityTilburg
Period20/11/1122/11/11

Fingerprint Dive into the research topics of 'Game tree search with adaptive resolution'. Together they form a unique fingerprint.

  • Cite this

    Chang, H. J., Tsai, M-T., & Hsu, T. S. (2012). Game tree search with adaptive resolution. In Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers (pp. 306-319). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7168 LNCS). https://doi.org/10.1007/978-3-642-31866-5_26