I recently made a post concerning illegal moves as a result of faulty updating of the PV-stack (http://talkchess.com/forum3/viewtopic.php?f=7&t=76708 , the code referenced in the links are not the corrected version since I haven't pushed the changes yet), but after correcting this, I have isolated yet another cause of illegal moves: The transposition table.
The way I probe and order the hash moves are:
In root search:
Code: Select all
bool ttHit = false;
TT_Entry* entry = tt->probe_tt(ss->pos->posKey, ttHit);
unsigned int pvMove = NOMOVE;
if (ttHit) {
pvMove = entry->data.move;
// Loop through the move list and find the pvMove
for (int m = 0; m < moves.size(); m++) {
if (moves[m]->move == pvMove) {
moves[m]->score = hash_move_sort;
break;
}
}
}
Code: Select all
// Step 1. Transposition table probing (~30 elo - too little?). This is done before quiescence since it is quite fast, and if we can get a cutoff before
// going into quiescence, we'll of course use that. Probing before quiescence search contributed with ~17 elo.
bool ttHit = false;
TT_Entry* entry = tt->probe_tt(ss->pos->posKey, ttHit);
int ttScore = (ttHit) ? value_from_tt(entry->data.score, ss->pos->ply) : -INF;
unsigned int ttMove = (ttHit) ? entry->data.move : NOMOVE;
int ttDepth = (ttHit) ? entry->data.depth : 0;
int ttFlag = (ttHit) ? entry->data.flag : NO_FLAG;
if (ttHit && ttDepth >= depth) {
switch (ttFlag) {
case ALPHA:
if (ttScore <= alpha) {
pvLine->length = 0;
return alpha;
}
break;
case BETA:
if (ttScore >= beta) {
pvLine->length = 0;
return beta;
}
break;
case EXACT:
pvLine->length = 0;
return ttScore;
}
}
/*
...
Pruning methods
...
*/
// Just before looping through the moves list:
// If the transposition table returned a move, this is probably the best, so we'll score it highest.
if (ttHit && ttMove != NOMOVE) {
for (int i = 0; i < moves.size(); i++) {
if (moves[i]->move == ttMove) {
moves[i]->score = hash_move_sort;
}
break;
}
}
Code: Select all
TT_Entry* TranspositionTable::probe_tt(uint64_t key, bool& hit) {
TT_Entry* slot = &entries[key % numEntries];
uint64_t* data = (uint64_t*) &slot->data;
if (slot->key == (key ^ *data)) {
hit = true;
return slot;
}
hit = false;
return nullptr;
}
void TranspositionTable::store_entry(const GameState_t* pos, int move, int score, int depth, int flag) {
TT_Entry* slot = &entries[pos->posKey % numEntries];
uint64_t* data = (uint64_t*) &slot->data;
assert(flag >= 0 && flag <= 2);
if (depth >= slot->data.depth || depth == slot->data.depth - 1) {
slot->key = pos->posKey ^ *data;
slot->data.move = move;
slot->data.score = value_to_tt(score, pos->ply);
slot->data.depth = depth;
slot->data.flag = flag;
}
}
Code: Select all
struct EntryData {
volatile unsigned int move = NOMOVE;
volatile int score = -INF;
volatile unsigned int depth = 0;
volatile int flag = NO_FLAG;
};
struct TT_Entry {
volatile uint64_t key = 0;
EntryData data;
};
For good measure, the entire search_root function is:
Code: Select all
// Root alpha beta
int search_root(SearchThread_t* ss, int depth, int alpha, int beta, SearchPv* pvLine) {
assert(depth > 0);
ss->info->nodes++;
pvLine->clear();
SearchPv line;
int score = -INF;
int best_score = -INF;
int best_move = NOMOVE;
int new_depth = depth;
bool raised_alpha = false;
int legal = 0;
MoveList moves;
ss->generate_moves(&moves);
// Step 1. In-check extensions.
bool in_check = ss->pos->in_check();
//if (in_check) {
// new_depth++;
//}
// Steo 2. Static evaluation.
if (in_check) {
ss->static_eval[ss->pos->ply] = VALUE_NONE;
}
ss->static_eval[ss->pos->ply] = Eval::evaluate(ss->pos);
// Step 3. Probe transposition table --> If there is a move from previous iterations, we'll assume the best move from that as the best move now, and
// order that first.
bool ttHit = false;
TT_Entry* entry = tt->probe_tt(ss->pos->posKey, ttHit);
unsigned int pvMove = NOMOVE;
if (ttHit) {
pvMove = entry->data.move;
// Loop through the move list and find the pvMove
for (int m = 0; m < moves.size(); m++) {
if (moves[m]->move == pvMove) {
moves[m]->score = hash_move_sort;
break;
}
}
}
// Now we'll loop through the move list.
for (int m = 0; m < moves.size(); m++) {
line.clear();
ss->pickNextMove(m, &moves);
unsigned int move = moves[m]->move;
if (!ss->pos->make_move(moves[m])) {
continue;
}
legal++;
// Print move, move number and such to the command line.
if (ss->thread_id == 0) {
uci_moveinfo(move, depth, legal);
}
// Set the previous move such that we can use the countermove heuristic.
ss->moves_path[ss->pos->ply] = move;
// Step 3. Principal Variation search. We search all moves with the full window until one raises alpha. Afterwards we'll search with a null window
// and only widen it if the null window search raises alpha, which is assumed unlikely.
if (!raised_alpha) {
score = -alphabeta(ss, new_depth - 1, -beta, -alpha, true, &line);
}
else {
score = -alphabeta(ss, new_depth - 1, -alpha - 1, -alpha, true, &line);
if (score > alpha && score < beta) {
score = -alphabeta(ss, new_depth - 1, -beta, -alpha, true, &line);
}
}
ss->pos->undo_move();
if (ss->info->stopped) { return 0; }
if (score >= beta) { // Fail high
if (legal == 1) {
ss->info->fhf++;
}
ss->info->fh++;
tt->store_entry(ss->pos, move, score, depth, BETA);
return beta;
}
if (score > best_score){
best_score = score;
if (score > alpha) {
alpha = score;
best_move = move;
raised_alpha = true;
ChangePV(best_move, pvLine, &line);
}
}
}
if (legal == 0) {
if (ss->pos->in_check()) {
return -INF + ss->pos->ply;
}
else {
return 0;
}
}
// If we improved alpha, we're in a PV-node
if (raised_alpha) {
assert(best_move == pvLine->pv[0]);
tt->store_entry(ss->pos, best_move, alpha, depth, EXACT);
}
else {
tt->store_entry(ss->pos, best_move, alpha, depth, ALPHA);
}
return alpha;
}
I really don't understand how the TT can cause illegal moves when I don't even use the hash move (if found) directly, but only if it already is in the list of pseudo-legal moves.
Is this a bug in the code or just a result of some sort of collisions in the TT? If the former: Could this be caused by the above code snippets?
Thanks for the help in advance!
