Exact node values

Code, algorithms, languages, construction...
Post Reply
CDaley11
Posts: 42
Joined: Thu Jan 10, 2013 6:23 am
Real Name: Christian Daley

Exact node values

Post by CDaley11 » Wed Jan 16, 2013 11:09 pm

So I've discovered a major bug in my transposition table. Right now I'm only considering nodes that returned an exact value, not nodes that produced cutoffs. Here's the steps I'm taking for it:

1. In the search method, before looping through each move, see if there's an entry in the table for the current hash key. If there is, simply return the value stored in the table.

2. After looping through each move, save the current hash key along with the determined value in the transposition table. Only save the hash key and value if the value is an exact value for the position.

I am under the impression that a node value is exact if and only if: A move was found that beat the current alpha value, and no move was found that exceeded the beta value.

However, my engine is not working with this. It allows its queen to be taken by a pawn. It doesn't do this if I take out the transposition table.

EDIT: I should be more clear. I get it to a point in the game where I move one of my pawns up, threatening my engine's queen. It makes a mindless rook move and allows me to capture the queen. If, however, I clear the Ttable before I make my pawn move, it doesn't allow it's queen to be taken. It makes a perfectly acceptable retreat of its queen.

lucasart
Posts: 201
Joined: Mon Dec 17, 2012 1:09 pm
Contact:

Re: Exact node values

Post by lucasart » Fri Jan 18, 2013 1:36 am

CDaley11 wrote:So I've discovered a major bug in my transposition table. Right now I'm only considering nodes that returned an exact value, not nodes that produced cutoffs. Here's the steps I'm taking for it:

1. In the search method, before looping through each move, see if there's an entry in the table for the current hash key. If there is, simply return the value stored in the table.

2. After looping through each move, save the current hash key along with the determined value in the transposition table. Only save the hash key and value if the value is an exact value for the position.

I am under the impression that a node value is exact if and only if: A move was found that beat the current alpha value, and no move was found that exceeded the beta value.

However, my engine is not working with this. It allows its queen to be taken by a pawn. It doesn't do this if I take out the transposition table.

EDIT: I should be more clear. I get it to a point in the game where I move one of my pawns up, threatening my engine's queen. It makes a mindless rook move and allows me to capture the queen. If, however, I clear the Ttable before I make my pawn move, it doesn't allow it's queen to be taken. It makes a perfectly acceptable retreat of its queen.
CDaley11 wrote: 1. In the search method, before looping through each move, see if there's an entry in the table for the current hash key. If there is, simply return the value stored in the table.
No! It's not that simple. You need to read the score, depth and score type from the TT entry. You only use TT for pruning (ie return TT score) when
- the depth is >= the remaining depth
- the score type is correct (a lower bound score >= beta, or an upper bound score <= alpha). By the way do not use exact scores for pruning, I recommend you only use TT for move ordering at PV nodes, and not for pruning.
- when the score is a mate score, you need to adjust it for the correct ply
CDaley11 wrote: 2. After looping through each move, save the current hash key along with the determined value in the transposition table. Only save the hash key and value if the value is an exact value for the position.
You need to save 4 things:
- for TT pruning: depth, score, score type (lower bound, upper bound, or exact score)
- for move ordering: the TT move. If the TT entry can't be used for pruning (see answer to first point) then you have at least a TT move to try first, and in the vast majority of cases (>90%) this will be the best move, and you should therefore use PVS rather than plain alpha-beta to take advantage of it.
CDaley11 wrote: I am under the impression that a node value is exact if and only if: A move was found that beat the current alpha value, and no move was found that exceeded the beta value.
[/code]
Yes, that is correct. In other words, when the best score verifies old_alpha < best_score < beta, then it is an exact score. If you use PVS, this can only happen at PV nodes: at all or cut nodes, all you have are upper and lower bound scores.
CDaley11 wrote: However, my engine is not working with this. It allows its queen to be taken by a pawn. It doesn't do this if I take out the transposition table.

EDIT: I should be more clear. I get it to a point in the game where I move one of my pawns up, threatening my engine's queen. It makes a mindless rook move and allows me to capture the queen. If, however, I clear the Ttable before I make my pawn move, it doesn't allow it's queen to be taken. It makes a perfectly acceptable retreat of its queen
The transposition table is not at fault, your implementation is. So you're doing it wrong, and you will NEVER find the answer by looking at pieces moving on the board, but by running a *debugger*, and looking at your *code*.

PS: Sorry, I may sound harsh, but I speak the truth from experience (been there, done that, got the T-shirt...)
"Talk is cheap. Show me the code." -- Linus Torvalds.

CDaley11
Posts: 42
Joined: Thu Jan 10, 2013 6:23 am
Real Name: Christian Daley

Re: Exact node values

Post by CDaley11 » Fri Jan 18, 2013 2:02 am

First of all, sorry for not stating this but I do use also save the depth that the position was searched to. Before I go any further here's the psudo code I'm using right now:

Code: Select all

//Before looping through each move
int index = currentHash % HASH_TABLE_SIZE;
if ( savedPositions[index] == currentHash && savedDepths[index] >= currentDepth ) {
     //savedPositions being the saved hash-keys, and savedDepths being the depth the positions were searched to
     if ( savedFlags[index] == HASH_EXACT) {
          //saved flags being what kind of node it was, exact, upper bound, etc. Right now I'm only using exact scores
          return savedValues[index];
    }
}

// Loop through each move. Through the course of the move loop if the value gets larger than beta it immediately cuts off
//...
// After the move loop. It will only get to this point if it hasn't exceeded the beta

if (value >= alpha) { // Alpha was raised
     savedPositions[index] = currentHash;
     savedDepths[index] = currentDepth;
     savedFlags[index] = HASH_EXACT;
     savedValues[index] = value;
}

return value;
I think I understand what you are saying, right now I do not store the best moves for positions but I hope to do that in the future. You say not to use exact scores for pruning. Why not? If we have the exact score for a node, then what is the point in searching it, assuming that the exact score we have is a score from an acceptable search depth.

lucasart
Posts: 201
Joined: Mon Dec 17, 2012 1:09 pm
Contact:

Re: Exact node values

Post by lucasart » Fri Jan 18, 2013 3:45 am

CDaley11 wrote:First of all, sorry for not stating this but I do use also save the depth that the position was searched to. Before I go any further here's the psudo code I'm using right now:

Code: Select all

//Before looping through each move
int index = currentHash % HASH_TABLE_SIZE;
if ( savedPositions[index] == currentHash && savedDepths[index] >= currentDepth ) {
     //savedPositions being the saved hash-keys, and savedDepths being the depth the positions were searched to
     if ( savedFlags[index] == HASH_EXACT) {
          //saved flags being what kind of node it was, exact, upper bound, etc. Right now I'm only using exact scores
          return savedValues[index];
    }
}

// Loop through each move. Through the course of the move loop if the value gets larger than beta it immediately cuts off
//...
// After the move loop. It will only get to this point if it hasn't exceeded the beta

if (value >= alpha) { // Alpha was raised
     savedPositions[index] = currentHash;
     savedDepths[index] = currentDepth;
     savedFlags[index] = HASH_EXACT;
     savedValues[index] = value;
}

return value;
I think I understand what you are saying, right now I do not store the best moves for positions but I hope to do that in the future. You say not to use exact scores for pruning. Why not? If we have the exact score for a node, then what is the point in searching it, assuming that the exact score we have is a score from an acceptable search depth.
I read your pseudo-code, and it's still nowhere near it. All I see is HASH_EXACT: where is HASH_LBOUND and HASH_UBOUND ? Besides, this is not going to work

Code: Select all

if (value >= alpha) { // Alpha was raised
You need to save the initial value of alpha at the beginning of the search (call it old_alpha), and then compare the value to old_alpha. After the move loop (beta cutoff or not) your code should do something like this:

Code: Select all

TTEntry tte;
tte.type = score <= old_alpha ? HASH_UBOUND : (score >= beta ? HASH_LBOUND : HASH_EXACT);
tte.move = best_move;
tte.score = best_score;
tte->depth = depth;
// Now save tte into the transposition table
"Talk is cheap. Show me the code." -- Linus Torvalds.

Post Reply