I've written a small chess engine (Plankton), the main aim being to have a fairly portable engine than can be ported to different microcontrollers. But I wanted to see how it would go with a hash table. I've been testing it against TSCP and the last round of 100 games Plankton won about 73% of the games. That's cool, but looking at game 13, Plankton returned a mate score in this position: k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31 with Bf3+. So occasionally it's making some pretty dumb moves. I suspect this is an issue with my hash table implementation. I'd really appreciate any insight into what could be wrong. Here is the AB search code:
const int16_t absearch(int16_t alpha, int16_t beta, uint8_t depth, const uint8_t null_move)
{
// if depth reached then return the score from quiesce
if (!depth) return quiesce(alpha,beta);
eo.nodes++;
// check if search time up
if ((eo.nodes&8191)==0 && millis()>eo.stop_time) eo.stop_search = true;
pvl[ply] = ply;
// if this isn't the root of the search tree (where we have
// to pick a move and can't simply return 0) then check to
// see if the position is a repeat if so, we can assume that
// this line is a draw and return 0
if (ply && reps()) return 0;
// don't search too deep
if (ply>=MAX_PLY-1) return eval();
// if in check then keep searching
const uint8_t in_check = king_attack(side);
if (in_check)
{
depth++;
////?
// if (eo.stop_search) printf("ignoring timeout!\r\n");
eo.stop_search = false;
}
// false checkmate score
//k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31
//fen 8/2r4k/p5p1/PP6/b2R1PPP/7r/3K4/6R1 b - - 0 46
//fen rnb4N/p1p4Q/2k1p2p/1p1n4/1b4q1/8/PP3PPP/1RK4R b - - 5 23 ***
#if HASH_TABLE_ENABLE
const uint32_t hi = hk%MAX_HASH_TABLE;
if (ply)
{
if (ht[hi].key==hk && ht[hi].depth>=depth && (ht[hi].flag&FL_SIDE)==side)
{
int16_t s = ht[hi].score;
if (s>MATE_VALUE) s -= ply; else if (s<-MATE_VALUE) s += ply;
if (ht[hi].flag&HASH_EXACT) {stats.nhash++; return s;}
else if ((ht[hi].flag&HASH_BETA) && s>=beta) {stats.nhash++; return beta;}
else if ((ht[hi].flag&HASH_ALPHA) && s<=alpha) {stats.nhash++; return alpha;}
}
}
#endif
#if NULLMOVE_ENABLE
if (null_move && !in_check && ply && depth>3)
{
int16_t nullmat = 0;
uint8_t p = EMPTY;
for (uint8_t i=0;i<64;i++)
{
if ((p=b[i]&0xf)==EMPTY) continue;
if ((p&0x07)==PAWN) continue;
if ((p&FL_SIDE)!=side) continue;
nullmat += (white_scores[p]+black_scores[p]);
}
if (nullmat>1400)
{
donullmove();
int16_t v = -absearch(-beta, -beta+1, depth - 1 - 2, false);
undonullmove();
if (eo.stop_search) return 0;
if (v>=beta && abs(v)<MATE_VALUE)
{
return beta;
}
}
}
#endif
// loop through the moves
gen_all_moves(side);
#if HASH_TABLE_ENABLE
if (ht[hi].key==hk)
{
const uint8_t origin = ht[hi].origin;
const uint8_t target = ht[hi].target;
for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
{
// don't replace the PV!
if (ml[i].order==65535u) continue;
if (origin==ml[i].m.origin && target==ml[i].m.target)
{
ml[i].order = 65000u;
stats.hashorder++;
break;
}
}
}
#endif
int16_t old_alpha = alpha;
int16_t best_score = -MAX_VALUE;
move_t best_move = {0};
uint8_t legal_move = 0;
uint8_t move_ordering = true;
for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
{
if (move_ordering) order_next_move(i);
move_ordering = ml[i].order>0;
if (!domove(ml[i].m)) continue;
legal_move++;
#if LMR_ENABLE
int16_t v = 0;
if (depth<4 || legal_move==1 || in_check || ml[i].order>60000u)
{
v = -absearch(-beta, -alpha, depth-1, true);
}
else
{
const uint8_t reduce = ml[i].order==0?2:1;
//const uint8_t reduce = ml[i].order<60000?2:1;
v = -absearch(-beta, -alpha, depth-1-reduce, false);
if (v>alpha)
{
v = -absearch(-beta, -alpha, depth-1, true);
}
}
#else
int16_t v = -absearch(-beta, -alpha, depth-1, true);
#endif
undomove();
if (eo.stop_search) return 0;
if (v>best_score)
{
// update the PV
ASSERT(ply+1<MAX_PLY);
pv[ply][ply].m = ml[i].m;
for (uint8_t j=ply+1;j<pvl[ply+1];j++) pv[ply][j] = pv[ply+1][j];
pvl[ply] = pvl[ply+1];
best_score = v;
best_move = ml[i].m;
if (v>alpha)
{
// since there was a cutoff increase the history or
// "curiosity" heuristic (this is a low memory version
// of the history heuristic which does a better job
// than nothing but not as good as full history - the
// difference in memory usage is significant!)
#if CURIOSITY_HEURISTIC
if (depth>2 && ml[i].m.capture==EMPTY)
curiosity[ml[i].m.target] += depth;
#elif HISTORY_HEURISTIC
if (depth>2 && ml[i].m.capture==EMPTY)
history[ml[i].m.origin][ml[i].m.target] += depth;
#endif
if (v>=beta)
{
// record killers
if (ml[i].m.capture==EMPTY)
{
killers[2][ply] = killers[1][ply];
killers[1][ply] = killers[0][ply];
killers[0][ply] = ml[i].m;
}
#if HASH_TABLE_ENABLE
// store hash table entry
ht[hi].key = hk;
ht[hi].origin = best_move.origin;
ht[hi].target = best_move.target;
ht[hi].depth = depth;
ht[hi].score = beta;
ht[hi].flag = side|HASH_BETA;
#endif
return beta;
}
alpha = v;
}
}
}
// if no legal moves then checkmate or stalemate
if (!legal_move)
{
if (in_check)
return -MAX_VALUE + ply;
else
return 0;
}
#if HASH_TABLE_ENABLE
ht[hi].key = hk;
ht[hi].origin = best_move.origin;
ht[hi].target = best_move.target;
ht[hi].depth = depth;
ht[hi].flag = side;
if (alpha==old_alpha)
{
ht[hi].flag |= HASH_ALPHA;
ht[hi].score = alpha;
}
else
{
ht[hi].flag |= HASH_EXACT;
ht[hi].score = best_score;
}
#endif
return alpha;
}
Staring at the code is usually not an efficient way for solving problems like this, if it solves anything at all. Better is to equip your program with the infra-structure necessary to resolve problems like this. What I always do is have the engine keep track of the path to the current node, and put diagnostic print statements that are only executed if that path satisfied a certain condition (usually that its first N moves must be equal to something). That way I can control in which nodes it prints.
It is then very useful to print move, score and best score so far (and possibly alpha and beta) after the recursive call; from this it is usually obvious which move has a wrong score, and by adding that to the path where you print you then get the same thing in the daughter, etc., until you zoomed in on the node where the error is generated.
If the erroneous score comes from a hash hit you let it print the hash key. You can put a print statement at the hash store that prints the path to the node when a store occured (plus what was stored); by following up that path you can then continue to search for the origin of the wrong score. (And check whether the position that stored the hash entry was indeed the same as the one that retrieved it.)
ianm wrote: ↑Sat Jun 27, 2020 8:13 ama fairly portable engine than can be ported to different microcontrollers.
Cool - my CT800 is running on a Cortex-M4!
So occasionally it's making some pretty dumb moves. I suspect this is an issue with my hash table implementation.
Try to disable the hash and see whether the problem goes away.
Another common bug in mid-range engines is wrong stalemate or even mate detection: if the position is so good or so bad that ALL moves are pruned away, the loop over the available moves is wrongly evaluated to "no legal move", i.e. mate or stalemate. The symptom is that the engine does something totally stupid and even thinks the eval is OK. The eval then drops once the position is on the board.
Another common bug in mid-range engines is wrong stalemate or even mate detection: if the position is so good or so bad that ALL moves are pruned away, the loop over the available moves is wrongly evaluated to "no legal move", i.e. mate or stalemate. The symptom is that the engine does something totally stupid and even thinks the eval is OK. The eval then drops once the position is on the board.
indeed. I got fed up with that. issues like this arise anytime you experience with pruning mechanism. it's so easy to break things in subtle ways that mating bugs will occur rarely in peculiar conditions (not caught by testing which focuses on game results and large number statistics).
I coded a radical solution to this problem in Demolito:
// Return worst possible score when all moves are pruned
if (bestScore <= -MATE) {
assert(bestScore == -MATE);
return max(alpha, mated_in(ply + 1));
}
I also put assert in score to/from hash score conversion (ply adjust) to verify that I never store or retrieve an impossible mate score (give current ply).
Double seatbelt!
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
This apparently supposes that you detect true stalemates somewhere earlier.
I just had a problem like this in the tiny AI of the Interactive Diagram. After I added a stalemate detection, which corrects bestScore to 0 when it was left at -MATE, and an additional null move searched for the purpose scores better than that, it saw many false stalemates. It turned out I had inadvertantly pruned away the stand-pat when eval <= alpha, i.e. this didn't update bestScore to eval (or alpha).
I now made sure that every move that is pruned is treated like it has score alpha. And I still had to be careful that other losing conditions that it is not illegal to expose yourself to (such as King baring or allowingthe opponent King to reach a goal square), and thus are no reason for claiming stalemate, do not return -MATE but -MATE+1. And then correct all bestScore <= -MATE+1 for the ply level, after correctimg only bestScore == -MATE for stalemate.
OK, I might have found the issue (or maybe a new one). I wasn't explicitly storing the mate score. I can't verify this is a fix for the actual position since the issue isn't reproducible. Anyway, here is the code:
const int16_t absearch(int16_t alpha, int16_t beta, uint8_t depth, const uint8_t null_move)
{
// if depth reached then return the score from quiesce
if (!depth) return quiesce(alpha,beta);
eo.nodes++;
// check if search time up
if ((eo.nodes&8191)==0 && millis()>eo.stop_time) eo.stop_search = true;
pvl[ply] = ply;
// if this isn't the root of the search tree (where we have
// to pick a move and can't simply return 0) then check to
// see if the position is a repeat if so, we can assume that
// this line is a draw and return 0
if (ply && reps()) return 0;
// don't search too deep
if (ply>=MAX_PLY-1) return eval();
// if in check then keep searching
const uint8_t in_check = king_attack(side);
if (in_check)
{
depth++;
eo.stop_search = false;
}
ASSERT(hk==get_hash());
// false checkmate score
//fen k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31
//fen 8/2r4k/p5p1/PP6/b2R1PPP/7r/3K4/6R1 b - - 0 46
//fen rnb4N/p1p4Q/2k1p2p/1p1n4/1b4q1/8/PP3PPP/1RK4R b - - 5 23 ***
#if HASH_TABLE_ENABLE
const uint32_t hi = hk%MAX_HASH_TABLE;
if (ply)
{
if (ht[hi].key==hk && ht[hi].depth>=depth && (ht[hi].flag&FL_SIDE)==side)
{
int16_t s = ht[hi].score;
if (s>MATE_VALUE) s -= ply; else if (s<-MATE_VALUE) s += ply;
if (ht[hi].flag&HASH_EXACT) {stats.nhash++; return s;}
else if ((ht[hi].flag&HASH_BETA) && s>=beta) {stats.nhash++; return beta;}
else if ((ht[hi].flag&HASH_ALPHA) && s<=alpha) {stats.nhash++; return alpha;}
}
}
#endif
#if NULLMOVE_ENABLE
if (null_move && !in_check && ply && depth>3)
{
int16_t nullmat = 0;
uint8_t p = EMPTY;
for (uint8_t i=0;i<64;i++)
{
if ((p=b[i]&0xf)==EMPTY) continue;
if ((p&0x07)==PAWN) continue;
if ((p&FL_SIDE)!=side) continue;
nullmat += (white_scores[p]+black_scores[p]);
}
if (nullmat>1400)
{
donullmove();
int16_t v = -absearch(-beta, -beta+1, depth - 1 - 2, false);
undonullmove();
if (eo.stop_search) return 0;
if (v>=beta && abs(v)<MATE_VALUE)
{
return beta;
}
}
}
#endif
// loop through the moves
gen_all_moves(side);
#if HASH_TABLE_ENABLE
// if there is a good move in the hash table
// order it highly (but below the PV)
if (ht[hi].key==hk)
{
const uint8_t origin = ht[hi].origin;
const uint8_t target = ht[hi].target;
if (origin|target)
{
for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
{
// don't replace the PV!
if (ml[i].order==65535u) continue;
if (origin==ml[i].m.origin && target==ml[i].m.target)
{
ml[i].order = 65000u;
stats.hashorder++;
break;
}
}
}
}
#endif
int16_t old_alpha = alpha;
int16_t best_score = -MAX_VALUE;
move_t best_move = {0};
uint8_t legal_move = 0;
uint8_t move_ordering = true;
for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
{
if (move_ordering) order_next_move(i);
move_ordering = ml[i].order>0;
if (!domove(ml[i].m)) continue;
legal_move++;
#if LMR_ENABLE
int16_t v = 0;
if (depth<4 || legal_move==1 || in_check || ml[i].order>60000u)
{
v = -absearch(-beta, -alpha, depth-1, true);
}
else
{
const uint8_t reduce = ml[i].order==0?2:1;
v = -absearch(-beta, -alpha, depth-1-reduce, false);
if (v>alpha)
{
v = -absearch(-beta, -alpha, depth-1, true);
}
}
#else
int16_t v = -absearch(-beta, -alpha, depth-1, true);
#endif
undomove();
if (eo.stop_search) return 0;
if (v>best_score)
{
// update the PV
ASSERT(ply+1<MAX_PLY);
pv[ply][ply].m = ml[i].m;
for (uint8_t j=ply+1;j<pvl[ply+1];j++) pv[ply][j] = pv[ply+1][j];
pvl[ply] = pvl[ply+1];
best_score = v;
best_move = ml[i].m;
if (v>alpha)
{
// since there was a cutoff increase the history or
// "curiosity" heuristic (this is a low memory version
// of the history heuristic which does a better job
// than nothing but not as good as full history - the
// difference in memory usage is significant!)
#if CURIOSITY_HEURISTIC
if (depth>2 && ml[i].m.capture==EMPTY)
curiosity[ml[i].m.target] += depth;
#elif HISTORY_HEURISTIC
if (depth>2 && ml[i].m.capture==EMPTY)
{
const uint16_t h = history[ml[i].m.origin][ml[i].m.target]+depth;
history[ml[i].m.origin][ml[i].m.target] = min(h,60000u);
}
#endif
if (v>=beta)
{
// record killers
if (ml[i].m.capture==EMPTY)
{
killers[2][ply] = killers[1][ply];
killers[1][ply] = killers[0][ply];
killers[0][ply] = ml[i].m;
}
#if HASH_TABLE_ENABLE
// store hash table entry
ht[hi].key = hk;
ht[hi].origin = best_move.origin;
ht[hi].target = best_move.target;
ht[hi].depth = depth;
ht[hi].score = beta;
ht[hi].flag = side|HASH_BETA;
#endif
return beta;
}
alpha = v;
}
}
}
#if HASH_TABLE_ENABLE
ht[hi].key = hk;
ht[hi].origin = best_move.origin;
ht[hi].target = best_move.target;
ht[hi].depth = depth;
ht[hi].flag = side|HASH_EXACT;
ht[hi].score = 0;
// if no legal moves then checkmate or stalemate
if (!legal_move)
{
if (in_check)
return (ht[hi].score = -MAX_VALUE + ply);
else
return 0;
}
if (alpha==old_alpha)
{
ht[hi].flag = side|HASH_ALPHA;
ht[hi].score = alpha;
}
else
{
ht[hi].score = best_score;
}
#else
if (!legal_move)
{
if (in_check)
return -MAX_VALUE + ply;
else
return 0;
}
#endif
return alpha;
}
The difference is, if there is a checkmate then the score is stored against the current position (wasn't before). Also, since there is no "best move" in this case I've added a check in the hash move ordering to ignore null moves (well it will anyway).
I have another problem with LMR and null moves now. I'll post about that soon!
I’m having an issue when both LMR and null moves are enabled. And not a problem when enabled independently. This is the test position:
[d]k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31
The best move should be b6c6. With null moves and LMR enabled, here’s what happens:
Ian's Low Memory Chess Program (plankton)
Version 8.7.0, 29/06/2020
Copyright 2020 Ian Mitchell
With late move reductions!
With history heuristic!
With evaluation cache!
With null moves!
With hash table!
"help" displays a list of commands.
plankton> fen k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31
A B C D E F G H
8 k . . r . . . . 8
7 . . . . .*p*p*p 7
6 . Q . . . n . . 6
5 . . . . . q . . 5
4 . . . r . . . . 4
3 . . . . . . P . 3
2*P . . . B*P .*P 2
1 . . . . . . K R 1
A B C D E F G H
lucasart wrote: ↑Mon Jun 29, 2020 6:44 amI coded a radical solution to this problem in Demolito:
I fixed that issue by having a "legal move was pruned" flag, initialised to false. After the node move loop, I both check whether the legal main move counter (pseudo legal move generator used) is still at 0 AND the flag is false. Only in that case, I return -MATE or 0 depending on whether it's in-check or not. If the main move counter is 0 but not the flag, no move has improved alpha, so I just return alpha, which results in a fail-low, which is a fail-high one level above, and that isn't harmful.
If pruning is disabled when being in check and returning a mate score is restricted to being in check as well then I do not see how this could ever go wrong.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
But setting a flag might be a lot cheaper than searching moves that deserve to be pruned (e.g. because of futility).
I don't think that false mate scores are really a problem here, as long as you only prune moves that would fail low. It doesn't matter much whether you fail low because of a mate score or poor evaluation. In a soft-fail scheme, at least. Of course with hard fail it is another matter; when you prune because you are confident the move will score below alpha, you must make sure that bestScore is increased to a reasonable estimate of what the move would give you. Or you might later retreave a completely unrealistic upper bound from the TT, which makes the node fail low compared to a now much lower alpha, while in fact the pruned move would have made it fail high in that case. E.g. when you futility prune because currentEval + victimValue < alpha - MARGIN you should set bestScore = currentEval + victimValue + MARGIN. This isn't really related to mate scores; if you don't do this things could go vary wrong in other situations as well.
The big problem is false stalemates. Which could make the node fail high when in fact it was arbitrarily poor (and not stalemate).
An additional problem in my tiny AI is that it really has no idea whether it is in check, and that figuring that out through a null move is rather expensive.
