什么algorithm可以用来确定AI的“最佳举动”？

在一个井字游戏的实现中，我猜测挑战性的部分是确定机器玩的最佳动作。

什么是可以追求的algorithm？ 我正在考虑从简单到复杂的实现。 我怎么去解决这个问题的这个部分呢？

维基百科的策略是玩一个完美的游戏（每次赢或平局），看起来像是直截了当的伪代码：

来自维基百科（Tic Tac Toe＃Strategy）

如果玩家从下面的列表中select第一个可用的移动，则可以玩井字游戏（赢得或至less抽取）的完美游戏，如Newell和Simon 1972年的井字游戏程序。[6]

  1. 赢：如果你有两个连续，打第三个连续三个。

  2. 阻挡：如果对手连续有两个，则打第三个阻挡他们。

  3. 叉：创造一个机会，你可以赢得两种方式。

  4. Block Opponent's Fork：

    选项1：连续创build两个强制对手进行防守，只要不会导致对手创build分叉或获胜。 例如，如果“X”有一个angular，“O”有中心，“X”也有对angular，“O”不能为了获胜而打angular。 （在这种情况下玩一个angular落创造了一个“X”分叉）。

    选项2：如果有对手可以分叉的configuration，则阻止该分叉。

  5. 中心：播放中心。

  6. 相反的angular落：如果对手在angular落里，玩对面的angular落。

  7. 空angular落：播放一个空的angular落。

  8. 空空的一面：空荡荡的一面。

认识到一个“叉”的情况看起来可以像所build议的那样以暴力的方式进行。

注意：“完美”的对手是一个不错的运动，但最终不值得“打”。 但是，你可以改变上面的优先事项，给对手人物以特征上的弱点。

你需要什么（对于井字游戏或象Chess这样更加困难的游戏）是minimaxalgorithm ，或者是稍微复杂一点的alpha-beta修剪 。 虽然普通的朴素的极大极小的游戏的search空间和井字游戏一样小。

简而言之，你想要做的不是寻找对你来说最好的结果，而是为了尽可能好的结果。 如果你假设你的对手打得最好，你必须假设他们会采取最糟糕的举动，因此你必须采取最小化他们的最大增益的举措。

生成每一个可能的棋盘，并根据棋盘进行打分的powershell方法在树下进一步生成并不需要太多记忆，特别是一旦你认识到90度棋盘旋转是多余的，就像垂直翻转一样，水平和对angular轴。

一旦你达到这一点，在树形图中有不到1k的数据来描述结果，因此是计算机的最佳select。

-亚当

一个典型的井字游戏应该看起来像这样：

董事会：代表董事会的九要素向量。 我们存储2（表示空白），3（表示X）或5（表示O）。 转动：一个整数，表示游戏即将进行的动作。 第一步将由1表示，最后是9。

algorithm

主algorithm使用三个函数。

Make2：如果电路板的中心平面为空，即电路板[5] = 2，则返回5。 否则，这个函数返回任何非angular点的正方形（2,4,6或8）。

Posswin（p）：如果玩家p在下一步移动中无法获胜，则返回0; 否则返回构成胜利的平方数。 这个function将使程序既能赢得也能阻挡对手获胜。 该function通过检查每一行，每列和对angular线进行操作。 通过将整个行（或列或对angular线）的平方值相乘，可以检查胜利的可能情况。 如果产品是18（3 x 3 x 2），那么X就可以赢。 如果产品是50（5 x 5 x 2），那么O就可以赢。 如果find一个获胜的行（列或对angular线），则可以确定其中的空白方块，并通过该函数返回该方块的数量。

Go（n）：在方块n中移动。 如果Turn为奇数，则此过程将板[n]设置为3;如果Turn为偶数，则将此设置为5。 它也增加了一个。

该algorithm对每一步都有一个内置的策略。 如果它播放X，则进行奇数移动，如果播放O，则进行偶数移动。 

Turn =1 Go(1) (upper left corner). Turn =2 If Board[5] is blank, Go(5), else Go(1). Turn =3 If Board[9] is blank, Go(9), else Go(3). Turn =4 If Posswin(X) is not 0, then Go(Posswin(X)) ie [ block opponent's win], else Go(Make2). Turn =5 if Posswin(X) is not 0 then Go(Posswin(X)) [ie win], else if Posswin(O) is not 0, then Go(Posswin(O)) [ie block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ]. Turn =6 If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2). Turn =7 If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank. Turn =8 if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank. Turn =9 Same as Turn=7.

我用过了。 让我知道你们的感受

由于您只处理可能位置的3x3matrix，因此只需在所有可能的情况下编写search，而不会对计算能力造成任何影响，这一点非常简单。 对于每个开放空间，计算所有可能的结果后，标记空间（recursion地，我会说），然后使用最有可能获胜的移动。

优化这将是一个浪费的努力，真的。 虽然一些容易的可能是：

  • 首先检查其他队伍是否可能获胜，阻止你发现的第一个（如果有2个比赛）。
  • 如果开放的话，总是以中心为中心（以前的规则没有候选人）。
  • 把angular落放在两边（如果以前的规则是空的话）

尝试不使用游戏场。

  1. 赢得（你的双倍）
  2. 如果不是，不输（对手的双）
  3. 如果不是，你已经有一个叉（有一个双重）
  4. 如果没有，如果对手有叉子
    1. search阻塞点可能双和叉（最终胜利）
    2. 如果不是在拦截点寻找叉子（这给对手最可能的失败）
    3. 如果不仅阻挡点（不输）
  5. 如果不search双和叉（最终胜利）
  6. 如果不是只search给予对手最大的损失可能性的叉子
  7. 如果不是只search一个双
  8. 如果不是死胡同，打结，随意。
  9. 如果没有（这意味着你的第一步）
    1. 如果这是游戏的第一步;
      1. 给予对手最大的失败可能性（algorithm只会导致对手失分7的可能性）
      2. 或随意打破无聊。
    2. 如果是游戏的第二招;
      1. 只find没有损失的点（给予更多的select）
      2. 或者在这个列表中find具有最佳获胜机会的点（它可能是无聊的，导致它只在所有的angular落或相邻的angular落或中心）

注意：当你有双重和叉子时，检查你的double是否给对手一个double.if它给，检查你的新的强制性的点是否包含在你的叉子列表中。

你可以让AI在一些示例游戏中学习。 使用监督学习algorithm，以帮助它。

用数字分数排列每个正方形。 如果采用正方形，则转到下一个选项（按排名降序排列）。 你将需要select一个战略（有两个主要的第一个和第三个（我认为）第二个）。 从技术上讲，你可以编程所有的策略，然后随机select一个。 这会让一个不太可预测的对手。

这个答案假定你理解为P1执行完美的algorithm，并讨论如何在普通人类玩家的条件下获得胜利，他们会比其他人更常犯一些错误。

如果两位球员都打得最好，那么当然这场比赛应该以平局结束。 在一个人的水平上，在一个angular落里打P1会产生更多的胜利。 无论出于什么心理上的原因，P2都被认为是在中心打球不是那么重要，这对他们来说是不幸的，因为这是对P1没有制胜的唯一反应。

如果P2在中锋正确阻挡，那么P1应该在对面angular球，因为无论出于什么心理原因，P2都会更喜欢打angular的对称性，这又为他们造成了一个失败的板子。

对于P1可能为开始移动所做的任何移动，如果两个玩家之后都以最佳方式播放，则P2可能产生的移动将为P1创造一个胜利。 从这个意义上说，P1可以在任何地方玩。 边缘移动是最弱的，因为这个移动的最大可能反应产生一个平局，但是仍然有反应会为P1创造一个胜利。

经验上（更确切地说，有趣的是）最好的P1开始移动似乎是第一个angular落，第二个中心和最后一个边缘。

您可以亲自或通过GUI添加下一个挑战，而不是显示板。 一个人肯定能够记住所有的状态，但是增加的挑战导致了对称板的偏好，这样就不需要太多的努力来记忆，导致我在第一个分支中列出的错误。

我知道，在派对上我很开心。

Interesting Posts