Author: Robert Hyatt
Date: 20:16:10 06/17/05
Go up one level in this thread
On June 17, 2005 at 18:53:53, Vincent Diepeveen wrote:
>On June 16, 2005 at 18:33:11, Vasik Rajlich wrote:
>
>>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.
>
>The basic flaw in the above argumentation is that it requires MTD to have
>somehow from the skies a magical sorting S which is a better one than PVS gives
>you.
>
>I directly bury that idea. MTD does *not* have a better move ordering than PVS
>gives you.
>
>The insight is just not there, let alone the proof, that MTD *can* give a better
>move ordering than PVS.
Actually it does have better ordering. Because you end up searching the _same_
set of moves, to the same search depth, repeatedly. Two passes, one above the
true score and one below the true score, and your move ordering ends up _really_
good.
Of course, that doesn't mean the final cumulative search tree is smaller than
PVS. For me it never was. But I'll give someone the doubt that they did a
better job of it than I did. I only fooled with it for a couple of months
before tossing it.
>
>>Anyway it's way too late at night to list all the problems with MTD (f) :)
>>Vas
>
>Of course MTD has another 10 problems why you don't want to use it. However the
>best insight we get in how outdated it is, is when looking to world champs 2004.
>
>There Stefan Meyer-Kahlen, someone who will be the last on the planet to do
>suggestions to others on how to improve their program, at the world champs 2004
>he very careful suggested to Rudolf Huber (ParSOS) that: "Perhaps it is time to
>consider dropping MTD and getting back some more decent search algorithm like
>PVS for example."
>
>I have never ever heard Stefan say such a clear suggestion to anyone on this
>planet like that.
>
>So perhaps...
>
>>>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.01 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.