Minimax算法缺陷
Minimax算法缺陷
提问于 2015-04-02 00:25:43
我一直在努力学习minimax算法，我偶然发现了一个错误，我无法解决这个问题。代码：
private List<Integer> generatemoves(int[] evalFields) {
List<Integer> nextMoves = new ArrayList<Integer>();
for (int i = 0; i < evalFields.length; i++) {
if (evalFields[i] == 0) {
nextMoves.add(i);
}
}
return nextMoves;
}
private int evaluateLine(int p1, int p2, int p3, int[] evalFields) {
int score = 0;
if (evalFields[p1] == 1) {
score = 1;
} else if (evalFields[p1] == 10) {
score = -1;
}
if (evalFields[p2] == 1) {
if (score == 1) {
score = 10;
} else if (score == -1) {
return 0;
} else {
score = 1;
}
} else if (evalFields[p2] == 10) {
if (score == -1) {
score = -10;
} else if (score == 1) {
return 0;
} else {
score = -1;
}
}
if (evalFields[p3] == 1) {
if (score > 0) {
score *= 10;
} else if (score < 0) {
return 0;
} else {
score = 1;
}
} else if (evalFields[p3] == 10) {
if (score < 0) {
score *= 10;
} else if (score > 1) {
return 0;
} else {
score = -1;
}
}
return score;
}
private int evaluateBoard(int [] evalFields) {
int score = 0;
score += evaluateLine(0, 1, 2, evalFields);
score += evaluateLine(3, 4, 5, evalFields);
score += evaluateLine(6, 7, 8, evalFields);
score += evaluateLine(0, 3, 6, evalFields);
score += evaluateLine(1, 4, 7, evalFields);
score += evaluateLine(2, 5, 8, evalFields);
score += evaluateLine(0, 4, 8, evalFields);
score += evaluateLine(2, 4, 6, evalFields);
return score;
}
private int bestMove(int currentTurn, int[] board) {
int move;
int bestScore;
if (currentTurn == 1) {
bestScore = Integer.MIN_VALUE;
} else {
bestScore = Integer.MAX_VALUE;
}
List<Integer> nextMoves = generatemoves(board);
List<Integer> bestScores = new ArrayList<Integer>();
for (int i = 0; i < nextMoves.size(); i++) {
int[] newBoards = new int[9];
for (int j = 0; j < board.length; j++) {
newBoards[j] = board[j];
}
newBoards[nextMoves.get(i)] = turn;
bestScores.add(evaluateBoard(newBoards));
}
for (int scores : bestScores) {
if (currentTurn == 1) {
if (scores > bestScore) bestScore = scores;
} else {
if (scores < bestScore) bestScore = scores;
}
}
move = nextMoves.get(bestScores.indexOf(bestScore));
return move;
}这是代码中最相关的部分。它所做的，或者我认为它所做的，是它从所谓的字段板中产生的每一个可能的移动。然后计算每个移动的得分。然后，它进行移动，导致最高或最低的分数，x(1)是试图得到最高，O(10)最低。所发生的错误是，当玩家开始并在中间占据场地时，ai动作正常，但在玩家第二轮转弯后，ai开始表现得很奇怪：
[ ][ ][ ] [O][ ][ ] [O][ ][O]
[ ][x][ ] => [ ][x][ ] => [x][x][ ]
[ ][ ][ ] [ ][ ][ ] [ ][ ][ ]如果玩家选择这样做：
[O][ ][ ] [O][ ][ ]
[ ][x][x] => [O][x][x]
[ ][ ][ ] [ ][ ][ ]那么艾城就正常运作了。我不知道出了什么问题，即使我正确地理解了极小极大算法。
*编辑*添加的代码仍然存在相同的问题
private int[] evaluateMove(int [] board, int currentTurn) {
int bestScore;
int currentScore;
int bestMove = -1;
if (currentTurn == 1) {
bestScore = Integer.MIN_VALUE;
} else {
bestScore = Integer.MAX_VALUE;
}
List<Integer> nextMoves = generatemoves(board);
if (nextMoves.isEmpty()) {
bestScore = evaluateTheBoard(board);
} else {
for (int move : nextMoves) {
int[] nextBoard = new int[9];
for (int i = 0; i < nextBoard.length; i ++) {
nextBoard[i] = board[i];
}
nextBoard[move] = currentTurn;
currentScore = evaluateMove(nextBoard, nextTurn())[0];
if (currentTurn == 1) {
if (currentScore > bestScore) {
bestScore = currentScore;
bestMove = move;
}
} else {
if (currentScore < bestScore) {
bestScore = currentScore;
bestMove = move;
}
}
}
}
return new int[] {bestScore, bestMove};
}回答 1
Stack Overflow用户
回答已采纳
发布于 2015-04-02 00:59:48
我想你误解了如何在这样的比赛中向前看。不要将evaluateLine返回的值“总计”。
下面是tac脚趾板( evaluateBoard应该返回的)极小极大分数的伪代码。注意，evaluateBoard需要有一个currentTurn的概念。
function evaluateBoard(board, currentTurn)
// check if the game has already ended:
if WhiteHasWon then return -10
if BlackHasWon then return +10
// WhiteHasWon returns true if there exists one or more winning 3-in-a-row line for white.
// (You will have to scan for all 8 possible 3-in-a-row lines of white pieces)
// BlackHasWon returns true if there exists one or more winning 3-in-a-row line for black
if no legal moves, return 0 // draw
// The game isn't over yet, so look ahead:
bestMove = notset
resultScore = notset
for each legal move i for currentTurn,
nextBoard = board
Apply move i to nextBoard
score = evaluateBoard(nextBoard, NOT currentTurn).score
if score is <better for currentTurn> than resultScore, then
resultScore = score
bestMove = move i
return (resultScore, bestMove)这个版本与您的版本和我的版本之间的一个非常关键的区别是，我的版本是递归。你的只有一层深。我从内部调用evaluateBoard，如果我们不小心的话，这将是一个无限循环(一旦板子填满，它就不能再深了，所以它实际上不是无限的)。
另一个不同之处是，当你不应该的时候，你的总得分是- 10 ,0，或者只有当你看完比赛结束的时候，你才能得到-10，0或10。你应该选择在那个时候球员可以使用的最好的移动，而完全忽略所有其他的可能性，因为你只关心“最佳”的游戏线。游戏得分等于最优游戏的结果。
扩展<better for currentTurn>在minimax中是杂乱无章的，这就是为什么否定更干净的原因。白色喜欢低分数，黑色喜欢高分，所以你需要一些if语句来让它选择合适的首选分数。您已经有了这个部分(在您的最佳移动代码的末尾)，但是它需要在递归中而不是在末尾进行评估。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29403124
复制相关文章
相似问题
腾讯云开发者
