Hard pruning history

[BB+]

Toga II used a version of "ignoring" moves, though it did so with history (as per the Fruit paradigm, as it were). I remember (back in 2007 when I was more into development) being impressed that such an idea (as opposed to reducing depth) could actually work.

Going through the versions at http://www.superchessengine.com/toga_ii.htm it seems that it was introduced in the 1.2 series (it is not in 1.1).

Here it is in 1.2.1a:

Code: Select all

     if (!in_check && depth <= 4 && node_type != NodePV && new_depth < depth
                    && value < (depth <= 3 ? HistoryValue / 3 : HistoryValue / 4)) 
                  continue;

So when we are at a depth of 4 ply or less, a move with a bad history score can simply be skipped.

The earliest I find such an idea is in 1.2 with a date of Mar 7 2006 on the search_full.cpp file.

[BB+]

It appears that Toga II 1.2beta2a was indeed released on Mar 8, 2006. For comparison, the release of Rybka 1.2 was May 1, 2006, while 1.1 was Mar 16, 2006, and there were a bunch of minor beta versions prior to that (reaching 13d). I think I only have 1.2 lying around (it was included with 2.3.2a if I recall). I don't know which, if any, of these Rybka versions utilised "hard pruning".

[hyatt]

This is just a form of futility pruning, which has been around forever. Early programs used outright forward pruning. Heinz's book describes "hard pruning" in last 2-3 plies. I've been doing it in last 4 for a couple of years since I worked on tuning it on our cluster... But it is certainly not a new idea.

In Cray Blitz, last 2 years' worth of versions, we had a full-width part of the search, then a much more selective last 4 plies, then dropped into the traditional q-search code. Going more than 4 plies seemed to be too risky back in 1995, and that still seems to be true today. At least I have found no suitable "futility margin" that works at ply=5 or greater, but the last 4 plies work well.

[BB+]

My recollection is that the terminology of Heinz had "razoring" at 3 ply, while "extended futility" was 2 ply, and "futility" was 1 ply, and the margins were rather large. I think the term "hard pruning" was meant to refer to pruning being made based on considerations centred around history score or place in a move list, rather than (say) on the difference between scout and eval.

[BB+]

As you say, the idea of looking at fewer moves at lesser depths is old. From the MacHack paper The Greenblatt chess program:

The width of the search
Like the depth, the number of moves considered at each level is a constant tempered by some heuristics. The constants (a difference one for each level are [...] increased to 15, 15, 9, 9, 7 for tournament play, which means that the basic width at the top two levels is 15, while the basic width at levels three and four is 9, and the width is 7 for all succeeding levels.
The heuristics involved all have the effect of extending the width beyond the basic setting [...]
The heuristics are:
1) All safe checks are investigated.
2) At the first or second level, all captures are investigated.
3) An attempt is made to investigate moves of a certain minimum number of distinct pieces [...]
4) Moves which lead to mate against the side to move are ignored and not tallied against the basic width [...]

[BB+]

From 1973, we have the COKO III: The Cooper-Koz Chess Program:

The restriction of moves to the set of Figure 12 [the ignored moves, called the "Fischer set"] is quite arbitrary and is a function of ply depth in the search tree. At ply 1, the [set] is defined as all but the top 50 moves [...] For higher ply levels, the [ignored moves set] becomes large and usually includes all moves except the tactical moves (also a function of ply level), plus one to six strategical moves.

[kingliveson]

It appears that Toga II 1.2beta2a was indeed released on Mar 8, 2006. For comparison, the release of Rybka 1.2 was May 1, 2006, while 1.1 was Mar 16, 2006, and there were a bunch of minor beta versions prior to that (reaching 13d). I think I only have 1.2 lying around (it was included with 2.3.2a if I recall). I don't know which, if any, of these Rybka versions utilised "hard pruning".

There are some more versions available here: http://cap.connx.com/chess-engines/new- ... a_fossils/ if this is what you meant.

[BB+]

My cursory glance indicates that R1.1/R1.2 was not using "hard pruning". My determination of this is based on noting that every move that is generated by next_move gets passed to make_move (there are two functions that call next_move, and each has this property). Of course, the hard pruning might be embedded in next_move, or maybe it is used after calling evaluate, or maybe the "low-depth" function doesn't use next_move, but I don't find any of those all that likely. I might also note that the search in R1.1 has various features not seen in the rather vanilla method of Rybka 1.0 Beta.

[BB+]

If I use this same analysis method with R2.1o/R2.3.2a, I find that the latter has repetition "pre-detection", but other than that there is no intervention between next_move and make_move as in R3. So my preliminary guess is that R3 was the first in Rybka series to have this "hard pruning", though I should point out that its effect in R3 is ameliorated by a comparison of scout and eval, with the "positional gain" of the move in the mix. In this sense, it is more like "futility" than some of the methods mentioned.

The conditions are something like: if count is more than 5, and phase is "ordinary moves", and move is not special, and the move's positional gain is too small (here the depth comes into play in the margin with the comparison), then ignore the move. After this, there is a similar condition for moves with a bad SEE. There is also a "post-make_move" condition (using the new evaluation, and perhaps with the condition on count differing) that can still eliminate moves without passing to recursion (the move is simply unmade). This is at "regular depth" CUT/ALL nodes and also "low depth" nodes, with the numerology differing at times (the R3 pre-evaluation can tweak some of the margins also).

[hyatt]

My recollection is that the terminology of Heinz had "razoring" at 3 ply, while "extended futility" was 2 ply, and "futility" was 1 ply, and the margins were rather large. I think the term "hard pruning" was meant to refer to pruning being made based on considerations centred around history score or place in a move list, rather than (say) on the difference between scout and eval.

I do not believe that pruning based on "history counters" is functional, after testing. And I even modified Fruit to test this as well, for verification.

I assume "pruning" means just that, to cut a branch off and never consider it. Which is done in futility pruning. Or, for me, in the last 4 plies but not particularly based on position in the move list, but upon other static considerations as well...

I've always tried to use the term "forward pruning" since that is more descriptive and distinguishes it from alpha/beta which uses "backward pruning" that is nowhere related to forward pruning at all.