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

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

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

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

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

使树像这样：

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 )

非常伪代码。