Hello,

I am trying to create a simple chess game. But there seems to be an error in my alpha beta pruning algorithm.

At this moment I have written the algorithm only for player 2 (the black pieces).

What it is the problem:

If I call my functions to search the tree for 2 ply's, everything seems to work.
(However my alpha beta pruning algorithm needs 89 moves to determine the best move for the black player, with only the white and black king on the board.

If I search the tree for 3 ply's with only a white and a black king on the board it needs 131 moves to determine the "best" move. Also the "best" move given by the algorithm isn't my best move in the case of 3 ply searches or more

My coordinates on the board of the white king are: H1
My coordinates on the board of the black king are: H8

So when I place my kings in the middle of the board the number of moves is around 400.

But as I said the given best move, isn't the "best".
If I call the function, with the kings on the coordinates given above, the algorithm will say the best move is G8 for the black king.
(I checked the evaluation function and the right answer should be G7).

I debugged it and what happens is:

He finds the best move for the first leave, which is indeed G8.
And the algorithm keeps this move as his best through the entire algorithm.
Also as I stated in the code the temporary best move isn't always filled in.

Code:
int AlphaBeta::findMove(int alpha, int beta, PLAYER player, int *bestMove, int *bestValue, int depth, int *nMoves){

    int value = 0;
    int bestMT = -1, bestVT = -1;  // Temporary best move

    for(int i=0; i < numPossibleMoves; i++){

        // Do move
        board->move(possibleMoves[i]);
        *nMoves += 1;

        if(checkmate(HUMAN)){
            value = -eval(WHITEPIECES);
        }else if(checkmate(AI)){
            value = eval(BLACKPIECES);
        }else if(depth == 0){
            if(player == HUMAN)
                value = -eval(WHITEPIECES);
            else
                value = eval(BLACKPIECES);
        }else{
                value = findMove(alpha, beta, other(player), bestMove, bestValue, depth-1, nMoves);
        }

        // Undo move
        board->move(possibleMoves[i]);

        if(player == AI){

            if(value >= beta){
                *bestMove = i;
                *bestValue = value;
                return value;
            }else if(value > alpha){
                alpha = value;
                bestMT = i;
                bestVT = value;
            }

        }else if(player == HUMAN){

            if(value <= alpha){
                *bestMove = i;
                *bestValue = value;
                return value;
            }else if(value < beta){
                beta = value;
                bestMT = i;
                bestVT = value;
            }
        }
    }
// these are sometimes still -1. Normally this isn't possible?
    *bestMove = bestMT;
    *bestValue = bestVT;

    if(player == AI)
        return alpha;
    else
        return beta;
}
I know this is a long text, to read and a hard problem to help me solve over the internet. But I am really stuck at this problem. So I would really appreciate your help.

Just ask if you need more information, or if I didn't explain my problem well enough. (English isn't my native language, so sorry for grammar mistakes.)


Hoping to see a reaction on this post.

Thank you for reading.