8

我知道这已经被问了很多，我已经搜索了其他代码，但我所看到的大部分内容似乎都不是完美无缺的（永远不会丢失），而且简单、优雅和高效。而且我无法决定哪种类型的解决方案适合该描述。

我见过的解决方案是：

(1) 使用带有 alpha-beta 剪枝的 minimax。这对我来说似乎很复杂，对于这样一个简单的游戏来说可能是不必要的？是不是太复杂了？如果不是，我需要做很多硬编码还是我误解了算法？

(2) 使用维基百科的伪代码策略编写代码......我不完全确定如何实现这一点。例如，它只是说“检查分叉”。这些检查中的大多数是否会通过拥有一系列winningLines并检查它们是否会被填写或类似的东西来完成？如果没有，有人可以给我关于什么数据结构的提示或关于如何实现伪代码中提出的检查的任何基本提示：http ://en.wikipedia.org/wiki/Tic-tac-toe#Strategy 。我还看到算法为“X”方和“O”方提供数值，然后使用总和来决定获胜者，但我不明白为什么这特别有用。

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

4

2 回答 2

9

老实说，在处理 AI 和启发式算法时，最简单的任务会很快变得复杂。极小极大方法将为您提供最佳结果，考虑到您正在实施人工智能这一事实，这应该不会太难。这是一个基于 2 玩家回合的游戏逻辑的既定标准。

看看这个网站......它对井字游戏 AI 和 minimax 实现提供了一些很好的见解。

http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

编辑：

注意到有人写了“蛮力”……这最终将成为实现极小极大启发式算法的一种低效方式。根据其他玩家的最后一步迭代每一个可能的移动只是实现启发式的另一种方式......除了在我看来，它似乎是更多的工作。Minimax 的实现将简单而有效。

编辑2：

“更简单的实现”是相对的。Minimax 是标准，正如我在评论中所说，您可以操纵启发式以适应您正在寻找的情况......

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

接受建议，看看你的游戏实现，然后看看最适合你的！

对一个人来说简单的事情，对另一个人来说可能很复杂。我只是想为您提供选择，而极小极大非常可靠。也许尝试调整它以满足您的需求。

编辑3：

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

于 2013-04-01T23:25:25.613 回答
3

使用您选择的格式将此图像“编码”为一组动作。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();
    }
}
于 2013-04-01T23:29:28.447 回答