Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f)

Author: Vasik Rajlich

Date: 03:09:10 06/18/05

Go up one level in this thread


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

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