Selectivity

Home * Search * Selectivity

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

• 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

• Fail-High Reductions - FHR
• Late Move Reductions - LMR
• Null Move Reductions
• RankCut
• Razoring

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
• 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 ¹
• 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 ²
• 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 ³
• 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

Vincent Peirani, Émile Parisien, Tony Paeleman, Julien Herné, Yoann Serra

Watch on YouTube

References