Advertisement
Published in:
2006 | OriginalPaper | Chapter
Similarity Pruning in PrOM Search
Authors : H. (Jeroen) H. L. M. Donkers, H. Jaap van den Herik, Jos W. H. M. Uiterwijk
Published in: Advances in Computer Games
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we introduce a new pruning mechanism, called
Similarity Pruning
for Probabilistic Opponent-Model (PrOM) Search. It is based on imposing a bound on the differences between two or more evaluation functions. Assuming such a bound exists, we are able to prove two theoretical properties, viz., the bound-conservation property and the bounded-gain property. Using these properties we develop a Similarity-Pruning algorithm. Subsequently we conduct a series of experiments on random game trees to measure the efficiency of the new algorithm. The results show that Similarity Pruning increases the efficiency of PrOM search considerably.