我的 tictactoe 极小极大算法有什么问题
What is wrong with my minimax algorithm for tictactoe
我正在构建一个井字游戏,以获得有趣的学习体验。我已经构建了一个 minimax 算法来 return 计算机的最佳移动,但不知何故我出错了,得到了这样的奇怪输出
TIC TAC TOE V1.0
---
---
---
Enter row, column of your move
1,1
---
-X-
---
...
0, 0: -1038
0, 1: -1470
0, 2: -1038
1, 0: -1470
1, 2: -1470
2, 0: -1038
2, 1: -1470
2, 2: -1038
O--
-X-
---
Enter row, column of your move
1,2
O--
-XX
---
...
0, 1: -15
0, 2: -9
1, 0: -10
2, 0: -1
2, 1: -29
2, 2: -41
O--
-XX
O--
Enter row, column of your move
1,0
O--
XXX
O--
WINNER: PLAYER
可以看到电脑选择了左下角而不是切断播放器。我的代码试图通过所有可能的游戏状态在回合之间递归地翻转,总结回合可能导致的每场胜利或失败的分数,然后 returns 得分最高的动作。打印输出是每回合之前的分数(你可以看到它选择了最高的),那我为什么不切断玩家呢?我怎样才能解决这个问题?这是我的代码。
int compMoveScoreRecursive(state_t **board, int dimension, int row, int col, state_t turn) {
board[row][col] = turn;
state_t winner = checkWinner(board, dimension);
if (winner == COMPUTER) {
return 1;
} else if (winner == PLAYER) {
return -1;
} else {
int score = 0;
state_t nextTurn = turn == COMPUTER ? PLAYER : COMPUTER;
for (int i = 0; i < dimension; i++) {
for (int j = 0; j < dimension; j++) {
if (board[i][j] == NIL) {
state_t **boardCopy = copyBoard(board, dimension);
score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn);
destroyBoard(boardCopy, dimension);
}
}
}
return score;
}
}
move_t optimalCompMove(state_t **board, int dimension) {
move_t optMove;
int optScore = INT_MIN;
for (int row = 0; row < dimension; row++) {
for (int col = 0; col < dimension; col++) {
if (board[row][col] == NIL) {
state_t **boardCopy = copyBoard(board, dimension);
int score = compMoveScoreRecursive(boardCopy, dimension, row, col, COMPUTER);
printf("%d, %d: %d\n", row, col, score);
if (score > optScore) {
optMove.row = row;
optMove.col = col;
optScore = score;
}
destroyBoard(boardCopy, dimension);
}
}
}
return optMove;
}
您的算法背后的概念似乎有缺陷。根据您描述的方式,您正在考虑每条打法,而不是假设对手会做出正确的举动。正因为如此,对手可以通过下一步行动获胜这一事实的重要性很小,因为您还考虑了其他 4 步行动提供的所有选择(尽管这些显然永远不会做出)。你必须改进你的算法以正确地最小-最大而不是搜索整个棋盘状态集
据我了解,在compMoveScoreRecursive
的实现中,递归计算的分数是通过
添加的
score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn);
而不是最大化或最小化值。然而,要返回的值应该在最小化时最大化,这取决于参数 turn
,这也是该方法称为 MinMax 的原因。
minmax
算法的概念是“最小化最大损失”(Wikipedia),所以你的算法首先出错的是你的总和。
对于游戏的任何状态 S
,以及对于当前玩家(假设玩家 1 P1
)可用的任何移动 M
,[=14= 的值] 是 P1
播放 M
时 P2
的 最大 可能输出。所以如果 P1
想要最大化他的获胜机会,他应该尽可能地减少 P2
的最大输出,即他必须找到 minimum输出。
在tictactoe minmax中,可以测试整个游戏(最多9步),意思是如果PX
赢了(1),你总是现在,输 (-1) 或平局 (0)。所以 minmax (state, PX)
将 return 只有这三个值之一。
在许多游戏中,您无法玩完整个游戏(例如草稿),因此 returned 值是状态的 指示 ,例如 -oo
如果你输了,+oo
如果你赢了,否则就是你和对手的选秀次数之差。
我正在构建一个井字游戏,以获得有趣的学习体验。我已经构建了一个 minimax 算法来 return 计算机的最佳移动,但不知何故我出错了,得到了这样的奇怪输出
TIC TAC TOE V1.0
---
---
---
Enter row, column of your move
1,1
---
-X-
---
...
0, 0: -1038
0, 1: -1470
0, 2: -1038
1, 0: -1470
1, 2: -1470
2, 0: -1038
2, 1: -1470
2, 2: -1038
O--
-X-
---
Enter row, column of your move
1,2
O--
-XX
---
...
0, 1: -15
0, 2: -9
1, 0: -10
2, 0: -1
2, 1: -29
2, 2: -41
O--
-XX
O--
Enter row, column of your move
1,0
O--
XXX
O--
WINNER: PLAYER
可以看到电脑选择了左下角而不是切断播放器。我的代码试图通过所有可能的游戏状态在回合之间递归地翻转,总结回合可能导致的每场胜利或失败的分数,然后 returns 得分最高的动作。打印输出是每回合之前的分数(你可以看到它选择了最高的),那我为什么不切断玩家呢?我怎样才能解决这个问题?这是我的代码。
int compMoveScoreRecursive(state_t **board, int dimension, int row, int col, state_t turn) {
board[row][col] = turn;
state_t winner = checkWinner(board, dimension);
if (winner == COMPUTER) {
return 1;
} else if (winner == PLAYER) {
return -1;
} else {
int score = 0;
state_t nextTurn = turn == COMPUTER ? PLAYER : COMPUTER;
for (int i = 0; i < dimension; i++) {
for (int j = 0; j < dimension; j++) {
if (board[i][j] == NIL) {
state_t **boardCopy = copyBoard(board, dimension);
score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn);
destroyBoard(boardCopy, dimension);
}
}
}
return score;
}
}
move_t optimalCompMove(state_t **board, int dimension) {
move_t optMove;
int optScore = INT_MIN;
for (int row = 0; row < dimension; row++) {
for (int col = 0; col < dimension; col++) {
if (board[row][col] == NIL) {
state_t **boardCopy = copyBoard(board, dimension);
int score = compMoveScoreRecursive(boardCopy, dimension, row, col, COMPUTER);
printf("%d, %d: %d\n", row, col, score);
if (score > optScore) {
optMove.row = row;
optMove.col = col;
optScore = score;
}
destroyBoard(boardCopy, dimension);
}
}
}
return optMove;
}
您的算法背后的概念似乎有缺陷。根据您描述的方式,您正在考虑每条打法,而不是假设对手会做出正确的举动。正因为如此,对手可以通过下一步行动获胜这一事实的重要性很小,因为您还考虑了其他 4 步行动提供的所有选择(尽管这些显然永远不会做出)。你必须改进你的算法以正确地最小-最大而不是搜索整个棋盘状态集
据我了解,在compMoveScoreRecursive
的实现中,递归计算的分数是通过
score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn);
而不是最大化或最小化值。然而,要返回的值应该在最小化时最大化,这取决于参数 turn
,这也是该方法称为 MinMax 的原因。
minmax
算法的概念是“最小化最大损失”(Wikipedia),所以你的算法首先出错的是你的总和。
对于游戏的任何状态 S
,以及对于当前玩家(假设玩家 1 P1
)可用的任何移动 M
,[=14= 的值] 是 P1
播放 M
时 P2
的 最大 可能输出。所以如果 P1
想要最大化他的获胜机会,他应该尽可能地减少 P2
的最大输出,即他必须找到 minimum输出。
在tictactoe minmax中,可以测试整个游戏(最多9步),意思是如果PX
赢了(1),你总是现在,输 (-1) 或平局 (0)。所以 minmax (state, PX)
将 return 只有这三个值之一。
在许多游戏中,您无法玩完整个游戏(例如草稿),因此 returned 值是状态的 指示 ,例如 -oo
如果你输了,+oo
如果你赢了,否则就是你和对手的选秀次数之差。