Alpha-beta stuck after certain moves

[kepuli]

I'm in the process of writing a chess program. So far, I've implemented correct move-generation and an alpha-beta pruning algorithm. The problem is, after certain moves the alpha-beta algorithm seems to take forever.

For example, the moves

e2e4 a7a5
Qd1h5 a5a4
Bf1c4

lead to a point where the alpha-beta call on depth 6 takes forever although the previous moves and some other moves only take a tiny bit of time. My program does perft(6) in half a minute, so is it realistic that the following moves cause the alpha-beta algorithm to take forever? I waited for half an hour and it hadn't finished. Do no beta-cutoffs occur in that certain move list until the very end with plain alpha-beta pruning (no iterative deepening or any move ordering), or why is it so slow?

My alpha-beta is organized as follows:

Code: Select all

int alphabeta(int alpha, int beta, int depth, Position& position) {
    if (depth == 0) return evaluate(position);
       
    MoveList moves;
    AddLegalMoves(moves);
    if (moves.Length == 0) {
        if (position.Checkmate()) return -INFINITY;
        return 0;
    }

    for (Move move : moves) {
        Position new_position = position;
        new_position.MakeMove(move);

        int score = alphabeta(-beta, -alpha, depth - 1, new_position);
        if (score >= beta) return beta;
        if (score > alpha) alpha = score;
    }

    return alpha;
}


[kepuli]

Quick update: The algorithm seems to have stopped evaluating positions after a while, but not finished. AFTER 6 HOURS.

[Robert Pope]

No way your alpha-beta search should take longer than a perft.
For reference, my fairly simple program does perft(6) in 13 seconds, and a 6ply alphabeta search (with evaluation and extensions) in 0.4 seconds.

How many nodes is each depth searching, compared to perft?

[kepuli]

Sorry for taking so long to answer. I found out the problem and it was not related to alphabeta. Apparently I had forgotten to check the correctness of castling move generation (since a perft(6) doesn't cover any castling moves), and there was a slight bug in the castling generation. Thanks for your input, though!

[Robert Pope]

Sorry for taking so long to answer. I found out the problem and it was not related to alphabeta. Apparently I had forgotten to check the correctness of castling move generation (since a perft(6) doesn't cover any castling moves), and there was a slight bug in the castling generation. Thanks for your input, though!

So far, I've implemented correct move-generation...

Seriously, you need to find a suite of perft positions to test. There are all sorts of edge cases that have to be stress-tested, like en passant captures that give (or remove) check, underpromotions, double checks, castling after a rook moves out of and back to H1, etc. And everything from both colors' perspective.