Does anyone see major problems with such an implementation, or any possible improvements (while keeping it on the given level, i.e. without killer, hash table, null move etc.)?
At least I hope this should be sufficient for finding mates correctly and quickly.
Code: Select all
int Searcher::search(Game & g, int alpha, int beta, int maxDepth, PV & pv)
{
// a very basic fail-soft alpha-beta search function that could serve as a
// starting point but still ignores important concepts like killer moves,
// hash table, null move, LMR, time control, ...
ASSERT(maxDepth > 0);
// ASSERT("never called for an illegal position");
if (g.detectDraw()) return 0;
g.generateMoves();
int bestV = -MAX_VALUE;
for (Move * m = g.nextMove(); m != 0 && bestV < beta; m = g.nextMove()) {
g.makeMove(m);
if (!g.lastMoveWasIllegal(m)) {
PV pvSub;
int v =
(maxDepth > 1) ?
-search (g, -beta, -Max(alpha, bestV), maxDepth - 1, pvSub) :
g.lastMoveWasCheck(m) ?
-search (g, -beta, -Max(alpha, bestV), maxDepth, pvSub) :
-qSearch(g, -beta, -Max(alpha, bestV));
if (v > bestV) {
bestV = v;
pv.update(*m, pvSub);
if (g.height() == 1) displayPV(bestV, pv);
}
}
g.unmakeMove(m);
}
if (bestV == -MAX_VALUE) {
// no legal move found
return g.isInCheckFlagSet() ? MATE_VALUE(g.height()) : 0;
} else {
return bestV;
}
}
int Searcher::qSearch(Game & g, int alpha, int beta)
{
int bestV = g.evaluate();
if (bestV >= beta) return bestV;
g.generateMovesQS();
for (Move * m = g.nextMove(); m != 0 && bestV < beta; m = g.nextMove()) {
g.makeMove(m);
if (!g.lastMoveWasIllegal(m)) {
int v = -qSearch(g, -beta, -Max(alpha, bestV));
if (v > bestV) {
bestV = v;
}
}
g.unmakeMove(m);
}
return bestV;
}