I am using negamax alpha-beta with principal variation search. There are no pruning methods, reductions or extensions implemented yet since I want to untangle this mess first.
My alpha-beta function looks like this:
Code: Select all
int alphabeta(SearchThread_t* ss, int depth, int alpha, int beta, SearchPv* pvLine) {
SIDE Us = ss->pos->side_to_move;
ss->info->nodes++;
SearchPv line;
pvLine->length = 0;
if (depth == 0) {
return quiescence(ss, alpha, beta);
}
// Return zero for a drawn position
if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
return 0;
}
if (ss->pos->ply > MAXDEPTH - 1) {
return Eval::evaluate(ss->pos);
}
int score = -INF;
int best_move = NOMOVE;
bool raised_alpha = false;
// When doing principal variation search, we are in a PV node if beta - alpha != 1 since we're then not in a null window
bool is_pv = (beta - alpha != 1) ? true : false;
/*
TRANSPOSITION TABLE PROBING:
- We'll check to see if the position has been reached before and saved in the transposition table.
*/
bool ttHit = false;
TT_Entry* ttEntry = tt->probe_tt(ss->pos->posKey, ttHit);
int ttScore = (ttHit) ? ttEntry->data.score : -INF;
int ttMove = (ttHit) ? ttEntry->data.move : NOMOVE;
int ttDepth = (ttHit) ? ttEntry->data.depth : 0;
int ttFlag = (ttHit) ? ttEntry->data.flag : NO_FLAG;
if (ttScore >= MATE) { ttScore -= ss->pos->ply; }
else if (ttScore <= -MATE) { ttScore += ss->pos->ply; }
// If ttHit is true, the pointer is a valid entry for the position. We just need to check if the depth is satisfactory.
if (ttHit && ttDepth >= depth && !is_pv) {
switch (ttFlag) {
case ALPHA:
if (ttScore <= alpha) {
return alpha;
}
break;
case BETA:
if (ttScore >= beta) {
return beta;
}
break;
case EXACT:
return score;
}
}
// Check if we need to stop, and drop out if we do.
if ((ss->info->nodes & 2047) == 0) {
CheckUp(ss);
}
if (ss->info->stopped) {
return 0;
}
// Generate all moves for the position
MoveList* moves = ss->generate_moves();
int legal = 0;
// If our transposition table probing returned a move, this will be scored the highest.
if (ttHit && ttMove != NOMOVE) {
for (int m = 0; m < moves->size(); m++) {
if ((*moves)[m]->move == ttMove) {
(*moves)[m]->score = 100000000;
break;
}
}
}
int move = NOMOVE;
// Now we begin searching the moves.
for (int m = 0; m < moves->size(); m++) {
ss->pickNextMove(m, moves);
move = (*moves)[m]->move;
// piece captured will be used for killer moves and history heuristic
int piece_captured = ss->pos->piece_list[(Us == WHITE) ? BLACK : WHITE][TOSQ(move)];
// The new_depth will be where we add the extensions and reductions
int new_depth = depth - 1;
if (!ss->pos->make_move((*moves)[m])) {
continue;
}
legal++;
/*
PRINCIPAL VARIATION SEARCH
*/
if (!raised_alpha) {
score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
}
else {
score = -alphabeta(ss, new_depth, -alpha - 1, -alpha, &line);
// If we somehow still raise alpha with a move we thought was bad, we need to re-search it.
// But if it also beats beta (score > beta) we dont need to do anything
if (score > alpha) {
score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
}
}
ss->pos->undo_move();
if (ss->info->stopped) { return 0; }
if (score > alpha) {
raised_alpha = true;
best_move = move;
if (score >= beta) {
if (legal == 1) {
ss->info->fhf++;
}
ss->info->fh++;
// Since we've beaten beta, we'll check if it is a quiet move. If it is, we'll add it to the killer and history heurstic
if (piece_captured == NO_TYPE && SPECIAL(move) != PROMOTION) {
ss->setKillers(ss->pos->ply, (*moves)[m]->move);
ss->history[FROMSQ(move)][TOSQ(move)] += depth * depth;
}
tt->store_entry(ss->pos, best_move, score, depth, BETA);
return beta;
}
ChangePV(best_move, pvLine, &line);
alpha = score;
}
}
delete moves;
// If we had zero legal moves, we're either in checkmate or stalemate.
if (legal == 0) {
if (ss->pos->in_check()) {
return -INF + ss->pos->ply;
}
else {
return 0;
}
}
// If we raised alpha, we're in a PV-node, otherwise we're in an all node
if (raised_alpha) {
tt->store_entry(ss->pos, best_move, alpha, depth, EXACT);
}
else {
tt->store_entry(ss->pos, best_move, alpha, depth, ALPHA);
}
return alpha;
} // alphabeta
Code: Select all
// At the moment quiescence only searches captures and promotions. FIXME: Should this also contain checks and check evasions?
int quiescence(SearchThread_t* ss, int alpha, int beta) {
SIDE Us = ss->pos->side_to_move;
ss->info->nodes++;
// Check if we need to stop, and drop out if we do.
if ((ss->info->nodes & 2047) == 0) {
CheckUp(ss);
}
if (ss->info->stopped) {
return 0;
}
// Return zero for a drawn position, or if we have reached our maximum search depth.
if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
return 0;
}
int stand_pat = Eval::evaluate(ss->pos);
if (ss->pos->ply > MAXDEPTH - 1) {
return stand_pat;
}
// If the static evaluation beats beta, we can do a cutoff
if (stand_pat >= beta) {
return beta;
}
else if (stand_pat > alpha) {
alpha = stand_pat;
}
// Only generate tatical moves in quiescence
MoveList* ml = ss->generate_moves(true);
int legal = 0; // Amount of legal moves. We need to know if they are zero, so we can return a mate score or stalemate score
int score = -INF;
for (int m = 0; m < ml->size(); m++) {
if (!ss->pos->make_move((*ml)[m])) {
continue;
}
legal++;
score = -quiescence(ss, -beta, -alpha);
ss->pos->undo_move();
// Return if we have been told to stop the search.
if (ss->info->stopped) { return 0; }
if (score > alpha) {
alpha = score;
if (score >= beta) {
// If this is the first move, and it beats beta, we failed high on the first move i.e. good move ordering.
if (legal == 1) {
ss->info->fhf++;
}
ss->info->fh++;
return beta;
}
}
}
if (legal == 0) {
if (ss->pos->in_check()) {
return -INF + ss->pos->ply;
}
else {
return 0;
}
}
delete ml;
return alpha;
} // quiescence
Code: Select all
// SearchThread_t is a structure that holds all information local to a thread. This includes static evaluations, move ordering etc..
struct SearchThread_t {
GameState_t* pos = new GameState_t;
SearchInfo_t* info = new SearchInfo_t;
int history[64][64] = { {0} };
int killers[MAXDEPTH][2] = { {0} };
int static_eval[MAXDEPTH] = { 0 };
int thread_id = 0;
void setKillers(int ply, int move);
void pickNextMove(int index, MoveList* ml);
MoveList* generate_moves(bool qsearch = false);
~SearchThread_t() {
delete pos;
delete info;
}
private:
void score_moves(MoveList* ml);
};
[pgn]1. Nc3 Nf6 2. e4 Nxe4 3. Nxe4 Rg8 4. Nf3 h6 5. d4 *[/pgn]
Can anyone see what I am doing wrong?
Any help is very much appreciated!