井字游戏人工智能：如何构建决策树？

Question

我在制作井字棋机器人时，在理解“树”这个概念上遇到了巨大的障碍。我理解这个概念，但我无法弄清楚如何实现它。

有人能展示一下如何为这种情况生成一棵树的例子吗？或者有一个关于生成树的好教程吗？我猜难点在于生成部分树。我知道如何实现生成整个树，但不知道如何生成其部分。

- cam

---

什么样的树？极小化极大树吗？ - Alex Budovski

任何存储下一步可能状态的树都可以。极小化极大树可以工作，我只是想看看如何填充/导航/等等“树”。我没有使用树的经验。 - cam

Answer 1

假设在井字棋棋盘上的任意一点，每个可能的走法都是一个分支。当前棋盘状态是根。每一步走法都是一个分支。现在假设（逐个假设），每个分支都成为当前状态。每个可能的走法都成为一个新的分支。树的叶子节点是最后一步走完并且棋盘已满的时候。

需要有这样一棵树的原因是，建立完毕之后，您需要找出哪个分支拥有最多的“胜利”场景。您可以构建所有可能结果的分支，计算总胜利数，然后选择可能获得最多胜利的那一个走法。

将树形结构制作成如下图：

class Node {
public:
   std::list< Node > m_branches;
   BoardState m_board;
   int m_winCount;
}

std::list< Node > tree;

现在，你需要遍历树中的分支列表，并对每个分支遍历其子分支。这可以通过递归函数实现：

int recursiveTreeWalk( std::list< Node >& partialTree)
{

   for each branch in tree
       if node has no branches
           calculate win 1/0;
       else
           recursiveTreeWalk( branch );

   partialTree.m_winCount = sum of branch wins;
}

// initial call
recursiveTreeWalk( tree )

非常伪代码。

- Kieveli

---

话虽如此，但在这一点上它并不真正是人工智能，而是对所有可能结果的严格确定，并采取恰当的风险。 - Kieveli

好的，谢谢你的解释，帮了我很多。但是我遇到的主要问题是如何实现它。我完全理解这个概念，但是生成树和遍历它让我感到困惑。我正在寻找一些能够帮助我的源代码，甚至是教程。在我理解代码中的一个概念之前，我的大脑需要看到一个例子。 - cam

为了让它更像人工智能，您可以使用最大深度来限制前瞻。或者使用一个计时器来限制前瞻所花费的时间 - 尽管在Tic Tac Toe游戏中，计算完整树只需要几纳秒。 - graham.reeds

Answer 2

我认为你不需要将一棵树存在内存中。你只需要实现一个递归函数，类似于下面的例子：

Move getBestMove(Board state, boolean myTurn)

然后，您只需递归，直到达到获胜、失败或平局状态。

如果在纸上绘制，调用堆栈随着时间的推移会形成一棵树。您应该返回导致对手（肯定/最有可能）输掉游戏的节点的移动（尽管他也使用getBestMove进行游戏）。

然而，在像井字游戏这样的状态空间中，您可以简单地使用最佳移动的完整查找表！ :-)

- aioobe

---

我想这就是我没有理解的地方。我以为实际上在内存中创建了一棵树形结构。目前我是使用递归函数而不是树来实现机器人的。 - cam

Answer 3

您可能会发现这篇CodeProject文章很有趣：

使用MiniMax算法解决井字棋问题

它是用C#编写的，但将其改为C++也不会有任何问题。

当我尝试在C++中实现我的第一个井字棋游戏时，这篇文章对我也很有帮助：

解释了MiniMax算法

- Jérôme

Answer 4

如果你想在内存中生成一棵树（这并非必要），或许可以使用类似以下的算法（伪代码）：

GenTree(State s):
  T <- empty tree  // T is a tree of States
  SetRoot(T, s)

  ForEach (s' in Successors(s)):
    AddChild(T, GenTree(s'))

  return T

// Call it
GenTree(currentMove)

在哪里

Successors(s)  // returns a list of successor states of s
AddChild(p, n)  // adds n to the list of p's children

- Alex Budovski

Answer 5

实现井字棋游戏可能是在AI和搜索空间方面解决的最简单问题。

关键是要使用Minimax， 迭代加深深度优先搜索和Alpha-beta剪枝算法来解决问题。

这是我用Python实现的游戏代码，仅有约200行代码，并且具备人对人、人对电脑和电脑对电脑的游戏能力。它还保留了有关深度和到达/剪枝节点数量的统计数据，以指导最佳移动。

我强烈推荐 edX.org 人工智能课程, 它可以为您提供关于当前AI主题和解决方案的基本知识。

- Ostati