Author: Dave Gomboc
Date: 22:55:52 05/13/99
Go up one level in this thread
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. Finally, if you haven't already done so, you will find it worthwhile to read (at least portions of) Aske Plaat's Ph.D. dissertation. 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.