我正试图用一个简单的minimax算法来解决井字游戏.简单,但应该涵盖很多语言.到目前为止我所拥有的:
该板表示为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.
好吧，由于您已经有了 move/4 谓词，我将从收集所有可能的移动开始：
findall(X-Y, move(Player, Board, X, Y), Moves)
然后就是评估每一步的问题，不是吗？为此，我会写一个这样的谓词board_player_move_value/4，给定一个棋盘和给定玩家的一步棋，确定该棋手的棋步有多好。正是这个谓词可能取决于此阶段（对于其他玩家）可能的进一步移动，这就是极小极大发生的地方。例如，如果这一步棋赢得了比赛，那么这一步棋就是好棋。如果其他玩家可以在下一步中获胜，那么这是一个糟糕的举动等。我将使用此谓词来构建 Value-Move 形式的术语集合，使用 keysort/2 对它们进行排序，然后选择其中一个动作具有最佳价值，其中“最佳”取决于我是否试图为最小化或最大化玩家找到一个动作。