25,161
edits
Changes
Created page with "'''Home * Search * Selectivity''' '''Selectivity''' gives a whiff of Shannon's Type B search to Shannon's Type A or..."
'''[[Main Page|Home]] * [[Search]] * Selectivity'''
'''Selectivity''' gives a whiff of [[Type B Strategy|Shannon's Type B]] search to [[Type A Strategy|Shannon's Type A]] or [[Brute-Force|brute-force]]. The goal is to search "interesting" and forced branches which are or are likely to become part of the [[Principal Variation|principal variation]] deeper than nominal, but to reduce uninteresting branches.
=[[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]]
* [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]] (Late Move Pruning)
* [[Multi-Cut]]
* [[Null Move Pruning]]
* [[Parity Pruning]]
* [[ProbCut]]
* [[Reverse Futility Pruning]]
* [[Uncertainty Cut-Offs]]
=[[Reductions]]=
* [[Fail-High Reductions]] - FHR
* [[Late Move Reductions]] - LMR
* [[Null Move Reductions]]
* [[Razoring]]
=See also=
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[Tord Romstad#Video|Parallelism and Selectivity in Game Tree Search | Video]], Talk by [[Tord Romstad]]
* [[Quiescence Search]]
* [[Selective Search]] (Magazine)
* [[WCCC 1986#Workshop|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 [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai83.html IJCAI 83], pp. 760-762. Karlsruhe. [http://ijcai.org/Past%20Proceedings/IJCAI-83-VOL-2/PDF/039.pdf pdf]
* [[Don Beal]] ('''1986'''). ''Selective Search without Tears.'' [[ICGA Journal#9_2|ICCA Journal, Vol. 9, No. 2]]
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
==1990 ...==
* [[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]]
* [[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
* [[Lev Finkelstein]], [[Shaul Markovitch]] ('''1998'''). ''[http://www.cs.technion.ac.il/%7Eshaulm/papers/abstracts/Finkelstein-1998-LPC.html Learning to Play Chess Selectively by Acquiring Move Patterns.]'' [[ICGA Journal#21_2|ICCA Journal, Vol. 21, No. 2]], [http://www.cs.technion.ac.il/%7Eshaulm/papers/pdf/Finkelstein-Markovitch-icca1998.pdf pdf]
* [[Rainer Feldmann]], [[Burkhard Monien]] ('''1998'''). ''[http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/ABSTRACTS/FM_T3E.html Selective Game Tree Search on a Cray T3E]''. [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/FM_T3E.ps.Z ps]
==2000 ...==
* [[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]
* [[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), [http://www.top-5000.nl/ps/The%20secret%20of%20selective%20earch%20when%20using%20random.pdf 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 ...==
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Optimizing Selective Search in Chess''. ICML Workshop on Machine Learning and Games, Haifa, Israel
* [[Maarten Schadd]] ('''2011'''). ''Selective Search in Games of Different Complexity''. Ph.D. Thesis. Department of Knowledge Engineering, [[Maastricht University]]
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=21017 A new selective heuristic?] by [[Frank Schneider]], [[CCC]], June 21, 1998 » [[Reductions]]
==2000 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7b66bdec7f729fa7 Selective Searching] by Bob Durrett, [[Computer Chess Forums|rgcc]], November 19, 2000
* [https://www.stmintz.com/ccc/index.php?id=267678 pruning vs extensions vs qsearch - are these all effectively the same?] by [[Scott Farrell]], [[CCC]], November 27, 2002
* [https://www.stmintz.com/ccc/index.php?id=338851 Evaluation-based Reductions and/or Extensions] by [[Tom Likens]], [[CCC]], December 28, 2003
* [https://www.stmintz.com/ccc/index.php?id=356488 extensions + reductions + pruning = confusion] by [[Johan de Koning]], [[CCC]], March 24, 2004 (was [https://www.stmintz.com/ccc/index.php?id=356109 Shredder 8 secret: search depth?])
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4820 Extension - Reductions and threats] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], May 17, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=29905 Extensions/Reductions] by [[Luca Hemmerich]], [[CCC]], September 28, 2009
==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.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm 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=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]]
=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner] by [[Ed Schroder|Ed Schröder]] <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> » [[Rebel]]
* [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
: [[Videos#VincentPeirani|Vincent Peirani]], [[Videos#EmileParisien|Émile Parisien]], [[Videos#TonyPaeleman|Tony Paeleman]], [http://www.julienherne.com/ Julien Herné], [http://www.simonoviez.com/english/YoannSerraus.htm Yoann Serra]
: {{#evu:https://www.youtube.com/watch?v=xoaSRUrL8lE|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
'''Selectivity''' gives a whiff of [[Type B Strategy|Shannon's Type B]] search to [[Type A Strategy|Shannon's Type A]] or [[Brute-Force|brute-force]]. The goal is to search "interesting" and forced branches which are or are likely to become part of the [[Principal Variation|principal variation]] deeper than nominal, but to reduce uninteresting branches.
=[[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]]
* [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]] (Late Move Pruning)
* [[Multi-Cut]]
* [[Null Move Pruning]]
* [[Parity Pruning]]
* [[ProbCut]]
* [[Reverse Futility Pruning]]
* [[Uncertainty Cut-Offs]]
=[[Reductions]]=
* [[Fail-High Reductions]] - FHR
* [[Late Move Reductions]] - LMR
* [[Null Move Reductions]]
* [[Razoring]]
=See also=
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[Tord Romstad#Video|Parallelism and Selectivity in Game Tree Search | Video]], Talk by [[Tord Romstad]]
* [[Quiescence Search]]
* [[Selective Search]] (Magazine)
* [[WCCC 1986#Workshop|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 [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai83.html IJCAI 83], pp. 760-762. Karlsruhe. [http://ijcai.org/Past%20Proceedings/IJCAI-83-VOL-2/PDF/039.pdf pdf]
* [[Don Beal]] ('''1986'''). ''Selective Search without Tears.'' [[ICGA Journal#9_2|ICCA Journal, Vol. 9, No. 2]]
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
==1990 ...==
* [[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]]
* [[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
* [[Lev Finkelstein]], [[Shaul Markovitch]] ('''1998'''). ''[http://www.cs.technion.ac.il/%7Eshaulm/papers/abstracts/Finkelstein-1998-LPC.html Learning to Play Chess Selectively by Acquiring Move Patterns.]'' [[ICGA Journal#21_2|ICCA Journal, Vol. 21, No. 2]], [http://www.cs.technion.ac.il/%7Eshaulm/papers/pdf/Finkelstein-Markovitch-icca1998.pdf pdf]
* [[Rainer Feldmann]], [[Burkhard Monien]] ('''1998'''). ''[http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/ABSTRACTS/FM_T3E.html Selective Game Tree Search on a Cray T3E]''. [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/FM_T3E.ps.Z ps]
==2000 ...==
* [[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]
* [[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), [http://www.top-5000.nl/ps/The%20secret%20of%20selective%20earch%20when%20using%20random.pdf 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 ...==
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Optimizing Selective Search in Chess''. ICML Workshop on Machine Learning and Games, Haifa, Israel
* [[Maarten Schadd]] ('''2011'''). ''Selective Search in Games of Different Complexity''. Ph.D. Thesis. Department of Knowledge Engineering, [[Maastricht University]]
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=21017 A new selective heuristic?] by [[Frank Schneider]], [[CCC]], June 21, 1998 » [[Reductions]]
==2000 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7b66bdec7f729fa7 Selective Searching] by Bob Durrett, [[Computer Chess Forums|rgcc]], November 19, 2000
* [https://www.stmintz.com/ccc/index.php?id=267678 pruning vs extensions vs qsearch - are these all effectively the same?] by [[Scott Farrell]], [[CCC]], November 27, 2002
* [https://www.stmintz.com/ccc/index.php?id=338851 Evaluation-based Reductions and/or Extensions] by [[Tom Likens]], [[CCC]], December 28, 2003
* [https://www.stmintz.com/ccc/index.php?id=356488 extensions + reductions + pruning = confusion] by [[Johan de Koning]], [[CCC]], March 24, 2004 (was [https://www.stmintz.com/ccc/index.php?id=356109 Shredder 8 secret: search depth?])
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4820 Extension - Reductions and threats] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], May 17, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=29905 Extensions/Reductions] by [[Luca Hemmerich]], [[CCC]], September 28, 2009
==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.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm 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=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]]
=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner] by [[Ed Schroder|Ed Schröder]] <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> » [[Rebel]]
* [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
: [[Videos#VincentPeirani|Vincent Peirani]], [[Videos#EmileParisien|Émile Parisien]], [[Videos#TonyPaeleman|Tony Paeleman]], [http://www.julienherne.com/ Julien Herné], [http://www.simonoviez.com/english/YoannSerraus.htm Yoann Serra]
: {{#evu:https://www.youtube.com/watch?v=xoaSRUrL8lE|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
