Again, rep-draws (and score aging)

[H.G.Muller]

Joker currently handles three-fold repetition draws by only scoring the third (tree) occurrence of a position as a draw, and suppressing hash probes and stores on repeated nodes. This guards the hash table from pollution by path-dependece, as the path-dependent stuff is all figured out between second and third occurrence, which are not stored. If the draw score of the 3rd occurence propagates to the 2nd (meaning that it is unfavorable for any side to break out of the repetition cycle), the position is really a draw irrespective of the path through which this second occurence was reached. So there is no harm in the draw score propagating down to all positions between first and second occurrence.

This works, but the problem of this method is that, if there is a perpetual on the board, most other lines can take 'the long way', visiting each position twice by interjecting 4 ply from the perpetual before continuing with the true pursuit of the alternative line. (e.g. see http://www.vpittlik.org/wbforum/viewtopic.php?t=6387 .)

It makes no sense at all to have lines that visit the same position twice. The second occurence is just a metaphore for the first occurrence, you really want to redo the search of that repeated node under different conditions of draw-scoring the repeat (causing path dependence), and not hashing the intervening nodes. So I guess what is really needed, is that once the search reaches the 2nd occurrence of a position, it should extend the line such that it searches that node to the same depth as was requested for the search of the first occurrence. (This depth should thus be stored in the repetition table.)

In fact you would redo the search as soon as you discover that returning to that same position might be relevant (i.e. it was not pruned before you arrived there), although it might still happen that you find side branches of the path between 1st and 2nd occurence that after all will make it irrelevant.

So you first do the search starting from the 2nd occurrence, to the depth that was requested for the 1st occurrence, under the assumption that a 3rd return to the position is a draw, but without storing the results for the repeated nodes in the hash (to prevent contamination). This search will tell you if the repetition is forced, or if one of the sides prefers to break out of it. Whatever the case, the result will be the path-independent score of the 2nd occurrence.

If the result of the second occurrence was a draw score, you award it to the move that led to the repeat, and finish the search of the first occurrence. This for the benifit of hashing the nodes on the path between the 1st and 2nd occurrence, which was suppressed in the repeat path between 2nd and 3rd occurrence. This 'finishing of the search' is mainly a formal thing, as all side branches of the repeat cycle, in so far they were not searched already, now have been searched to the requested depth as part of the search of the 2nd occurence. And the side branches were hashed (in so far they were not repeats themselves). So there is not much extra time involved in searching the repeating position twice, each side branch is only searched once, be it before or after the repeat is encountered, and the second time it is taken from the hash. Only the nodes on the repeat path really are searched twice.

But (and now comes the crux), if it was favorable to break out of the repeat, giving the current move its true score does cause a problem. The branch that leads to this score, searched in the sub-tree from the 2nd occurrence, might not have been searched yet in the tree from the first occurrence. And if we encounter it later the score will be axactly the same, as a long line and a short line leading to the same end-leaf in minimax have the same score. And in a case where a new move produces an equal score to a move we already have, we consider it a fail low, and stick with the old move. Also in cases where the new move was the short-cut, and the old move was the detour through the 2nd repeat! On the other hand, we cannot arbitrarily adjust the score, as this will cause contamination in the underlying nodes (which are hashed).

A solution to this dilemma can be provided by the general mechanism of 'aging' scores: if two paths eventually lead to the same (score-determining) position, the side that is winning prefers the short path, the side that is losing the long path. (This is also true for paths without repeats.) Plain minimax does not take account of this. One way to implement this principle is to give the losing side (the side with negative score, i.e. below draw) a slight bonus for each move he does. This is a little tricky, as you will know the score only afterwards, and you must make sure to precompensate the search window so that out-of-window results cannot move back into the window by the later tinkering with the score. But it can be done, has a logical basis, and thus has many advantages in other areas (e.g. you would be liberated of that ridiculous stuff of adjusting checkmates for depth in the tree.)

With the aging, the score of the branch that breaks out of the repetition after the 2nd repeat, (which will be a branch in favor of the side that breaks out, or he would not do it), will have devaluated in being passed towards the root in favor of the loser. So when compared later with the (hashed) value of that same branch between 1st and 2nd repeat, the scores are no longer equal, but will seem inferior to the winning side. So that this side will prefer the move that breaks out immediately. The aging bonus can be as small as you want, so that it does not have any real effect on scoring, but just acts as a tie breaker between otherwise exactly equal scores.

The whole scheme still requires extra work to search and generate moves in the nodes on the repeat-cycle path twice. I am not sure if repeats occur often enough to make this have a significant impact on performance. Perhaps most of the danger for this can be eliminated by sorting moves that obviously offer the opportunity for the opponent to cause a repeat (because they reverse the move done 2 ply before, and the move 1-ply before was reversible) in very last place, and the move that actually brings about the repeat likewise (in simple back-and-forth moving cycles, both these moves satisfy that same criterion). Usually the repeat path will then be alpha-beta pruned in one of the two nodes before the repeat, unless it really might become PV.

[H.G.Muller]

The final idea is this:

Code: Select all

struct _Repeat
{   int RepLock;
    int RepDepth;
    int RepCnt;
} RepTab[SIZE];

Search(Depth, Alpha, Beta)
{
    struct _Repeat *Rep = LookUp(RepTab, HashKey);

    if(Alpha<0) Alpha--; // pre-adjust window for aging bonus
    if(Beta<=0) Beta--;

    // Handle repeats
    switch(Rep->RepCnt)
    {   case 0:
            if(HashProbe(HashKey) == OK_HIT) return HASHSCORE;
            Rep->RepDepth = Depth; // remember depth of 1st occurrence
            break;
        case 1:
            Depth = Rep->RepDepth; // restore depth of 1st occurrence
            break;
        case 2:
            return DRAW_SCORE; // 3rd occurrence
    }
    Rep->RepCnt++;

    // section that you would find in any normal search
    BestScore = -INF;
    for(ALL_MOVES)
    {   Make();
        Score = -Search(Depth-1, -Beta, -Alpha);
        UnMake;

        .... // minimaxing stuff

        if(BestScore >= Beta) break; // beta cutoff
    }
    if(NO_LEGAL_MOVES && !InCheck) BestScore = DRAW_SCORE; // (stale)mate stuff

    Rep->RepCnt--;
    if(BestScore < 0) BestScore++; // aging bonus for losing side
    if(Rep->RepCnt == 0) HashStore(HashKey); // only 1st occurrences

    return BestScore;
}


As a bonus of the aging you will never have to worry about mate depths anymore, the aging bonus will take care of it that mate in N is just a tad better than mate in N+1, as the loser will get a 1-point bonus for the extra move. You never have to correct anything before storing or after retrieveing from the hash table. Score for being checkmated will be -INF+1, score for mate-in-one will be INF-1, score for checkmated-in-one will be -INF+2, etc. (In a King-capture engine +INF would be the score for King capture, which is better than mate-in-one, and -INF would be the score for illegal move.)

And the beautiful thing is that it does not only work for checkmates, but also if you have to chose between taking a Queen in one or in two moves, or have your King take the short route towards taking a trapped piece, or avoiding repetitions... The aging bonus really solves all these problems in a fundamental way.

In combinations with the repeat-avoidance, however, it is really essential that you compare the moves that break the repeat cycle at the same depth. If the first and second opportunity are searched to different depth, there might be a score difference larger than the aging bonus can overcome, so that postponing the breakout can seem better, while in fact it was just more inaccurate. Hence you need to give the extension at the 2nd occurrence (which is nearly free, as the subtree hanging from it would have to be searched to that depth anyway).

[H.G.Muller]

Too bad. Although theoretically ideal, in practice this seems to cause stack-overflow. Apparently the search finds too many too long repeat cycles, and resetting the depth (redoing the search from the second occurrence with the path from 1st to 2nd still on the stack) apparently leeads to accumulation of too many redundant path sections if side branches of the second search again hit upon positions in the existing path

So I have to think of something else. Perhaps my initial, more complex idea of maintaining a shadow-score range of what the score could have been had we not hit upon the repeat is the only way to do it.

[H.G.Muller]

OK, entirely different approach.

Basically, the "3rd occurence = draw" scheme is OK, but we don't want to have PVs that contain duplicates, as they must be surely due to search inaccuracy: such duplicates merely show that the later, less deeply searched move breaking out of the repeat cycle between 2nd and 3rd occurrence does seem better than the more deeply searched move between 1st and 2nd, where in fact we know it to be the same.

So in any node it should be forbidden to pick a 'best move' that leads to a repeat of the current position along the projected best continuation (its PV), unless the score of that move is the draw score. In principle you could dig this information out of the triangular PV array, if you kept one, but that would be rather cumbersome.

So we do it differently: we let Search pass back towards the root the complete list of nodes that it searched for a second time in its PV. We encode this as a bitmap in which we set the bit corresponding to the tree level of the first occurrence of the position, bit 0 = the root, bit 1 = 1 ply from the root, etc. A (first-occurring) leaf node returns a clear bitmap. Other nodes return the bitmap that was handed to them by the best move they found, to which they add the bit of the level of their 1st occurrence if they are themselves a 2nd occurrence. To make this possible, the level of each 1st occurrence is stored in the repeat table.

If a 1st occurrence picks a move which returned a bitmap with the bit of the current level set, it should top off the score of such a move at the draw score, as anything that move has above that is a false promise: if there is a continuation that good, we should be able to get there though another move from the current node, skipping the preceeding repeat cycle.

Code: Select all

struct _Repeat
{   int RepLock;
    int RepLevel;
    int RepCnt;
} RepTab[SIZE];

int NewRepMap;

Search(Depth, Alpha, Beta, Ply)
{
    struct _Repeat *Rep = LookUp(RepTab, HashKey);
    int RepMap = 0;

    // Handle repeats
    switch(Rep->RepCnt)
    {   case 0:
            if(HashProbe(HashKey) == OK_HIT)
            {   NewRepMap = 0; // unfortunately we cannot know PV of hash hit
                return HASH_SCORE;
            }
            Rep->RepLevel = Ply; // remember level of 1st occurrence
            break;
        case 2:
            return DRAW_SCORE; // 3rd occurrence always draw
    }
    Rep->RepCnt++;

    // section that you would find in any normal search
    for(ALL_MOVES)
    {   Make();
        Score = -Search(Depth-1, -Beta, -Alpha, Ply+1);
        UnMake;

        if((NewRepMap & (1 << Ply))  && Score > DRAW_SCORE )
            Score = DRAW_SCORE; // top off score that leads to repeat

        // minimaxing stuff
        if(Score >= Alpha)
        {   RepMap = NewRepMap; // copy PV of chosen best branch
             ....
        }

        if(BestScore >= Beta) break; // beta cutoff
    }
    if(NO_LEGAL_MOVES && !InCheck) BestScore = DRAW_SCORE; // (stale)mate stuff

    Rep->RepCnt--;
    switch(Rep->RepCnt)
    {   case 0:
            HashStore(HashKey); // only 1st occurrences are hashed
        case 1:
            RepMap |= (1 << Rep->RepLevel); // mark first occurence in PV
            break;
    }

    NewRepMap = RepMap; // return PV bitmap
    return BestScore;
}


Note that we cannot know the PV beyond a hash hit. (It would not even help storing the RepMap in the hash, as the path under which the hashed entry was derived might be different from the current path leading to it.) This problem is partly overcome by forbidding hash probes in repeated occurences.

The hashing problem remains a very fundamental critical problem. If we have a repeat cycle A -> B -> C -> D -> A, we can be so unlucky that we could enter the cycle at both A and C at the same level of the tree. At one iteration, both are then searched to 3 ply without the repeat being visible yet. But if we request a 4-ply search in the next iteration, although the hashed values no longer have sufficient depth, the 4-ply search of A will after two ply get a hash hit with sufficient draft on C (requested depth = 2, stored draft = 3), and vice versa. This will go on forever, at each iteration there will only be two ply of real search before the hash hit. And two ply is not enough to recognize the repeat cycle...

The only solution I see to this problem of mutual bootstrapping is to reconsruct the PV from the hash on a hash hit, doing repeat-testing along its path. This is very expensive, (though not as expensive as doing no hash cutoffs at all), as it will require many hash probes. But at least you would never have to go beyond any irreversible move. Still, you could consider to do it only at large remaining depth. (Meaning you take the risk to miss perpetuals near the end of the tree. But you might not have many hash hits there anyway.)

Note further that, although only the 3rd repeat is scored as a draw immediately on entering a node, even a search that only has the 2nd repeat within its horizon will be scored as a draw in hindsight, if we discover from the PV bitmap at the 1st occurrence that the best continuation returns to it. The fact that we prune after the third occurrence is merely an efficiency matter. After the 2nd occurrence there was reason to search on, for the benifit of obtaining correct scores in the nodes just before it. After the 3rd occurrence, however, that reason no longer exists, as the nodes just before it are 2nd occurrences, which are not hashed.

[Fritz Grau]

Although I have not worked out all of your explanations yet, it seems to me that your aim is to avoid "polluted" scores in the sense that they are affected by a repetition draw score. However, it seems to me that the opposite problem - to use a hash value which was correct under the assumption that no repetition draw occurs, while it may be used in a situation where the pv of that position would repeat a history move - is only slightly less critical.

The only way to solve both problems that occurs to me is to assign the set of history moves to the positional information . However, this would greatly diminish the positive effects of the transposition table.

So it seems to me that there are three ways to go:
1. Ignore the draw score pollution problem (efficient, but unsound)
2. Use transposition tables only for move ordering
3. Store bestmoves as before, but make the information on the value of the position depend on the history (e.g. by a 2nd Zobrist key).

The 3rd option would cost much more memory than the 2nd, so it appears to me that (2) would be the best sound option, while the stupid choice (1) might lead to the strongest play.

I would be happy if you could point out a mistake in my reasoning because I believe that incorrect handling of draw scores is the most probable source for incorrect evaluations, once pruning is disabled.

[Chan Rasjid]

Hello,

Although I have not worked out all of your explanations yet, it seems to me that your aim is to avoid "polluted" scores in the sense that they are affected by a repetition draw score. However, it seems to me that the opposite problem - to use a hash value which was correct under the assumption that no repetition draw occurs, while it may be used in a situation where the pv of that position would repeat a history move - is only slightly less critical.

I may be wrong. I don't yet understand or am aware of any "opposite" problem with a hash table that has only non-polluted path-independent scores. If we test repetition (the 1st) before probing the hash table, there may be no opposite problem:-

Code: Select all

//within search()
updateHashKey(move);
if (is_repeat_1(node-after-make)){
return 0;
}
//node-after-make is certain not to be a repetition of any nodes lower or of any history moves
probeTT(node-after-make);
makemove()


Best Regards,
Rasjid

[Pradu]

I have fixed my problems with path-dependencies by doing "always replace" if hashTable->hashkey==pos->hashkey. Haven't looked into why it works but this way bad entries don't get propogated up the tree easily. Anyways this shouldn't hurt performance much as this case will only happen when the hashtable entry is a bound that didn't cutoff.

[Pradu]

Hello,

Although I have not worked out all of your explanations yet, it seems to me that your aim is to avoid "polluted" scores in the sense that they are affected by a repetition draw score. However, it seems to me that the opposite problem - to use a hash value which was correct under the assumption that no repetition draw occurs, while it may be used in a situation where the pv of that position would repeat a history move - is only slightly less critical.

I may be wrong. I don't yet understand or am aware of any "opposite" problem with a hash table that has only non-polluted path-independent scores. If we test repetition (the 1st) before probing the hash table, there may be no opposite problem:-

Code: Select all

//within search()
updateHashKey(move);
if (is_repeat_1(node-after-make)){
return 0;
}
//node-after-make is certain not to be a repetition of any nodes lower or of any history moves
probeTT(node-after-make);
makemove()


Best Regards,
Rasjid

This doesn't fix the problem because I check repetition before probing hash table as well and had rep-draw problems in select positions. Hash table always has path-dependent scores because the game of chess itself is path-dependent -- eg fifty move counter. It is just that in the majority of cases the hash-table entry corresponds correctly. Places where it won't correspond correctly always is for positions with lots of 3-rep and perhaps some positions near the 50-move boundary. Example positions and traced examples of these can be found here: http://www.vpittlik.org/wbforum/viewtopic.php?t=6238 .

[Pradu]

I would be happy if you could point out a mistake in my reasoning because I believe that incorrect handling of draw scores is the most probable source for incorrect evaluations, once pruning is disabled.

Check the well known and strong SOS on this position and you'll see that's not the case:
8/8/8/8/2k5/1p6/8/1K6 b - - 1 2
Also check any engine that does only depth-replacement in the hashtable and PVS (age based replacement doesn't matter when doing a test position). As for playing strength I don't think it matters much if you just totally ignore the problem.

[Chan Rasjid]

Hello Pradu,

This doesn't fix the problem because I check repetition before probing hash table as well and had rep-draw problems in select positions.

Over at CCC about a year back, there were some fairly detailed posts on methods of hashing free of repetition dependencies, almost only from me and Muller. The general consensus seems to favor ignoring the issue. Fruit and Crafty ignored repetition dependencies. Fruit's code seems to indicate it may hash a zero(draw) score in the hash tables .
Dr. Hyatt favors the view that "the cure is worst than the disease... ".
The method that I proposed seem to have been acknowledged by Muller to be correct as a viable solution, i.e no repetition dependencies will be hashed. I think with a test of repeat-1 before hash probe and the proper method, there should not be any rep-3 bugs. Maybe Muller can comment. I have not found my Snailchess conceding any rep-draws when it wins.

Hash table always has path-dependent scores because the game of chess itself is path-dependent -- eg fifty move counter.

I think hashing a fifty-draw is theoretically correct, i.e hashing zero whenever fifty == 99 and there is a valid move that is not a pawn/capture. Whenever there is a probe hit of a fifty-draw 0 score, it is valid for the relevant node. This is so because every fifty-draw position corresponds to a unique fifty0 position.

Best Regards,
Rasjid

[Fritz Grau]

If we test repetition (the 1st) before probing the hash table, there may be no opposite problem:-

I am not sure whether I correctly understand your pseudocode. What I thought of was the following situation (description may be a little awkward, but I am not familiar with any standard notation):

1. You analyse position X, and the value is based on a continuation through positions X1, X2, X3. The value of X is not "polluted by a draw score", so it is stored in your hash table; let us assume that the value of position X is "+3".

2. In the analysis of position Y, you encounter a continuation "Y, Y1, X"; hash table lookup evaluates this continuation as "+3".

But if, e.g., Y1=X3, the sequence Y, Y1, X, X1, X2, X3 contains a repetition and should be correctly evaluated as "draw"; but the repetition occurs only at "X3", so you won't find it when you probe the hash table for the position "X".[/quote]

[Chan Rasjid]

Hello Fritz,

1. You analyse position X, and the value is based on a continuation through positions X1, X2, X3. The value of X is not "polluted by a draw score", so it is stored in your hash table; let us assume that the value of position X is "+3".

2. In the analysis of position Y, you encounter a continuation "Y, Y1, X"; hash table lookup evaluates this continuation as "+3".

But if, e.g., Y1=X3, the sequence Y, Y1, X, X1, X2, X3 contains a repetition and should be correctly evaluated as "draw"; but the repetition occurs only at "X3", so you won't find it when you probe the hash table for the position "X".

If I understand your notation, X3 is nearer root then X2,...

There may be an error in your analysis. From (1) when you search X, you must first call isRep1() for every move of X and one of it must return 0 (draw score) as your condition in (2) imply that position X has a move that leads to Y1 and the further assumption of "if Y1==X3" . So the +3 of X from (1) is a polluted score as Y1 repeats X3. Had the earlier path bypass X3 and instead cuts into X2 (X, X1, X2,....), the score of X may not be +3. A polluted score needs special treatment and hashing +3 as in your (1) above means you have hashed rep3 path dependencies into your hash table.

Another thing I like to mention is that some scheme to achieve hashing free of rep3 path dependency may be fairly complex, especially those from Muller. A simplest and theoretically correct scheme is this:-
Node B is to be searched for a value. If the paths from root is A, A+1, A+2,..., B-2, B-1, B,...
and if B is the first repetition of A, then all search scores from nodes A+1,....B-1 are all polluted. B being a repeat of an earlier nodes will pass "corrupted" scores downwards towards the root and will end only at A for this AB repetition. If we avoid hashing all nodes from A+1 to B-1, then our hash tables will be strictly free of dependencies. Muller noted that this scheme is too restrictive - probably having nothing much to hash.

Best Regards,
Rasjid

[Chan Rasjid]

Hello Fritz,

But if, e.g., Y1=X3, the sequence Y, Y1, X, X1, X2, X3 contains a repetition and should be correctly evaluated as "draw"; but the repetition occurs only at "X3", so you won't find it when you probe the hash table for the position "X".

I think there is another notational ambiguity about "... evaluated as draw..". Nodes have a score for a search depth. When we are at Y1, there is no need to search as repetition is detected by a call to isRep1() and the score of Y1 is 0 and independent of depth. Y1 pass the score 0 downwards.

Best Regards,
Rasjid

[Chan Rasjid]

Hello,

I think hashing a fifty-draw is theoretically correct, i.e hashing zero whenever fifty == 99 and there is a valid move that is not a pawn/capture. Whenever there is a probe hit of a fifty-draw 0 score, it is valid for the relevant node. This is so because every fifty-draw position corresponds to a unique fifty0 position.

My apology.The above is another silly and fairly serious mistake of mine! I don't know how my mind was (not) working when "fifty-move" itself suggests a count of moves between two nodes A(fifty 0) and B(fifty 100), i.e path dependency.

AB in general may be traversed through other alternative routes much shorter than 100 and, if hashed and retrieved as 0, may seriously corrupt search if B can lead to a win.

edit - it may be best to avoid hashing a node if the path triggers a fifty draw. If hashing is also free of rep-3 dependencies, then our hash table may be rigorously clean.

Best Regards,
Rasjid

[Fritz Grau]

Hello Chan,

If I understand your notation, X3 is nearer root then X2,...

Although I did not explicitly state it, I meant that the positions are listed in the order in which they appear in the game, so e.g. in the line "X, X1, X2, X3", X3 is farther from the root than X2, but in "Y, Y1=X3, X[, X1, X2 (HT)]" the move X2 is nearer the root; the impossibility to decide in general which position is nearer or farther from the root is the source of the problem I was trying to describe.

There may be an error in your analysis. From (1) when you search X, you must first call isRep1() for every move of X and one of it must return 0 (draw score) as your condition in (2) imply that position X has a move that leads to Y1 and the further assumption of "if Y1==X3".

X itself has no move that directly leads to Y1, as you cannot replicate a position in just 2 plies: It takes at least 4 plies for a repetition to occur.

So the +3 of X from (1) is a polluted score as Y1 repeats X3.

There may be a misunderstanding: As I wrote down the positions in the order in which they appear in the game, Y1 occurs before X3. Perhaps this is the main problem in our communication?

Best regards,
Fritz Grau

[Chan Rasjid]

Hello Fritz,

1. You analyse position X, and the value is based on a continuation through positions X1, X2, X3. The value of X is not "polluted by a draw score", so it is stored in your hash table; let us assume that the value of position X is "+3".

2. In the analysis of position Y, you encounter a continuation "Y, Y1, X"; hash table lookup evaluates this continuation as "+3".

But if, e.g., Y1=X3, the sequence Y, Y1, X, X1, X2, X3 contains a repetition and should be correctly evaluated as "draw"; but the repetition occurs only at "X3", so you won't find it when you probe the hash table for the position "X".

Thanks for clarifying the nomenclature.

If my understanding of how repetition dependency may corrupt hashing is correct, then your concern as shown in the quote above may be invalid. It seems there should not be an "opposite" issue to clean hashing contrary to what you first suggested.

Rep-3 dependency is passed downwards with a score of draw0. The first node that receives it and all nodes lower are "infected" by this draw0. If B is the first node that repeats A lower down, then B is not searched but return draw0 and this begins the infection. Subsequent search scores for nodes B-1, B-2, ... A+2, A+1 all would be infected and hashing such scores unconditionally means the hash table gets corrupted. The simplest scheme(there may be better scheme) to have a clean hash table is simply not to hash infected scores as just mentioned.

It is because of such path dependency that there is suggestion to use hash only for move ordering and not for cut-off or update of best score. I think a clean hash table may be used "safely" and cutoff and updates of bounds from clean entries should be correct. The only condition is that a hash hit may be used (safely) only if the node does not repeat any node lower down towards the root. No other condition applies. From the quote above, you seem to think that a hash hit and use of +3 for X in Y, Y1, X sort of violates a certain "draw" situation if Y1 == X3, "...should be correctly evaluated as "draw" ...". I think the reasoning that X3 above X repeats Y1(X3) below X caused a problem is flawed. The use of +3 of X from a clean hash is correct and safe as long as X does not repeat any nodes lower down. The fact that there are nodes in the subtree(higher up) to be searched for X that repeat other nodes lower than X are irrelevant.

Hope the above is not flawed as this is what is implemented in my chess program.

Best Regards,
Rasjid

[Fritz Grau]

Hello Chan,

Hope the above is not flawed as this is what is implemented in my chess program.

I believe that all efficient chess programs are flawed in this way because a correct draw score evaluation is impossible if you don't store the set of prior positions at least up to the last capture/pawn move alongside with each position; nobody would or should do so because that destroys most of the transposition table benefit.

However, each time you use the value of position which was evaluated relative to a different history, you run the risk that the value is wrong. In my example above, the engine would think: "Y, Y1, X" has the value 3 (because that is the value of position X in the hash table, which relies on the continuation "X1, X2, X3"), that is good, let's choose the move "Y", our PV is "Y, Y1, X[, X1, X2, X3 (HT)]"; the repetition (in this case 2-fold, to keep the example simple) would not occur within the search tree, so it is not detected; but the engine cannot continue with PV moves without running into a draw.

With regard to my example, I claim that (1) the engine would use the hash value of "+3" for the position X, (2) it would choose the move "Y", if there is no line yielding an evaluation of more than "+3", (3) the PV would be "Y, Y1, X, X1, X2, X3" and thus lead to a draw.
Could you tell me which of these claims is wrong?

I noticed this kind of behaviour in a zugzwang position with pawns only, where my engine gave a "+M19" instead of "+M18" with nullmove disabled, but an unrealistically reduced hash table size.

Kind regards,
Fritz Grau

[Chan Rasjid]

Hello Fritz,

However, each time you use the value of position which was evaluated relative to a different history, you run the risk that the value is wrong. ...

I think this is what you meant by the "opposite" problem .

With regard to my example, I claim that (1) the engine would use the hash value of "+3" for the position X, (2) it would choose the move "Y", if there is no line yielding an evaluation of more than "+3", (3) the PV would be "Y, Y1, X, X1, X2, X3" and thus lead to a draw.
Could you tell me which of these claims is wrong?

I think you are correct. The issue is that a hashed clean value is only clean relative to the corresponding history of the search that evaluated and hashed the value. If Y,Y1(X3),X is the pv of score +3, the truncated pv continuation is X1,X2,X3 and if this pv is played out, I think it is a draw and not +3.

Thanks for pointing out. I need to think about what the significance is as it relates to schemes that keep
hashing free of path dependency.

Best Regards,
Rasjid

[/quote]

[Fritz Grau]

Hello Chan,

I expect the problem to be of no practical relevance for gameplay; the reason I ran into it was my hope to produce a theoretically sound engine.

The cheapest sound implementation that I can think of is this:
- count 2-fold repetitions as draws (avoids need to discriminate between first and second appearances of a position; also speeds up the search)
- incrementally XOR the Zobrist key of each position with distorted keys generated from the Zobrist keys of each position (so the Zobrist key of the final position knows the "set of history position" but ignores their order).

However, I have not implemented this in my engine because
- it makes the engine slower because positions which only differ in the set of history positions need to be considered separately (ignoring the rep-draw pollution problem is like a kind of pruning which has very little draw-backs)
- once you use Zobrist keys you already leave the realm of theoretical soundness
- you need to invent a "random, but bijective" function to distort the original Zobrist keys of positions into keys that are used to determine the history.

Best regards,

Fritz

[H.G.Muller]

Yes, the opposite problem is a real pain. This is exactly what I meant by "unfortunately we cannot see the PV after a hash hit". The example Y, Y1, X[, X1, X2, X3 (HT)] is even worse than one might think, as it is not even needed that Y1=X3, and it still can be a draw: The side that is behind could have a move to X2->Y1, which in itself seemed to make no particular sense when X2 occurred in the 3-ply search tree of X, but with this new history containing Y1 suddenly should score as a draw. Or perhaps there would have been another move X->X1' which would force the leading side to play X1'->X2', where Y1 is reachable from X2'. In other words, there could have been an Y1 hidden amongst the leaves of the search tree of X, that wnet by unnoticed at the time of the search as Y1 was not in the path leading to X at the time of this search.

I think the best way to combat this is to try to make the all-side prefer forcing reversible moves, and store those as hash move. Normally the best move in an alpha node is meaningless anyway. If the all-side would benifit from a draw, he should try to pick a reversible move that cannot be refuted by null move and not by a capture. This enhances the probability that if he can force the cut-side to a single reply, the corresponding positions will end up in the 'best' continuation.

This would make it possible to extract the continuation from the hash table after a hash hit. So if we find position X in the hash table with score +3 through the path Y, Y1, X, we would not blindly accept the score, but do some more hash probes to follow the hash moves to X1, X2, X3, until we encounter an irreversible move. If it turns out that X3=Y1 or X2=Y, we know the hash score is no good after this path. Even if X3!=Y1, but the move X1->X2 is the reverse of the move Y1->X1 we should become suspicious, as it means theat X2->Y1 would have been possible, even though X2->X3 was chosen.