14

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

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

4

5 回答 5

15

想象一下，在井字游戏中的任何一点，每一个可能的动作都是一个分支。板的当前状态是根。一个动作是一个分支。现在假设（一次一个），每个分支都成为当前状态。每个可能的移动都成为一个新的分支。树的叶子是当最后一步完成并且棋盘已满时。

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

使树像这样：

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 )

非常伪代码。

于 2010-04-30T12:12:11.720 回答
5

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

Move getBestMove(Board state, boolean myTurn)

然后，您只需递归，直到您达到赢、输或平局状态。

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

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

于 2010-04-30T12:07:16.160 回答
4

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

使用 MiniMax 算法解决井字游戏

它在 C# 中，但在 C++ 中调整它不会有任何问题。

当我尝试用 C++ 实现我的第一个井字游戏时，这篇文章对我来说也是一本不错的读物：

极小极大解释

于 2010-04-30T12:29:55.980 回答
0

如果您想在内存中生成树（这不是必需的），也许可以使用如下算法（伪代码）：

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
于 2010-04-30T12:24:44.647 回答
0

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

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

这是我用 Python实现的游戏，它只有大约 200 行代码，并且能够以Human vs. Human、Human vs. Computer和Computer vs. Computer. 它还保留有关深度和达到/修剪的节点数量的统计信息，以达到最佳移动。

I highly recommend edX.org Artificial Intelligence course, which gives the the fundamental knowledge on current AI topics and solutions.

于 2019-04-05T17:21:40.443 回答