Author: Robert Hyatt
Date: 19:43:25 06/18/05
Go up one level in this thread
On June 18, 2005 at 11:21:08, Vincent Diepeveen wrote:
>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.
>
>Obviously you are contradicting yourself here, as this isn't a proof nor insight
>that the move ordering is *better* than from PVS.
Sure it is. The defnition of "better" move ordering is that you get a move that
causes a cutoff searched first more often than a program with "worse" move
ordering. Clearly mtd(f) will do this, because it searches the same positions
so many times only changing the alpha/beta bounds being used. If you are below
the true score with the bounds, things will consistently fail high each
successive pass. Move ordering gets more accurate.
Of course this isn't the only measure that is important. Since I can produce
perfect pvs move ordering by simply searching the same iteration multiple times,
but it doesn't do much for overall search performance.
>
>PVS is a 2 pass search. You start with -infinite,+infinite in the root.
>Secondly directly from hashtable you get the root PV and within say 50 nodes you
>have a very good 'alfa' (seen from the root).
No argument except for the "2 pass" concept. I only make one pass most of the
time.
>
>With that you repeatedly try nullwindow searches.
>
>This true bound that you directly get for free from the hashtable is of course a
>far BETTER bound for your move ordering than *any* bound MTD might start with.
I also don't buy that. When searching iteration N+1, the hash table entries
from iteration N won't be giving me any true scores at all.
>
>The whole idea that MTD is having a more efficient sorting and more efficient
>search is complete bullocks of course as soon as we assume a good chessprogram
>with a decent move ordering and good working hashtables.
>
>Of course the whole point is that your MAINLINE must have an accurate mainline
>which might not be true for random searchers. For todays search depths and
>improving chess software it is the case however that you directly have that
>great value in the root from hashtable where MTD can never compete against.
>
>With at most 1 research you can make that score a little bit more accurate,
>where MTD has massive overhead in terms of hashtable calls and massive overhead
>in number of searches (especially if pawn=1000 or so in your program).
The problem is that you are _assuming_ that MTD is going to have to do lots of
re-searches. Nothing says this is necessarily true. It was for my tests, but
that doesn't mean that it doesn't work for others. Discounting things like that
is generally a dangerous approach...
>
>The only area where MTD has distinguished itself is for random searchers at a
>ply or 5 which were searching at testsets where you knew in advance that a move
>would fail high. And even there it wasn't done with statistical accuracy and at
>software in a time that a branching factor of 10.0 was very normal.
>
>The whole problem with that is that this just isn't reality. You *need* to
>assume that there is are hashtables and that it is not a random tree you're
>searching, but a tree where you have a decent move ordering.
>
>In any case there still isn't any proof that MTD has a better move ordering than
>PVS.
>
>Only the insight for the opposite is there.
>
>>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.