What program first used hard pruning?

[lkaufman]

Which is the earliest program known to make use of hard pruning. I mean by this arbitrarily discarding all "quiet" moves (moves other than captures, checks, promotions, and perhaps certain other moves) on the last couple of plies once N moves have been examined? I know Rybka used it, but I'd like to know whether earlier programs (perhaps Fruit?) also used this idea. Who gets credit for it?

[bob]

Which is the earliest program known to make use of hard pruning. I mean by this arbitrarily discarding all "quiet" moves (moves other than captures, checks, promotions, and perhaps certain other moves) on the last couple of plies once N moves have been examined? I know Rybka used it, but I'd like to know whether earlier programs (perhaps Fruit?) also used this idea. Who gets credit for it?

Any early program. Mackhack. Old Blitz. Chess 3.x and predecessors. Coko. JBIIT (Berliner). Etc...

The idea has been around _forever_.

[lkaufman]

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?

[Michael Sherwin]

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?

As far as I know, I started the modern use of it. I had it in a version of RomiChess. I think that it was Version P3a. RomiChess P3a is the only RomiChess version to score 100% in a WBEC test tournament. I then posted about it here at talkchess. Uri Blass posted in that thread. After that it was used in the new Glaurung. I came up with the idea on my own as I was not aware that it had ever been tried with LMR that way. Fruit 2.1 does not use it. And I called it LMP.

So, unless someone can prove otherwise, I am taking credit for it!

[Michael Sherwin]

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.

[mcostalba]

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?

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.

[Michael Sherwin]

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.

Well, they are in giant zip files in the form of individual text files. So unless there is a program that can search through a directory of those for the key words then I don't think that they will be retrievable.

[Gian-Carlo Pascutto]

The idea is extremely obvious when you know about LMR or history pruning.

Deep Sjeng 1.5 did this. I'm sure many people invented it independently.

[lkaufman]

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?

[mcostalba]

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?

Because you reach higher depths using the same allotted time.

You can assume that given a certain amount of time to think this translates in a given numer of searched nodes that is more or less independent on what nodes you search.

So given your 'searchable nodes' budget you can use it on small depths but with very exsaustive search or instead going on higher depths with a more partial search, i.e. with more pruning.


Tradoff that pays off in chess it seems is a tradoff of search depth vs per node accuracy.