ENHANCED REALIZATION PROBABILITY SEARCH

Mark H. M. Winands () and Yngvi Björnsson ()
Additional contact information
Mark H. M. Winands: MICC-IKAT Games and AI Group, Faculty of Humanities and Sciences, Universiteit Maastricht, P.O. Box 616 6200MD Maastricht, The Netherlands
Yngvi Björnsson: School of Computer Science, Reykjavík University, Ofanleiti 2 IS-103 Reykjavík, Iceland

New Mathematics and Natural Computation (NMNC), 2008, vol. 04, issue 03, 329-342

Abstract: In this paper, we show that Realization Probability Search (RPS) significantly improves the playing strength of a world-class Lines-of-Action (LOA) computer program, even when used in combination with existing state-of-the-artαβsearch enhancements. In a 600-game match, a RPS-based version of the program defeats the original one with a winning score of 62.5%. The main contribution of the paper, however, is the introduction of a much improved variant of RPS, called Enhanced Realization Probability Search (ERPS). The new algorithm addresses two weaknesses of RPS and overcomes them by using a better focussed re-searching scheme, resulting in both more robust tactical play and reduced search overhead. Our experiments in the domain of LOA show that ERPS offers just as a significant improvement over regular RPS, as the latter improves upon regular search. More specifically, the ERPS-based variant scores 62.1% against the RPS variant, and an impressive 72.2% score against the original program. This represents an improvement of over 100 ELO points over the original state-of-the-art player.

Keywords: Search; heuristics; games (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S1793005708001070
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:nmncxx:v:04:y:2008:i:03:n:s1793005708001070

Ordering information: This journal article can be ordered from

DOI: 10.1142/S1793005708001070

Access Statistics for this article

New Mathematics and Natural Computation (NMNC) is currently edited by Paul P Wang

More articles in New Mathematics and Natural Computation (NMNC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().