Computing eine Bewegung Punktzahl in einem Minimax Baum von einer gewissen Tiefe

Question

ich ein Schachspiel in C, mit den folgenden Strukturen implementiert haben:

Bewegung - die einen Übergang von (a, b) darstellt, zu (c, d) auf einem Spielbrett [8] [8] (Schachbrett)

bewegt - das ist eine verkettete Liste von Zügen mit Kopf und Schwanz.

Variablen: playing_color ist 'W' oder 'B'. minimax_depth ist eine Minimaxtiefe, die zuvor festgelegt wurde.

Hier ist mein Code der Minimax-Funktion mit Alpha-Beta-Suche und der getMoveScore Funktion, die die Partitur des Umzugs in Minimax Baum eines bestimmten minimax_depth zurückkehren sollte, die vor dem festgelegt wurden.

Auch ich benutze die getBestMoves Funktion, die ich hier auch auflisten werde, es findet grundsätzlich die besten Bewegungen während des Minimax Algorithmus und speichert sie in einer globalen Variable, so dass ich sie später benutzen kann.

Ich muss hinzufügen, dass alle Funktionen, die in den drei Funktionen aufgelistet, die ich hier hinzufügen, werden einwandfrei funktionieren und wurden getestet, so das Problem ist entweder ein logisches Problem des alphabetaMax Algorithmus oder die Implementierung von getBestMoves/getMoveScore.

Das Problem ist vor allem, dass, wenn ich meine besten Bewegungen in der Tiefe N (die auch nicht richtig somewhy berechnet werden) und dann überprüfen Sie ihre Gäste auf der gleichen Tiefe mit getMoveScore Funktion bekommen, erhalte ich unterschiedliche Scores, die don nicht die Punktzahl dieser tatsächlichen besten Züge. Ich habe Stunden damit verbracht, das zu debuggen und konnte den Fehler nicht sehen, ich hoffe, dass irgendjemand mir einen Tipp geben könnte, das Problem zu finden.

Hier ist der 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; 
    } 
} 

Wie Eugene klargestellt hat,-Ich bin ein Beispiel das Hinzufügen hier: http://imageshack.com/a/img910/4643/fmQvlm.png

Ich bin derzeit der weiße Spieler, ich habe nur König-K und Königin-Q, die entgegengesetzte Farbe hat König-K und Turm-R. Offensichtlich ist mein bester Zug hier, einen Turm zu essen oder wenigstens einen Check zu machen. Bewegungen der Teile werden getestet und sie funktionieren gut. Obwohl ich die Funktion get_best_moves in Tiefe 3 anrufe, erhalte ich in dieser Tiefe viele unnötige Bewegungen und negative Werte. Vielleicht ist es jetzt ein bisschen klarer. Vielen Dank!

Answer 1

Ohne den gesamten Code zu debuggen, ist mindestens EINES der Probleme die Tatsache, dass Ihre Scoreverification mit einem Minimax-Algorithmus funktionieren könnte, aber nicht mit einem Alpha-Beta. Folgendes Problem:

Die Funktion getMoveScore() muss mit einem offenen AB-Fenster beginnen.

Die getBestMoves() ruft getMoveScore() jedoch mit einem bereits geschlossenen AB-Fenster auf.

Im Fall von getBestMoves kann es Zweige geben, die nicht in getMoveScore() abgeschnitten werden, daher ist die Punktzahl nicht genau und das ist der Grund (oder mindestens EINER von ihnen), warum diese Werte abweichen können .