Author: Josue Forte
Date: 17:47:56 03/26/05
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.
PS.
I am attaching my code for Search() function to clarify my question.
Here is the code:
int Search(int alpha, int beta, int depth_remaining)
{
int *move;
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);
}
}
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.