Author: Ricardo Gibert
Date: 18:16:52 06/19/05
Go up one level in this thread
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.
IIUC, no progress pruning does not fail when used in conjunction with HT. It
continues to prune correctly. The problem is that it breaks the HT pruning. It
counterfeits some of the assumptions that HT pruning depends on.
>
>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.
>
>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.