25,161
edits
Changes
Created page with "'''Home * Search * Opponent Model Search''' FILE:532 MI Bn DUI.png|border|right|thumb| Nosce hostem - know the enemy <ref>Nosce hostem, 532nd [https://en...."
'''[[Main Page|Home]] * [[Search]] * Opponent Model Search'''
[[FILE:532 MI Bn DUI.png|border|right|thumb|
Nosce hostem - know the enemy <ref>Nosce hostem, 532nd [https://en.wikipedia.org/wiki/Military_Intelligence_Corps_(United_States_Army) Military Intelligence Battalion] [https://en.wikipedia.org/wiki/Distinctive_unit_insignia Distinctive Unit Insignia], [https://en.wikipedia.org/wiki/United_States_Army United States Army], [https://en.wikipedia.org/wiki/Distinctive_unit_insignia Distinctive unit insignia from Wikipedia]</ref>
]]
'''Opponent Model Search''' incorporates asymmetric search and [[Asymmetric Evaluation|asymmetric evaluation]] techniques considering the peculiarities of an opponent, which requires explicit [[Knowledge|knowledge]] or assumption, and includes a model on how the opponent evaluates positions. Naive approaches in computer chess tournaments are [[Opening Book|opening book]] preparation and [[Contempt Factor|contempt]]. Some chess programs, notably [[Psion]] <ref>[[Kaare Danielsen]] ('''1987'''). ''The 7th World Microcomputer Chess Championship, Rome, Italy, September 14-20, 1987''. [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]] » [[WMCCC 1987]]</ref> , its successor [[Chess Genius]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b456400a43207b02 Genius' asymmetric-search by example: TRY yourself] by [[Thorsten Czub]], [[Computer Chess Forums|rgcc]], December 30, 1997</ref> , and [[KnightCap]] <ref>[https://groups.google.com/group/rec.games.chess.computer/msg/f9bfe5d4457a19ad asymmetry] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], August 12, 1997</ref> , apply [[Asymmetric evaluation|asymmetric evaluation]] and search, for instance to [[Extensions|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|anti-computerchess]] specialists, for instance to reduce the program's tendency to trade material and to avoid blocked positions with a high [[Pawn Rams (Bitboards)|rammed pawn]] versus [[Pawn Levers (Bitboards)|lever]] ratio. [[Ed Schroder|Ed Schröder]] proposed to reward own [[Hanging Piece|hanging pieces]] to encourage complicated, [[Tactics|tactical]] play versus humans, and to keep opponents under time pressure in playing immediate [[Pondering|ponder hits]] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2546&start=1 Re: Anti Coward Mode] by [[Ed Schroder|Rebel]], [[Computer Chess Forums|OpenChess Forum]], December 22, 2013</ref> . Programs may [[Automated Tuning|tune]] and [[Learning|learn]] feature vectors and their respective weights to maximize result scores against certain opponents as well.
<span id="SpeculativePlay"></span>
=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 <ref>[[Peter Jansen]] ('''1990'''). ''Problematic Positions and Speculative Play.'' [[Computers, Chess, and Cognition]]</ref> . In his 1992 Ph.D. thesis ''Using Knowledge about the Opponent in Game-Tree Search'' <ref>[[Peter Jansen]] ('''1992'''). ''Using Knowledge about the Opponent in Game-Tree Search''. Ph.D. thesis, [[Carnegie Mellon University]], [http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA259234&Location=U2&doc=GetTRDoc.pdf pdf]</ref> , Jansen elaborates on opponent modeling, specially in KQKR, relaxing [[Claude Shannon|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 [https://en.wikipedia.org/wiki/Sun_Tzu 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'''* <ref>[[David Carmel]], [[Shaul Markovitch]] ('''1993'''). ''Learning Models of Opponent's Strategy in Game Playing''. [[AAAI]] Proceedings, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.6488 CiteSeerX]</ref> , a generalization of [[Minimax|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 <ref>[[David Carmel]], [[Shaul Markovitch]] ('''1996'''). ''Incorporating Opponent Models into Adversary Search''. [[AAAI]] 1996 Proceedings, [http://www.aaai.org/Papers/AAAI/1996/AAAI96-018.pdf pdf]</ref> . Gao et al. researched on a generalization of opponent model search, called '''(D, d)-OM''' search, where '''D''' stands for the [[Depth|depth]] of [[Search|search]] by the player and '''d''' for the opponent’s depth of search <ref>[[Xinbo Gao]], [[Hiroyuki Iida]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_5 A Speculative Strategy]''. [[CG 1998]]</ref> . The '''Probabilistic''' Opponent-Model Search ('''PrOM''') for several game domains was developed by Donkers, Uiterwijk and Van den Herik, published in 2000 <ref>[[Jeroen Donkers]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2000'''). ''Investigating Probabilistic Opponent-Model Search''. JCIS 2000, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cbnaic00.pdf pdf] (extended abstract)</ref> . It uses an extended model that includes uncertainty of the opponent.
=See also=
* [[Asymmetric Evaluation]]
* [[Contempt Factor]]
* [[Knowledge]]
* [[Learning]]
* [[Planning]]
=Publications=
==BCE ...==
* [https://en.wikipedia.org/wiki/Sun_Tzu Sun Tsu] ('''around 500 BCE'''). ''[https://en.wikipedia.org/wiki/The_Art_of_War The Art of War.]'' CreateSpace Independent Publishing Platform, 2012.
==1980 ...==
* <span id="RB"></span>[[Andrew L. Reibman]], [[Bruce W. Ballard]] ('''1983'''). ''[http://www.aaai.org/Library/AAAI/1983/aaai83-084.php Non-Minimax Search Strategies for Use against Fallible Opponents]''. Proceedings of [[AAAI]] 83
* [[Ed Felten]] ('''1989'''). ''Playing Against an Imperfect Opponent''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
* [[Peter Jansen]] ('''1989'''). ''Problematic Positions and Speculative Play.'' [[WCCC 1989#Workshop|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]], [http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA259234&Location=U2&doc=GetTRDoc.pdf pdf]
* [[Ingo Althöfer]] ('''1992'''). ''On Asymmetries in Chess Programs.'' [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
* [[Peter Jansen]] ('''1992'''). ''KQKR: Awareness of a Fallible Opponent''. [[ICGA Journal#15_3|ICCA Journal, Vol. 15, No. 3]]
* [[Peter Jansen]] ('''1993'''). ''KQKR: Speculatively Thwarting a Human Opponent.'' [[ICGA Journal#16_1|ICCA Journal, Vol. 16, No. 1]]
* [[David Carmel]], [[Shaul Markovitch]] ('''1993'''). ''Learning Models of Opponent's Strategy in Game Playing''. [[AAAI]] Proceedings, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.6488 CiteSeerX]
* [[Hiroyuki Iida]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1993'''). ''Opponent-Model Search''. Technical Reports in Computer Science, CS 93-03. Department of Computer Science, [[Maastricht University|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.'' [[ICGA Journal#16_4|ICCA Journal, Vol. 16, No. 4]]
* [[Luis Antunes]], [[Luis Moniz]], [[Carlos Azevedo]] ('''1993'''). ''[https://www.semanticscholar.org/paper/Rb-the-Dynamic-Estimation-of-the-Opponent-s-Antunes-Moniz/4844e9d1694f61d4052a87de94c4aeb2510c2404 Rb+: the Dynamic Estimation of the Opponent's Strength]''. [https://en.wikipedia.org/wiki/INESC-ID INESC-ID], [https://en.wikipedia.org/wiki/Lisbon Lisbon], [https://en.wikipedia.org/wiki/Portugal Portugal] » [[Opponent Model Search#RB|RB]]
* [[Hiroyuki Iida]], [[Jos Uiterwijk]], [[Jaap van den Herik]], [[Bob Herschberg]] ('''1994'''). ''Potential Applications of Opponent-Model Search. Part 2. Risks and strategies''. [[ICGA Journal#17_1|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, [http://www.cs.technion.ac.il/~shaulm/papers/pdf/Carmel-Markovitch-CIS9402.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54865&start=27 Re: Different eval for white/black] by [[Ronald de Man]], [[CCC]], January 08, 2015</ref>
==1995 ...==
* [[Steven Walczak]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228334&dl=ACM&coll=DL&CFID=34101495&CFTOKEN=18614940 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 Proceedings, [http://www.aaai.org/Papers/AAAI/1996/AAAI96-018.pdf 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'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_5 A Speculative Strategy]''. [[CG 1998]]
==2000 ...==
* [[Jeroen Donkers]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2000'''). ''Investigating Probabilistic Opponent-Model Search''. JCIS 2000, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cbnaic00.pdf 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'''). ''[http://www.sciencedirect.com/science/article/pii/S0304397500000773 Strategies anticipating a difference in search depth using opponent-model search]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 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]], [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cacg10.pdf pdf]
* [[Jeroen Donkers]] ('''2003'''). ''Nosce Hostem - Searching with Opponent Models''. Ph.D. thesis [[Maastricht University|Universiteit Maastricht]], [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cnoscehostem.pdf pdf]
* [[Jeroen Donkers]] ('''2004''') ''Opponent Models and Knowledge Symmetry in Game Tree Search''. Proceedings of the First Knowledge and Games Workshop. University of Liverpool, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Ckag2004.pdf pdf]
* [[Jeroen Donkers]], [[Jaap van den Herik]] ('''2004'''). ''[http://www.ercim.eu/publication/Ercim_News/enw57/donkers.html Opponent Models in Games]''. Ercim News – Special: Game Technology, Nr. 57, April 2004, pp. 42-43. [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cercim.pdf 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. [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cicec2004.pdf pdf]
==2005 ...==
* [[Jeroen Donkers]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2005'''). ''Selecting Evaluation Functions in Opponent-Model Search''.[https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 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, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cherikcig2005.pdf pdf].
* [[Jeroen Donkers]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/11922155_5 Similarity Pruning in PrOM Search]''. [[Advances in Computer Games 11]]
* [[Jeroen Donkers]], [[Pieter Spronck]] ('''2006'''). ''Preferenced-Based Player Modelling''. In AI Game Programming Wisdom 3
* [[Sander Bakkes]], [[Pieter Spronck]], [[Jaap van den Herik]] ('''2009'''). ''Opponent Modelling for Case-based Adaptive Game AI''. [http://www.journals.elsevier.com/entertainment-computing/ Entertainment Computing], Vol. 1, Nr. 1, pp. 27-37, [http://ticc.uvt.nl/~pspronck/pubs/bakkes_journalOM.pdf pdf]
==2015 ...==
* [[Mohd Nor Akmal Khalid]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[https://www.researchgate.net/publication/281152992_Critical_Position_Identification_in_Games_and_Its_Application_to_Speculative_Play Critical Position Identification in Games and Its Application to Speculative Play]''. [http://www.scitepress.org/DigitalLibrary/ProceedingsDetails.aspx?ID=+mGlly8Sp00=&t=1 ICAART 2015]
* [[Naoki Mizukami]], [[Yoshimasa Tsuruoka]] ('''2015'''). ''Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models''. [[IEEE#TOCIAIGAMES|IEEE CIG 2015]], [http://www.logos.ic.i.u-tokyo.ac.jp/~mizukami/paper/cig_2015.pdf pdf]
* [[Roland Stuckardt]] ('''2017'''). ''"Too clever is dumb" - Kleine Philosophie des Schwindelns.'' In: [https://glarean-magazin.ch/2017/06/06/schach-essay-to-clever-is-dumb-philosophie-des-schwindelns-roland-stuckardt/ Glarean Magazin, June 6th, 2017.] [http://www.stuckardt.de/rsdokumente/glarean-magazin.ch-Schach-Essay%20von%20R%20Stuckardt%20Too%20clever%20is%20dumb.pdf (PDF)]
=Forum Posts=
* [https://groups.google.com/group/rec.games.chess.computer/msg/f9bfe5d4457a19ad asymmetry] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], August 12, 1997 » [[KnightCap]], [[Parity Pruning]]
* [https://www.stmintz.com/ccc/index.php?id=404966 Collector's Corner..Knowing your opponent..] by [[Steve Blincoe]], [[CCC]], January 10, 2005
* [https://www.stmintz.com/ccc/index.php?id=436702 Opponent-modeling in computer chess] by [[Mathieu Pagé]], [[CCC]], July 14, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=31117 Knowing your opponents] by [[Mark Lefler]], [[CCC]], December 17, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=54865 Different eval for white/black] by [[Matthew Lai]], [[CCC]], January 05, 2015 » [[Asymmetric evaluation]]
=External Links=
* [http://www.ercim.eu/publication/Ercim_News/enw57/donkers.html Opponent Models in Games] by [[Jeroen Donkers]] and [[Jaap van den Herik]]
* [https://en.wikipedia.org/wiki/Know_Your_Enemy Know Your Enemy (Disambiguation) from Wikipedia]
* [http://ignoranthussy.blogspot.de/2006/08/know-your-enemy.html Ignorant Hussy: Know your enemy]
* [https://en.wikipedia.org/wiki/Rage_Against_the_Machine Rage Against the Machine] - [https://en.wikipedia.org/wiki/Know_Your_Enemy_%28Rage_Against_the_Machine_song%29 Know Your Enemy] <ref>[https://en.wikipedia.org/wiki/1999_Seattle_WTO_protests 1999 Seattle WTO protests from Wikipedia]</ref> <ref>[[Mathematician#Chomsky|Noam Chomsky]]</ref> <ref>[https://en.wikipedia.org/wiki/Manufacturing_Consent:_The_Political_Economy_of_the_Mass_Media Manufacturing Consent: The Political Economy of the Mass Media - Wikipedia]</ref> , [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=aIsZwGbi9g8|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
[[FILE:532 MI Bn DUI.png|border|right|thumb|
Nosce hostem - know the enemy <ref>Nosce hostem, 532nd [https://en.wikipedia.org/wiki/Military_Intelligence_Corps_(United_States_Army) Military Intelligence Battalion] [https://en.wikipedia.org/wiki/Distinctive_unit_insignia Distinctive Unit Insignia], [https://en.wikipedia.org/wiki/United_States_Army United States Army], [https://en.wikipedia.org/wiki/Distinctive_unit_insignia Distinctive unit insignia from Wikipedia]</ref>
]]
'''Opponent Model Search''' incorporates asymmetric search and [[Asymmetric Evaluation|asymmetric evaluation]] techniques considering the peculiarities of an opponent, which requires explicit [[Knowledge|knowledge]] or assumption, and includes a model on how the opponent evaluates positions. Naive approaches in computer chess tournaments are [[Opening Book|opening book]] preparation and [[Contempt Factor|contempt]]. Some chess programs, notably [[Psion]] <ref>[[Kaare Danielsen]] ('''1987'''). ''The 7th World Microcomputer Chess Championship, Rome, Italy, September 14-20, 1987''. [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]] » [[WMCCC 1987]]</ref> , its successor [[Chess Genius]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b456400a43207b02 Genius' asymmetric-search by example: TRY yourself] by [[Thorsten Czub]], [[Computer Chess Forums|rgcc]], December 30, 1997</ref> , and [[KnightCap]] <ref>[https://groups.google.com/group/rec.games.chess.computer/msg/f9bfe5d4457a19ad asymmetry] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], August 12, 1997</ref> , apply [[Asymmetric evaluation|asymmetric evaluation]] and search, for instance to [[Extensions|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|anti-computerchess]] specialists, for instance to reduce the program's tendency to trade material and to avoid blocked positions with a high [[Pawn Rams (Bitboards)|rammed pawn]] versus [[Pawn Levers (Bitboards)|lever]] ratio. [[Ed Schroder|Ed Schröder]] proposed to reward own [[Hanging Piece|hanging pieces]] to encourage complicated, [[Tactics|tactical]] play versus humans, and to keep opponents under time pressure in playing immediate [[Pondering|ponder hits]] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2546&start=1 Re: Anti Coward Mode] by [[Ed Schroder|Rebel]], [[Computer Chess Forums|OpenChess Forum]], December 22, 2013</ref> . Programs may [[Automated Tuning|tune]] and [[Learning|learn]] feature vectors and their respective weights to maximize result scores against certain opponents as well.
<span id="SpeculativePlay"></span>
=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 <ref>[[Peter Jansen]] ('''1990'''). ''Problematic Positions and Speculative Play.'' [[Computers, Chess, and Cognition]]</ref> . In his 1992 Ph.D. thesis ''Using Knowledge about the Opponent in Game-Tree Search'' <ref>[[Peter Jansen]] ('''1992'''). ''Using Knowledge about the Opponent in Game-Tree Search''. Ph.D. thesis, [[Carnegie Mellon University]], [http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA259234&Location=U2&doc=GetTRDoc.pdf pdf]</ref> , Jansen elaborates on opponent modeling, specially in KQKR, relaxing [[Claude Shannon|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 [https://en.wikipedia.org/wiki/Sun_Tzu 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'''* <ref>[[David Carmel]], [[Shaul Markovitch]] ('''1993'''). ''Learning Models of Opponent's Strategy in Game Playing''. [[AAAI]] Proceedings, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.6488 CiteSeerX]</ref> , a generalization of [[Minimax|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 <ref>[[David Carmel]], [[Shaul Markovitch]] ('''1996'''). ''Incorporating Opponent Models into Adversary Search''. [[AAAI]] 1996 Proceedings, [http://www.aaai.org/Papers/AAAI/1996/AAAI96-018.pdf pdf]</ref> . Gao et al. researched on a generalization of opponent model search, called '''(D, d)-OM''' search, where '''D''' stands for the [[Depth|depth]] of [[Search|search]] by the player and '''d''' for the opponent’s depth of search <ref>[[Xinbo Gao]], [[Hiroyuki Iida]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_5 A Speculative Strategy]''. [[CG 1998]]</ref> . The '''Probabilistic''' Opponent-Model Search ('''PrOM''') for several game domains was developed by Donkers, Uiterwijk and Van den Herik, published in 2000 <ref>[[Jeroen Donkers]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2000'''). ''Investigating Probabilistic Opponent-Model Search''. JCIS 2000, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cbnaic00.pdf pdf] (extended abstract)</ref> . It uses an extended model that includes uncertainty of the opponent.
=See also=
* [[Asymmetric Evaluation]]
* [[Contempt Factor]]
* [[Knowledge]]
* [[Learning]]
* [[Planning]]
=Publications=
==BCE ...==
* [https://en.wikipedia.org/wiki/Sun_Tzu Sun Tsu] ('''around 500 BCE'''). ''[https://en.wikipedia.org/wiki/The_Art_of_War The Art of War.]'' CreateSpace Independent Publishing Platform, 2012.
==1980 ...==
* <span id="RB"></span>[[Andrew L. Reibman]], [[Bruce W. Ballard]] ('''1983'''). ''[http://www.aaai.org/Library/AAAI/1983/aaai83-084.php Non-Minimax Search Strategies for Use against Fallible Opponents]''. Proceedings of [[AAAI]] 83
* [[Ed Felten]] ('''1989'''). ''Playing Against an Imperfect Opponent''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
* [[Peter Jansen]] ('''1989'''). ''Problematic Positions and Speculative Play.'' [[WCCC 1989#Workshop|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]], [http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA259234&Location=U2&doc=GetTRDoc.pdf pdf]
* [[Ingo Althöfer]] ('''1992'''). ''On Asymmetries in Chess Programs.'' [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
* [[Peter Jansen]] ('''1992'''). ''KQKR: Awareness of a Fallible Opponent''. [[ICGA Journal#15_3|ICCA Journal, Vol. 15, No. 3]]
* [[Peter Jansen]] ('''1993'''). ''KQKR: Speculatively Thwarting a Human Opponent.'' [[ICGA Journal#16_1|ICCA Journal, Vol. 16, No. 1]]
* [[David Carmel]], [[Shaul Markovitch]] ('''1993'''). ''Learning Models of Opponent's Strategy in Game Playing''. [[AAAI]] Proceedings, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.6488 CiteSeerX]
* [[Hiroyuki Iida]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1993'''). ''Opponent-Model Search''. Technical Reports in Computer Science, CS 93-03. Department of Computer Science, [[Maastricht University|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.'' [[ICGA Journal#16_4|ICCA Journal, Vol. 16, No. 4]]
* [[Luis Antunes]], [[Luis Moniz]], [[Carlos Azevedo]] ('''1993'''). ''[https://www.semanticscholar.org/paper/Rb-the-Dynamic-Estimation-of-the-Opponent-s-Antunes-Moniz/4844e9d1694f61d4052a87de94c4aeb2510c2404 Rb+: the Dynamic Estimation of the Opponent's Strength]''. [https://en.wikipedia.org/wiki/INESC-ID INESC-ID], [https://en.wikipedia.org/wiki/Lisbon Lisbon], [https://en.wikipedia.org/wiki/Portugal Portugal] » [[Opponent Model Search#RB|RB]]
* [[Hiroyuki Iida]], [[Jos Uiterwijk]], [[Jaap van den Herik]], [[Bob Herschberg]] ('''1994'''). ''Potential Applications of Opponent-Model Search. Part 2. Risks and strategies''. [[ICGA Journal#17_1|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, [http://www.cs.technion.ac.il/~shaulm/papers/pdf/Carmel-Markovitch-CIS9402.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54865&start=27 Re: Different eval for white/black] by [[Ronald de Man]], [[CCC]], January 08, 2015</ref>
==1995 ...==
* [[Steven Walczak]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228334&dl=ACM&coll=DL&CFID=34101495&CFTOKEN=18614940 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 Proceedings, [http://www.aaai.org/Papers/AAAI/1996/AAAI96-018.pdf 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'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_5 A Speculative Strategy]''. [[CG 1998]]
==2000 ...==
* [[Jeroen Donkers]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2000'''). ''Investigating Probabilistic Opponent-Model Search''. JCIS 2000, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cbnaic00.pdf 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'''). ''[http://www.sciencedirect.com/science/article/pii/S0304397500000773 Strategies anticipating a difference in search depth using opponent-model search]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 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]], [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cacg10.pdf pdf]
* [[Jeroen Donkers]] ('''2003'''). ''Nosce Hostem - Searching with Opponent Models''. Ph.D. thesis [[Maastricht University|Universiteit Maastricht]], [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cnoscehostem.pdf pdf]
* [[Jeroen Donkers]] ('''2004''') ''Opponent Models and Knowledge Symmetry in Game Tree Search''. Proceedings of the First Knowledge and Games Workshop. University of Liverpool, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Ckag2004.pdf pdf]
* [[Jeroen Donkers]], [[Jaap van den Herik]] ('''2004'''). ''[http://www.ercim.eu/publication/Ercim_News/enw57/donkers.html Opponent Models in Games]''. Ercim News – Special: Game Technology, Nr. 57, April 2004, pp. 42-43. [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cercim.pdf 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. [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cicec2004.pdf pdf]
==2005 ...==
* [[Jeroen Donkers]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2005'''). ''Selecting Evaluation Functions in Opponent-Model Search''.[https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 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, [http://www.fdg.unimaas.nl/educ/donkers/pubs/..%5Cpdf%5Cherikcig2005.pdf pdf].
* [[Jeroen Donkers]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/11922155_5 Similarity Pruning in PrOM Search]''. [[Advances in Computer Games 11]]
* [[Jeroen Donkers]], [[Pieter Spronck]] ('''2006'''). ''Preferenced-Based Player Modelling''. In AI Game Programming Wisdom 3
* [[Sander Bakkes]], [[Pieter Spronck]], [[Jaap van den Herik]] ('''2009'''). ''Opponent Modelling for Case-based Adaptive Game AI''. [http://www.journals.elsevier.com/entertainment-computing/ Entertainment Computing], Vol. 1, Nr. 1, pp. 27-37, [http://ticc.uvt.nl/~pspronck/pubs/bakkes_journalOM.pdf pdf]
==2015 ...==
* [[Mohd Nor Akmal Khalid]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[https://www.researchgate.net/publication/281152992_Critical_Position_Identification_in_Games_and_Its_Application_to_Speculative_Play Critical Position Identification in Games and Its Application to Speculative Play]''. [http://www.scitepress.org/DigitalLibrary/ProceedingsDetails.aspx?ID=+mGlly8Sp00=&t=1 ICAART 2015]
* [[Naoki Mizukami]], [[Yoshimasa Tsuruoka]] ('''2015'''). ''Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models''. [[IEEE#TOCIAIGAMES|IEEE CIG 2015]], [http://www.logos.ic.i.u-tokyo.ac.jp/~mizukami/paper/cig_2015.pdf pdf]
* [[Roland Stuckardt]] ('''2017'''). ''"Too clever is dumb" - Kleine Philosophie des Schwindelns.'' In: [https://glarean-magazin.ch/2017/06/06/schach-essay-to-clever-is-dumb-philosophie-des-schwindelns-roland-stuckardt/ Glarean Magazin, June 6th, 2017.] [http://www.stuckardt.de/rsdokumente/glarean-magazin.ch-Schach-Essay%20von%20R%20Stuckardt%20Too%20clever%20is%20dumb.pdf (PDF)]
=Forum Posts=
* [https://groups.google.com/group/rec.games.chess.computer/msg/f9bfe5d4457a19ad asymmetry] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], August 12, 1997 » [[KnightCap]], [[Parity Pruning]]
* [https://www.stmintz.com/ccc/index.php?id=404966 Collector's Corner..Knowing your opponent..] by [[Steve Blincoe]], [[CCC]], January 10, 2005
* [https://www.stmintz.com/ccc/index.php?id=436702 Opponent-modeling in computer chess] by [[Mathieu Pagé]], [[CCC]], July 14, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=31117 Knowing your opponents] by [[Mark Lefler]], [[CCC]], December 17, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=54865 Different eval for white/black] by [[Matthew Lai]], [[CCC]], January 05, 2015 » [[Asymmetric evaluation]]
=External Links=
* [http://www.ercim.eu/publication/Ercim_News/enw57/donkers.html Opponent Models in Games] by [[Jeroen Donkers]] and [[Jaap van den Herik]]
* [https://en.wikipedia.org/wiki/Know_Your_Enemy Know Your Enemy (Disambiguation) from Wikipedia]
* [http://ignoranthussy.blogspot.de/2006/08/know-your-enemy.html Ignorant Hussy: Know your enemy]
* [https://en.wikipedia.org/wiki/Rage_Against_the_Machine Rage Against the Machine] - [https://en.wikipedia.org/wiki/Know_Your_Enemy_%28Rage_Against_the_Machine_song%29 Know Your Enemy] <ref>[https://en.wikipedia.org/wiki/1999_Seattle_WTO_protests 1999 Seattle WTO protests from Wikipedia]</ref> <ref>[[Mathematician#Chomsky|Noam Chomsky]]</ref> <ref>[https://en.wikipedia.org/wiki/Manufacturing_Consent:_The_Political_Economy_of_the_Mass_Media Manufacturing Consent: The Political Economy of the Mass Media - Wikipedia]</ref> , [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=aIsZwGbi9g8|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
