Author: Stan Arts
Date: 10:18:04 03/27/05
Go up one level in this thread
Hi Josue,
a while ago I posted an awnser for a similair question in the winboard-forum,
(Link to the post: http://volker-pittlik.name/wbforum/viewtopic.php?t=929)
I'll paste a relevant part below.
Hope it will be of any help. (my program Neurosis finds the solution to this
problem on the correct depth.)
Goodluck!
Stan
---------------------------------
When I started to experiment with using hashtablescores/transportations and
comming across the draw-problem, there were a few things that seemed to help. (a
bit)
I don't use a hashtablescore when it's 0. (or another drawscore, but I don't
have contempt so always 0.) This is the case for repetitiondraws and 50-move
rule draws. (Drawscores that I return in the searchtree, instead of evaluation)
0 scores returned by evaluation I make -1, so these do get used next time.
Further I take a look if the current position is a 2x repetition already, (with
Neurosis I only give draw-scores for 3x (not 2x) repetitions.) in that case I
won't use a hashtablescore (no matter what it is) as well in this position.
This was a big help and fixed most of the problems for me.
-----
On March 26, 2005 at 20:47:56, Josue Forte wrote:
>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.