井字游戏的minimax [英] minimax for tic-tac-toe

问题描述

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

I'm trying to solve tic-tac-toe with a simple minimax algorithm. Simple, but should cover a lot of the language. What I have so far:

董事会代表着9个（未绑定）变量的数组，这些变量都设置为 x 或 o 。

The board is represented as an array of 9 (unbound) variables, that are either set to x or o.

赢的条件基本上是： win（Player，[X1，X2，X3 | _]）：-X1 == Player，X2 == Player，X3 == Player。等等，用于所有八个变体。

The win condition is then basically: win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player. etc for all eight variants. draw is just a simple check whether all variables are bound.

移动子句也很简单： move（Player，[X | _]， 0，0）：-var（X），X = Player。，再次对所有可能的位置（我将代码重用打开供以后的程序使用：））。

The move clauses are also simple: move(Player, [X|_], 0, 0) :- var(X), X=Player., again for all possible positions (I'll leave code reuse open for a later program :) ).

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

Now I can generate all possible moves by simple backtracking: move(Player, Board, X, Y). which should basically be all what I need for minimax (obviously a simple utility function that returns 1 if the computer wins, 0 in case of a draw and -1 if the human wins, that's easy). I just have no idea how to implement it and all examples I find on the net are rather complicated and not well explained.

请注意，我对n ^ 2或更糟糕的运行时行为-这实际上与效率无关。是的，我确实知道如何在Lisp，Python，Java中编写minimax-只是不知道如何将代码移植到序言中。

Note I'm fine with n^2 or worse runtime behavior - it's really not about efficiency. And yes I do know how to write minimax in lisp, python, java - just no idea how to "port" that code to prolog.

推荐答案

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

Well, as you already have your move/4 predicate, I would start with collecting all moves that are possible:

findall（ XY，移动（玩家，棋盘，X，Y），移动）

然后简单地评估每个移动是是吗？为此，我将编写一个像 board_player_move_value / 4 这样的谓词，给定一个棋盘和一个给定玩家的移动，它确定该玩家的移动情况。该谓词很可能取决于在此阶段可能发生的（对另一位玩家而言）进一步的移动，而这正是发生最小最大化的地方。例如，如果此举赢得了比赛，那将是一个很好的举动。如果其他玩家可以在下一步行动中获胜，那将是一个糟糕的行动，等等。我将使用此谓词构建Value-Move形式的条款集合，使用keysort / 2对其进行排序，然后选择其中一项行动具有最佳价值的最佳，取决于我是否要寻找最小化或最大化玩家的举动。

And then it's simply a matter of assessing each move, isn't it? For that I would write a predicate like board_player_move_value/4 that, given a board and a move of a given player, determines how good the move is for this player. It is this predicate that likely depends on further moves that are possible (for the other player) at this stage, and this is where minimax takes place. For example, if this move wins the game, it's a good move. If the other player can win in the next move, it's a bad move etc. I would use this predicate to build a collection of terms of the form Value-Move, use keysort/2 to sort them, and then pick one of the moves with the best value, where "best" depends on whether I'm trying to find a move for the minimizing or the maximizing player.

这篇关于井字游戏的minimax的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！