Alpha-beta stuck after certain moves

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Alpha-beta stuck after certain moves

Postby kepuli » 03 Mar 2016, 10:55

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
 
Posts: 3
Joined: 03 Mar 2016, 00:07

Re: Alpha-beta stuck after certain moves

Postby kepuli » 03 Mar 2016, 16:18

Quick update: The algorithm seems to have stopped evaluating positions after a while, but not finished. AFTER 6 HOURS.
kepuli
 
Posts: 3
Joined: 03 Mar 2016, 00:07

Re: Alpha-beta stuck after certain moves

Postby Robert Pope » 03 Mar 2016, 21:28

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?
Robert Pope
 
Posts: 39
Joined: 08 Apr 2006, 17:27

Re: Alpha-beta stuck after certain moves

Postby kepuli » 06 Mar 2016, 04:16

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!
kepuli
 
Posts: 3
Joined: 03 Mar 2016, 00:07

Re: Alpha-beta stuck after certain moves

Postby Robert Pope » 10 Mar 2016, 15:58

kepuli wrote: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.
Robert Pope
 
Posts: 39
Joined: 08 Apr 2006, 17:27


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Yahoo [Bot] and 4 guests

cron