2

我做了一个井字游戏 AI 给定每个棋盘状态，我的 AI 将返回 1 个确切的移动位置。我还制作了一个函数，可以循环使用 AI 制作的所有可能的游戏

所以它是一个递归函数，让 AI 为给定的棋盘移动，然后让其他游戏做出所有可能的移动，并为每个可能的移动调用它自己的递归函数，并使用一个新的棋盘。

我这样做是为了当人工智能先行时，当另一个人先行时……然后将它们加在一起。我最终得到 418 次可能的胜利和 115 次可能的平局，以及 0 次可能的失败。

但现在我的问题是，我如何最大化获胜的数量？我需要将此统计数据与某些东西进行比较，但我无法弄清楚将其与什么进行比较。

4

8 回答 8

6

我的感觉是，您引用的统计数据已经相当不错了。两位专业的井字游戏玩家总是以平局告终，如果你的对手知道如何玩游戏，就没有办法强行获胜。

更新

可能有一种更优雅的方法来证明你的 AI 的正确性，但最直接的方法是蛮力方法。只需将所有可能的棋盘位置枚举为游戏树，并修剪直接导致失败的分支。然后对于树中的每个分支，您可以计算出跟随该分支所产生的获胜概率。然后，您只需要在每个棋盘位置上测试您的 AI，并确保它选择获胜概率最高的分支。

于 2012-12-02T06:44:20.720 回答
3

您应该首先观察第 9 步始终是强制的：棋盘上只有一个空方格。移动也可以被认为是 8 强制，因为在七步之后可能恰好有三种情况：

  • O可以在下一步获胜，在这种情况下，它需要获胜
  • 在剩下的两个方格中的任何一个方格中放置一个X赢得比赛X，在这种情况下O无论下一步如何都输了
  • X有零或一条通往胜利的道路，在这种情况下O阻止以强制平局

这意味着游戏最多在七步之后就结束了。

还要注意只有三个开场动作：中心、角落或侧面。您选择四个角或边中的哪一个都没有关系，因为板可以旋转以匹配“规范”开口（左上角或顶边的中间）。

您现在可以构建您的状态分析代码。从三个可能的开局中的每一个开始，使用在您进行移动时打开的所有方格回溯多达六个额外的移动。每次走完后，分析位置看是否X或O已经赢了；markX以 Wx 获胜，O以 Wo 获胜。其余职位未定。

Wx 或 Wo 之后不要探索位置：只需返回上一步，报告对应方的胜利。

当你到达第七步时，静态分析位置以确定它是否是上述三种情况之一，将位置标记为 Wx、Wo 或 Draw。

现在到最重要的一步：当你回溯到N-1玩家的移动时p，

  • 如果您尝试的移动之一使得下一级的所有位置都变为 Wp，则也将当前位置声明为 Wp。
  • 如果您尝试的所有动作都导致对手获胜，则宣布当前位置为对手获胜
  • 否则，将当前位置声明为平局，并返回上一级。

如果您这样做正确，所有三个空缺职位都将被归类为平局。三步后你应该会看到一些强行获胜。

运行此过程将每个位置分类为 Wx、Wo 或 Draw。如果您的 AI 在分类为 Wp 的位置上为玩家赢得胜利p，或者在分类为平局的位置上让您平局，那么您的 AI 就是完美的。另一方面，如果存在静态分类为 Wp 且 AIp仅获得平局的位置，那么您的 AI 引擎需要改进。

附加阅读：您可以在本文中找到有关该游戏的更多见解，该文章描述了计算可能的井字游戏游戏的方法。

于 2012-12-11T16:13:32.260 回答
2

你所做的比人工智能更线性优化。我不会在这里描述井字游戏的所有线性代数，网上有很多例子。

所以使用线性代数，你不必证明你的结果（搜索神奇的统计数据等），因为你的结果可以通过原始方程中的简单解注入来验证。

总之，有两种情况：

  • 您正在使用简单的“演绎”逻辑（实际上是非形式线性代数公式）：如果不查看您的代码，我们无法找到一种现成的方法来检查您的结果。编辑：正如 Andrew Cooper 所建议的，蛮力可以是一种随时可用的方法，而无需查看您的代码。

  • 您正在使用正式的线性代数公式：您的结果可以通过原始方程中的简单解注入来验证。

于 2012-12-06T11:40:08.827 回答
0

您唯一可以比较的是一个潜在的行动反对另一个。每当轮到计算机采取行动时，让它从那时起玩所有可能的游戏，然后选择可能导致最高获胜次数的行动。你不可能总是赢，但你可以给对手更多的机会做出一个坏的举动。

于 2012-12-06T20:14:04.077 回答
0

或者，您可以随时尝试以下链接中的井字游戏算法：

井字完美AI算法：更深的“造叉”步骤

于 2012-12-10T07:51:30.173 回答
0

鉴于我们知道

  • 不能强求胜利
  • 最佳策略是不会输的

你的人工智能已经被证明是最优的，如果

  • 你在对抗它时确实搜索了整棵树
  • 并且您的 AI 是确定性的（如果它在某些阶段掷骰子，您将不得不对抗所有组合）

它没有输，你不能要求它赢。它没有计算的胜利，因为您的完整树搜索也包括错误的移动。就是这样，你完成了。

只是为了好玩：
如果您对赢得/平局/输掉比赛的机会没有先验知识，那么一个常见的策略就是不断地挽救失去的位置。在下一场比赛中，你会尽量避免他们。如果您无法避免移动到丢失的位置，那么您会找到另一个位置。通过这种方式，您可以学会不输给某个策略（如果可能）或避免策略错误。

于 2012-12-11T00:20:21.667 回答
0

为了证明你的井字游戏 AI 是正确的，它需要满足两个条件：

  1. 它绝不能输。
  2. 当对手偏离最佳打法时，它必须获胜。

这两个条件都源于这样一个事实，即如果两个玩家都发挥最佳，井字游戏总是以平局告终。

确定程序是否满足这两个条件的一种自动方法是为每个可能的井字游戏构建所谓的“极小极大树”。极小极大树完全表征了每个玩家的最佳移动，因此您可以使用它来查看您的程序是否总是选择最佳移动。这意味着我的回答基本上可以归结为，“写一个完美的人工智能，然后看看它是否和你自己的人工智能一样发挥作用。” 但是，极小极大算法很有用，据我所知，这是测试您的 AI 是否真正发挥最佳效果的唯一方法。

以下是 minimax 算法的工作原理（有关 gif 说明，请参阅Wikipedia 。Wikipedia article on minimax中也有一些伪代码。）：

  1. 从正在考虑的井字游戏设置开始，构建所有可能后续动作的树。根节点处的初始位置。在树的最低级别，您拥有所有可能的最终位置。

  2. 将 +1 值分配给第一个玩家获胜的所有最终位置，将值 -1 分配给第二个玩家获胜的所有移动，并将值 0 分配给所有平局。

  3. 现在我们将这些值沿树传播到根节点。假设每个玩家都发挥最佳。在最后一步中，玩家一将选择任何具有+1 值的棋步，即赢得比赛的棋步。如果没有一个动作的值为+1，玩家一将选择一个值为0的动作，平局。因此，玩家玩家一号移动的节点被分配了其任何子节点的最大值。相反，当是玩家二的着法时，他们更喜欢选择值为 -1 的着法，从而赢得比赛。如果没有可用的获胜动作，他们更愿意平局。因此，轮到玩家二的节点被分配一个等于其子节点最小值的值。使用此规则，您可以将值从树中的最深层一直传播到根节点。

  4. 如果根节点的值为 +1，则第一个玩家应该以最佳游戏获胜。如果它的值为-1，则第二个玩家应该获胜。如果它的值为 0，则最佳游戏会导致平局。

您现在可以在每种情况下确定您的算法是否选择了最佳移动。构建井字游戏中所有可能移动的树，并使用极小极大算法为每个移动分配 +1、0 或 -1。如果您的程序是玩家一号，则最好始终选择最大值的移动。如果它扮演玩家二，那么它总是选择具有最小值的移动是最佳的。

然后你可以循环遍历树中的每一个动作，并让你的 AI 选择一个动作。上面告诉你如何确定它选择的移动是否是最优的。

于 2012-12-12T21:52:57.013 回答
0

我会使用决策树来解决这个问题。

简而言之，决策树是一种递归计算最终结果的期望（和机会）的方法。树中的每个“分支”都是一个决策，其期望值是根据sum of (value * chance)该决策的可能性计算得出的。

在有限的选项场景（如井字游戏）中，您可以预先计算整个树，因此在人类玩家的每一步（机会）之后，您可以做出选择（决定）下一个分支女巫的期望最高赢。

在国际象棋游戏中，解决方案类似，但树不是预先构建的：每次移动后，计算机都会计算棋盘上每个可能移动的值，以便n向前推进。根据玩家选择的游戏难度选择最佳、次佳或第 n 次最佳期望。

于 2012-12-12T21:58:50.380 回答