Author: Dan Homan
Date: 11:20:06 05/14/99
Go up one level in this thread
On May 14, 1999 at 08:32:13, Andrew Williams wrote:
>On May 13, 1999 at 23:12:41, Dan Homan wrote:
>
>>
>>I've tried the mtdf algorithm a few times with no luck. It was
>>always noticably slower than pure PVS. (For reference: mtdf is
>>an algorithm which uses a series of null-window searches from the
>>root to narrow in and find the true score of a position.)
>>
>>Today I tried mtdf again, but this time with more determination.
>>It is an easy change to my program because all I need to modify
>>is the loop that calls my PVS function from the root. Again, I found
>>that it was much slower than normal PVS at first. However,
>>by modifying the algorithm to use an adaptive step-size (meaning that
>>I don't try neighboring (+/- 1 point) windows for re-searches but
>>rather try to bound the score more efficently) and by
>>reducing my score resolution from 1/100 th of a pawn to 1/25 th of
>>a pawn, I got better results from mtdf than from pure PVS.
>>
>>I went from 277 correct solution on the WAC test set (5 sec limit on a
>>Cel 400) to 281 correct solutions with mtdf. My rms solution time for
>>both runs (with and without mtdf) were nearly the same. Of course,
>>these tests are not really conclusive... For example I don't know how
>>pure PVS will do with 1/25 th of a pawn scoring rather than 1/100 th.
>>What this does indicate to me is that mtdf is a viable solution. Previously,
>>I had assumed it would be very difficult to implement effectively.
>>
>>If I decide to commit to mtdf, there are (presumably) more optimizations
>>I could take advantage of. What kind of experience do other programmers
>>have with mtdf?
>>
>> - Dan
>
>
>PostModernist uses mtd(f). I've actually never used PVS, so I can't really
>compare. But one worry I always have with mine is having to depend on the
>transposition table to build my Principal Variation. I'm always worried that
>I've got cabbage in there, although when I look closely, it's normally pretty
>sensible. How did you get your PV when you tried mtdf?
I just recorded the pv normally as I do in my pvs search. This code
wasn't changed at all, but because of the null-window searches.. the only
move stored in the pv was the best move at the root. I hadn't worried
about getting the rest of the pv yet, but I can see that this would
be a problem. An accurate pv seems important for debugging.
>
>I'm interested in whether you made any change to your TT when you tried mtd(f).
>Mine has separate lower and upper scores for each position and a separate
>draft for each. Did you do this? This is better in my program, although it
>makes insertions and probes somewhat slower. I think the upper and lower
>bounds must be required, although the separate drafts are optional.
I made no changes or modifications to my transposition table. Your
suggestion sounds like a good idea to maximize performance, thanks for
the tip.
>
>I don't have the facility to change the granularity of my eval, although this
>is one of the major tasks I have for the Summer, if I can find time. I'll see
>what effect this has on my program.
Actually, I fudged the granularity of my eval. I just bit-shifted the
output of my search by two bits and bit-shifted the bounds of the
search by two bits in the opposite direction when doing the search. As a
result, my search windows weren't really null-windows but rather
(beta, beta-4). I used...
g = (some reasonable score in 1/100th of a pawn)>>2;
step = 16; flag_up = 0; flag_down = 0;
lowerbound = -MATE; upperbound = +MATE;
while(lowerbound < upperbound) {
if(g==lowerbound) beta = g+1; else beta = g;
root_alpha = (beta-1)<<2; root_beta = (beta)<<2;
g = pvs(root_alpha, root_beta, depth)>>2;
if(g < beta) {
upperbound = g;
g -= step; flag_down = 1;
} else {
lowerbound = g;
g += step; flag_up = 1;
}
if(flag_up&flag_down) step>>1; else step<<1;
}
g = g<<2; // To convert back to 1/100 of a pawn
All of this was, of course, embedded in a standard iterative deeping
frame-work. This was a very rough cut at mtdf. With more time, I would
implement the change in granularity correctly.
- Dan
>
>I've replied to Dave Gomboc's post on this subject further down the thread
>as well.
>
>Thanks a lot for the post - I'll send some more stuff if I can think of
>anything else that might be interesting.
>
>
>Andrew
This page took 0 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.