NegaMax 알고리즘 및 TicTacToe ... 무엇이 잘못 되었나요?

Question

저는 게임 트리 알고리즘에 익숙하지 않고 컴퓨터 AI 플레이어의 타일 점수를 평가하기 위해 NegaMax 알고리즘을 사용하는 간단한 tictactoe 게임을 구현하려고했습니다. 그러나 AI는 똑똑한 방식으로 행동하지 않습니다 (AI가 내 움직임을 차단하지 않기 때문에 항상 이길 수 있습니다). NegaMax 알고리즘을 잘못 구현 한 것 같습니다.

누군가 다음 코드를 사용하면 도움이 될 것입니다. 나는 오랜 시간을 다른 일들을 시도하면서 보냈지 만 결코 일하게 만들지 못했습니다.

#include <stdlib.h> 
#include <stdio.h> 
#include <malloc.h> 
#include <limits.h> 
#include "game_board.h" 

/** 
* Constructs a new game board. 
* 
* @param size the size of the board (the length of fields) 
* @return a new GameBoard 
*/ 
GameBoard* game_board_new(int size) 
{ 
    GameBoard* board = (GameBoard*) calloc(1, sizeof(GameBoard)); 
    board->size = size; 
    board->turn = WHITE; 
    board->fields = (enum Player*) calloc(size, sizeof(enum Player)); 
    return board; 
} 

/** 
* Releases a game board. 
* 
* @param board the GameBoard to release 
*/ 
void game_board_free(GameBoard* board) 
{ 
    free(board->fields); 
    free(board); 
} 

/** 
* Copies a game board. 
* 
* @param original the GameBoard to copy 
* @return a new GameBoard which is copied from the original 
*/ 
GameBoard* game_board_copy(GameBoard* original) 
{ 
    GameBoard* copy; 
    int i; 

    copy = game_board_new(original->size); 
    copy->size = original->size; 
    copy->turn = original->turn; 

    for (i = 0; i < original->size; i++) 
    { 
     copy->fields[i] = original->fields[i]; 
    } 

    return copy; 
} 

/** 
* Returns the winner for the current game or EMPTY if 
* there is no winner, yet. 
* 
* @param board the GameBoard to check 
* @return the winning Player or EMPTY 
*/ 
enum Player game_board_check_winner(GameBoard* board) 
{ 
    enum Player* f; 

    f = board->fields; 

    // Columns 
    if (f[0] != EMPTY && f[0] == f[3] && f[0] == f[6]) 
     return f[0]; 
    if (f[1] != EMPTY && f[1] == f[4] && f[1] == f[7]) 
     return f[1]; 
    if (f[2] != EMPTY && f[2] == f[5] && f[2] == f[8]) 
     return f[2]; 

    // Rows 
    if (f[0] != EMPTY && f[0] == f[1] && f[1] == f[2]) 
     return f[0]; 
    if (f[3] != EMPTY && f[3] == f[4] && f[4] == f[5]) 
     return f[3]; 
    if (f[6] != EMPTY && f[6] == f[7] && f[7] == f[8]) 
     return f[6]; 

    // Diagonal 
    if (f[0] != EMPTY && f[0] == f[4] && f[4] == f[8]) 
     return f[0]; 
    if (f[2] != EMPTY && f[2] == f[4] && f[4] == f[6]) 
     return f[2]; 

    return EMPTY; 
} 

void game_board_toggle_player(GameBoard* board) 
{ 
    if (board->turn == WHITE) 
     board->turn = BLACK; 
    else if (board->turn == BLACK) 
     board->turn = WHITE; 
} 

int game_board_is_ended(GameBoard* board) 
{ 
    return game_board_check_winner(board) || game_board_is_full(board); 
} 

static int evaluate(GameBoard* board) 
{ 
    enum Player winner = game_board_check_winner(board); 

    if (winner != EMPTY && winner == board->turn) 
    { 
     return 1; 
    } 
    else if (winner != EMPTY && winner != board->turn) 
    { 
     return -1; 
    } 
    else 
    { 
     return 0; 
    } 
} 

int negamax(GameBoard* board, int depth) 
{ 
    int bestvalue = INT_MIN; 
    int i; 
    int value; 

    enum Player winner = game_board_check_winner(board); 

    if (winner != EMPTY || depth == 0) 
     return evaluate(board); 

    for (i = 0; i < board->size; i++) 
    { 
     if (board->fields[i] == EMPTY) 
     { 
      GameBoard* copy = game_board_copy(board); 
      game_board_make_move(copy, i); 
      game_board_toggle_player(board); 

      value = -negamax(copy, depth-1); 
      bestvalue = max(value, bestvalue); 

      game_board_free(copy); 
     } 
    } 

    return bestvalue; 
} 

/** 
* Evaluates the current board according to NegaMax 
* algorithm. 
* 
* @param board the GameBoard to evaluate 
* @return a NegaMax score 
*/ 
int game_board_evaluate(GameBoard* board, int* best_pos) 
{ 
    int i; 
    int maxVal; 
    int val; 

    maxVal = INT_MIN; 

    for (i = 0; i < board->size; i++) 
    { 
     if (board->fields[i] == EMPTY) 
     { 
      val = negamax(board, 9); 
      if (val > maxVal) 
      { 
       maxVal = val; 
       printf("Best move: %i\n", i); 
       (*best_pos) = i; 
      } 
     } 
    } 

    return maxVal; 
} 

int game_board_is_full(GameBoard* board) 
{ 
    int i; 

    for (i = 0; i < board->size; i++) 
    { 
     if (board->fields[i] == 0) 
     { 
      return 0; 
     } 
    } 

    return 1; 
} 

void game_board_make_move(GameBoard* board, int pos) 
{ 
    board->fields[pos] = board->turn; 
} 

/** 
* Prints a game board. 
* 
* @param board the GameBoard to print 
*/ 
void game_board_print(GameBoard* board) 
{ 
    int i; 

    for (i = 0; i < board->size; i++) 
    { 
     printf("%i (%i)\t", board->fields[i], i); 

     if (i == 2 || i == 5) 
      printf("\n"); 
    } 

    printf("\n"); 
} 

Answer 1

game_board_toggle_player(board); 

는

game_board_toggle_player(copy); 

있어야하지 않나요?

Answer 2

일반적인 오류는 값을 트리로 전달하지 않고 각 레벨에서 MIN으로 시작하는 것입니다. 필자는 패러다임의 네가 맥스 알고리즘과 비교하기 위해 코드를 자세히 연구하지는 않았지만, 그 오류를 만든 것으로 보입니다.

Answer 3

NegaMax 프레임 워크에서 평가 기능은 다르게보아야합니다. 평가 함수 다음보십시오 :

이

int evaluateNegaMax(GameBoard* board) 
{ 
    if (board->turn == MAXPLAYER) 
     return evaluate(board); 
    else 
     return -evaluate(board); 
} 

chessprogramming 사이트가 이유를 설명 :

negaMax가 작동하려면, 정적 평가 함수가 평가 되 고 옆으로 점수 상대를 반환해야합니다 위해