Selectivity - peregrineshahin/ChessProgrammingWiki GitHub Wiki
title: 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.
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
- Internal Iterative 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 [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
Vincent Peirani, Émile Parisien, Tony Paeleman, Julien Herné, Yoann Serra
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