Author: Dave Gomboc
Date: 09:50:29 05/14/99
Go up one level in this thread
On May 14, 1999 at 08:21:19, Andrew Williams wrote: >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. So if you search the window for +50, and the fail-soft returns 49, the next null-window you try is 46? If the fail-soft returns 40, are you still using 46, or are you using 40? >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 Dave
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.