Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f)

Author: Vincent Diepeveen

Date: 15:53:53 06/17/05

Go up one level in this thread


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.

>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.