What program first used hard pruning?
Moderators: hgm, Rebel, chrisw
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
What program first used hard pruning?
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?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: What program first used hard pruning?
Any early program. Mackhack. Old Blitz. Chess 3.x and predecessors. Coko. JBIIT (Berliner). Etc...lkaufman wrote: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?
The idea has been around _forever_.
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: What program first used hard pruning?
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?
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: What program first used hard pruning?
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.lkaufman wrote: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?
So, unless someone can prove otherwise, I am taking credit for it!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: What program first used hard pruning?
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.
I'll see if I can find it on Dann Corbit's site. I understand that he has the older stuff.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: What program first used hard pruning?
IMHO pruning and LMR do work due because of this:lkaufman wrote: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?
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.
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: What program first used hard pruning?
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.Michael Sherwin wrote: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 are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: What program first used hard pruning?
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.
Deep Sjeng 1.5 did this. I'm sure many people invented it independently.
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: What program first used hard pruning?
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 wrote: IMHO pruning and LMR do work due because of this:
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.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.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: What program first used hard pruning?
Because you reach higher depths using the same allotted time.lkaufman wrote: 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?
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.