java - MiniMax 算法的一个非常有趣的问题。什么可能导致这种行为?
问题描述
我已经实现了 MiniMax 算法(使用 alpha-beta 修剪),但是它的行为方式很有趣。我的球员会创造一个巨大的领先优势,但是当是时候进入决赛时,获胜的动作并没有采取那个动作,而是一直拖延比赛。
这是我的极小极大函数:
// Game states are represented by Node objects (holds the move and the board in that state)
//ValueStep is just a pair holding the minimax value and a game move (step)
private ValueStep minimax(Node gameState,int depth,int alpha,int beta) {
//Node.MAXDEPTH is a constant
if(depth == Node.MAXDEPTH || gameOver(gameState.board)) {
return new ValueStep(gameState.heuristicValue(),gameState.step);
}
//this method definately works. child nodes are created with a move and an
//updated board and MAX value
//which determines if they are the maximizing or minimizing players game states.
gameState.children = gameState.findPossibleStates();
if(state.MAX) { //maximizing player
ValueStep best = null;
for(Node child: gameState.children) {
ValueStep vs = new ValueStep(minimax(child,depth+1,alpha,beta).value,child.move);
//values updated here if needed
if(best==null || vs.value > best.value) best = vs;
if(vs.value > alpha) alpha = vs.value;
if(alpha >= beta) break;
}
return best;
} else { //minimizing player
ValueStep best = null;
for(Node child: gameState.children) {
ValueStep vs = new ValueStep(minimax(child,depth+1,alfa,beta).value,child.move);
if(best==null || vs.value < best.value) best = vs;
if(vs.value < beta) beta = vs.value;
if(alpha >= beta) break;
}
return best;
}
}
首先我认为问题出在我的评估函数上,但如果是,我找不到它。在这个游戏中,两个玩家都有一个分数,我的函数只是根据分数差计算启发式值。这里是:
public int heuristicValue() {
//I calculate the score difference here in this state and save it in
//the variable scoreDiff. scoreDiff will be positive if I am winning
//here, negative if im loosing.
//"this" is a Node object here. If the game is over here, special
//heuristic values are returned, depending on who wins (or if its a
//draw)
if(gameOver(this.board)) {
if(scoreDiff>0) {
return Integer.MAX_VALUE;
} else if(scoreDiff==0) {
return 0;
} else {
return Integer.MIN_VALUE;
}
}
int value = 0;
value += 100*scoreDiff; //caluclate the heuristic value using the score differerence. If its high, the value will be high as well
return value;
}
我已将我的代码“翻译”成英文,因此可能存在拼写错误。我相当确定问题出在某个地方,但是如果您需要其他代码,那么我会更新问题。同样,我的玩家可以创造优势,但由于某种原因它不会成为最终的获胜举措。我感谢您的帮助!
解决方案
假设您的 Minimax 玩家处于可以证明可以保证获胜的位置。通常会有许多不同的方式仍然可以保证最终获胜。有的招式可能是立竿见影的,有的招式可能会不必要地拖拖拉拉……只要不是真正愚蠢的招式突然让对手赢(或平局),都是赢,而且都是一样的博弈论价值(Integer.MAX_VALUE
在您的代码中)。
您的 Minimax 算法不会区分这些移动,而只是播放恰好是gameState.children
列表中第一个的移动。这可能是一场快速、浅薄的胜利,也可能是一场缓慢、非常深刻的胜利。
有两种简单的方法可以让您的 Minimax 算法优先考虑快胜于慢胜:
- 最好的选择(因为它还有许多其他优点)是使用Iterative Deepening。您可以查看详细信息,但基本思想是您首先进行深度限制为 1 的 Minimax 搜索,然后进行深度限制为 2 的另一个搜索,然后深度限制为 3,依此类推。您的一次搜索证明了胜利,您可以终止搜索并玩那个获胜的动作。这将使您的算法总是更喜欢最短的胜利(因为首先找到那些)。
- 或者,您可以修改
heuristicValue()
函数以合并搜索深度。例如,您可以Integer.MAX_VALUE - depth
在获胜位置返回。这将使更快的胜利实际上具有稍大的评估。
推荐阅读
- c# - 如何在 .Net Core 5 中使用 MemberShip
- c++ - 如何获得模板参数包的最大成员?
- java - 如何使java嵌套循环高效
- excel - 排序列表但保留单个单元格的格式
- javascript - PromiseRejectionEvent 的发生取决于拒绝参数类型(原始与错误)
- android - 插件 [id: 'gradle.plugin.com.onesignal.onesignal-gradle-plugin'] 未找到
- javascript - 是否可以在 shell 脚本中执行时返回 javascript 方法的结果?
- sql - oracle:使用计算列对行进行分类的 ALTER 表?
- c++ - 获取 UUID 时结果错误
- python - ValueError: Input 0 is in compatible with layer model_5: expected shape=(None, 64, 64, 3), found shape=(50, 64, 80, 3)