计算一定深度的Minimax树中的移动得分

Question

我在C中实现了一个国际象棋游戏,具有以下结构:

移动 - 代表在char板上从(a,b)到(c,d)的移动[8] [8](棋盘)

移动 - 这是一个有头部和尾部的移动链表.

变量: playing_color是'W'或'B'.minimax_depth是之前设置的极小极大深度.

这是我使用alpha-beta修剪和getMoveScore函数的Minimax函数的代码,该函数应返回之前设置的某个minimax_depth的Minimax树中的移动得分.

我也在使用getBestMoves函数,我将在这里列出它,它基本上找到Minimax算法中的最佳移动并将它们保存到全局变量中,以便我以后能够使用它们.

我必须补充说,我将​​在这里添加的三个函数中列出的所有函数都正常工作并进行了测试,因此问题是alphabetaMax算法的逻辑问题或getBestMoves/getMoveScore的实现.

问题主要在于,当我在深度N处获得最佳动作时(为什么还没有计算出来),然后使用getMoveScore函数在相同深度上检查他们的分数,我得到的分数与得分不匹配那些实际的最佳动作.我花了几个小时来调试这个并且看不到错误,我希望也许有人可以给我一个关于找到问题的小费.

这是代码:

/*
* 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;
    }
}

正如Eugene指出的那样 - 我在这里添加一个例子:http: //imageshack.com/a/img910/4643/fmQvlm.png

我现在是白人球员,我只有王-K和女王-q,相反的颜色有王-K和车-R.显然,我最好的举动是吃车或至少检查一下.部件的移动经过测试,工作正常.虽然当我在深度3调用get_best_moves函数时,我会在那个深度获得许多不必要的移动和负分数.也许现在它更清楚了.谢谢!

Answer 1

如果不调试整个代码，至少有一个问题是您的分数验证可能适用于极小极大算法，但不适用于 Alpha-Beta。以下问题：

getMoveScore() 函数必须从打开的 AB 窗口开始。

然而， getBestMoves() 使用已经关闭的 AB 窗口调用 getMoveScore()。

因此，在 getBestMoves 的情况下，可能存在未在 getMoveScore() 中修剪的分支，因此分数不准确，这就是这些值可能不同的原因（或至少其中之一）。