井字棋的极小化极大算法

Question

我正在尝试用简单的极小化极大算法解决井字游戏。虽然简单，但应该涵盖很多语言。我目前有以下内容：

棋盘表示为一个包含9个（未绑定）变量的数组，这些变量设置为“x”或“o”。

然后胜利条件基本上是：对于所有八种情况，“win(Player，[X1，X2，X3 | _])：- X1 == Player，X2 == Player，X3 == Player。”等等。平局只是一个简单的检查是否所有变量都已绑定。

移动子句也很简单：对于所有可能的位置，“move(Player，[X | _]，0，0)：- var(X)，X = Player。”（我将在稍后的程序中保留代码重用 :)）。

现在，我可以通过简单的回溯生成所有可能的移动：“move(Player，Board，X，Y)。”这基本上应该是我需要进行极小化极大化的所有内容（显然，一个简单的实用程序函数，如果计算机获胜则返回1，在平局时返回0，在人类获胜时返回-1，那很容易）。我只是不知道如何实现它，我在网上找到的所有示例都相当复杂且解释不清。

请注意，我对n ^ 2或更糟的运行时行为感到满意-这确实与效率无关。是的，我知道如何在lisp、python、java中编写极小化极大化算法-只是不知道如何将该代码“移植”到prolog。

- Voo

---

请参见 http://stackoverflow.com/a/8436788/502187。 - user502187

Answer 1

好的，既然您已经有了move/4谓词，我会从收集所有可能的移动开始：

findall(X-Y, move(Player, Board, X, Y), Moves)

然后就是评估每个移动了，对吧？为此，我会编写一个名为board_player_move_value/4的谓词，它给定一个棋盘和一个给定玩家的移动，确定这个移动对于该玩家来说有多好。这个谓词可能依赖于在这个阶段其他玩家可能采取的进一步移动，这就是最小最大算法发挥作用的地方。例如，如果这个移动赢得了比赛，那么这是一个好的移动。如果其他玩家可以在下一步获胜，那么这是一个糟糕的移动等等。我会使用这个谓词来构建形式为Value-Move的术语集合，使用keysort/2进行排序，然后选择其中一个具有最佳值的移动，其中“最佳”取决于我是要为最小化还是最大化玩家寻找移动。

- mat

---

啊，findall返回所有可能的移动列表，这已经很有帮助了。我的问题是我不知道如何实现最大值的缩减。基本上，在lisp中，max-value看起来像这样：(if (terminalp state) (utility state)(reduce #'max (mapcar #'min-value (successors state))))（我希望即使没有深入的lisp知识，这也相当清楚，只是最简单的可能的minimax版本，没有任何启发式算法）。if语句的基本情况很容易处理，(successors state)部分使用findall就可以了，但我不知道如何在该列表上执行map和reduce操作。 - Voo

你可以轻松地将每个Lisp函数翻译成一个Prolog谓词，只需添加一个额外的参数来保存函数的返回值，这样代码看起来会很相似：（terminal（State） - > state_utility（State，Utility）; state_successors（State，Succs），maplist（min_value，Succs，Mins），max_list（Mins，Utility））。这是可能的，因为函数只是关系的一种特殊情况。 - mat