Opponent Model Search
Home * Search * Opponent Model Search
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.
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 [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 ...
- Sun Tsu (around 500 BCE). The Art of War. CreateSpace Independent Publishing Platform, 2012.
1500 ...
1980 ...
- Andrew L. Reibman, Bruce W. Ballard (1983). Non-Minimax Search Strategies for Use against Fallible Opponents. Proceedings of AAAI 83
- Ed Felten (1989). Playing Against an Imperfect Opponent. Workshop on New Directions in Game-Tree Search
- Peter Jansen (1989). Problematic Positions and Speculative Play. Workshop on New Directions in Game-Tree Search
1990 ...
- Peter Jansen (1990). Problematic Positions and Speculative Play. Computers, Chess, and Cognition
- Peter Jansen (1992). Using Knowledge about the Opponent in Game-Tree Search. Ph.D. thesis, Carnegie Mellon University, pdf
- Ingo Althöfer (1992). On Asymmetries in Chess Programs. ICCA Journal, Vol. 15, No. 1
- Peter Jansen (1992). KQKR: Awareness of a Fallible Opponent. ICCA Journal, Vol. 15, No. 3
- Peter Jansen (1993). KQKR: Speculatively Thwarting a Human Opponent. ICCA Journal, Vol. 16, No. 1
- David Carmel, Shaul Markovitch (1993). Learning Models of Opponent's Strategy in Game Playing. AAAI 1993, FS-93-02, pdf
- Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik (1993). Opponent-Model Search. Technical Reports in Computer Science, CS 93-03. Department of Computer Science, University of Limburg. ISSN 0922-8721.
- Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik, Bob Herschberg (1993). Potential Applications of Opponent-Model Search. Part 1: The Domain of Applicability. ICCA Journal, Vol. 16, No. 4
- Luis Antunes, Luis Moniz, Carlos Azevedo (1993). Rb+: the Dynamic Estimation of the Opponent's Strength. INESC-ID, Lisbon, Portugal » RB
- Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik, Bob Herschberg (1994). Potential Applications of Opponent-Model Search. Part 2. Risks and strategies. ICCA Journal, Vol. 17, No. 1
- Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik, Bob Herschberg (1994). Thoughts on the Application of Opponent-Model Search. Advances in Computer Chess 7
- Jos Uiterwijk, Jaap van den Herik (1994). Speculative Play in Computer Chess. Advances in Computer Chess 7
- David Carmel, Shaul Markovitch (1994). The M* Algorithm: Incorporating Opponent Models into Adversary Search. CIS Report #9402, pdf [12]
1995 ...
- Steven Walczak (1996). Improving Opening Book Performance Through Modeling of Chess Opponents. ACM Conference on Computer Science 1996
- Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik (1996). A Game-Tree Model Including an Opponent Model. NAIC'96)
- David Carmel, Shaul Markovitch (1996). Incorporating Opponent Models into Adversary Search. AAAI 1996, pdf
- Hiroyuki Iida, Yoshiyuki Kotani, Jos Uiterwijk, Jaap van den Herik (1997). Gains and Risks of OM Search. Advances in Computer Chess 8
- Xinbo Gao, Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik (1998). A Speculative Strategy. CG 1998
2000 ...
- Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2000). Investigating Probabilistic Opponent-Model Search. JCIS 2000, pdf (extended abstract)
- Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2001). Probabilistic Opponent-Model Search. Information Science, Vol. 135, Nos. 3-4
- Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2001). Admissibility in Opponent Model Search. BNAIC 2001
- Xinbo Gao, Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik (2001). Strategies anticipating a difference in search depth using opponent-model search. Theoretical Computer Science, Vol. 252, Nos. 1–2
- 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, Jos Uiterwijk, Jaap van den Herik (2003). Admissibility in Opponent-Model Search. IS Journal, in press.
- Jeroen Donkers, Jaap van den Herik, Jos Uiterwijk (2003). Opponent Models in Bao: Conditions of a Successfull Application, Advances in Computer Games 10, pdf
- Jeroen Donkers (2003). Nosce Hostem - Searching with Opponent Models. Ph.D. thesis Universiteit Maastricht, pdf
- 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 (2004). Opponent Models in Games. Ercim News – Special: Game Technology, Nr. 57, April 2004, pp. 42-43. 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
2005 ...
- Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2005). Selecting Evaluation Functions in Opponent-Model Search.Theoretical Computer Science, Vol 349, No. 2
- Jaap van den Herik, Jeroen Donkers, Pieter Spronck (2005). Opponent Modelling and Commercial Games. (Keynote paper). CIG’05
- Jeroen Donkers, Jaap van den Herik, Jos Uiterwijk (2005). Similarity Pruning in PrOM Search. Advances in Computer Games 11
- Jeroen Donkers (2005). Opponent Models and Knowledge Symmetry in Game-Tree Search. IKAT Universiteit Maastricht
- Austin Parker, Dana S. Nau, V.S. Subrahmanian (2006). Overconfidence or Paranoia? Search in Imperfect-Information Games. AAAI 2006, pdf
- Jeroen Donkers, Pieter Spronck (2006). Preferenced-Based Player Modelling. In AI Game Programming Wisdom 3
- Alan J. Lockett, Charles L. Chen, Risto Miikkulainen (2007). Evolving Explicit Opponent Models for Game Play. GECCO 2007
- Sander Bakkes, Pieter Spronck, Jaap van den Herik (2009). Opponent Modelling for Case-based Adaptive Game AI. Entertainment Computing, Vol. 1, Nr. 1, pp. 27-37, pdf
2015 ...
- Mohd Nor Akmal Khalid, Umi Kalsom Yusof, Hiroyuki Iida, Taichi Ishitobi (2015). Critical Position Identification in Games and Its Application to Speculative Play. ICAART 2015
- Naoki Mizukami, Yoshimasa Tsuruoka (2015). Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models. IEEE CIG 2015, pdf
- Roland Stuckardt (2017). "Too clever is dumb" - Kleine Philosophie des Schwindelns. In: Glarean Magazin, June 6th, 2017. (PDF)
2020 ...
- Hung-Jui Chang, Cheng Yueh, Gang-Yu Fan, Ting-Yu Lin, Tsan-sheng Hsu (2021). Opponent Model Selection Using Deep Learning. Advances in Computer Games 17
Forum Posts
- asymmetry by Andrew Tridgell, rgcc, August 12, 1997 » KnightCap, Parity Pruning
- Collector's Corner..Knowing your opponent.. by Steve Blincoe, CCC, January 10, 2005
- Opponent-modeling in computer chess by Mathieu Pagé, CCC, July 14, 2005
- Knowing your opponents by Mark Lefler, CCC, December 17, 2009
- Different eval for white/black by Matthew Lai, CCC, January 05, 2015 » Asymmetric Evaluation
External Links
- Opponent Models in Games by Jeroen Donkers and Jaap van den Herik
- Know Your Enemy (Disambiguation) from Wikipedia
- Ignorant Hussy: Know your enemy
- Rage Against the Machine - Know Your Enemy [13] [14] [15] , YouTube Video
References
- ↑ Nosce hostem, 532nd Military Intelligence Battalion Distinctive Unit Insignia, United States Army, Distinctive unit insignia from Wikipedia
- ↑ Kaare Danielsen (1987). The 7th World Microcomputer Chess Championship, Rome, Italy, September 14-20, 1987. ICCA Journal, Vol. 10, No. 3 » WMCCC 1987
- ↑ Genius' asymmetric-search by example: TRY yourself by Thorsten Czub, rgcc, December 30, 1997
- ↑ asymmetry by Andrew Tridgell, rgcc, August 12, 1997
- ↑ Re: Anti Coward Mode by Rebel, OpenChess Forum, December 22, 2013
- ↑ Peter Jansen (1990). Problematic Positions and Speculative Play. Computers, Chess, and Cognition
- ↑ Peter Jansen (1992). Using Knowledge about the Opponent in Game-Tree Search. Ph.D. thesis, Carnegie Mellon University, pdf
- ↑ David Carmel, Shaul Markovitch (1994). The M* Algorithm: Incorporating Opponent Models into Adversary Search. CIS Report #9402, pdf
- ↑ David Carmel, Shaul Markovitch (1996). Incorporating Opponent Models into Adversary Search. AAAI 1996, pdf
- ↑ Xinbo Gao, Hiroyuki Iida, Jos Uiterwijk, Jaap van den Herik (1998). A Speculative Strategy. CG 1998
- ↑ Jeroen Donkers, Jos Uiterwijk, Jaap van den Herik (2000). Investigating Probabilistic Opponent-Model Search. JCIS 2000, pdf (extended abstract)
- ↑ Re: Different eval for white/black by Ronald de Man, CCC, January 08, 2015
- ↑ 1999 Seattle WTO protests from Wikipedia
- ↑ Noam Chomsky
- ↑ Manufacturing Consent: The Political Economy of the Mass Media - Wikipedia
