我正在尝试用简单的极小极大算法来解决井字游戏。简单,但应该涵盖很多语言。到目前为止我所拥有的:
该板表示为 9 个(未绑定)变量的数组,这些变量可以设置为x
or o
.
获胜条件基本上是:win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player.
等等所有八个变体。 draw 只是一个简单的检查是否所有变量都已绑定。
移动条款也很简单:move(Player, [X|_], 0, 0) :- var(X), X=Player.
,再次针对所有可能的位置(我将为以后的程序保留代码重用:))。
现在我可以通过简单的回溯生成所有可能的移动:move(Player, Board, X, Y).
这基本上应该是我对 minimax 所需要的全部内容(显然是一个简单的实用函数,如果计算机获胜则返回 1,如果平局则返回 0,如果人类获胜则返回 -1,这很容易)。我只是不知道如何实现它,而且我在网上找到的所有示例都相当复杂并且没有得到很好的解释。
请注意,我可以接受 n^2 或更糟糕的运行时行为 - 这实际上与效率无关。是的,我确实知道如何用 lisp、python、java 编写极小极大 - 只是不知道如何将该代码“移植”到序言中。