Tic-Tac-Toe AI：如何制作树？

Question

在制作井字游戏机器人时，我在尝试理解“树”时遇到了巨大的障碍。我理解这个概念，但我不知道如何实现它们。

有人可以向我展示一个如何针对这种情况生成树的示例吗？或者关于生成树的好教程？我想最困难的部分是生成部分树。我知道如何实现生成整棵树，但不知道它的一部分。

Answer 1

就人工智能而言，实现井字游戏可能是最简单的问题
和搜索空间。

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

这是我用 Python 实现的游戏实现，只有大约 200 行代码，并且能够玩人与人、人与计算机和计算机与计算机游戏。它还保留了导致最佳移动的深度和达到/修剪的节点数量的统计数据。

我强烈推荐 edX.org 人工智能 课程，提供当前人工智能主题和解决方案的基础知识。

Answer 2

想象一下，在井字棋盘上的任何一点，每一个可能的动作都是一个分支。董事会的当前状态是根。一动即为枝。现在假装（一次一个）每个分支都成为当前状态。每个可能的移动都会成为一个新的分支。树的叶子是当最后一步走完并且棋盘已满时。

您需要一棵树的原因是，一旦构建完成，您需要找出哪个分支具有最多的叶子，这些叶子是“获胜”场景。您建立所有可能结果的分支，将获胜的总数相加，然后采取有机会获得最多胜利的举动。

让树看起来像这样：

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 )

非常伪代码。

Answer 3

我认为你不需要在内存中保留一棵树。您只需要实现一个递归函数，其工作原理如下：

Move getBestMove(Board state, boolean myTurn)

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

如果你把它画在纸上，随着时间的推移，调用堆栈看起来就像一棵树。您应该返回导致对手（肯定/最有可能）失败的节点的移动（即使他也使用 getBestMove 进行游戏），

但是对于像井字游戏一样小的状态空间，您可以简单地执行完整的查找表与最佳动作！ :-)

Answer 4

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

用 MiniMax 算法解决 Tic Tac Toe

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

当我尝试用 C++ 实现我的第一个 Tic-Tac-Toe 游戏时，这篇文章对我来说也是一本很好的读物：

极小极大解释

Answer 5

可以使用如下算法（伪代码）：

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