Alpha beta pruning in chess

This is a discussion on Alpha beta pruning in chess within the Game Programming forums, part of the General Programming Boards category; Hello, I am trying to create a simple chess game. But there seems to be an error in my alpha ...

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    4

    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.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Edit - You have a case where you have a possible else that doesn't get handled.
    Code:
            if(player == AI){
                if(value >= beta){
                    *bestMove = i;
                    *bestValue = value;
                    return value;
                }else if(value > alpha){
                    alpha = value;
                    bestMT = i;
                    bestVT = value;
                }
                /* else what? */
    Is this why sometimes you get -1 when you think you shouldn't?


    Quzah.
    Last edited by quzah; 05-03-2011 at 06:09 PM.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    May 2011
    Posts
    4
    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

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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?

  5. #5
    Registered User
    Join Date
    May 2011
    Posts
    4
    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.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by fiber View Post
    Thank you for your reply.

    Yes that is the reason, but normally, if I wrote the algorithm right, It shouldn't be -1.
    Why? You have cases that don't have a final "else", which means that you end up with -1.
    Quote Originally Posted by fiber
    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.
    Stick two kings in the middle of an empty board. What's the best move? NONE! It doesn't matter where you move, because you can't win. Say we got up one for our first check. Why is that worse than going down, or left or right? You don't gain anything on any move. So...
    Code:
                if (Score >= Beta) {
                    *Square = Sq;
                    return Score;
                } else if (Score > Alpha) {
                    Alpha = Score;
                    Best_Square = Sq;
                }
    It's not better than Beta or better than Alpha. It's the same crappy move, so you end up with -1. Or at least that's how I see it.


    Quzah.
    Last edited by quzah; 05-05-2011 at 05:56 PM.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    May 2011
    Posts
    4
    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).

  8. #8
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    Alpha-beta efficiency depends on move ordering. In the worst case ordering, it's exactly the same as regular minimax.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alpha beta pruning on Iterative deepening
    By thescratchy in forum C Programming
    Replies: 3
    Last Post: 02-04-2011, 12:15 AM
  2. Replies: 24
    Last Post: 08-05-2010, 05:30 PM
  3. Windows 7 RC, Visual Studio 2010 Beta, Office 2010 beta, anyone in?
    By indigo0086 in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 05-20-2009, 01:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21