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.

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.

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.

Quote:

Originally Posted by fiber

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.

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.