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:
Code: Select all
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;
}
