What program first used hard pruning?

[lkaufman]

I know all this, but my question is whether hard pruning can possibly ever help results AT A GIVEN DEPTH. It would seem to be impossible, but in Komodo we actually observed a gain in Elo AT FIXED DEPTH for pruning on the last ply. Have you ever observed this in SF, and/or can you explain it?

[Daniel Shawul]

Last ply pruning is equivalent to lazy evaluation at top of qsearch. So more positional terms are sacrificed for "wood" with the pruning. So I will not be surprised if it actually helped at fixed depth games. The prunings above ply 1 gamble with the material itself which is too risky. Once I used margin = 0 at ply 1 accidentally (still in there btw) which scored better ...
YMMV

[jdart]

I first became aware of this when I saw it in the Toga source code, although as noted Romichess may have used it earlier. But really, this is just an example of a "Shannon Type B" strategy, which has been around for a very long time, but has become more popular rather recently.

--Jon

[mcostalba]

I know all this, but my question is whether hard pruning can possibly ever help results AT A GIVEN DEPTH. It would seem to be impossible, but in Komodo we actually observed a gain in Elo AT FIXED DEPTH for pruning on the last ply. Have you ever observed this in SF, and/or can you explain it?

No, we have never tested under such conditions.

[opraus]

It would seem then that in many cases, 'worse' moves were pruned, which would have otherwise been chosen by the shallow search; Indicating that a static pruning condition can be smarter than a shallow search ... interesting.

I wonder what these conditions were?

[bob]

I'm quite surprised to hear this. I don't recall ever hearing of it twenty years ago when I worked with Don on RexChess or with Don and Julio Kaplan on Socrates. It seems rather silly to just look at the first N moves and then discard the others, so it's really strange to hear that this was in such early programs. I know that some programs picked out moves based on various criteria, but the idea of simply examining only the first N moves (plus checks and captures) is hard to justify. Can you provide the rationale for its use in your old program, and your opinion of the idea now?

You can probably find Greenblatt's paper published in the DEC journal. In it he describes a "tapered pruning approach" where the default was to search 5 plies deep, looking at the "best 15 moves at ply=1, tapering to "best 9" (or whatever, memory fails me at the moment) at ply=5.

Over on OpenChess, I made this same comment and BB+ provided the excerpts from the papers I mentioned, showing that the idea was old in 1970, already.

We did exactly this in the 1968-1977 versions of Blitz, converting to full-width in 1978 after the brute-force "revolution" hit.

The "rationale" was in 1968 nobody could do a full-width 5 ply search. In 1968 I was searching one node per second, so even 2 plies + some captures was a real stretch. Forward pruning was the only way to get to reasonable depth, although it introduced some significant errors. My selective search program in 1977 was almost 75,000 lines of Code. Coko was close to 100,000 lines. My (much stronger) brute force program in 1978 was under 10,000 lines by comparison. All that extra code was used to try to pick the "best N" moves, which is a mighty challenge.

[bob]

I think that the time frame that I would have made the post about LMP would have been from late 2005 to early 2006. The post do not go back that far.

I'll see if I can find it on Dann Corbit's site. I understand that he has the older stuff.

If you search for Greenblatt's paper in the late 60's on his chess program, you will find details about the idea given there. It is _not_ new.

In the late 60's and early 70's we _had_ to prune like that just to get to depth=5. At one node per second, hardware was very limited.

[bob]

IMHO pruning and LMR do work due because of this:

Code: Select all

If after having searched the first moves of a node you _still_ are unable to have a cut-off then the probability of reaching a cut-off with at least one of the remaining moves is quite low.

This statistical behaviour it seems is the _rule_ that holds in chess, so all the feautures that rely on this underlying property (either pruning late moves or reducing them) happens to work.

Your explanation implies that hard pruning should always have some Elo cost (however small) at a given depth, which is more than offset by the time saved. Can you think of any reason why hard pruning would ever actually HELP the Elo at a given depth?

If you mean, say, to take Crafty, and set the depth to N, and play the normal version limited to that depth against a set of opponents, and then play a modified version with pruning disabled, but using the same depth, then absolutely the latter will be stronger. Because there certainly is error associated. But you gain by going deeper. So you miss some things you would see with no pruning, but you see _more_ things that you would miss if forced to use the reduced depth.

[bob]

I know all this, but my question is whether hard pruning can possibly ever help results AT A GIVEN DEPTH. It would seem to be impossible, but in Komodo we actually observed a gain in Elo AT FIXED DEPTH for pruning on the last ply. Have you ever observed this in SF, and/or can you explain it?

"serendipity".



No rational explanation I can think of where you throw moves out and get a better result, unless your evaluation is bad and throwing out moves eliminates positions you evaluate badly.

[bob]

I first became aware of this when I saw it in the Toga source code, although as noted Romichess may have used it earlier. But really, this is just an example of a "Shannon Type B" strategy, which has been around for a very long time, but has become more popular rather recently.

--Jon

"but has become more popular _again_ rather recently. In the 60's and 70's this was the rule to do searches in chess... unless you could accept a 1-2 ply search result.