7

我有一个关于 Minimax 算法的简单问题：例如对于井字游戏，我如何确定每个玩家玩的效用函数？它不会自动执行此操作，是吗？我必须对游戏中的值进行硬编码，它不能自己学习它们，是吗？

4

4 回答 4

10

不，MiniMax 不会学习。它是蛮力树搜索的更智能版本。

于 2009-10-19T14:00:39.753 回答
3

通常，您将直接实现实用程序功能。在这种情况下，算法不会学习如何玩游戏，它会使用您在实现中明确硬编码的信息。

但是，可以使用遗传编程(GP) 或一些等效技术来自动导出效用函数。在这种情况下，您不必编码任何显式策略。相反，进化会发现自己玩游戏的方式。

您可以将您的极小极大代码和 GP 代码组合成一个（可能非常慢）自适应程序，或者您可以先运行 GP，找到一个好的实用函数，然后将这个函数添加到您的极小极大代码中，就像您做任何手一样-编码函数。

于 2009-10-21T22:19:02.630 回答
2

Tic-Tac-Toe 足够小，可以将游戏运行到最后，并指定 1 为赢，0 为平局，-1 为输。

否则，您必须提供一个以启发式方式确定位置值的函数。例如，在国际象棋中，一个重要因素是材料的价值，还有谁控制中心或棋子移动的容易程度。

至于学习，你可以在位置的不同方面添加权重因素，并尝试通过反复玩游戏来优化这些因素。

于 2009-10-19T14:05:07.777 回答
2

如何确定每个游戏的效用函数？

小心 ;-)本文展示了一个有轻微缺陷的评估函数（例如，一个在可能的层数树中向前看时不够“深入”，或者未能捕捉到某些板的相对强度位置）导致整体弱算法（更经常丢失的算法）。

它不能自己学习它们，是吗？

不，它没有。然而，有一些方法可以让计算机了解棋盘位置的相对强度。例如，通过研究Donald Mitchie 和他的 MENACE 程序，您将了解如何使用随机过程来学习棋盘，而无需任何先验知识，而无需了解游戏规则。有趣的是，虽然这可以在计算机中实现，但由于游戏空间相对较小，而且由于各种对称性，所以只需要几百个彩色珠子和火柴盒。

在学习了这种教计算机如何玩的很酷的方法之后，我们可能不会像应用井字游戏那样对回到 MinMax 感兴趣。毕竟MinMax 是一种相对简单的修剪决策树的方法，在井字游戏的小游戏空间中几乎不需要这种方法。但是，如果我们必须 ;-) [回到 MinMax]...

我们可以查看与下一场比赛相关的“火柴盒”（即根本不深入），并使用与每个方格相关的珠子百分比作为附加因素。然后，我们可以评估一棵传统的树，但只进行 2 或 3 次深度移动（通常以失败或平局告终的浅预测深度）并根据简单的 -1（损失），0（平局/未知），+1（获胜）评级。然后通过结合珠子百分比和简单评级（比如加法，当然不是乘法），我们能够以更类似于在无法评估的情况下使用它的方式有效地使用 MinMax游戏树到尽头。

底线：在井字游戏的情况下，只有当我们消除游戏的确定性时，MinMax 才会变得更有趣（例如帮助我们探索特定效用函数的有效性），这与简单的评估相关联树。另一种使游戏[数学上]有趣的方法是与犯错误的对手一起玩……

于 2009-10-19T14:06:09.813 回答