Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f)

Author: Vasik Rajlich

Date: 15:08:15 06/19/05

Go up one level in this thread


On June 19, 2005 at 15:36:47, Vincent Diepeveen wrote:

>On June 18, 2005 at 14:19:00, Vasik Rajlich wrote:
>
>>On June 18, 2005 at 11:09:51, Vincent Diepeveen wrote:
>>
>>>On June 18, 2005 at 06:09:10, Vasik Rajlich wrote:
>>>
>>>>On June 18, 2005 at 00:37:52, Ricardo Gibert wrote:
>>>>
>>>>>On June 17, 2005 at 20:39:58, Ricardo Gibert wrote:
>>>>>
>>>>>>On June 17, 2005 at 18:56:08, Vincent Diepeveen wrote:
>>>>>>
>>>>>>>On June 16, 2005 at 18:42:44, Vasik Rajlich wrote:
>>>>>>>
>>>>>>>>On June 16, 2005 at 13:31:39, Vincent Diepeveen wrote:
>>>>>>>>
>>>>>>>>>On June 16, 2005 at 05:22:26, Vasik Rajlich wrote:
>>>>>>>>>
>>>>>>>>>>On June 15, 2005 at 22:40:22, Tor Alexander Lattimore wrote:
>>>>>>>>>>
>>>>>>>>>>>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();
>>>>>>>>>>> MOVE move_to_search;
>>>>>>>>>>> int best=-INFINITY;
>>>>>>>>>>> GenMoves();
>>>>>>>>>>> while (GetNextMove(&move_to_search))
>>>>>>>>>>> {
>>>>>>>>>>>  PlayMove(move_to_search);
>>>>>>>>>>>  val = -MTD(depth - 1, -guess + 1);
>>>>>>>>>>>  UnPlayMove(move_to_search);
>>>>>>>>>>>  if (val>best)
>>>>>>>>>>>  {
>>>>>>>>>>>   best=val;
>>>>>>>>>>>   if (val>=guess)
>>>>>>>>>>
>>>>>>>>>>You missed a line here. Fail-hard is "return guess", fail-soft is "return val".
>>>>>>>>>>
>>>>>>>>>>Fail soft helps when you need to re-search, so it helps more in MTD (f) than
>>>>>>>>>>PVS, and doesn't matter at all in pure alpha-beta.
>>>>>>>>>          ^^^^^^^
>>>>>>>>>I guess you meant a small typo here. doesn't ==> does
>>>>>>>>>
>>>>>>>>
>>>>>>>>Actually I just forgot about hash effects at the next iteration. Without those,
>>>>>>>>the statement would be true .. (as far as I can see)
>>>>>>>
>>>>>>>The hashtable is the thing that is refuting so so many algorithms... ...one of
>>>>>>>them is for example no-progress pruning. With a hashtable it is an incorrect way
>>>>>>>to search.
>>>>>>
>>>>>>
>>>>>>I've "reverse engineered" the no progress pruning algorithm and it does not
>>>>>>depend on the transposition table. Unless I've somehow reverse engineered it
>>>>>>"improperly," the idea appears to be 100% sound to me.
>>>>>
>>>>>I've thought it over and I think understand what it is you're getting at now.
>>>>>Interesting.
>>>>>
>>>>>Thanks for making me think!
>>>>>
>>>>
>>>>Yes, but it's nothing unusual. One extreme is to do like Uri and not even use
>>>>the hash table for transpositions. Most people just live with these things.
>>>>
>>>>Note BTW that "no progress pruning" should be "no progress reduction" - as
>>>>always. So these problems won't kill you, they'll just give you some
>>>>non-theoretical values.
>>>>
>>>>Vas
>>>
>>>If your definition of "won't kill you" means that the computer won't pick up a
>>>rifle and fire you dead litterary, then you might be correct.
>>>
>>>However if "won't kill you" refers to: "it will not back up very poor moves to
>>>the root", then that's not true.
>>>
>>>When i refer to 'incorrect' way to search i do not mean that the last few plies
>>>of the search you *might* get an error sometimes. It refers to that incorrect
>>>scores get backed up to the root regurarly and regurarly lose games for you.
>>>
>>>Of course such effects are measurable only when software plays strong and when
>>>you do accurately test say a 1000 games at tournament level against a variaty of
>>>opponents and then compare the 2 runs of 500 games with each other.
>>>
>>>Such tests only commercials are doing. Not a single amateur is.
>>>
>>
>>I would be really surprised if there was some pruning or search control which
>>would fail only because of interactions with HT.
>>
>>Let's imagine that without any hash table, some "no progress reduction" works,
>>ie. program plays stronger. If this is true, then the chance is 98% that no
>>progress reduction also works (ie. makes the program play stronger) when you do
>>use a hash table.
>
>I would expect Uri Blass write such a posting and am rather amazed you did it
>here.
>
>You are obviously going to store thanks to no progress pruning in your hashtable
>nodes as a fail high whereas in reality it is a fail low and vice versa. You can
>simulate this behaviour very easily in your program.
>

Search is full of not-correct stuff. If you don't like it, you won't use HT,
null move, aspiration windows, etc ..

The question is, how often are you going to come to a position where no progress
has been made the last few moves, then later come to that same position in a
different path where progress was made, and the extra few plies of search would
have flipped your score.

Vas

>Just give randomly a cutoff from hashtable, before checking the hashtable.
>
>After you tested that at Crafty or something, please let me know how many rating
>points it has become stronger or weaker and after you were kicked a 1000 times
>please tell me whether you conclude it still is a correct form of search.
>
>Vincent
>
>>Vas
>>
>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>>>Vas
>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>Vas
>>>>>>>>>>
>>>>>>>>>>>  }
>>>>>>>>>>> }
>>>>>>>>>>> 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 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.