极小极大算法

Question

我有一个关于极小极大算法一个简单的问题：例如对于井字棋游戏，我该如何确定效用函数是为每个玩家戏？它不会自动做的，不是吗？我必须硬编码在游戏中的价值，它本身不能学他们，不是吗？

Answer 1

没有，一个极小不学习。这是一个强力树搜索的智能版本。

Answer 2

通常，您将直接实现的效用函数。在这种情况下，算法将没有学会如何玩游戏，它会使用你已经明确在实施硬编码的信息。

然而，这将有可能使用遗传编程（GP）或一些等同技术自动推导出效用函数。在这种情况下，你就不必编码任何明确的战略。相反，进化会发现自己的玩游戏好办法。

您既可以结合您的极小代码和GP代码到一个单一的（可能很慢）自适应程序，或者你可以先运行GP，找到一个很好的效用函数，然后这个函数只是添加到您的极小代码为你将任何手工编码的功能。

Answer 3

井字棋是小到足以运行游戏的结束，并指定1取胜，0为平局和-1输

否则必须提供一种启发式决定的位置的值的函数。在国际象棋例如一个很大的因素是材料的价值，而且也谁控制中心或如何容易地将片可以移动。

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

Answer 4

如何确定每个发挥效用函数？的

小心地;-)此文章显示了如何略有瑕疵的评价函数（一个为前。它要么不走“深”，足以在可能的pLys，或者其中一个出现故障的树放眼望去捕捉到一些板位置的相对车力量）结果在一个整体弱算法（一个失去更经常）。

它本身不能学他们，不是吗？的

没有，它没有。有办法，然而，让计算机学会董事会职位的相对强度。例如，通过寻找到的唐纳德Mitchie和他MENACE程序 你会看到一个随机过程如何可以用来学习板没有任何的的先验的知识，而是游戏规则。有趣的是，尽管这可以在计算机上实现，几百彩色珠子和火柴盒是所有需要，由于游戏空间的规模相对较小，而且由于各种对称性。

学习教学电脑怎么玩的这么酷的方式后，我们可能不那么感兴趣应用于井字棋回去MINMAX。毕竟 MINMAX是修剪决策树的一个比较简单的方法，它几乎不需要用井字棋的小游戏空间。但是，如果我们必须;-) [返回MINMAX] ...

我们可以看看下一个游戏相关的（即不是在所有深去）的“火柴盒”，并使用与每平方米的珠的百分比，作为附加因素。然后，我们可以评估一个传统的树，但只打算，说深2或3步（浅前瞻深度通常会结束通常是在损失或平）和简单的基础上，各评级下一步-1（损失），0（画/未知）+1（WIN）的评级。届时（当然不是通过乘以比如说此外，）结合珠百分比和简单的评价，我们能够有效地使用MINMAX的方式是更接近它的情况下使用的方式，当它是不可能的，以评估博弈树到其端部。

底线：在井字棋的情况下，MINMAX仅变得更加有趣（例如在帮助我们探索一个特定的效用函数的有效性）时除去了游戏的确定性性质，用简单的相关联评估完整的树。使得游戏的另一种方式[数学]有趣的是，与对手，这使得失误打...