I've implemented a Chess game in C, with the following structs:
move - which represents a move from (a,b) to (c,d) on a char board[8][8] (Chess board)
moves - which is a linked list of moves with head and tail.
Variables: playing_color is 'W' or 'B'. minimax_depth is a minimax depth that was set before.
Here is my code of the Minimax function with alpha-beta pruning and the getMoveScore function which should return the score of the move in Minimax Tree of a certain minimax_depth that was set before.
As well I'm using the getBestMoves function which I will also list here, it basicly find the best moves during the Minimax algorithm and saves them into a global variable so that I will be able to use them later.
I must add that all the functions that are listed within the three functions that I will add here are working properly and were tested, so the problem is either a logic problem of the alphabetaMax algorithm or the implementation of getBestMoves/getMoveScore.
The problem mainly is that when I get my best moves at depth N (which are also not computed right somewhy) and then check their score on the same depth with getMoveScore function, I'm getting different scores that don't match the score of those actual best moves. I've spent hours on debugging this and couldn't see the error, I hope maybe anyone could give me a tip on finding the problem.
Here is the code:
/*
* Getting best possible moves for the playing color with the minimax algorithm
*/
moves* getBestMoves(char playing_color){
//Allocate memory for the best_moves which is a global variable to fill it in a minimax algorithm//
best_moves = calloc(1, sizeof(moves));
//Call an alpha-beta pruned minimax to compute the best moves//
alphabeta(playing_color, board, minimax_depth, INT_MIN, INT_MAX, 1);
return best_moves;
}
/*
* Getting the score of a given move for a current player
*/
int getMoveScore(char playing_color, move* curr_move){
//Allocate memory for best_moves although its not used so its just freed later//
best_moves = calloc(1, sizeof(moves));
int score;
char board_cpy[BOARD_SIZE][BOARD_SIZE];
//Copying a a current board and making a move on that board which score I want to compute//
boardCopy(board, board_cpy);
actualBoardUpdate(curr_move, board_cpy, playing_color);
//Calling the alphabeta Minimax now with the opposite color , a board after a given move and as a minimizing player, because basicly I made my move so its now the opponents turn and he is the minimizing player//
score = alphabeta(OppositeColor(playing_color), board_cpy, minimax_depth, INT_MIN, INT_MAX, 0);
freeMoves(best_moves->head);
free(best_moves);
return score;
}
/*
* Minimax function - finding the score of the best move possible from the input board
*/
int alphabeta(char playing_color, char curr_board[BOARD_SIZE][BOARD_SIZE], int depth,int alpha,int beta, int maximizing) {
if (depth == 0){
//If I'm at depth 0 I'm evaluating the current board with my scoring function//
return scoringFunc(curr_board, playing_color);
}
int score;
int max_score;
char board_cpy[BOARD_SIZE][BOARD_SIZE];
//I'm getting all the possible legal moves for the playing color//
moves * all_moves = getMoves(playing_color, curr_board);
move* curr_move = all_moves->head;
//If its terminating move I'm evaluating board as well, its separate from depth == 0 because only here I want to free memory//
if (curr_move == NULL){
free(all_moves);
return scoringFunc(curr_board,playing_color);
}
//If maximizing player is playing//
if (maximizing) {
score = INT_MIN;
max_score = score;
while (curr_move != NULL){
//Make the move and call alphabeta with the current board after the move for opposite color and !maximizing player//
boardCopy(curr_board, board_cpy);
actualBoardUpdate(curr_move, board_cpy, playing_color);
score = alphabeta(OppositeColor(playing_color), board_cpy, depth - 1,alpha,beta, !maximizing);
alpha = MAX(alpha, score);
if (beta <= alpha){
break;
}
//If I'm at the maximum depth I want to get current player best moves//
if (depth == minimax_depth){
move* best_move;
//If I found a move with a score that is bigger then the max score, I will free all previous moves and append him, and update the max_score//
if (score > max_score){
max_score = score;
freeMoves(best_moves->head);
free(best_moves);
best_moves = calloc(1, sizeof(moves));
best_move = copyMove(curr_move);
concatMoves(best_moves, best_move);
}
//If I have found a move with the same score and want to concatenate it to a list of best moves//
else if (score == max_score){
best_move = copyMove(curr_move);
concatMoves(best_moves, best_move);
}
}
//Move to the next move//
curr_move = curr_move->next;
}
freeMoves(all_moves->head);
free(all_moves);
return alpha;
}
else {
//The same as maximizing just for a minimizing player and I dont want to look for best moves here because I dont want to minimize my outcome//
score = INT_MAX;
while (curr_move != NULL){
boardCopy(curr_board, board_cpy);
actualBoardUpdate(curr_move, board_cpy, playing_color);
score = alphabeta(OppositeColor(playing_color), board_cpy, depth - 1,alpha,beta, !maximizing);
beta = MIN(beta, score);
if (beta <= alpha){
break;
}
curr_move = curr_move->next;
}
freeMoves(all_moves->head);
free(all_moves);
return beta;
}
}
As Eugene has pointed out-I'm adding an example here: http://imageshack.com/a/img910/4643/fmQvlm.png
I'm currently the white player, i got only king-k and queen-q, the opposite color has king-K and rook-R. Obviously my best move here is to eat a rook or cause a check at least. Moves of the pieces are tested and they work fine. Although when i call get_best_moves function at depth 3, I'm getting lots of unnecessary moves and negative scores for them at that depth. Maybe now it's a little more clear. Thanks!