如何为一款井字棋变体游戏创建一个评估函数

Question

我正在开发一款棋盘游戏，它是“井字游戏”（TIC-TAC-TOE）的一个变体。游戏的规则如下：

1. 游戏在一个可变尺寸的 n x n 棋盘上进行。

2. 若一方成功地放置了 k 个连续的记号（X 或 O），则该方获胜，其中 k 可变。

3. 连续的记号可以是横向、纵向或对角线上的 l 个标记，l 是固定的。

4. 若整个 n x n 的棋盘都被占满（无法再加入新的 X 或 O），且没有任何一方成功地放置了 k 个连续的记号，则游戏以平局结束。

我使用了一个 alpha-beta 剪枝算法中的 minmax 方法。这是我第一次写人工智能程序，我不确定如何创建用于该算法的评估函数。我在网上看到了一些示例，它们使用材料加权来评估局面，但我无法应用到我的情况中。目前我正在使用一个随机评估函数，它会返回介于 -100 和 100 之间的值。

    float Conf_eval(Configuration c)
       {
         return (rand()%201)-100;
       }

有没有想法如何评估给定的棋盘配置？

- blackbishop

---

在游戏中，如果找到一个好的启发式方法太难，蒙特卡罗方法似乎是最好的选择（在围棋等棋类游戏中取得了巨大成功）。 - lejlot

Answer 1

这在书中已经详细讨论了《人工智能：一种现代方法》。

此外，基于该系列的优秀实现也可用（这是Java，还有Python，您可以谷歌搜索更多）。包括井字棋（和alpha-beta修剪代理）。

如果您正在使用min-max算法和alpha-beta剪枝，除了您的启发式函数（一个简单的utility-function将胜利分配为1，平局为0，输为-1 - 这些都是min-max扩展树的叶节点），您可以使用已排序的“Actions”列表以获得更好的性能。

要对操作进行排序，您可以优先选择将您的符号(X, O)添加到明显的胜利路径上的操作。这应该最终导致更好的剪枝。

- Reut Sharabani

---

你所说的排序过的“Actions”列表是什么意思？ - blackbishop

极小化极大算法基于行动。您在状态上应用一个操作，结果是一个新状态。如果您按照您认为可以产生最佳结果的方式对“可用操作”列表进行排序，则可以通过更快地获取每个玩家的“好”结果来获得更好的修剪（也就是说，如果您是正确的）。 - Reut Sharabani

谢谢提供的链接。我已经开始构建线性评估函数。 - blackbishop

祝你好运，我不能说自己是个专家，你可能在这里问会有更好的运气：http://cstheory.stackexchange.com/ - Reut Sharabani