Author: Uri Blass
Date: 14:13:54 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.
I wonder why do you expect me to write it.
1)Movei is not using hash tables for pruning and there are a lot of other things
to improve that are not thinking how to use hash tables for pruning in a
productive way.
2)I never claimed that the way that Crafty use hash tables for pruning is
productive with other tricks that I use.
3)I did not try hash tables for pruning also for other reasons.
Movei is badly written and I probably need to rewrite the alphabeta function in
order to do it and I have other priorities.
Uri
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.