Author: Andrew Williams
Date: 05:21:19 05/14/99
Go up one level in this thread
On May 14, 1999 at 01:55:52, Dave Gomboc 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 > >Well, it's _really_ good for Awari. :-) > >I think a common mistake is that when the null-window search fails high or fails >low, people adjust the score by +1 or -1, and re-search. This can be adequate, >or extremely inefficient, depending on the particular situation. You are >supposed to use fail-soft alpha-beta, and use the score that is returned by it >to re-search with. So you end up searching e.g. +25, +38, +42, +44 score=44, >instead of +25, +26, +27, ... +43, +44 score=44. > >If you weren't already doing this, give it a try and let us know how it works >for you! :-) Also, of course, adequate hash table size is an absolute >necessity, but I am sure you are aware of this already, because otherwise your >mtd(f) would perform really badly compared to your pvs. > >Having pointed out the above, some people find they can do even better than >using the value returned by fail-soft, so it is still worth experimenting in >this area. > >Don Dailey has also told me that lazy evaluation and mtd(f) sometimes don't mix >very well. Another observation is that it is usually less work to prove that >you are too low than you are too high. This is due to the nature of minimaxing. > Yes. For this reason, for successive fail-highs, I add on 1 then 2 then 3 then 4 then 5 etc etc. For successive fail-lows, I subtract 4, then 9, then 16, then 25, then 36 etc. I have messed about with this a *lot*, and at the moment I'm happy with this. I use fail-soft, of course as you say. I would be VERY interested in what anybody else does with this. Also on how close the lower and upperbounds have to be before you consider the score to be final. Plus any other information you want to share! 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.