6

一个学校项目让我用 C++ 编写一个日期游戏（例如http://www.cut-the-knot.org/Curriculum/Games/Date.shtml），其中计算机玩家必须使用 alpha-beta 修剪实现 Minimax 算法. 到目前为止，我理解算法背后的目标是最大化潜在收益，同时假设对手会缩小它们。

但是，我阅读的所有资源都没有帮助我理解如何设计 minimax 所基于的所有决策的评估函数。所有示例都为叶节点分配了任意数字，但是，我需要为这些节点实际分配有意义的值。

直觉告诉我，获胜叶节点的值类似于 +1，失败的叶节点为 -1，但中间节点如何评估？

非常感激任何的帮助。

4

3 回答 3

5

最基本的 minimax 只评估叶节点，标记获胜、失败和平局，并将这些值备份到树上以确定中间节点值。在博弈树难以处理的情况下，您需要使用截止深度作为您的极小极大函数的附加参数。一旦达到深度，您需要对不完整状态运行某种评估函数。

minimax 搜索中的大多数评估函数都是特定于域的，因此为您的特定游戏寻找帮助可能很困难。请记住，评估需要返回某种特定玩家获胜的位置百分比期望值（通常是最大值，尽管在使用 negamax 实现时不是）。几乎任何研究较少的游戏都将与另一个研究较多的游戏非常相似。这与游戏拾音器密切相关。仅使用 minimax 和 alpha beta，我猜这个游戏很容易上手。  

如果你必须为非终端位置创建一个评估函数，这里有一点帮助分析棍子游戏，你可以决定它是否对日期游戏有用。

通过查看最终位置和所有可能导致该位置的移动，开始寻找一种强制结果的方法。在棍子游戏中，终端位置是在最后一步中剩余 3 个或更少的棍子。因此，立即进入最终位置的位置将 4 棒留给您的对手。现在的目标是无论如何都给你的对手留下 4 根棍子，这可以通过留给你 5、6 或 7 根棍子来完成，并且你想迫使对手将你留在其中一个位置。为了让你进入 5、6 或 7，你的对手需要的位置是 8。不断地继续这个逻辑，一个模式很快就会变得可用。总是给你的对手一个能被 4 整除的数字，你赢了，否则，你输了。  

这是一个相当琐碎的游戏，但确定启发式的方法很重要，因为它可以直接应用于您的作业。由于最后一步在前，并且您一次只能更改 1 个日期属性，因此您知道要赢，还需要恰好剩下 2 步……以此类推。

祝你好运，让我们知道你最终做了什么。

于 2010-06-28T19:09:11.170 回答
3

评估函数的最简单情况是 +1 表示获胜，-1 表示失败，0 表示任何未完成的位置。鉴于你的树足够深，即使是这个简单的函数也会给你一个很好的播放器。对于任何具有高分支因子的非平凡游戏，通常您需要一个更好的函数，并带有一些启发式（例如，对于国际象棋，您可以为棋子分配权重并找到总和等）。在日期游戏的情况下，我将只使用最简单的评估函数，所有中间节点都为 0。

附带说明一下，极小极大并不是这个特定游戏的最佳算法。但我想你已经知道了。

于 2010-06-08T23:55:03.710 回答
0

根据我对您链接到的日期游戏的了解，似乎玩家唯一可能的结果是赢或输，中间没有（如果我错了，请纠正我）。

在这种情况下，只需将值 1 分配给获胜位置（当前玩家到达 12 月 31 日），将值 -1 分配给失败位置（其他玩家到达 12 月 31 日）。

您的 minimax 算法（没有 alpha-beta 修剪）看起来像这样：

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome
于 2010-06-28T20:16:58.647 回答