Author: Vasik Rajlich
Date: 03:00:37 06/18/05
Go up one level in this thread
On June 17, 2005 at 23:16:10, Robert Hyatt wrote:
>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.
>
Let me put it like this: in MTD (f), if the first move you happen to try is
weak, you will spend less time on it. You will just prove that it's worse than
your first alpha, and continue to the next move. In PVS, you will have to show
exactly where in the window it falls (or prove that it falls outside of the
whole window).
You will see this behavior in any PVS engine - even a good one. At depth=12, it
thinks move x is best with a score of 0.25. (Let's say.) At depth=13, move x
becomes rather weak, and the engine goes on to show that x scores exactly -0.20
before even considering any other move. This is potentially a big search. Then,
the search continues on to move y, which is right back to +0.25 or so.
This inefficiency is also repeated inside the tree, and it is what MTD (f) tries
to avoid.
I guess I see MTD (f) as a promising and logical bad idea, rather than a
completely pointless one :)
>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...
>>
Most of the search experts don't like MTD (f). Tord has stopped using it, Fabien
also never liked it. (A discussion from CCC IIRC ..)
As I see it, it has one huge flaw: when you come to a node, you don't know the
"true" bounds (ie. the eventual range of values you'll come to that node with),
and you can't use it to make search decisions.
The most simple example is null move. In every PVS engine I've seen, null move
is required to fail high. Nobody allows null moves to score inside the window -
ie. nobody will put null moves in the PVs. In MTD (f), though, if you do a null
move at a node at the alpha value, and it fails high, you just potentially put a
null move into your PV.
(This also happens in a PVS engine if a null move fails high, but a research is
later needed.)
Anyway, there are a number of possible solutions to these problems, but then you
have to ask yourself if it's worth the trouble. If the final savings are 10% of
nodes, is it worth dealing with these issues?
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.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.