Opponent Model Search

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Opponent Model Search

Nosce hostem - know the enemy [1]

Opponent Model Search incorporates asymmetric search and asymmetric 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 [2] , its successor Chess Genius [3] , and KnightCap [4] , 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 [5] . Programs may tune and learn feature vectors and their respective weights to maximize result scores against certain opponents as well.

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 [6] . In his 1992 Ph.D. thesis Using Knowledge about the Opponent in Game-Tree Search [7] , 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* [8], 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 [9] . 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 [10] . The Probabilistic Opponent-Model Search (PrOM) for several game domains was developed by Donkers, Uiterwijk and Van den Herik, published in 2000 [11] . It uses an extended model that includes uncertainty of the opponent.

See also

Publications

BCE ...

1500 ...

1980 ...

1990 ...

1995 ...

2000 ...

2005 ...

2015 ...

2020 ...

Forum Posts

External Links

References

  1. Nosce hostem, 532nd Military Intelligence Battalion Distinctive Unit Insignia, United States Army, Distinctive unit insignia from Wikipedia
  2. Kaare Danielsen (1987). The 7th World Microcomputer Chess Championship, Rome, Italy, September 14-20, 1987. ICCA Journal, Vol. 10, No. 3 » WMCCC 1987
  3. Genius' asymmetric-search by example: TRY yourself by Thorsten Czub, rgcc, December 30, 1997
  4. asymmetry by Andrew Tridgell, rgcc, August 12, 1997
  5. Re: Anti Coward Mode by Rebel, OpenChess Forum, December 22, 2013
  6. Peter Jansen (1990). Problematic Positions and Speculative Play. Computers, Chess, and Cognition
  7. Peter Jansen (1992). Using Knowledge about the Opponent in Game-Tree Search. Ph.D. thesis, Carnegie Mellon University, pdf
  8. David Carmel, Shaul Markovitch (1994). The M* Algorithm: Incorporating Opponent Models into Adversary Search. CIS Report #9402, pdf
  9. David Carmel, Shaul Markovitch (1996). Incorporating Opponent Models into Adversary Search. AAAI 1996, pdf
  10. Xinbo Gao, Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik (1998). A Speculative Strategy. CG 1998
  11. Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2000). Investigating Probabilistic Opponent-Model Search. JCIS 2000, pdf (extended abstract)
  12. Re: Different eval for white/black by Ronald de Man, CCC, January 08, 2015
  13. 1999 Seattle WTO protests from Wikipedia
  14. Noam Chomsky
  15. Manufacturing Consent: The Political Economy of the Mass Media - Wikipedia

Up one level