极大极小为井字棋(minimax for tic-tac-toe)

我试图解决井字棋有一个简单的算法，极大极小。 很简单，但应涵盖了很多的语言。 我到目前为止有：

该板被表示为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或更糟糕的运行时行为 - 这真的不是效率。 是的，我知道如何在口齿不清，蟒蛇，Java编写极小 - 只是不知道如何“口”该代码Prolog的。

Answer 1:

那么，你已经在你的移动/ 4谓词，我会收集所有那些可能的行动开始：

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

然后，它只是评估每项举措的事，不是吗？ 为此，我会写这样一个谓词board_player_move_value/4 ，给定板和指定玩家的一招，确定移动有多好，这个球员。 正是这种谓词可能取决于在这个阶段进一步举动，是可能的（对于其他播放器），而这正是极小发生。 例如，如果这一招赢得了比赛，这是一个很好的举措。 如果其他球员能够在接下来的举动赢了，这是我会用这个谓词来构建形式价值移动的术语的集合不好动等，使用keysort / 2对它们进行排序，然后挑选的招式之一最好的价值，其中“最佳”取决于我是否试图找到的最小化或最大化的球员转会。

文章来源: minimax for tic-tac-toe