理解Minimax算法
理解Minimax算法
提问于 2015-03-13 20:29:32
我正试图为一个两人8x8的棋盘游戏创造一个AI对手。经过一项研究，我发现Minimax算法足够方便地完成这项工作。我正在创建的AI对手将与另一个AI对手或人类进行对抗。
我对极小极大算法的理解有疑问。
我试图创建一个AI的对手，但在网络上发现的解释说，我需要为两个球员(最小的球员和最大的球员)写代码，我从下面的伪代码理解。
MinMax (GamePosition game) {
return MaxMove (game);
}
MaxMove (GamePosition game) {
if (GameEnded(game)) {
return EvalGameState(game);
}
else {
best_move < - {};
moves <- GenerateMoves(game);
ForEach moves {
move <- MinMove(ApplyMove(game));
if (Value(move) > Value(best_move)) {
best_move < - move;
}
}
return best_move;
}
}
MinMove (GamePosition game) {
best_move <- {};
moves <- GenerateMoves(game);
ForEach moves {
move <- MaxMove(ApplyMove(game));
if (Value(move) > Value(best_move)) {
best_move < - move;
}
}
return best_move;
}我可以进一步理解，最大的球员将是人工智能，我将发展和最低的球员是对手。
我的问题是，为什么我必须为最低和最大的球员都写代码，以返回最佳的移动？
下面给出的伪代码是基于C#的。
提前谢谢。
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-03-13 20:59:13
你只需在最坏的情况下为两位玩家寻找最好的解决方案，那就是为什么叫minmax，你不需要更多：
function minimax( node, depth )
if node is a terminal node or depth <= 0:
return the heuristic value of node
α = -∞
foreach child in node:
α = max( a, -minimax( child, depth-1 ) )
return α节点是一个游戏位置，子在节点是下一步(从列表中的所有可用移动)，深度是最大移动搜索两个玩家在一起。
您可能无法运行8x8上的所有可能的移动(取决于您有多少下一个移动选项)，例如，如果每个您有8个不同的可能移动，并且在40次移动后游戏结束(应该是最坏的情况)，那么您将得到8^40位置。计算机将需要几十年甚至更多的时间来解决这一问题，这就是为什么你需要深度参数，并使用启发式函数(例如随机森林树)来知道游戏位置有多好而无需检查所有选项。
minmax的一个更好的算法是Alpha-Beta剪枝，一旦他找到了目标(β参数)就完成了搜索：
function negamax( node, depth, α, β, color )
if node is a terminal node or depth = 0
return color * the heuristic value of node
foreach child of node
value = -negamax( child, depth-1, -β, -α, -color )
if value ≥ β
return value /** Alpha-Beta cut-off */
if value ≥ α
α = value
return α最好首先使用一个没有很多位置的游戏(例如抽搐脚趾)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29041413
复制相关文章
相似问题
腾讯云开发者
