Opponent Model Search incorporates asymmetric search and evaluation techniques considering the peculiarities of an opponent, which requires explicit knowledge or assumption, and includes a model on how the opponent evaluates positions. Naive approaches in computer chess tournaments are opening book preparation and contempt. Some chess programs, notably Psion[1] , its successor Chess Genius[2] , and KnightCap[3] , apply asymmetric evaluation and search, for instance to extend when the own side is in trouble but not the opponent. Other programs, like Crafty, can be adapted asymmetric for playing human chess players, specially anti-computerchess specialists, for instance to reduce the program's tendency to trade material and to avoid blocked positions with a high rammed pawn versus lever ratio. Ed Schröder proposed to reward own hanging pieces to encourage complicated, tactical play versus humans, and to keep opponents under time pressure in playing immediate ponder hits[4] . Programs may tune and learn feature vectors and their respective weights to maximize result scores against certain opponents as well.
In the late 80s, Deep Thought co-developer Peter Jansen investigated dynamic features of a standard search algorithm to asses the difficulty of a chess position, which were used to classify human errors into several types of mistakes [7] . In his 1992 Ph.D. thesis Using Knowledge about the Opponent in Game-Tree Search[8] , Jansen elaborates on opponent modeling, specially in KQKR, relaxing Shannon's assumptions of symmetry, identity and optimality, where he mentioned the paradox in computer chess, when a program gives material to avoid mate which could not possibly found by the opponent.
Cross-Disciplinary Aspects
In his essay "Too clever is dumb" – Kleine Philosophie des Schwindelns,Roland Stuckardt (2017) investigates speculative play from a cross-disciplinary perspective of chess, game theory, strategic decision making, philosophy, and literature, elucidating that always choosing the objectively best move (in chess as well as in everyday’s social interactions) might yield suboptimal outcomes, and that „knowing your enemy“ – as the prerequisite for successful (algorithmic as well as human) swindles – has in fact been long known to be the appropriate guiding principle in diverse scenarios of imperfect knowledge, dating back to the Chinese General and philosopher Sun Tsu around 500 BCE.
Carmel and Markovitch introduced M* [9] , a generalization of minimax that uses an arbitrary opponent model to simulate the opponent’s search, and further proved a sufficient condition for pruning and present the αβ* algorithm which returns the M* value of a tree while searching only necessary branches [10] . Gao et al. researched on a generalization of opponent model search, called (D, d)-OM search, where D stands for the depth of search by the player and d for the opponent’s depth of search [11] . The Probabilistic Opponent-Model Search (PrOM) for several game domains was developed by Donkers, Uiterwijk and Van den Herik, published in 2000 [12] . It uses an extended model that includes uncertainty of the opponent.
Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2002). Learning Opponent-Type Probabilities for PrOM Search. Proceedings of the 14th Dutch-Belgian Artificial Intelligence Conference (BNAIC 2002 )(eds. H. Blockeel and M. Denecker), pp. 91-98. Leuven, Belgium.
Jeroen Donkers (2004) Opponent Models and Knowledge Symmetry in Game Tree Search. Proceedings of the First Knowledge and Games Workshop. University of Liverpool, pdf
Jeroen Donkers, Jaap van den Herik, Jos Uiterwijk, (2004). Probabilistic Opponent-Model Search in Bao. International Conference on Entertainment Computing - ICEC 2004. LNCS 3166, Springer, Berlin. pp. 409-419. pdf
Table of Contents
Speculative Play
In the late 80s, Deep Thought co-developer Peter Jansen investigated dynamic features of a standard search algorithm to asses the difficulty of a chess position, which were used to classify human errors into several types of mistakes [7] . In his 1992 Ph.D. thesis Using Knowledge about the Opponent in Game-Tree Search [8] , Jansen elaborates on opponent modeling, specially in KQKR, relaxing Shannon's assumptions of symmetry, identity and optimality, where he mentioned the paradox in computer chess, when a program gives material to avoid mate which could not possibly found by the opponent.Cross-Disciplinary Aspects
In his essay "Too clever is dumb" – Kleine Philosophie des Schwindelns, Roland Stuckardt (2017) investigates speculative play from a cross-disciplinary perspective of chess, game theory, strategic decision making, philosophy, and literature, elucidating that always choosing the objectively best move (in chess as well as in everyday’s social interactions) might yield suboptimal outcomes, and that „knowing your enemy“ – as the prerequisite for successful (algorithmic as well as human) swindles – has in fact been long known to be the appropriate guiding principle in diverse scenarios of imperfect knowledge, dating back to the Chinese General and philosopher Sun Tsu around 500 BCE.Further Research
Opponent Model search was further investigated by various game researchers, such as David Carmel, Shaul Markovitch, Xinbo Gao, Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik, Bob Herschberg, Jeroen Donkers, Pieter Spronck and Sander Bakkes.Carmel and Markovitch introduced M* [9] , a generalization of minimax that uses an arbitrary opponent model to simulate the opponent’s search, and further proved a sufficient condition for pruning and present the αβ* algorithm which returns the M* value of a tree while searching only necessary branches [10] . Gao et al. researched on a generalization of opponent model search, called (D, d)-OM search, where D stands for the depth of search by the player and d for the opponent’s depth of search [11] . The Probabilistic Opponent-Model Search (PrOM) for several game domains was developed by Donkers, Uiterwijk and Van den Herik, published in 2000 [12] . It uses an extended model that includes uncertainty of the opponent.
See also
Publications
BCE ...
1980 ...
1990 ...
1995 ...
2000 ...
2005 ...
2015 ...
Forum Posts
External Links
References
What links here?
Up one level