Author: Vincent Diepeveen
Date: 03:28:50 06/20/05
Go up one level in this thread
On June 19, 2005 at 18:08:15, Vasik Rajlich wrote:
>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.
However never it is so completely wrong like no progress pruning is by giving
these random cutoffs are for your search. I know very dubious types of forward
pruning which sometimes screw your program in the same way (nearly all losses of
shredder are BECAUSE of it's dubious search, its search really has gone over the
top), but the huge advantage such pruning methods give is that they search you
plies deeper and give back a relative small error rate. Also the error rate
forward pruning gives to you is only possible real wrong near the leaves which
next iteration gets corrected. It IS possible that in a position that seems to
be >= beta that you miss some move and you give back a score <= alfa. That IS
possible.
However with no progress pruning the errors start to exist more closer to the
root and far deeper in the search. In fact it will 2 ply to 4 ply closer to the
root backup a DIRECT and a HUGE error back to the root.
Obviously that means that just a few ply away from the root you get MASSIVE
errors back from the hashtable. Instead of >= beta it gives <= alfa back.
The deeper you search the more likely no progress errors get backed up to the
root obviously as the effect of it at the search tree is bigger and more chances
for it to back up an error to the root. So a deep search in combination with no
progress is going to be having a bigger and bigger error for the root score.
With forward pruning, especially if you just do it last few ply (that can be
with nullmove too for example) the odds for *that* are real real tiny.
So the errors that no progress pruning introduces into your search tree are
MASSIVE, this for a very tiny saving in the middle game. There IS a few special
positions where it can make you search plies deeper, but that isn't the
middlegame, that with no exceptions is some far endgame.
>If you don't like it, you won't use HT,
>null move, aspiration windows, etc ..
a combination of hashtable, nullmove, pvs and a parallel search is very nice to
have. i see little post it here, but for a parallel search the hashtable is even
more important than for a single cpu program.
turning off transposition cutoffs is not a very clever idea, as the improvement
in branching factor transposition cutoffs give are obviously much better than no
progress.
>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.
Basically the problem of no progress is that every few branches you cut away
something, you introduce in fathers of that branch an error in hashtable which
is exactly the opposite of the real score.
Let's say you do 10 cuts with no progress at depthleft == 7 ply.
that means most likely that 2 nodes of <= 8 ply depthleft suddenly flip in
score and from that nodes at depthleft <= 9 ply flip some in score too in an
incorrect way.
How many forward pruning algorithms introduce such errors at such search depths
left, not far away from the root?
Usually forward pruning means that some branches are searched to a shorter depth
than others, which introduces some errors. It doesn't miss anything within that
search (reduced) depth. With no progress however you are going to give randomly
cutoffs from hashtable in top levels of the search in an incorrect manner.
No progress pruning is really the worst algorithm invented the past years.
It causes hundreds of rating points loss in playing strength for todays top
programs.
When i tried a few years ago in Diep some runs with a version that had it
implemented, i suddenly saw pathetic moves getting played. Really the difference
was so so huge, that after a few games i already stopped it.
It wasn't a bug, but was on paper very easily explainable by means of the
backing up of incorrect values at bigger depthlefts than where the pruning
occured to the hashtable.
Vincent
>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.