6

我正在尝试用一个简单的极小极大算法来解决井字游戏。简单，但应该涵盖很多语言。到目前为止我所拥有的：

该板表示为 9 个（未绑定）变量的数组，这些变量设置为x或o。

获胜条件基本上是：win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player.所有八个变体的等等。draw 只是一个简单的检查是否所有变量都被绑定。

move 子句也很简单：move(Player, [X|_], 0, 0) :- var(X), X=Player.，同样适用于所有可能的位置（我将为以后的程序保留代码重用 :) ）。

现在我可以通过简单的回溯生成所有可能的移动：move(Player, Board, X, Y).这基本上应该是我所需要的 minimax （显然是一个简单的实用函数，如果计算机获胜则返回 1，如果平局则返回 0，如果人类获胜则返回 -1，这就是简单的）。我只是不知道如何实现它，而且我在网上找到的所有示例都相当复杂并且没有得到很好的解释。

请注意，我对 n^2 或更差的运行时行为很好 - 这实际上与效率无关。是的，我确实知道如何在 lisp、python、java 中编写 minimax - 只是不知道如何将该代码“移植”到 prolog。

4

1 回答 1

2

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

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

然后只是评估每一步的问题，不是吗？为此，我会写一个这样的谓词board_player_move_value/4，给定一个棋盘和一个给定玩家的移动，确定该移动对这个玩家有多好。正是这个谓词可能取决于在这个阶段（对于其他玩家）可能的进一步移动，这就是极小极大发生的地方。例如，如果这一招赢得了比赛，那就是一个好招。如果另一个玩家可以在下一步中获胜，那么这是一个糟糕的举动等等。我会使用这个谓词来构建一个 Value-Move 形式的术语集合，使用 keysort/2 对它们进行排序，然后选择其中一个动作具有最佳价值，其中“最佳”取决于我是否正在尝试为最小化或最大化玩家找到移动。

于 2012-04-20T15:48:45.870 回答