Difference between revisions of "Selectivity"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
| Line 62: | Line 62: | ||
* [[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''. MSc-Thesis, [http://www.ru.is/lisalib/getfile.aspx?itemid=12149 pdf] | * [[Pálmi Skowronski]] ('''2009'''). ''Gradual Focus: A Method for Automated Feature Discovery in Selective Search''. MSc-Thesis, [http://www.ru.is/lisalib/getfile.aspx?itemid=12149 pdf] | ||
==2010 ...== | ==2010 ...== | ||
| Line 79: | Line 79: | ||
* [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/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]] | ||
| Line 86: | Line 86: | ||
=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] | ||
Revision as of 23:25, 29 July 2019
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.
Contents
Extensions
- Botvinnik-Markoff Extension
- Capture Extensions
- Check Extensions
- Mate Threat Extensions
- One Reply Extensions
- Passed Pawn Extensions
- PV Extensions
- Recapture Extensions
- SEX Algorithm
- Singular Extensions
Pruning
- AEL-Pruning
- Delta Pruning
- Enhanced Forward Pruning
- Futility Pruning
- History Leaf Pruning
- Mate Distance Pruning
- Move Count Based Pruning (Late Move Pruning)
- Multi-Cut
- Null Move Pruning
- Parity Pruning
- ProbCut
- Reverse Futility Pruning
- Uncertainty Cut-Offs
Reductions
See also
- Bobby's Strategic Quiescence Search
- Parallelism and Selectivity in Game Tree Search | Video, Talk by Tord Romstad
- Quiescence Search
- Selective Search (Magazine)
- Selective Search versus Brute Force - Conference at WCCC 1986
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
- 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)
- Pálmi Skowronski (2009). Gradual Focus: A Method for Automated Feature Discovery in Selective Search. MSc-Thesis, pdf
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 ...
- Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012 [2]
- 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
- delaying tactics: prune or extend? by Harm Geert Muller, CCC, March 10, 2019 » 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
- ↑ Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder
