Names of selectivity algorithms

[xr_a_y]

I feel sometimes lost about selectivity tricks name.

Let's say we can do things when

• a- staticEval > beta + margin
• b- staticEval < beta - margin
• c- staticEval > alpha + margin
• d- staticEval < alpha - margin
• e- mountCount > threshold
• f- see < threshold

Things we can to are

• 1- skip a (silent) node
• 2- return a value right now
• 3- do a reduce search
• 4- switch to qsearch directly
• 5- do a nullmove search (eventually verified by reduced or qsearch)
• 6- reduce the search depth

d:1 is futility pruning
e:1 is mount count pruning
f:1 is see pruning
a:5 is null move pruning
a:2 is razoring ?
...

Do we have a name for every combination ?

[Sven]

You will find the answers here:
https://www.chessprogramming.org/Selectivity
and until end of July here:
https://chessprogramming.wikispaces.com/Selectivity

Btw, never heard about "mount count" in this context, I guess you meant "move count"?

[xr_a_y]

Apparently I am more dyslexic than I thought ! Yes I was referring to move count pruning of course.

I knew this wiki page already, but I feel that many choices have no (clear) name yet.

Depending on the margin involved for example, one can directly return a value (for a large margin) and this is often called a "pruning", verify a little more with qsearch (for a smaller margin) and this is often called a "verified" pruning or just reduce the search (for an even smaller margin) and this is often called a "reduction".

But for example, only futility "pruning" is used, not "verified futility pruning", nor "futility reduction".

[Sven]

Some notes have to be added.

I think most combinations do not make any sense. Also it is not as easy as putting one of a-f together with one of 1-6, there are also some conditions (e.g. node type - PV node or zero-window), context (e.g. are we at the parent or at the child node), type of search (full-width/QS) or maybe other important "primary" parameters.

Also a-f is not complete, you mention staticEval but also the dynamic score of a subtree can be subject of a decision about pruning or reduction.

Items 3 and 6 appear identical to me.

Item 5 "do a nullmove search" is in the wrong group: first you do a nullmove search, and if that fails high (and possibly a verification search fails high as well) then you take your decision - usually "2" (return a value).

Nullmove pruning and a:5 does not match exactly. A typical precondition for trying the null move is staticEval >= beta (so >= instead of >, and no non-zero margin involved).

Items 1 and 2 are almost the same, only with different context. 1 skips a subtree from parent viewpoint while 2 does the same after having already entered the child node. Both imply to assume that the skipped subtree has no impact on the overall search result. For 2 this is only possible by returning a "fail high" score which the parent (through negamax) sees as "that move does not raise alpha for me".

Razoring typically is not a:2, it is more like a:4 (from child node viewpoint) or d:4 (from parent viewpoint), but again with >= resp. <=. Of course margins will differ depending on whether you are at the child node already (so you made the move) or not.

f:1 is typically applied in QS only.

d:1 is futility pruning at the parent node, a:1 at the child node, again with <= resp. >= in both cases.

e:1 would be "move-count based late move pruning" (LMP), I'm not sure whether that exists, it sounds dangerous to me without additional pruning conditions. e:3 is move-count based late move reduction (LMR).

This is certainly not the whole story

[DustyMonkey]

An accurate list of all the permutations of all the sets of simultaneous "selectivity" inputs is not possible, since the set of all possible selectivity inputs is in practice inexhaustible.

The history heuristic is an example of how a selectivity input can be invented. There is no practical end to the ways that you can decimate the data being generated by the on-going search, to effectively steer the on-going search.

Which way to steer is a statistical problem.
Which way to decimate is a combinatorial problem.

The underlying principles are the same as all other information-theory related fields, such as data compression. You are building a predictive model, but instead of predicting the next symbol or if an email is spam or not, you are predicting the utility of a set of possible search efforts.