我有一个关于Minimax算法的简单问题：例如对于井字游戏，我如何确定每个玩家的效用函数？它不会自动完成，是吗？我必须在游戏中硬编码这些值，它不能自己学习，对吗？
4个回答
10
不，MiniMax算法不会学习。它是一种更智能的暴力搜索树的版本。
- H H
2
1由于这是一种暴力算法，因此使用类似Alpha-Beta修剪的优化方法进行优化非常重要。
http://en.wikipedia.org/wiki/Alpha-beta_pruning - Brendan Enrick
berrick：是的，当然。但是通常情况下，我们在谈论negamax时，都会默认包含alpha/beta剪枝算法。 - H H
3
通常情况下，您会直接实现实用函数。在这种情况下，算法不会学习如何玩游戏，它将使用您在实现中明确硬编码的信息。
但是，可以使用遗传编程（GP）或某些等效技术自动派生实用函数。在这种情况下，您不必编码任何显式策略。相反，演化将发现自己玩游戏的好方法。
您可以将最小化代码和GP代码组合成单个（可能非常慢）自适应程序，或者您可以先运行GP，找到一个好的实用函数，然后像任何手动编码的函数一样将此函数添加到您的最小化代码中。
但是，可以使用遗传编程（GP）或某些等效技术自动派生实用函数。在这种情况下，您不必编码任何显式策略。相反，演化将发现自己玩游戏的好方法。
您可以将最小化代码和GP代码组合成单个（可能非常慢）自适应程序，或者您可以先运行GP，找到一个好的实用函数，然后像任何手动编码的函数一样将此函数添加到您的最小化代码中。
- Dan Dyer
2
井字游戏足够简单，可以运行到结束并为胜利分配1，平局分配0，失败分配-1。
否则，您必须提供一个函数来启发式地确定位置的价值。例如，在国际象棋中，一个重要因素是材料的价值，但也包括谁控制中心或棋子如何移动。
至于学习，您可以将不同方面的权重因素添加到位置上，并通过反复玩游戏来优化这些因素。
- starblue
2
如何确定每个游戏的效用函数？
谨慎地进行；-) 这篇文章展示了一个略有缺陷的评估函数（例如，它要么没有深入考虑可能的移动树，要么无法捕捉某些棋盘位置的相对强度）会导致整体算法较弱（输得更多）。
它不能自己学习，是吗？
不，它并不会。但是，有方法可以让计算机学习棋盘位置的相对强度。例如，通过查看唐纳德·米奇和他的MENACE程序，您将了解如何使用随机过程学习游戏规则之外的棋盘。有趣的是，虽然这可以在计算机上实现，但只需要几百个彩色珠子和火柴盒，因为游戏空间相对较小，并且还存在各种对称性。
总之，在井字棋的情况下，只有当我们消除了与完整树的简单评估相关的确定性时（例如帮助我们探索特定效用函数的有效性），MinMax才变得更加有趣。使游戏[数学上]有趣的另一种方法是与犯错误的对手玩...
谨慎地进行；-) 这篇文章展示了一个略有缺陷的评估函数（例如，它要么没有深入考虑可能的移动树，要么无法捕捉某些棋盘位置的相对强度）会导致整体算法较弱（输得更多）。
它不能自己学习，是吗？
不，它并不会。但是，有方法可以让计算机学习棋盘位置的相对强度。例如，通过查看唐纳德·米奇和他的MENACE程序，您将了解如何使用随机过程学习游戏规则之外的棋盘。有趣的是，虽然这可以在计算机上实现，但只需要几百个彩色珠子和火柴盒，因为游戏空间相对较小，并且还存在各种对称性。
学习了这样一种酷炫的教授计算机玩游戏的方法后，我们可能对回到MinMax应用于井字棋不太感兴趣了。毕竟，MinMax是修剪决策树的相对简单的方法，而井字棋的游戏空间非常小，几乎不需要这种方法。但是，如果我们必须（回到MinMax）...
我们可以研究与下一个游戏相关的“火柴盒”，并使用与每个方格相关联的珠子百分比作为额外因素。然后，我们可以评估传统树，但仅深入进行2或3步移动（通常以损失或平局结束的浅层前瞻深度），并根据简单的-1（输）、0（平局/未知）和+1（赢）等级对每个下一步进行评分。通过将珠子百分比和简单评分组合（例如通过加法，而不是乘法），我们能够有效地使用MinMax，这种方法更类似于在无法评估游戏树到底部的情况下使用它的方式。总之，在井字棋的情况下，只有当我们消除了与完整树的简单评估相关的确定性时（例如帮助我们探索特定效用函数的有效性），MinMax才变得更加有趣。使游戏[数学上]有趣的另一种方法是与犯错误的对手玩...
- mjv
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接