Move Ordering

Alpha-beta pruning is only as good as the move ordering. The best case is searching the best move first every time. In the worst case - we always search the worst moves first - pruning thereby does nothing here. Move ordering is therefore one of the highest-leverage things you can do to improve search performance.

The scoring heuristic prioritises moves in this order: promotion-captures, captures ordered by MVV-LVA, quiet promotions, and everything else scored zero. MVV-LVA (Most Valuable Victim, Least Valuable Attacker) is the key idea: prefer capturing a queen with a pawn over capturing a pawn with a queen, because the queen capture is more likely to be good.

static int scoreMove(const Move& m, const Board& board){
    if (m.flags == EN_PASSANT)
        return 10*Eval::PIECE_VALUES[PAWN] - Eval::PIECE_VALUES[PAWN];

    if (m.flags == CAPTURE || m.flags == PROMOTION_CAPTURE){
        Piece victim = NO_PIECE;
        uint64_t to = 1ULL << m.to;
        Color defender = opposite(board.turn);
        for(int p = PAWN; p <= KING; p++)
            if (board.pieces[defender][p] & to){ victim = (Piece)p; break; }

        if (victim != NO_PIECE && m.flags == CAPTURE)
            return 10*Eval::PIECE_VALUES[victim] - Eval::PIECE_VALUES[m.piece];
        if (victim != NO_PIECE && m.flags == PROMOTION_CAPTURE)
            return 10000 + 10*Eval::PIECE_VALUES[victim]
                         - Eval::PIECE_VALUES[m.piece];
    }
    if (m.flags == PROMOTION)
        return 8000 + Eval::PIECE_VALUES[m.promotionPiece];
    return 0;
}

The formula 10 * victim_value - attacker_value ensures that among all captures of a given victim, we prefer the cheapest attacker. Multiplying the victim by 10 means a pawn capturing a queen ranks far above a queen capturing a pawn, for example. The numbers work out so any capture of a more valuable piece by a less valuable piece scores positively.

Moves are sorted with std::sort before the main loop in negamax for efficient and quick pruning.