How to make a chess negamax algorithm prefer captures and other good moves found shallower in the decision tree?

  alpha-beta-pruning, c++, chess, negamax

Suppose we have the following position (FEN 8/1K6/8/4q2P/8/8/5k2/8 b - - 3 2):
FEN 8/1K6/8/4q2P/8/8/5k2/8 b - - 3 2

My chess engine produces the correct move of Qxh5 when the search depth is below 3. After that, it seems the problem is that it thinks the capture can be made later (considers Qh2 as the best move). I cannot see any obvious ways to prefer the branches where the capture is made earlier in the evaluation algorithm, since that would break the evaluation symmetry needed for negamax (and minimax) to work.

Just for reference, here is my actual negamax code (copied from wikipedia):

int Search::negamaxSearch (Board& positionToSearch, int depth, int alpha, int beta) {
    std::vector<Move> moves = positionToSearch.getMoves();

    if (moves.empty()) {
        if (positionToSearch.isCheck()) {
            return EvaluationConstants::LOSE;
        } else {
            return EvaluationConstants::DRAW;
        }
    }

    if (depth == 0) {
        return BoardEvaluator::evaluateSimple(positionToSearch);
    }

    orderMoves(positionToSearch, moves, depth);

    int positionValue = -1e9;
    for (auto move : moves) {
        positionToSearch.executeMove(move);
        int newValue = -negamaxSearch(positionToSearch, depth - 1, -beta, -alpha);
        positionToSearch.unmakeMove();

        positionValue = std::max(positionValue, newValue);
        alpha = std::max(alpha, newValue);

        if (alpha >= beta) {
            ++cutoffs;
            break;
        }
    }

    return positionValue;
}

And the evaluation function:

int BoardEvaluator::evaluateSimpleOneSide (const Board& board, PieceColor perspective) {
    if (board.isCheckmate()) return EvaluationConstants::LOSE;

    int value = 0;
    for (int pieceType = 0; pieceType < PieceTypes::KING; ++pieceType) {
        value += board.getPieces(perspective).boards[pieceType].popCount() * pieceValues[pieceType];
    }

    return value;
}

int BoardEvaluator::evaluateSimple (const Board& board) {
    return evaluateSimpleOneSide(board, board.getTurn()) - evaluateSimpleOneSide(board, flip(board.getTurn()));
}

Is there something obvious wrong that I haven’t noticed?

Source: Windows Questions C++

LEAVE A COMMENT