Author: Robert Hyatt
Date: 09:23:29 02/27/06
Go up one level in this thread
On February 27, 2006 at 11:51:09, Miguel A. Ballicora wrote:
>On February 27, 2006 at 09:41:37, Tord Romstad wrote:
>
>>On February 27, 2006 at 06:48:18, Tord Romstad wrote:
>>
>>>I'll try to write an explanation on my web page, and refer to that one
>>>in the future. I hope to have it ready today or tomorrow. Stay tuned!
>>
>>My first draft is ready:
>>
>>http://www.glaurungchess.com/lmr.html
>>
>>Comments, corrections and suggested additions or improvements
>>are welcome.
>
>I was away from CC 3 years and I was wondering what this technique was. Thanks
>for the explanation, it was pretty clear.
>Unfortunately, I tried this ~5 years ago in several ways and it did not work .
>It was not my idea, it was Bob Hyatt's here at CCC. I still have in my code this
>ancient lines (nodecount is moves searched):
>
> #if 0
> /* BH's suggestion, modified */
> if (nodecount == 15 && depth == 1) {
> break;
> }
> #endif
>
> #if 0
> /* BH's suggestion */
> if (nodecount == 15 && depth == 2) {
> depth--;
> }
> #endif
>
> #if 0
> /* BH's suggestion, modified */
> if (nodecount == 15 && prun_cand ) {
> break;
> }
> #endif
>
>Considering that after moves 15 the order in my case is determined by history
>heuristics, one the options literally was history pruning, and I tried
>reductions too. The tree decreased but my engine (gaviota) played terrible.
>Maybe I should give it a try again. As you can see, the implementation was too
>raw.
>
>Miguel
I think that came from Bruce and myself. We were playing with this basic idea
before the 1996 WMCCC event. We had noticed the "late move effect" where on a
node where you expect every move to fail low, that not searching some of the
late moves, or else searching them to reduced depth, could speed the search
dramatically. We even (or at least I did) took this a bit further to not
include captures and checks in this.
The one thing we did not think about, was using some sort of "history-driven"
criterion to further eliminate moves from the possible moves to be reduced.
That seems to be the missing ingredient in what we did. Tord also suggested the
idea that should one of these "reduced searches" fail high (where we are
expecting it to fail low) that we re-search the move without the reduction to
see if it fails high there as well.
I ran with a flavor of this in CCT8 and noticed no problems whatsoever from a
tactical perspective. My original thinking when implementing this was that it
would hurt tactics, but improve positional play, since reducing the depth on the
oddball moves would tend to drive the tactics over the horizon. Interestingly,
in testing the idea prior to CCT8, I discovered the opposite.
For example, one way I tested (besides using a bunch of nunn-type game matches)
was to take a test suite (I used several, including WAC) and tested using a
modification I've always had in my test code that says "run each position until
max time has been reached, or until an iteration completes and the solution move
was the best move." This "trick" gives useful information because the last
iteration done for each test position is the iteration where the key move was
chosen as best. For WAC, I run all positions with a 60 second time limit, only
one cpu, and then compute "sum of times squared" for each position (most are
zero seconds of course). I compare these numbers with the lowest being best,
and the late-move reduction version had the lowest time in every test I ran.
For WAC on my dual xeon, using 1 2.8ghz processor to eliminate the SMP variance,
it takes about 180 seconds total time to solve all 300 of them correctly. A
couple still take some time. #163 takes a little time, and #230 takes about 30
seconds or so. #2 is also not instant. #141 is easy to find the best move with
a fail high, but it takes quite a few seconds to get the mate score back, which
has to happen before the iteration completes.
So, bottom line, the idea seems workable now. I've got a few other things to
test, and some are playing with the reduction amount (I used 1.0 plies for CCT8
but Mike has been testing with 2.0 so there is room for improvement probably).
There are also a few other types of moves that might be excluded, but I am not
doing this at present (yet). Passed pawn pushes for example probably should be
excluded, but presently are not.
I'll release all the details once the WCCC event is over, but the idea appears
to be fully workable despite what "some" will say. :)
>
>>
>>The only two engines I mention in my "Sample Code" paragraph are
>>Fruit and Glaurung. This is because of ignorance, and not because
>>of disrespect to other authors. If you are the author of an open source
>>engine using history pruning (or whatever you prefer to call it) and
>>wants it to be mentioned on my page, please let me know.
>>
>>Tord
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.