极小极大算法：成本/评估功能？

Question

一个学校项目具有我用C编写日期游戏++（例如在 http://www.cut-the-knot.org/Curriculum/Games/Date.shtml ），其中电脑玩家必须实现一个极小的算法与α-β剪枝。至此，我明白目标是什么算法背后最大化潜在收益，同时假定对手将它们最小的条款。

不过，我没有读帮助资源我了解如何设计评价函数的极大极小基地所有它的决定上。所有的例子有过分配给叶节点任意数，但是，我需要实际分配有意义的值的那些节点。

直觉告诉我，这将会是像+1一胜叶节点，-1亏损，但怎么做中间节点评价？

任何帮助，将最理解。

Answer 1

最基本极小仅评估叶节点，标记胜，损失和绘制，并且背这些值了树，以确定所述中间节点的值。在这种博弈树是顽固性的情况下，你需要使用截止深度作为附加参数，以极小的功能。一旦达到的深度，你需要运行某种评价函数的不完整状态。

在一个极小的搜索

大多数评价功能是特定于域，所以找到适合您的特定游戏的帮助是很困难的。只要记住，评估需要返回某种位置是为特定的玩家获胜的百分比预期（通常为最大，虽然使用negamax执行时没有）。几乎所有的研究较少游戏正在酷似另一个更研发的游戏。在非常接近这一个关系与游戏皮卡棒的。使用极小和α，β而已，我猜的游戏是容易处理。

如果你必须创建非终端位置的评价函数，这里是用棍棒游戏，你可以，如果它的日期游戏或没有用处决定的分析一点帮助。

开始寻找一种方式通过看一个终端位置，并且所有这些都可能导致该位置的移动迫使的结果。在棒的游戏中，终端位置与残留在最后一步3个或更少棒。因此立即进入该终端位置的位置离开4粘到你的对手。现在的目标是用4支离开你的对手，不管是什么，这可以从5，6或7支完成被留给你，你想迫使对手让你在那些位置之一。你的对手需要的地方，是为了让你在任5，6或7 8.继续上和这个逻辑和模式很快成为可用。总是由4留下一个数整除你的对手，你赢了，别的，你输了。

这是一个相当琐碎的游戏，但对于确定的启发式方法，因为它可以直接应用到你的任务是什么是非常重要的。自从上次到移动先走了，你只能更改一次1个日期属性，你就知道赢，需要有准确2向左移动...等等。

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

Answer 2

的评价函数的最简单的情况是1一胜，-1为任何非成品位置的损失和0。鉴于你的树是深足，即使这个简单的功能会给你一个不错的球员。对于任何不平凡的游戏，具有很高的分支因子，通常你需要一个更好的功能，具有一定的启发（例如国际象棋，你可以分配权重件和发现的总和，等等）。在日期游戏的情况下，我只想用最简单的评价函数，其中0为所有的中间节点。

作为边注，极大极小不是此特定游戏的最佳算法;但我想你已经知道了。

Answer 3

据我所知日期游戏，你链接到，似乎对于一个球员的唯一可能的结果是赢还是输，没有介于两者之间（请纠正我，如果我错了）。

在这种情况下，它仅分配值1，一个成功的位置（当前播放机到达12月31日）的问题，并且为-1到失去位置的值（其他玩家获得对12月31日）。

您极大极小算法（没有α-β修剪）将看起来像这样：

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