Author: Vasik Rajlich
Date: 15:33:11 06/16/05
Go up one level in this thread
On June 16, 2005 at 13:38:55, Vincent Diepeveen wrote:
>On June 15, 2005 at 22:40:22, Tor Alexander Lattimore wrote:
>
>I wonder why there is still people using MTD in chessprograms above PVS.
>
>In PVS you can of course easily determine the maximum number of nodes you had to
>search extra on top of nullwindows. In DIEP it's just a couple of thousands at
>in total millions of moves.
>
>So the theoretic gain MTD CAN give, when you start measuring it, it is really
>negative.
>
I agree now after some bad experiments that MTD (f) isn't worth the trouble, but
the refutation isn't quite this simple.
Imagine white has two moves, x and y. x is weak, but you search it first with a
big window. The first response to x gives a score of -2.0, and now you search
all the other responses to x (with null-windows around -2.0), and after a big
search x is able to maintain the -2.0. Note that the vast majority of this
search is null-window.
Now finally you search y, and it gives you 0.0.
You could have skipped all (almost all) of those zero-window searches of x, if
only you had switched to y more quickly. That's what MTD (f) tries to do. You're
not committing to a move. Basically a wide window commits you to the first move
you happen to try - you're going to search it anywhere inside that window.
Anyway it's way too late at night to list all the problems with MTD (f) :)
Vas
>For material only searches or evaluation functions which have little fluctuation
>and a small range it's pretty fast though to use MTD, provided you don't mind to
>lose sometimes games when you hit its worse case.
>
>The worst case you can see in the program ParSOS very well at world champs,
>when it starts to doubt then it has a search depth of plies less to the others.
>
>Nevertheless here my answers:
>
>>Hi
>>Is it possible to use a single variable in the MTD(f) search? Something like
>>this:
>>
>>int MTD(int depth, int guess)
>>{
>> if (depth<1) return Evaluate();
>
>Using hashtable in qsearch of course is a necessity for MTD because of the many
>researches you're doing.
>
>So for very fast searching software MTD is pretty expensive to use, as the
>hashtable more and more gets a big overhead. Crafty (correct me if i'm wrong for
>latest version) isn't hashing in qsearch for example.
>
>> MOVE move_to_search;
>> int best=-INFINITY;
>> GenMoves();
>> while (GetNextMove(&move_to_search))
>> {
>> PlayMove(move_to_search);
>> val = -MTD(depth - 1, -guess + 1);
>
>If you just search with 1 bound, then it's obvious to do:
> val = -MTD(depth - 1, -guess);
>
>> UnPlayMove(move_to_search);
>> if (val>best)
>> {
>> best=val;
>> if (val>=guess)
> break;
>> }
>> }
>> return (best);
>>}
>>
>>perhaps there is something very wrong with this? or perhaps it's used already, I
>>just noticed that on Aske Plaat's site he always uses an Alpha-Beta search with
>>0 width windowed searches, but doesn't this do the same thing? Is using
>>fail-soft type algorithms used in MTD(f) since it could well help zoom into the
>>correct score sooner?
>>
>>Cheers
>>Tor
This page took 0.02 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.