Hashtable fails to detect draw by repetition.

[Josu? Forte]

Hi,

Two weeks ago I found a problem in my engine concerning hashtable.
It fails to detect a draw by repetition during the search when I set up
the following position:
r4r1k/6R1/4p2r/3p1p2/4b3/Np6/1P6/K5R1 w - - 0 1

In this position white can force a draw by repetition in 7 plies
like this: g7h7 h8xh7 g1g7 h7h8 g7g8 h8h7 g8g7 (draw by repetition)

For the test, I wrote a very simple evaluation function (only
material is evaluated), no quiescent_search is used and no extensions
are done during the search.
I used the following piece values:
Pawn = 100
Knight = 300
Bishop = 300
Rook = 500
Queen = 900

The search results follows:

Depth | SCORE | Best variation
1 | -800 | g7g8
2 | -1100 | g7e7 a8xa3
3 | -700 | g7e7 f8d8 e7xe6
4 | -1100 | g7e7 f8d8 e7f7 a8xa3
5 | -700 | g7e7 f8d8 e7f7 d8e8 f7xf5
6 | -1000 | g7b7 h6h3 g1e1 f8g8 e1xe4 f5xe4
7 | -700 | g7b7 h6h3 g1e1 f8g8 b7f7 e4f3 e1xe6

The problem occurs at search depth 7. After finding the main variation
above, Matheus evaluate another line like this:
g1c1 h8xg7 c1g1 g7h8 g1g8 h8h7 g8xf8 (score: 800 for black)

It stores the result of the position g1c1 h8xg7 c1g1 g7h8 g1g8 in the
hashtable with the following values:
score = 800 (for black)
best_move = h8h7
depth_remaining = 2
hash_flag = Lower bound (beta at this point was 700)

When Matheus searches g7h7 h8xh7 g1g7 h7h8 g7g8, (this is the subtree
that leads to draw) it finds this position in the hashtable. (see above)
Hashkey, depth_remaining and hash_flag are suitable for a cutoff, so it
prune this subtree and did not see the draw line.
Every thing is correct, but this approach simply fails when draw by repetition
is an issue.
If I disable hashtable, Matheus finds the solution correctly in 7 plies.


Anybody has faced this problem and can give me a solution?

Thanks in advance for any help.
Josu? Forte.

[Sune Fischer]

Do you test for repetition before or after probing the HT?

-S.

[Josu? Forte]

Hi Sune,

Well, the first thing I do is to test for repetition after making a move. Then I call search() and the first thing I do in search() is to probe the HT.

Better to show you my code in Search() to clarify.
Here it is:

int Search(int alpha, int beta, int depth_remaining)
{
int *move;
int extension;
int score;
HASH_ENTRY *hash_entry;
int pvs = 0;
int temp_alpha = -MATE_VALUE; ///

if (++node_counter > node_counter_limit) ScanInput();
depth_remaining--;

// Install the next PV move into the hash table so that it will be played first.
hash_entry = &hashtable[moving_color][(unsigned int)hashkey & hashtable_size_mask];
if (follow_pv) {
MOVE *pv_move = (MOVE *)&pv[0][ply];
if (ply >= pv_length[0]) {
follow_pv = 0;
goto SKIP_HASHTABLE;
}
else if (depth_remaining <= 0)
depth_remaining = 1;

if (MoveIsLegal(pv_move->from, pv_move->to, pv_move->piece, pv_move)) {
hash_entry->always.hashkey = hashkey;
hash_entry->always.move = pv[0][ply];
hash_entry->always.flag.bound = EXACT_SCORE;
hash_entry->always.depth_remaining = (char)depth_remaining;
}
goto SKIP_HASHTABLE;
}

// Verify if this position is in the hashtable. ("always" element)
if (hash_entry->always.hashkey != hashkey)
follow_pv = 0;
else {
if (follow_pv) {
if (ply >= pv_length[0])
follow_pv = 0;
else if (depth_remaining <= 0)
depth_remaining = 1;
goto SKIP_HASHTABLE;
}
if (hash_entry->always.depth_remaining >= (char)depth_remaining) {
int hash_score = (int)hash_entry->always.score;

// Mate scores have to be adjusted because here "hash_score" represents mate in N plies
// from this position. We must retrieve "hash_score" as mate in N plies from the root.
if (abs(hash_score) >= MATE_VALUE - MAX_DEPTH) {
if (hash_score > 0) hash_score -= ply;
else hash_score += ply;
}
if (hash_entry->always.flag.bound & LOWER_BOUND) {
if (hash_score >= beta) {
return(hash_score);
}
}
else if (hash_entry->always.flag.bound & UPPER_BOUND) {
if (hash_score <= alpha) {
return(hash_score);
}
}
}
}

// Verify if this position is in the hashtable. ("depth" element)
if (hash_entry->depth.hashkey != hashkey);
else if (hash_entry->depth.depth_remaining >= (char)depth_remaining) {
int hash_score = (int)hash_entry->depth.score;

// Mate scores have to be adjusted because here "score" represents mate in N moves
// from this position. We must retrieve "score" as mate in N moves from the root.
if (abs(hash_score) >= MATE_VALUE - MAX_DEPTH) {
if (hash_score > 0) hash_score -= ply;
else hash_score += ply;
}
if (hash_entry->depth.flag.bound & LOWER_BOUND) {
if (hash_score >= beta) {
return(hash_score);
}
}
else if (hash_entry->depth.flag.bound & UPPER_BOUND) {
if (hash_score <= alpha) {
return(hash_score);
}
}
}

SKIP_HASHTABLE:

next_move_pointer[ply + 1] = LegalMoveGenerator(next_move_pointer[ply]);
legal_moves[ply] = next_move_pointer[ply + 1] - next_move_pointer[ply];
if (legal_moves[ply] > 1) {
ValuateMoves(next_move_pointer[ply], next_move_pointer[ply + 1], hash_entry);
SortMoves(next_move_pointer[ply], 0, legal_moves[ply] - 1);
}


// Search starts here.
for (move = next_move_pointer[ply]; move < next_move_pointer[ply + 1]; move++) {
(*move) &= 0x7FFFFF;
MakeMove((MOVE *)move);
current_move[ply] = *((MOVE*)move);

// Check for draw by 3 fold repetition or 50 move rule.
if (status[move_number].fifty_move_rule > 3) {
if (IsDraw()) {
follow_pv = score = 0;
pv_length[ply + 1] = 0;
goto SKIP_SEARCH;
}
}

// Check for insufficient material.
if (insufficient_material) {
if (!IsAttacked(KING_SQUARE(not_moving_color), moving_color)) {
follow_pv = score = 0;
pv_length[ply + 1] = 0;
goto SKIP_SEARCH;
}
}

// Check for maximum search depth.
if (ply >= MAX_DEPTH) {
score = -Evaluate(); /// Verificar depois se est? certo.
pv_length[ply + 1] = 0;
goto SKIP_SEARCH;
}

// Check for node search level.
if (node_search) {
if (node_counter >= node_search) {
stop_search = 1;
goto SKIP_SEARCH;
}
}
moving_color = not_moving_color;
not_moving_color ^= 1;
ply++;

if (depth_remaining > 0) {
if (pvs) {
score = -Search(-alpha - 1, -alpha, depth_remaining);
if ((score > alpha) && (score < beta))
score = -Search(-beta, -alpha, depth_remaining);
}
else score = -Search(-beta, -alpha, depth_remaining);
}
else
score = -QuiescentSearch(-beta, -alpha);

ply--;
not_moving_color = moving_color;
moving_color ^= 1;

SKIP_SEARCH:

UnMakeMove((MOVE *)move);
if (stop_search) return(score);

if (score >= beta) { // Fail High.
int temp_score = score;

if (abs(score) >= (MATE_VALUE - MAX_DEPTH)) {
if (score > 0) score += ply;
else score -= ply;
}

// Record search result in hashtable. ("always" element)
hash_entry->always.flag.bound = LOWER_BOUND;
hash_entry->always.move = *move;
hash_entry->always.hashkey = hashkey;
hash_entry->always.score = score;
hash_entry->always.depth_remaining = (char)depth_remaining;

// Record search result in hashtable. ("depth" element)
if ((age != hash_entry->depth.flag.age) ||
(hash_entry->depth.depth_remaining < (char)depth_remaining)) {
if (age != hash_entry->depth.flag.age) {
hashtable_write++;
hash_entry->depth.flag.age = (unsigned char)age;
}
hash_entry->depth.move = *move;
hash_entry->depth.hashkey = hashkey;
hash_entry->depth.depth_remaining = (char)depth_remaining;
hash_entry->depth.score = score;
hash_entry->depth.flag.bound = LOWER_BOUND;
}
return(temp_score);
}

if (score > alpha) {
alpha = score;
pv[ply][ply] = *move;
UpDatePV();
pvs = 1;
}
if (score > temp_alpha) temp_alpha = score;
}

if (legal_moves[ply] == 0) { // Verify if it is Mate or Stalemate.
pv[ply][ply] = 0;
pv_length[ply] = 0;
if (IsAttacked(KING_SQUARE(moving_color), not_moving_color))
return(ply - MATE_VALUE);
else
return(0);
}

score = alpha;
if (pvs) {

// This is an EXACT_SCORE, so update killer moves.
UpdateKillerMove((MOVE *)&pv[ply][ply]);

// Record search result in hashtable. ("always" element)
if (abs(alpha) >= (MATE_VALUE - MAX_DEPTH)) {

// Mate scores have to be adjusted because here "score" represents mate in N moves
// from this position. We must retrieve "score" as mate in N moves from the root.
if (alpha > 0) score = alpha + ply;
else score = alpha - ply;

// If EXACT_SCORE on +mate, change it to LOWER_BOUND.
if (alpha > 0) {
hash_entry->always.move = pv[ply][ply];
hash_entry->always.flag.bound = LOWER_BOUND;
}

// If EXACT_SCORE on -mate, change it to UPPER_BOUND.
else {
hash_entry->always.move = 0;
hash_entry->always.flag.bound = UPPER_BOUND;
}
}
else {
hash_entry->always.flag.bound = EXACT_SCORE;
hash_entry->always.move = pv[ply][ply];
}
hash_entry->always.hashkey = hashkey;
hash_entry->always.score = score;
hash_entry->always.depth_remaining = (char)depth_remaining;

// Record search result in hashtable. ("depth" element)
if ((age != hash_entry->depth.flag.age) ||
(hash_entry->depth.depth_remaining < (char)depth_remaining)) {
if (age != hash_entry->depth.flag.age) {
hashtable_write++;
hash_entry->depth.flag.age = (unsigned char)age;
}
if (abs(alpha) >= (MATE_VALUE - MAX_DEPTH)) {

// EXACT_BOUND on +mate. Change it to LOWER_BOUND.
if (alpha > 0) {
hash_entry->depth.move = pv[ply][ply];
hash_entry->depth.flag.bound = LOWER_BOUND;
}

// EXACT_BOUND on -mate. Change it to UPPER_BOUND.
else {
hash_entry->depth.move = 0;
hash_entry->depth.flag.bound = UPPER_BOUND;
}
}
else {
hash_entry->depth.move = pv[ply][ply];
hash_entry->depth.flag.bound = EXACT_SCORE;
}
hash_entry->depth.hashkey = hashkey;
hash_entry->depth.score = score;
hash_entry->depth.depth_remaining = (char)depth_remaining;
}
return(alpha);
}
else { // Fail Low.
if (abs(temp_alpha) >= (MATE_VALUE - MAX_DEPTH)) {

// Mate scores have to be adjusted because here "score" represents mate in N moves
// from this position. We must retrieve "score" as mate in N moves from the root.
if (temp_alpha > 0) score = temp_alpha + ply;
else score = temp_alpha - ply;
}

// Record search result in hashtable. ("always" element)
hash_entry->always.hashkey = hashkey;
hash_entry->always.move = 0;
hash_entry->always.flag.bound = UPPER_BOUND;
hash_entry->always.score = score;
hash_entry->always.depth_remaining = (char)depth_remaining;

// Record search result in hashtable. ("depth" element)
if ((age != hash_entry->depth.flag.age) ||
(hash_entry->depth.depth_remaining < (char)depth_remaining)) {
if (age != hash_entry->depth.flag.age) {
hashtable_write++;
hash_entry->depth.flag.age = (unsigned char)age;
}
hash_entry->depth.hashkey = hashkey;
hash_entry->depth.move = 0;
hash_entry->depth.flag.bound = UPPER_BOUND;
hash_entry->depth.score = score;
hash_entry->depth.depth_remaining = (char)depth_remaining;
}
return(temp_alpha);
}
}

[Sune Fischer]

Ok, so it wasn't as easy as that...

I'm looking at the line you gave in the first post:
g1c1 h8xg7 c1g1 g7h8 g1g8 h8h7 g8xf8 (score: 800 for black)

I think something is wrong if you store 800 for black the move before g8xf8,
because only the last move is losing.
It is within your horizon to see g8g7 and draw.

-S.

[Sune Fischer]

The code is a bit too large for me to spot the problem, but If I have to
take a guess I'd say it is possibly a draft bug.

Do you probe and store with the same depth always?

Another idea, do you score repetition draw on the second or the first
repetition?
I guess it is possible to get a hashhit on the first repetition and thus never reach the second (drawing) repeition due to the cutoff.

-S.

[Josu? Forte]

Answering your questions:
"Do you probe and store with the same depth always?"
No.

"Another idea, do you score repetition draw on the second or the first
repetition? "
I score draw in the first repetition.


The key point in my post is that one positition can be reached in different paths.
For instance, consider the initial position
r4r1k/6R1/4p2r/3p1p2/4b3/Np6/1P6/K5R1 w - - 0 1

If I play
g1c1 h8xg7 c1g1 g7h8 g1g8
or if I play
g7h7 h8xh7 g1g7 h7h8 g7g8
I get the same position (same hashkey). This is the so called transposition.
But note that when a transposition can involve a draw by repetition, this
is a problem if we use hashtables. This is what I mean.

In the first line I can not get a draw by repetition in the next two plies.
But in the second line I can get a draw by repetition in the next two plies by playing g7h7 h8xh7 g1g7 h7h8 g7g8 h8h7 g8g7.

Unfortunately, hashtables don't consider paths in their structures. They consider only positions (hashkey).

Making an analogy to null move heuristic, this is like to make a null move in a zugswang position.
It seems the problem doesn't have an efficient solution, or does it?
Well, it is getting late here in Brazil. Time to go to bed.

Josu?.




, (this is the subtree
that leads to draw) it finds this position in the hashtable. (see above)
Hashkey, depth_remaining and hash_flag a

[Anonymous]

Unfortunately, hashtables don't consider paths in their structures. They consider only positions (hashkey).

It seems the problem doesn't have an efficient solution, or does it?

Correct. But typically the problem solves itself with a bit higher depth.

But for the concrete position: you might also have a bug. I did not study the lines you gave or your code. Yace shows draw from depth 3 with the following line:

2528 0.031 0.00 3. 1.Rh7+ Kxh7 2.Rg7+ Kh8 3.Rg8+ Rxg8 {-1750}

Regards,
Dieter

[Sune Fischer]

Hi Josu?

Yes the hash is path independent and that can create some problems with
scores that are path dependent.

I don't think it is as bad as the nullmove issue, like Dieter said it is usually
solved at the next ply.

That is why I suspected a draft problem, if you don't eventually see the
draw you must be somehow reusing the same entry again at higher depths.

-S.

[peterhughes]

Josu?

I had/have this exact same problem in SharpChess.

Firstly, I updated my hashkey function to return a different hashkey for a 3-move-repetition (3MR), to that same position when it is not 3MR. I had to do this because, even though the pieces are in the same position, in the 3MR case it's NOT actually the same position in terms of score (because it's a draw position). I remember having to do the same kind of thing with En Passent possitions also.

However, although I was certain that this would fix it, it actually didn't! In the end, I "frigged" it and added some extra code to clear the hash table at the start of a computer turn, if the current position on the board is two-move-repetition. This worked a treat, but I still can't help feeling abit "dirty"!

Regards
Peter Hughes

[Chan Rasjid]

Does it not help if we do not store into hash a draw due to repetition?

Hash should be for a node score that is completely detemined by only
board positioms, and not path dependent.

[Anonymous]

I just remembered one thing that has helped my engine. I almost always have a best move in the hash (generally also for upper bounds, not for null move, TB hits or otherwise terminal nodes). When I get a hash hit, that is good for a cutoff, I calculate the repetition counter for the position after this move. If it is not zero, and the score is not zero either, don't trust the stored score. (Sometimes you can do more - when zero score is good enough for a beta cutoff, for example, you can now immediately return zero before you generated any moves.)

I vaguely remember an example in Dennis Breuker's thesis (you can find it easily with google). One chapter is about the "graph history interaction". There he investigates one example, where due to the HT, the search result will be wrong.

Regards,
Dieter

[Sune Fischer]

Guys,

I don't think any special tricks are really needed here.
I would suggest looking for a bug rather than try and code around it.

-S.

[Sven Schüle]

Does it not help if we do not store into hash a draw due to repetition?

Hash should be for a node score that is completely detemined by only
board positioms, and not path dependent.

This is exactly what I think about the given problem: it might a problem of the approach, not a coding bug. I would not (and do not within Surprise) store "draw by repetition" positions, or other final positions, in the main hash table. The hash table should save searching nodes, but it should not make things more complicated.
Just my 2 cents.
Sven

[Josu? Forte]

Hi Guys,

Thank you very much for your comments and suggestions.
I will consider them in my research about this issue.

All the best,
Josu