Moderator: Andres Valverde
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;
}
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;
}
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.
//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()
Chan Rasjid wrote: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
Check the well known and strong SOS on this position and you'll see that's not the case:Fritz Grau wrote: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.
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.
If we test repetition (the 1st) before probing the hash table, there may be no opposite problem:-
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".
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 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.
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.
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".
Hope the above is not flawed as this is what is implemented in my chess program.
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. ...
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?
Return to Programming and Technical Discussions
Users browsing this forum: No registered users and 2 guests