Search function for chess engines

Question

I'm creating a bitboard based chess engine in c++ and I'm trying to write the search function. It currently looks something like this

double search(Position& pos, int depth, double alpha, double beta) {
    Move_list move_list = Move_list(pos);
    double evaluation;

    if (move_list.size() == 0) {
        if (check(pos)) {
            return -1024;
        }
        return 0;
    }
    if (depth == 0) {
        return eval(pos, true);
    }
    for (auto& m : move_list) {
        do_move(pos, m);
        evaluation = -search(pos, depth - 1, -beta, -alpha);
        undo_move(pos, m);
        if (evaluation >= beta) {
            return beta;
        }
        if (evaluation > alpha) {
            alpha = evaluation;
        }
    }
    return alpha;
}

Now I have a couple of problems. Say I do a search on the position "k7/8/8/8/8/8/7R/1R5K - w -". We obviously have a mate in one with h2a2. The search function however "sees" that there is no way for the black king to escape, so it just shuffles pieces around because it knows it can deliver mate whenever it wants to. One solution to this problem would be to prioritize checks if two moves have the same evaluation, but it is kind of an ugly solution and I'm sure there are other positions where the same problem occurs but the first move is not a check (say a mate in 2 of some sort).

Another solution would be to first do a search of depth 1. Order the moves so that the highest evaluated move comes first and then do a search of whichever depth we want. This would mean it always makes the move with the best evaluation, but if there are 2 moves with the same evaluation it prioritizes the move which gives the best evaluation on the next move.

Maybe this would be even more effective with alpha beta pruning if I do a search of depth 1, then 2 all the way up to the depth we want. This seems counterintuitive, but would it be faster because of the reordering of the moves at each depth?

If this is the way to do it, how would I even go about writing such a search function. Would it then also take as an argument a reference Move_list to reorder it? If any of you have code of your own to solve this problem I would love to see it!

Answer 1

One possible approach is to decrement the evaluation for a mate score. For instance:

evaluation = -search(pos, depth - 1, -beta, -alpha);
if (evaluation > 900) {
    evaluation--;
} else if (evaluation < -900) { // you could also drop this case
    evaluation++;
} [...]

This way your program can tell apart a mate in 1 from a mate in 3. It will choose the fastest mate and you can even calculate the distance to mate from the evaluation given.

Worth noting eventually you might still want to reorder the to be searched moves in the original position since alpha-beta search becomes more effective if you search the best move first. One option might indeed be to pass those so called root moves as a parameter though there are other solutions of course. (usually you would have a different function for that too, so for instance root_search which then calls the normal search) However, that is a problem for another day.