MiniMax算法
MiniMax算法
提问于 2018-09-15 16:57:59
这是我的C实现的Minimax算法来玩toe.我认为自己是一个C初学者，所以任何关于风格、最佳实践或效率的反馈都是非常受欢迎的。
# define HUMAN_PLAYER 'X'
# define AI_PLAYER 'O'
# define NONE '\0'
typedef struct Point {
int x, y;
} Point;
typedef struct Board {
Point location;
Point boundary;
int size;
int current_player;
int last_player;
int nmoves_played;
int ai_mode;
char last_cell_symbol;
char **cells;
} Board;
typedef struct MiniMaxMove {
int score;
int x;
int y;
} MiniMaxMove;
int has_won(Point last_destination, char player, Board *board) {
// columns
for (int i = 0; i < board->size; i++) {
if (board->cells[last_destination.x][i] != player)
break;
if (i == board->size - 1) {
return 1;
}
}
// rows
for (int i = 0; i < board->size; i++) {
if (board->cells[i][last_destination.y] != player)
break;
if (i == board->size - 1) {
return 1;
}
}
// diagonal
if (last_destination.x == last_destination.y) {
for (int i = 0; i < board->size; i++) {
if (board->cells[i][i] != player)
break;
if (i == board->size - 1) {
return 1;
}
}
}
// anti diagonal
if (last_destination.x + last_destination.y == board->size - 1) {
for (int i = 0; i < board->size; i++) {
if (board->cells[i][(board->size-1)-i] != player)
break;
if (i == board->size - 1){
return 1;
}
}
}
return 0;
}
int is_a_draw(Board *board) {
if (board->nmoves_played == (pow(board->size, 2) - 1)) {
return 1;
}
return 0;
}
MiniMaxMove minimax(Point last_destination, char player, Board *board) {
if (has_won(last_destination, HUMAN_PLAYER, board)) {
return (MiniMaxMove) { .score = -10 };
} else if (has_won(last_destination, AI_PLAYER, board)) {
return (MiniMaxMove) { .score = 10 };
} else if (is_a_draw(board)) {
return (MiniMaxMove) { .score = 0 };
}
MiniMaxMove *moves = malloc(sizeof(MiniMaxMove *) * board->size * board->size);
size_t moves_size = 0;
for (int i = 0; i < board->size; i++) {
for (int j = 0; j < board->size; j++) {
if (board->cells[i][j] == '\0') {
MiniMaxMove move;
move.x = i;
move.y = j;
board->cells[i][j] = player;
// caclulate the score for the opponent
if (player == AI_PLAYER) {
MiniMaxMove mm_move = minimax(last_destination, HUMAN_PLAYER, board);
move.score = mm_move.score;
} else if (player == HUMAN_PLAYER) {
MiniMaxMove mm_move = minimax(last_destination, AI_PLAYER, board);
move.score = mm_move.score;
}
// reset the board to what it was
board->cells[i][j] = '\0';
moves[moves_size++] = move;
}
}
}
int best_move_idx;
if (player == AI_PLAYER) {
int best_score = -10000;
for (unsigned int i = 0; i < moves_size; i++) {
if (moves[i].score > best_score) {
best_score = moves[i].score;
best_move_idx = i;
}
}
} else {
int best_score = 10000;
for (unsigned int i = 0; i < moves_size; i++) {
if (moves[i].score < best_score) {
best_score = moves[i].score;
best_move_idx = i;
}
}
}
return moves[best_move_idx];
}回答 1
Code Review用户
回答已采纳
发布于 2018-09-16 10:32:16
快速地看，代码看起来很好；很好地使用了结构，相对独立的函数，很好的缩进。所以主要是一些可以改进的小东西：
使用静态const变量而不是#define
而不是
# define HUMAN_PLAYER 'X'写入：
static const char HUMAN_PLAYER = 'X';考虑使用枚举
而不是传递一个char来表示播放器，你可以使用枚举代替。这表明它是一个单独的类型。例如：
typedef enum player {
NONE = '\0',
HUMAN_PLAYER = 'X',
AI_PLAYER = 'O',
} player_t;在适当的地方使用bool类型(
)
不要返回整数1和0以指示成功和失败，而是使用bool类型。例如：
#include <stdbool.h>
...
bool has_won(Point last_destination, char player, Board *board) {
// columns
for (int i = 1; i < board->size; i++) {
if (board->cells[last_destination.x][i] != player)
break;
if (i == board->size - 1) {
return true;
}
}
}简化了if (foo) return true; else return false
直接返回foo！例如：
bool is_a_draw(Board *board) {
return board->nmoves_played == pow(board->size, 2) - 1;
}在处理整数
时避免浮点函数
表达式pow(board->size, 2)将把整数转换为双倍，稍后它们可能会被转换回其他的东西。最好避免这种情况，只需编写board->size * board->size即可。如果经常使用平方整数，则编写一个简单的函数来完成以下操作：
int square(int x) {
return x * x;
}或者，在这种情况下，您可以将板大小的平方存储在它自己的变量中。
在可能的情况下使用
(变量)而不是多少(类型)
正如@chux已经提到的，使用sizeof有一个错误。最好总是重复变量名，而不是它的类型，并确保结构本身的大小，而不是指针的大小。所以：
MiniMaxMove *moves = malloc(sizeof *moves * board->size * board->size);不使用任意限制
您正在为best_score设置一些任意的限制：
int best_score = -10000;这实际上限制了您的董事会大小。您可以在这里使用int的实际最低值：
#include <limits.h>
...
int best_score = INT_MIN;或者使用找到的第一个分数初始化它：
int best_move_idx = 0;
int best_score = moves[0].score;
if (player == AI_PLAYER) {
for (unsigned int i = 1; i < moves_size; i++) {
if (moves[i].score > best_score) {
...总是释放分配给
的内存
你打电话给malloc()，但我没看到free()。在您的示例中，我将执行以下操作以正确清理数组，同时不会导致return语句出现问题：
...
MiniMaxMove best_move = moves[best_move_idx];
free(moves);
return best_move;
}避免在不必要的情况下分配内存
仔细观察代码，实际上根本不需要分配数组moves。在minimax()中的第一个for-循环中，您将项添加到数组中，然后只是尝试在数组中找到最佳项。您可以只跟踪到到目前为止在第一个for-循环中找到的最好的项目！因此，与其：
moves[moves_size++] = move;不要分配数组moves，只需保留一个MiniMaxMove best_move，并将上面的行替换为如下所示：
if (player == AI_PLAYER) {
if (move.score > best_move.score) {
best_move = move;
}
} else {
if (move.score < best_move.score) {
best_move = move;
}
}页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/203786
复制相关文章
相似问题
腾讯云开发者
