极小极大算法：成本/评估函数？

Question

一个学校项目要求我使用C++编写一个日期游戏（示例网址：http://www.cut-the-knot.org/Curriculum/Games/Date.shtml），其中计算机玩家必须实现带有Alpha-Beta剪枝的Minimax算法。到目前为止，我理解了算法的目标是最大化潜在收益，同时假设对手会尽量减少这些收益。

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

直觉告诉我，赢得叶节点应该是+1，输掉应该是-1，但中间节点如何评估呢？

非常感谢您提供任何帮助。

- Dave

Answer 1

最基本的极小极大算法只评估叶节点，标记胜利、失败和平局，并将这些值传递到树中确定中间节点的值。如果游戏树无法处理，则需要使用截止深度作为极小极大函数的附加参数。一旦达到深度，您需要针对不完整状态运行某种评估函数。

在极小极大搜索中，大多数评估函数都是特定于领域的，因此找到特定游戏的帮助可能很困难。只需记住，评估需要返回某种百分比期望，表明特定玩家获胜的位置（通常是max，但不使用negamax实现时）。几乎任何未经研究的游戏都会与另一个更经过研究的游戏非常相似。这个游戏非常类似于pickup sticks游戏。仅使用极小极大和alpha-beta，我猜测游戏是可处理的。

如果您必须为非终端位置创建评估函数，那么这里有一些有关棍子游戏分析的小提示，您可以决定它是否对日期游戏有用。

开始寻找一种方法来强制结果，查看终止位置和所有可以导致该位置的移动。在棍棒游戏中，终止位置是在最后一次移动时剩下3根或更少的棍子。因此，紧接着该终止位置的位置就是留给你的对手4根棍子。现在的目标是无论如何都要让你的对手剩下4根棍子，这可以从剩下5、6或7根棍子的任一状态实现，而且你希望迫使对手将你留在这些位置之一。你的对手需要处于8的位置才能让你处于5、6或7的位置。继续这样推理下去，很快就会出现一种模式。总是让你的对手剩下一个可被4整除的数字，你就赢了，否则你就输了。

这是一个相当琐碎的游戏，但确定启发式的方法非常重要，因为它可以直接应用于你的任务。由于最后一步走的人先走，而你只能每次改变1个日期属性，所以你知道要赢必须剩下正好2步……等等。

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

- Nick Larsen

Answer 2

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

另外，极小化极大算法不是这个特定游戏的最佳算法；但我猜你已经知道了。

- Igor Krivokon

Answer 3

从我理解你提供的日期游戏，似乎玩家唯一可能的结果是赢或输，没有中间状态（如果我错了，请纠正我）。

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

您的极小化极大算法（不带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

- MAK

---

你正在描述Negamax算法。 我唯一的批评是，如果没有定义“increase_month”和“increase_day”，你的算法就没有多大意义。 你可以将天数增加到当前日期与31天之间的任何一天（取决于当前月份），并且可以将月份增加到任何你想要的月份（取决于日期）。 对于每个移动，可能的下一个状态远远不止两个。 - Nick Larsen

@NickLarsen：确实，对于我们如何允许增加问题陈述中的日期并不清楚。我正在更新我的答案。谢谢。 - MAK