我正在尝试用简单的极小化极大算法解决井字游戏。虽然简单,但应该涵盖很多语言。我目前有以下内容:
棋盘表示为一个包含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。
棋盘表示为一个包含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。