Home * Search * Opponent Model Search
Nosce hostem.jpg

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.
Nosce hostem [5] [6]

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.

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

1980 ...

1990 ...

1995 ...

2000 ...

2005 ...

2015 ...


Forum Posts


External Links


References

  1. ^ Kaare Danielsen (1987). The 7th World Microcomputer Chess Championship, Rome, Italy, September 14-20, 1987. ICCA Journal, Vol. 10, No. 3 » WMCCC 1987
  2. ^ Genius' asymmetric-search by example: TRY yourself by Thorsten Czub, rgcc, December 30, 1997
  3. ^ asymmetry by Andrew Tridgell, rgcc, August 12, 1997
  4. ^ Re: Anti Coward Mode by Rebel, OpenChess Forum, December 22, 2013
  5. ^ Ignorant Hussy: Know your enemy
  6. ^ RomanArmyTalk :: Topic: Translation...this should be easy!
  7. ^ Peter Jansen (1990). Problematic Positions and Speculative Play. Computers, Chess, and Cognition
  8. ^ Peter Jansen (1992). Using Knowledge about the Opponent in Game-Tree Search. Ph.D. thesis, Carnegie Mellon University, pdf
  9. ^ David Carmel, Shaul Markovitch (1993). Learning Models of Opponent's Strategy in Game Playing. AAAI Proceedings, CiteSeerX
  10. ^ David Carmel, Shaul Markovitch (1996). Incorporating Opponent Models into Adversary Search. AAAI 1996 Proceedings, pdf
  11. ^ Xinbo Gao, Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik (1998). A Speculative Strategy. CG 1998
  12. ^ Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2000). Investigating Probabilistic Opponent-Model Search. JCIS 2000, pdf (extended abstract)
  13. ^ Re: Different eval for white/black by Ronald de Man, CCC, January 08, 2015
  14. ^ 1999 Seattle WTO protests from Wikipedia
  15. ^ Noam Chomsky
  16. ^ Manufacturing Consent: The Political Economy of the Mass Media - Wikipedia

What links here?


Up one level