Affordable Access

Publisher Website

Probabilistic opponent-model search

Information Sciences
Publication Date
DOI: 10.1016/s0020-0255(01)00133-5
  • Games
  • Heuristic Search
  • Opponent Modelling
  • Subjective Probability
  • Loa
  • Computer Science


Abstract A new approach for heuristic game-tree search, probabilistic opponent-model search (PrOM search), is proposed. It is based on standard opponent-model search (OM search). The new approach takes into account a multiple-opponent model. It incorporates uncertainty which mimics the uncertainty of a player about the behaviour of the opponent. Some theoretical results on PrOM search are derived. Implementations of both OM and PrOM search (both with β-passing) are presented and best-case analyses are given. To investigate the computational efficiency, experiments are performed on random game trees. PrOM search appears to lead to serious computational costs when the search depth increases. To test the effectiveness of OM and PrOM search in practice, three tournaments in the game of LOA are performed. The tournaments suggest that PrOM search is more effective than α– β search when search trees of the same depth are used. The tournaments also show that OM search performs not very good and sometimes even disastrous. In spite of the computational costs, the encouraging results of the tournaments and the opportunity that PrOM search offers for actual opponent modelling during the search makes PrOM search a viable alternative to minimax-based search algorithms.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Admissibility in opponent-model search

on Information Sciences Jan 01, 2003

Selecting evaluation functions in Opponent-Model s...

on Theoretical Computer Science Jan 01, 2005

Strategies anticipating a difference in search dep...

on Theoretical Computer Science Jan 01, 2001
More articles like this..