Thread: Alpha beta pruning in chess

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.

Thank you for your reply.

Yes that is the reason, but normally, if I wrote the algorithm right, It shouldn't be -1.

I found an implementation in c from the game tic tac toe, using alpha beta pruning.
SC_TTT.ZIP - \SC_TTT.C - Tic-Tac-Toe program (C source)

This is his alpha beta algorithm:

Code:

int Best_Move(Board_Type Board, Square_Type Player, int *Square, int Move_Nbr,
              int Alpha, int Beta) {
    int Best_Square = -1;
    int Moves = 0;
    int I;
    Move_Heuristic_Type Move_Heuristic[Squares];

    Total_Nodes++;

    /* Find the heuristic for each move and sort moves in descending order */
    for (I = 0; I < Squares; I++) {
        if (Board[I] == Empty) {
            int Heuristic;
            int J;
            Play(Board, I, Player);
            Heuristic = Evaluate(Board, Player);
            Play(Board, I, Empty);
            for (J = Moves-1; J >= 0 &&
                              Move_Heuristic[J].Heuristic < Heuristic; J--) {
                Move_Heuristic[J + 1].Heuristic = Move_Heuristic[J].Heuristic;
                Move_Heuristic[J + 1].Square = Move_Heuristic[J].Square;
            }
            Move_Heuristic[J + 1].Heuristic = Heuristic;
            Move_Heuristic[J + 1].Square = I;
            Moves++;
        }
    }

    for (I = 0; I < Moves; I++) {
        int Score;
        int Sq = Move_Heuristic[I].Square;
        Square_Type W;

        /* Make a move and get its score */
        Play(Board, Sq, Player);

        W = Winner(Board);
        if (W == 'X')
            Score = (Maximum_Moves + 1) - Move_Nbr;
        else if (W == 'O')
            Score = Move_Nbr - (Maximum_Moves + 1);
        else if (W == 'C')
            Score = 0;
        else
            Score = Best_Move(Board, Other(Player), Square, Move_Nbr + 1,
                              Alpha, Beta);

        Play(Board, Sq, Empty);

        /* Perform alpha-beta pruning */
        if (Player == 'X') {
            if (Score >= Beta) {
                *Square = Sq;
                return Score;
            } else if (Score > Alpha) {
                Alpha = Score;
                Best_Square = Sq;
            }
        } else {
            if (Score <= Alpha) {
                *Square = Sq;
                return Score;
            } else if (Score < Beta) {
                Beta = Score;
                Best_Square = Sq;
            }
        }
    }
    *Square = Best_Square;
    if (Player == 'X')
        return Alpha;
    else
        return Beta;
}

I tried it and this works. So I don't think I need to add an "else" statement.

Hoping on some more input.
Maybe someone that can verify if my implementation of the alpha beta algorithm is correct.

Thank you

I haven't looked through your code but this:
"""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."""
seems to describe a greedy algorithm, which MINIMAX with alpha-beta pruning is not.

Also, how do you decide that the algorithm does not find the "best" move? It doesn't find the best move based on your knowledge of chess or it doesn't find the optimal move based on your scoring function?

1. I know my algorithm isn't behaving as it should have. But I just can't figure out what is wrong with it. Therefor that I made this post. I based my algorithm at the algorithm I found (link above) in the tic tac toe game. It seems to work in that case.
And when searching the net for alpha beta pruning I find similar algorithms.


2. It doesn't find the optimal move based on my evaluation function.
The algorithm processes this node, but because the alpha and beta values are wrong the move gets thrown away.

What you are saying is true, but in my evaluation function I make a difference on what place the kings are standing. Therefor one move is better than another one. So the kings should be fighting for the same place.

But you are right, that problem is solved with a simple test if the values are still -1. What doesn't change my algorithm, so therefor its ok.

However when I place my 2 kings in the middle of the board and let my algorithm search 5 ply's deep. It needs around 3000 - 4000 moves to find the best move. Is this realistic? Shouldn't it be much lower for alpha beta pruning?

Brute force should be around: 8^5 = 32 768 moves. (every king can move to 8 places).

Alpha-beta efficiency depends on move ordering. In the worst case ordering, it's exactly the same as regular minimax.