Author: Vasik Rajlich
Date: 02:31:17 06/20/05
Go up one level in this thread
On June 19, 2005 at 21:16:52, Ricardo Gibert 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.
>
>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.
>
I don't understand why that would be the case. Can you explain?
The interaction of no progress pruning with HT will cause you some problems
because the pruning is path-dependent, while the positions in the HT are not.
You'll store in the HT a position which was later pruned (actually reduced)
because of lack of progress, and then you'll come to that same position via a
different path where this pruning (actually reducing) shouldn't be done.
The question not everybody agrees about is how of much of a problem this is.
Vas
>>
>>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.