简单的井字棋人工智能

Question

我知道这个问题已经被问了很多次，我也查找了其他代码，但是大部分看起来都不完美（从不输）并且不够简洁、优雅和高效。我无法决定哪种解决方案适合这种描述。

我看到的解决方案有：

(1) 使用带有alpha-beta剪枝的minimax算法。对于这样一个简单的游戏来说，这似乎过于复杂了吧？如果不是，那么我需要进行大量的硬编码或者我误解了算法吗？

(2) 使用维基百科上的伪代码策略编写代码...我不确定如何实现这个。例如，它只是说“检查叉子”。大多数这些检查是否可以通过拥有一组获胜线并检查它们是否填充来完成？如果不是，有人能给我提示吗？关于如何实现此处伪代码中提出的检查的数据结构或任何基本提示：http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy 。我还看到了将“X”方块和“O”方块赋予一个数字值，然后使用总和来决定胜者的算法，但我不明白为什么这特别有用。

还有其他合理的解决方案吗？

- user1136342

---

对于这样一个小的游戏树，直接暴力求解即可。模拟每种可能的游戏所需的时间非常短。 - Dave

翻译：看起来并不完美（总是赢）= 看起来正常。我总是在井字游戏中获胜，或者最坏的情况下打成平局。任何聪明人都会有同样的结果。这就是为什么10岁后没有人玩井字游戏的原因。当没有人赢时，这并不好玩。 - nathan hayfield

另外，是的，“总是赢”不是一个有效的要求（永远不是）。想象一下你的算法自己对弈。 - Dave

那么你可能应该编辑你的问题。 - Nick Mitchinson

Minimax算法并不需要很复杂，对于这样一个小游戏来说，剪枝也并不是必须的。例如，可以参考这个实现。 - trincot

Answer 1

老实说，当处理人工智能和启发式时，最简单的任务很快就会变得复杂。使用极小化极大算法会给您带来最佳结果，考虑到您正在实现人工智能，这应该不难。它是一种已经建立的标准，适用于两个玩家轮流进行游戏的逻辑。

查看这个网站...它提供了有关井字棋人工智能和极小化极大算法实现的有益见解。 http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html 编辑：

注意到有人写了“蛮力算法”...这将成为实现极小化极大算法中涉及的启发式的低效方法。基于其他玩家上一步移动迭代遍历每个可能的移动只是另一种实现启发式的方式..除了在我看来，更多的工作。极小化极大算法实现将是简单而有效的。

编辑2：

“更简单的实现”有点相对性。极小化极大算法是标准的，正如我在评论中所说，您可以操纵启发式以适应您正在寻找的情况...

我希望我能告诉您最简单的方法，但是有很多变量取决于您在代码中对游戏的实现。

接受建议，查看您的游戏实现，然后看看哪种最适合您！

对于一个人来说简单的东西对于另一个人来说可能很复杂。我只是想给您提供选项，极小化极大算法非常可靠。也许尝试调整它以适应您的需求。

编辑3：

如果您需要更多指导，请告诉我。我很乐意帮忙。

- AnxGotta

---

请明确一下，您是在说极小化算法实际上比检查维基百科条目中的所有情况更简单，还是说它不会更复杂，同时还允许更高效和优雅的代码？ - user1136342

我是说如果你想要动态玩法，可以使用极小化极大算法。在井字棋的情况下，你可以硬编码这些选项并以“蛮力”的方式跟随它们，这样就可以保证在某些情况下获胜。我是说如果你想要一个通用的启发式来处理这些情况，你可以使用带有特定启发式的极小化极大算法。你可以将那些“明确获胜”的情况包含在启发式中，以确保它们被覆盖，然后在需要时退而求其次选择更一般的选项。我认为包含两者的混合启发式会为你提供最好的服务。 - AnxGotta

“在某些情况下保证获胜”是什么意思？难道不应该在所有情况下都保证获胜吗？ - user1136342

是的。如果我没有表达清楚，对不起。语义... - AnxGotta

Answer 2

使用您选择的格式将此图像“编码”成一组动作。 AI将始终获胜或平局。

例如，您可以按以下方式进行编码：

var turns = {
  "mefirst":{
    "move":0,
    "next":[
      null,
      {
        "move":4,
        "next":[
          null,
          null,
          {"move":8}, // win
          {"move":8}, // win
          null,
          {"move":8}, // win
          {"move":8}, // win
          {"move":8}, // win
          {
            "move":6,
            "next":[
              null,
              null,
       /* AND SO ON... */
    ]
  }
};

然后，您可以从以下开始：

if( ai_goes_first) {
    game = turns.mefirst;
    makeMove(game.move);
}
else game = turns.themfirst;
playerTurn();

playerTurn是类似于以下内容的变量：

function playerTurn() {
    when player clicks a valid squeare {
        game = game.next[chosenSquare];
        makeMove(game.move);
        if( game.next) playerTurn();
    }
}

- Niet the Dark Absol