NegaMax算法和TicTacToe ……出了什么问题？

我是游戏树算法的新手，我试图实现一个简单的tictactoe游戏，利用NegaMax算法来评估计算机AI玩家的平铺分数。 然而，人工智能行为不是很聪明（我可以一直赢，因为AI不会阻止我的行动），我认为我错误地实施了NegaMax算法。

如果有人可以帮助我使用以下代码，那将是很棒的。 我花了这么长时间尝试不同的东西，但我从来没有让它工作。

#include  #include  #include  #include  #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 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 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 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 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 size; i++) { printf("%i (%i)\t", board->fields[i], i); if (i == 2 || i == 5) printf("\n"); } printf("\n"); } 

Answer 1

在NegaMax框架中，评估function必须看起来不同。 尝试以下评估function：

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

国际象棋编程网站解释了原因：

为了使negaMax工作，您的静态评估函数必须返回相对于要评估的一侧的分数

Answer 2

不能

 game_board_toggle_player(board); 

是

 game_board_toggle_player(copy); 

？

Answer 3

通常的错误是从每个级别的MIN开始，而不是在树中传递值。 我没有详细研究你的代码以与范式negamax算法进行比较，但似乎你可能正在犯这个错误。