Вычисление счет перемещения в минимаксном Дереве определенной глубины

Question

Я реализованный шахматную игру в C, со следующими структурами:

шага - который представляет собой переход от (а, б) (c, d) на доске [8] [8] (Шахматная доска)

ходы - это связанный список ходов с головой и хвостом.

Переменные: play_color is 'W' or 'B'. minimax_depth - минимаксная глубина, которая была установлена ​​ранее.

Вот мой код функции Минимакса с альфа-бета обрезкой и функцией getMoveScore, которая должна вернуть оценку хода в Минимаксе Древе определенного minimax_depth, который был установлен ранее.

Также я использую функцию getBestMoves, которую я также перечислил здесь, она в основном находит лучшие ходы во время алгоритма Minimax и сохраняет их в глобальную переменную, чтобы я мог использовать их позже.

Я должен добавить, что все функции, которые перечислены в трех функций, которые я добавлю здесь работают должным образом и были испытаны, так что проблема либо логическая задача алгоритма alphabetaMax или реализация getBestMoves/getMoveScore.

Проблема в основном в том, что, когда я получаю мои лучшие хода на глубине N (которые также не вычисленные правые somewhy), а затем проверить их счет на ту же глубину, с функцией getMoveScore, я получаю разные результаты, что дон 't соответствует оценке этих фактических лучших ходов. Я потратил часы на отладку этого и не мог видеть ошибку, надеюсь, что кто-нибудь может дать мне совет по поиску проблемы.

Вот код:

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

Как Юджин указывал-я, добавив пример здесь: http://imageshack.com/a/img910/4643/fmQvlm.png

Я в настоящее время белый игрок, я получил только king-k и queen-q, противоположный цвет имеет king-K и rook-R. Очевидно, что мне лучше всего есть ладью или, по крайней мере, проверить чек. Перемещения частей тестируются, и они работают нормально. Хотя, когда я вызываю функцию get_best_moves на глубине 3, я получаю много ненужных ходов и отрицательных оценок для них на этой глубине. Может быть, теперь это немного более ясно. Благодаря!

Answer 1

Без отладки всего кода, по крайней мере, одна из проблем заключается в том, что ваша оценка может работать с минимаксным алгоритмом, но не с альфа-бета-версией. Следующая проблема:

Функция getMoveScore() должна начинаться с открытого окна AB.

Однако getBestMoves() вызывает callMoveScore() с уже закрытым окном AB.

Таким образом, в случае getBestMoves могут быть разделены ветви, которые не обрезаются в getMoveScore(), поэтому оценка не является точной, и это причина (или, по крайней мере, ОДИН из них), почему эти ценности могут отличаться ,