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?

"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.

One theory is that since moves are ordered by history, a pruned move that actually would have been chosen on the last ply is one with a better eval but a worse history than the chosen move. Apparently good history is more important than the apparent change in the score on the last ply, given a large difference in history. Another theory is that if many moves say the position is bad, but one says it's good, maybe the good move is an illusion more often than not. Either of these theories seem right to anyone?

[Don]

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.

One theory is that since moves are ordered by history, a pruned move that actually would have been chosen on the last ply is one with a better eval but a worse history than the chosen move. Apparently good history is more important than the apparent change in the score on the last ply, given a large difference in history. Another theory is that if many moves say the position is bad, but one says it's good, maybe the good move is an illusion more often than not. Either of these theories seem right to anyone?

That is the explanation I believe. The moves we are throwing out cannot have much impact anyway. For example if the history says Nh3g5 is bad, the evaluation probably thinks it's good because it gets the knight off the edge, but then the opponent is going to gain a tempo playing a move the search cannot yet see. The history knows better, the evaluation doesn't.

[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.

One theory is that since moves are ordered by history, a pruned move that actually would have been chosen on the last ply is one with a better eval but a worse history than the chosen move. Apparently good history is more important than the apparent change in the score on the last ply, given a large difference in history. Another theory is that if many moves say the position is bad, but one says it's good, maybe the good move is an illusion more often than not. Either of these theories seem right to anyone?

That is the explanation I believe. The moves we are throwing out cannot have much impact anyway. For example if the history says Nh3g5 is bad, the evaluation probably thinks it's good because it gets the knight off the edge, but then the opponent is going to gain a tempo playing a move the search cannot yet see. The history knows better, the evaluation doesn't.

That sounds like an exception rather than a rule. A knight at h3 is almost always badly placed. And a good evaluation will correctly see this and try to correct it. I don't want to throw out a move that is occasionally bad, when 95% of the time it is actually good...

[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.

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.

I tried to respond to BB+ on this subject at openchess, but I did not receive the activation email. So, I am ranting here. He is also saying Toga Toga Toga. Well it wasn't Toga Toga Toga it was Romi Romi Romi.

I agree that various forms of hard pruning were done at the beginning for the reason stated. However, the question was who first started doing it with LMR. I started that ball rolling, for everyone, when I tried it in RomiChessP3a and then POSTED ABOUT IT HERE IN LATE 2005, EARLY 2006. Maybe Deep Sjeng 1.5 used it before I posted about it, I don't know. The point is that I am the one that posted about it. Is it so impossible to give me any credit for it ending up in several programs and so easy to deny that my post had anything to do with it? But of course it is.

Tord gave me an unspecified credit for ideas that ended up in Glaurung 2 that made Glaurung 2 much stronger. This idea is just one of the ideas that I posted about that are in Glaurung 2. But, unless Tord gives some specifics about what my contribution to Glaurung 2 was I will never get credit for anything that I have ever posted about. Except Sam Hamilton and Oliver Brauch gave me credit for my null move reduction scheme that I posted about that ended up in their engines.

If it was not for the few gracious authors that are willing to give credit where credit is due I would have kissed this place good by sooner rather than later.

[Albert Silver]

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.

Google Desktop

[Don]

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.

Google Desktop

What's wrong with grep?

[Karlo Bala]

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.

There are other explanations. Posts from Amir Ban, some 12 years ago:

>not much you can do... horizon effect happens anytime you stop the search
>in a non-quiet position... everybody sees it... just get faster..

I don't agree with this statement. The exposure to horizon effects is what usually limits a program's strength, more than the depth it can reach. The fact that it cannot be totally overcome is irrelevant to the fact that limiting its damage is a first priority. Just getting generally deeper is a poor way to do that, and not very effective either.

Amir

...
I don't think the right way is to add more stuff to the quiescence search, and I suspect that many programs try too hard in quiescence. This can be not only expensive but counterproductive too, since it is quite possible for a program to become stronger by seeing less, a consequence of the horizon effect.

Amir

[Engin]

if i am not wrong a big improvement in computerchess maked Sargon with the alpha beta cutoff ??

[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.

I tried to respond to BB+ on this subject at openchess, but I did not receive the activation email. So, I am ranting here. He is also saying Toga Toga Toga. Well it wasn't Toga Toga Toga it was Romi Romi Romi.

It was done well before 2005. Both Bruce Moreland and I played with the idea in 1995/1996, after talking to others. The problem then was that depth was limited due to hardware speeds, and we did not do anything more than _pure_ LMR which did not work well (and which doesn't work for me today). Yes, as moves appear later in the list, their likelihood of becoming a new best move are low, but there is more to it than just using the position in the list. And that was the thing we did not experiment with in 1995. I do not know if the topic started from Kittinger, SMK, or someone else. But it was discussed a few times. SMK was using it well prior to 2005, for certain.

I agree that various forms of hard pruning were done at the beginning for the reason stated. However, the question was who first started doing it with LMR. I started that ball rolling, for everyone, when I tried it in RomiChessP3a and then POSTED ABOUT IT HERE IN LATE 2005, EARLY 2006. Maybe Deep Sjeng 1.5 used it before I posted about it, I don't know. The point is that I am the one that posted about it. Is it so impossible to give me any credit for it ending up in several programs and so easy to deny that my post had anything to do with it? But of course it is.

Tord gave me an unspecified credit for ideas that ended up in Glaurung 2 that made Glaurung 2 much stronger. This idea is just one of the ideas that I posted about that are in Glaurung 2. But, unless Tord gives some specifics about what my contribution to Glaurung 2 was I will never get credit for anything that I have ever posted about. Except Sam Hamilton and Oliver Brauch gave me credit for my null move reduction scheme that I posted about that ended up in their engines.

If it was not for the few gracious authors that are willing to give credit where credit is due I would have kissed this place good by sooner rather than later.

Or perhaps simply don't be so worried about the credit?

In the case of the tests Bruce and I did in the 1995-1996 range, I had made a change to crafty to stop worrying about the history value for ordering moves after trying 4 "history-suggested moves" (as in Schaeffer's papers). After settling on 4 (eventually, after a lot of testing) I told Bruce what I was doing and he tried the same thing and saw the same speedup. But he mentioned that since we were giving up on ordering since we were pretty convinced that after the TT move, good captures, killers and 4 history moves, we were not going to get a fail high, why not reduce the depth of the rest of the moves by a ply. And we fiddled around with this. But never thought about the idea of not reducing checks, etc, and just considered where the move was to be tried (early or late).

We were both convinced that SMK used this same idea to make Shredder reach the rather extreme depths it was seeing when it dominated computer chess for a few years...


As far as "starting the LMR ball rolling", particularly when we get to LMP as opposed to LMR, LMP was a 1960's technique, clearly. LMR came along in the mid to late 90's. Yes, there are changes in LMP today compared to 1960's. Today we limit it to plies near the tips. In 1960's _all_ nodes searched were "near the tips" since 5 plies was the limit.

[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.

One theory is that since moves are ordered by history, a pruned move that actually would have been chosen on the last ply is one with a better eval but a worse history than the chosen move. Apparently good history is more important than the apparent change in the score on the last ply, given a large difference in history. Another theory is that if many moves say the position is bad, but one says it's good, maybe the good move is an illusion more often than not. Either of these theories seem right to anyone?

My comment has to be that this is again serendipity. You mis-evaluate a move if you search it, so you produce a better result if you prune it. Ideally you would not prune a good move, nor would you search a bad move to any significant depth. Realistically, however...