Difference between revisions of "Selectivity"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(6 intermediate revisions by the same user not shown) | |||
Line 55: | Line 55: | ||
* [[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. MSc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf] | * [[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. MSc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf] | ||
* [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Selective Extensions in Game-Tree Search''. [[3rd Computer Olympiad#Workshop|Heuristic Programming in AI 3]] | * [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Selective Extensions in Game-Tree Search''. [[3rd Computer Olympiad#Workshop|Heuristic Programming in AI 3]] | ||
+ | * [[David McAllester]], [[Deniz Yuret]] ('''1993'''). ''Alpha-Beta Conspiracy Search''. [http://ttic.uchicago.edu/~dmcallester/abc.ps ps (draft)] » [[Alpha-Beta Conspiracy Search]] | ||
* [[Javier Ros Padilla]] ('''1994'''). ''Estimating Asymmetry and Selectivity in Chess Programs''. [[ICGA Journal#17_1|ICCA Journal, Vol. 17, No. 1]] <ref>[https://groups.google.com/d/msg/rec.games.chess/5_dMbe0_juo/bXQQVYVEpykJ ICCA Journal, Vol. 17, No. 1] by [[Jos Uiterwijk]], [[Computer Chess Forums|rgcc]], May 02, 1994</ref> | * [[Javier Ros Padilla]] ('''1994'''). ''Estimating Asymmetry and Selectivity in Chess Programs''. [[ICGA Journal#17_1|ICCA Journal, Vol. 17, No. 1]] <ref>[https://groups.google.com/d/msg/rec.games.chess/5_dMbe0_juo/bXQQVYVEpykJ ICCA Journal, Vol. 17, No. 1] by [[Jos Uiterwijk]], [[Computer Chess Forums|rgcc]], May 02, 1994</ref> | ||
* [[Deniz Yuret]] ('''1994'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=EJurXJ4AAAAJ&cstart=40&citation_for_view=EJurXJ4AAAAJ:TQgYirikUcIC The Principle of Pressure in Chess]''. TAINN 1994 | * [[Deniz Yuret]] ('''1994'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=EJurXJ4AAAAJ&cstart=40&citation_for_view=EJurXJ4AAAAJ:TQgYirikUcIC The Principle of Pressure in Chess]''. TAINN 1994 | ||
Line 62: | Line 63: | ||
* [[Paul E. Utgoff]], [[Richard P. Cochran]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_1 A Least-Certainty Heuristic for Selective Search]''. [[CG 2000]], [http://people.cs.umass.edu/~utgoff/papers/springer-lcf.pdf pdf] » [[Richard P. Cochran#LCF|LCF]] | * [[Paul E. Utgoff]], [[Richard P. Cochran]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_1 A Least-Certainty Heuristic for Selective Search]''. [[CG 2000]], [http://people.cs.umass.edu/~utgoff/papers/springer-lcf.pdf pdf] » [[Richard P. Cochran#LCF|LCF]] | ||
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Selective Depth-First Search Methods''. in [[Jaap van den Herik]], [[Hiroyuki Iida]] (eds.) ('''2000'''). ''Games in AI Research''. [[Maastricht University|Universiteit Maastricht]], [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint] | * [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Selective Depth-First Search Methods''. in [[Jaap van den Herik]], [[Hiroyuki Iida]] (eds.) ('''2000'''). ''Games in AI Research''. [[Maastricht University|Universiteit Maastricht]], [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint] | ||
− | * [[Ulf Lorenz]], [[Burkhard Monien]] ('''2002'''). ''[http://www.springerlink.com/content/f6b4wb6l63dpd0jv/ The Secret of Selective Game Tree Search, When Using Random-Error Evaluations]''. Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), [ | + | * [[Ulf Lorenz]], [[Burkhard Monien]] ('''2002'''). ''[http://www.springerlink.com/content/f6b4wb6l63dpd0jv/ The Secret of Selective Game Tree Search, When Using Random-Error Evaluations]''. Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS) |
− | * [[Pálmi Skowronski]] ('''2009'''). ''Gradual Focus: A Method for Automated Feature Discovery in Selective Search''. | + | * [[David McAllester]], [[Deniz Yuret]] ('''2002'''). ''Alpha-Beta Conspiracy Search''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]] » [[Alpha-Beta Conspiracy Search]] |
+ | * [[Brian Sheppard]] ('''2004'''). ''[https://link.springer.com/chapter/10.1007/11674399_1 Efficient Control of Selective Simulations]''. [[CG 2004]] | ||
+ | * [[Brian Sheppard]] ('''2004'''). ''Efficient Control of Selective Simulations''. [[ICGA Journal#27_2|ICGA Journal, Vol. 27, No. 2]] <ref>slightly revised version of the [[CG 2004]] paper</ref> | ||
+ | * [[Pálmi Skowronski]] ('''2009'''). ''Gradual Focus: A Method for Automated Feature Discovery in Selective Search''. M.Sc. thesis | ||
==2010 ...== | ==2010 ...== | ||
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Optimizing Selective Search in Chess''. ICML - Workshop on Machine Learning and Games | * [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Optimizing Selective Search in Chess''. ICML - Workshop on Machine Learning and Games | ||
Line 79: | Line 83: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=29905 Extensions/Reductions] by [[Luca Hemmerich]], [[CCC]], September 28, 2009 | * [http://www.talkchess.com/forum/viewtopic.php?t=29905 Extensions/Reductions] by [[Luca Hemmerich]], [[CCC]], September 28, 2009 | ||
==2010 ...== | ==2010 ...== | ||
− | * [http://www.talkchess.com/forum/viewtopic.php?t=44686 Nullmove vs classic selective search] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 04, 2012 <ref> | + | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=42677 Counting depth as a function of number of legal moves] by [[Pio Korinth]], [[CCC]], February 28, 2012 » [[Depth]] |
+ | * [http://www.talkchess.com/forum/viewtopic.php?t=44686 Nullmove vs classic selective search] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 04, 2012 <ref>Selective Search Techniques in REBEL (introduction) from [[Rebel#ProgrammerCorner|Programmer Corner]] by [[Ed Schroder|Ed Schröder]]</ref> | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=45624 Houdini 3 reducing the depth feature] by Maurizio Maglio, [[CCC]], October 17, 2012 » [[Houdini]] | * [http://www.talkchess.com/forum/viewtopic.php?t=45624 Houdini 3 reducing the depth feature] by Maurizio Maglio, [[CCC]], October 17, 2012 » [[Houdini]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=51264 selective depth definition] by [[Uri Blass]], [[CCC]], February 13, 2014 » [[Stockfish]] | * [http://www.talkchess.com/forum/viewtopic.php?t=51264 selective depth definition] by [[Uri Blass]], [[CCC]], February 13, 2014 » [[Stockfish]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=66298 Is modern chess software lossless or lossy?] by Meni Rosenfeld, [[CCC]], January 10, 2018 » [[Playing Strength]] | * [http://www.talkchess.com/forum/viewtopic.php?t=66298 Is modern chess software lossless or lossy?] by Meni Rosenfeld, [[CCC]], January 10, 2018 » [[Playing Strength]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=68082 Names of selectivity algorithms] by [[Vivien Clauzon]], [[CCC]], July 26, 2018 | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70165 delaying tactics: prune or extend?] by [[Harm Geert Muller]], [[CCC]], March 10, 2019 » [[Tactics]] | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70165 delaying tactics: prune or extend?] by [[Harm Geert Muller]], [[CCC]], March 10, 2019 » [[Tactics]] | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74170 Tactical search] by [[Alvaro Cardoso]], [[CCC]], June 13, 2020 » [[Tactics]] | ||
=External Links= | =External Links= | ||
− | |||
* [http://www.vincent-peirani.com/projets Living Being Quintet] - On the heights, [http://www.altitudejazz.com/programme-concerts-festival-jazz-hautes-alpes.html Altitude Jazz Festival 2015], [https://en.wikipedia.org/wiki/YouTube YouTube] Video | * [http://www.vincent-peirani.com/projets Living Being Quintet] - On the heights, [http://www.altitudejazz.com/programme-concerts-festival-jazz-hautes-alpes.html Altitude Jazz Festival 2015], [https://en.wikipedia.org/wiki/YouTube YouTube] Video | ||
: [[:Category:Vincent Peirani|Vincent Peirani]], [[:Category:Émile Parisien|Émile Parisien]], [[:Category:Tony Paeleman|Tony Paeleman]], [http://www.julienherne.com/ Julien Herné], [http://www.simonoviez.com/english/YoannSerraus.htm Yoann Serra] | : [[:Category:Vincent Peirani|Vincent Peirani]], [[:Category:Émile Parisien|Émile Parisien]], [[:Category:Tony Paeleman|Tony Paeleman]], [http://www.julienherne.com/ Julien Herné], [http://www.simonoviez.com/english/YoannSerraus.htm Yoann Serra] |
Latest revision as of 21:02, 25 June 2020
Selectivity gives a whiff of Shannon's Type B search to Shannon's Type A or brute-force. The goal is to search "interesting" and forced branches which are or are likely to become part of the principal variation deeper than nominal, but to reduce uninteresting branches.
Extensions
Pruning
Reductions
See also
Publications
1970 ...
- Russell M. Church, Kenneth W. Church (1977). Plans, Goals, and Search Strategies for the Selection of a Move in Chess. Chess Skill in Man and Machine
1980 ...
- Hermann Kaindl (1983). Searching to Variable Depth in Computer Chess. Proceedings of IJCAI 83, pp. 760-762. Karlsruhe. pdf
- Don Beal (1986). Selective Search without Tears. ICCA Journal, Vol. 9, No. 2
- Hermann Kaindl, Helmut Horacek, Marcus Wagner (1986). Selective Search versus Brute Force. ICCA Journal, Vol. 9, No. 3
- David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
1990 ...
- Chun Ye (1992). Experiments in Selective Search Extensions. MSc. thesis, Department of Computing Science, University of Alberta, pdf
- Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3
- David McAllester, Deniz Yuret (1993). Alpha-Beta Conspiracy Search. ps (draft) » Alpha-Beta Conspiracy Search
- Javier Ros Padilla (1994). Estimating Asymmetry and Selectivity in Chess Programs. ICCA Journal, Vol. 17, No. 1 [1]
- Deniz Yuret (1994). The Principle of Pressure in Chess. TAINN 1994
- Lev Finkelstein, Shaul Markovitch (1998). Learning to Play Chess Selectively by Acquiring Move Patterns. ICCA Journal, Vol. 21, No. 2, pdf
- Rainer Feldmann, Burkhard Monien (1998). Selective Game Tree Search on a Cray T3E. ps
2000 ...
- Paul E. Utgoff, Richard P. Cochran (2000). A Least-Certainty Heuristic for Selective Search. CG 2000, pdf » LCF
- Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. in Jaap van den Herik, Hiroyuki Iida (eds.) (2000). Games in AI Research. Universiteit Maastricht, pdf preprint
- Ulf Lorenz, Burkhard Monien (2002). The Secret of Selective Game Tree Search, When Using Random-Error Evaluations. Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS)
- David McAllester, Deniz Yuret (2002). Alpha-Beta Conspiracy Search. ICGA Journal, Vol. 25, No. 1 » Alpha-Beta Conspiracy Search
- Brian Sheppard (2004). Efficient Control of Selective Simulations. CG 2004
- Brian Sheppard (2004). Efficient Control of Selective Simulations. ICGA Journal, Vol. 27, No. 2 [2]
- Pálmi Skowronski (2009). Gradual Focus: A Method for Automated Feature Discovery in Selective Search. M.Sc. thesis
2010 ...
- Omid David, Moshe Koppel, Nathan S. Netanyahu (2010). Optimizing Selective Search in Chess. ICML - Workshop on Machine Learning and Games
- Maarten Schadd (2011). Selective Search in Games of Different Complexity. Ph.D. Thesis. Department of Knowledge Engineering, Maastricht University
Forum Posts
1998 ...
- A new selective heuristic? by Frank Schneider, CCC, June 21, 1998 » Reductions
2000 ...
- Selective Searching by Bob Durrett, rgcc, November 19, 2000
- pruning vs extensions vs qsearch - are these all effectively the same? by Scott Farrell, CCC, November 27, 2002
- Evaluation-based Reductions and/or Extensions by Tom Likens, CCC, December 28, 2003
- extensions + reductions + pruning = confusion by Johan de Koning, CCC, March 24, 2004 (was Shredder 8 secret: search depth?)
- Extension - Reductions and threats by mjlef, Winboard Forum, May 17, 2006
- Extensions/Reductions by Luca Hemmerich, CCC, September 28, 2009
2010 ...
- Counting depth as a function of number of legal moves by Pio Korinth, CCC, February 28, 2012 » Depth
- Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012 [3]
- Houdini 3 reducing the depth feature by Maurizio Maglio, CCC, October 17, 2012 » Houdini
- selective depth definition by Uri Blass, CCC, February 13, 2014 » Stockfish
- Is modern chess software lossless or lossy? by Meni Rosenfeld, CCC, January 10, 2018 » Playing Strength
- Names of selectivity algorithms by Vivien Clauzon, CCC, July 26, 2018
- delaying tactics: prune or extend? by Harm Geert Muller, CCC, March 10, 2019 » Tactics
2020 ...
- Tactical search by Alvaro Cardoso, CCC, June 13, 2020 » Tactics
External Links
- Living Being Quintet - On the heights, Altitude Jazz Festival 2015, YouTube Video
References
- ↑ ICCA Journal, Vol. 17, No. 1 by Jos Uiterwijk, rgcc, May 02, 1994
- ↑ slightly revised version of the CG 2004 paper
- ↑ Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder