井字棋评分板算法

Question

我已经用AI实现了井字游戏，但现在我面临一个问题，如何评估井字游戏的棋盘？也许一开始我应该描述它应该如何工作：

1. 我们有n个井字游戏棋盘（具有不同的变体）
2. 我们的AI应该评估哪个棋盘是最好移动的/对手最差的
3. AI通过minimax算法计算移动（完成）

问题在于第二步。有没有办法“评估”一个棋盘？

我想说我不希望任何人为我编写代码，只是帮我找到算法或其他东西：）

感谢大家的帮助！

编辑#1

好的，我有一个minimax可以玩棋盘，但如何评估许多棋盘并选择最佳的呢？也许我没有清楚地表达我的意思，所以我会展示它。

e = 空

 *   x | e | e      e | o | e
 *  ---+---+---    ---+---+---
 *   x | e | e      e | o | e
 *  ---+---+---    ---+---+---
 *   o | e | e      x | x | e

现在，我的极小化极大算法实现只是告诉我应该把标记（比如o）放在哪里，但我需要告诉它放在哪个棋盘上，那么如何使用它来评估整个棋盘以选择放在哪里？

极小化极大算法代码：

minimax : function(tempBoard,depth){
    if (CheckForWinner(tempBoard) !== 0)
        return score(tempBoard, depth);
    depth+=1;
    var scores = new Array();
    var moves = new Array();
    var availableMoves = Game.emptyCells(tempBoard);
    var move, possibleGame, maxScore, maxScoreIndex, minScore,minScoreIndex;

    for(var i=0; i < availableMoves.length; i++) {
        move = availableMoves[i];
        possibleGame = Game.getNewBoard(move,tempBoard);
        scores.push(Ai.minimax(possibleGame, depth));
        moves.push(move);
        tempBoard = Game.undoMove(tempBoard, move);
    }
    if (Game.turn === "ai") {
        maxScore = Math.max.apply(Math, scores);
        maxScoreIndex = scores.indexOf(maxScore);
        choice = moves[maxScoreIndex];
        return scores[maxScoreIndex];

    } else {
        minScore = Math.min.apply(Math, scores);
        minScoreIndex = scores.indexOf(minScore);
        choice = moves[minScoreIndex];
        return scores[minScoreIndex];
    }
}

- Direkts

---

尝试了解MINIMAX算法，并根据你的需求进行修改！ - N00b Pr0grammer

你确定这个方法返回的是玩家应该下棋的位置，而不仅仅是在哪个棋盘上吗？我指的不是棋盘，而是具体的位置。从我看到的代码来看，你只是返回了每个玩家的最佳得分 return scores[minScoreIndex] 和 return scores[maxScoreIndex]，但并没有返回玩家应该下棋的位置以达到这个得分。 - Omar Sharaki

Answer 1

井字棋的移动评分可以使用极小化极大算法进行。该算法旨在执行要评估的移动，切换到对手的视角（对手反过来也试图做最好的移动），并递归地评估移动，直到其中一名玩家获胜（这意味着已经到达了游戏树的叶子节点）。

尽管实现基本版本的此算法并不难，但理解方法至关重要；请注意，“人工智能”基本上由假设使用所有可能的移动玩整个游戏组成 - 它不是启发式而是确切的算法。使用Alpha-Beta剪枝可以改进它，以节省不必要的游戏树子树进行评估。

- Codor

---

可能的游戏数量不到9！= 362880。人们可能会想知道修剪是否有任何用处。 - user1196549

@YvesDaoust 或许这并没有什么用，我只是为了完整性而加上了这个备注。想象一下在极其有限的硬件上运行Minimax算法。 - Codor

Answer 2

以下是一种公式，可用于评估板子：

value = (10 * x3 + 3 * x2 + x1) - (10 * o3 + 3 * o2 + o1)

其中：

• xN => 具有N个x并且没有o的行/列/对角线数
• oN => 具有N个o并且没有x的行/列/对角线数

这假定max-player是X。如果不是，可以更改符号。

- vish4071

---

谢谢，@vish4071，非常好的回答！只有一件事：x1 = 有N个x且没有o的行数x2 = 有N个x且没有o的列数x3 = 有N个x且没有o的对角线数o1 = 有N个o且没有x的行数o2 = 有N个o且没有x的列数o3 = 有N个o且没有x的对角线数这正确吗？ - Direkts

жҳҜзҡ„гҖӮе®һйҷ…дёҠжӣҙеғҸжҳҜ x1 = еңЁиҜҘиЎҢдёӯжңү1дёӘxдё”жІЎжңүoзҡ„иЎҢж•° зӯүзӯү... иҝҷжҳҜеӣ дёәеҰӮжһңеңЁиҜҘиЎҢдёӯжңү oпјҢеҲҷж°ёиҝңдёҚеҸҜиғҪйҖҡиҝҮеңЁиҜҘиЎҢдёҠз”»еҮәжқҘиҺ·иғңгҖӮ - vish4071

那么 x3 = 在没有 o 的情况下，有 3 个 x 的行数是多少？ - Direkts

是的...基本上，游戏到这里就结束了。我在之前实现井字棋机器人的一个版本中使用了这个公式。基本上，如果你的得分>10，则存在必胜的情况；同样地，如果得分<-10，则你必败。虽然它是足够的条件，但并不是必要条件。 - vish4071