我正在尝试实现一种算法,它将为Connect 4的游戏选择最佳的下一步 . 我只是想确保基本的 minimax 正常工作,我实际上是在4x4字段上测试它就像一个Connect 3 . 这样,当算法做出愚蠢的举动时,我就更加明显了 .
问题是算法 always 以最左边的移动开始游戏,并且在游戏中它也会看到最好的移动 .
我已经彻底测试了方法 makeMove()
, undoMove()
, getAvailableColumns()
, isWinningMove()
和 isLastSpot()
所以我绝对是 sure 问题不存在 .
这是我的算法 .
NextMove.java
private static class NextMove {
final int evaluation;
final int moveIndex;
public NextMove(int eval, int moveIndex) {
this.evaluation = eval;
this.moveIndex = moveIndex;
}
int getEvaluation() {
return evaluation;
}
public int getMoveIndex() {
return moveIndex;
}
}
The Algorithm
private static NextMove max(C4Field field, int movePlayed) {
// moveIndex previously validated
// 1) check if moveIndex is a final move to make on a given field
field.undoMove(movePlayed);
// check
if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
field.playMove(movePlayed, C4Symbol.RED);
return new NextMove(BLUE_WIN, movePlayed);
}
if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
field.playMove(movePlayed, C4Symbol.RED);
return new NextMove(RED_WIN, movePlayed);
}
if (field.isLastSpot()) {
field.playMove(movePlayed, C4Symbol.RED);
return new NextMove(DRAW, movePlayed);
}
field.playMove(movePlayed, C4Symbol.RED);
// 2) moveIndex is not a final move
// --> try all possible next moves
final List<Integer> possibleMoves = field.getAvailableColumns();
int bestEval = Integer.MIN_VALUE;
int bestMove = 0;
for (int moveIndex : possibleMoves) {
field.playMove(moveIndex, C4Symbol.BLUE);
final int currentEval = min(field, moveIndex).getEvaluation();
if (currentEval > bestEval) {
bestEval = currentEval;
bestMove = moveIndex;
}
field.undoMove(moveIndex);
}
return new NextMove(bestEval, bestMove);
}
private static NextMove min(C4Field field, int movePlayed) {
// moveIndex previously validated
// 1) check if moveIndex is a final move to make on a given field
field.undoMove(movePlayed);
// check
if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
field.playMove(movePlayed, C4Symbol.BLUE);
return new NextMove(BLUE_WIN, movePlayed);
}
if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
field.playMove(movePlayed, C4Symbol.BLUE);
return new NextMove(RED_WIN, movePlayed);
}
if (field.isLastSpot()) {
field.playMove(movePlayed, C4Symbol.BLUE);
return new NextMove(DRAW, movePlayed);
}
field.playMove(movePlayed, C4Symbol.BLUE);
// 2) moveIndex is not a final move
// --> try all other moves
final List<Integer> possibleMoves = field.getAvailableColumns();
int bestEval = Integer.MAX_VALUE;
int bestMove = 0;
for (int moveIndex : possibleMoves) {
field.playMove(moveIndex, C4Symbol.RED);
final int currentEval = max(field, moveIndex).getEvaluation();
if (currentEval < bestEval) {
bestEval = currentEval;
bestMove = moveIndex;
}
field.undoMove(moveIndex);
}
return new NextMove(bestEval, bestMove);
}
这个想法是算法接受 currentField
和 lastPlayedMove
的参数 . 然后它检查最后一次移动是否以某种方式完成了游戏 . 如果确实如此,我只是返回那一步,否则我会深入了解后续的动作 .
蓝色玩家是MAX,红色玩家是MIN .
在每个步骤中,我首先撤消最后一步,因为更容易检查“下一步”移动是否将完成游戏,而不是检查当前字段是否已完成(这将需要分析该字段中所有可能的获胜选项) . 检查后,我只是重做了一下 .
从某种原因,这不起作用 . 我坚持了好几天!我不知道出了什么问题......任何帮助都非常感谢!