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

在制作Tic-Tac-Toe机器人时,我正试图了解"树木".我理解这个概念,但我无法想出来实现它们.

有人能告诉我一个如何为这种情况生成树的例子吗？还是一个关于生成树木的好教程？我想难以产生部分树木.我知道如何实现生成整棵树,但不是它的一部分.

想象一下,在tic-tac-toe板的任何一点,每一个可能的移动都是一个分支.董事会的当前状态是根.一举是一个分支.现在假装(一次一个),每个分支成为当前状态.每个可能的移动都成为新的分支.树的叶子是最后一次移动并且板已满的时候.

你需要一棵树的原因是,一旦它被构建,你需要弄清楚哪个分支的叶子最多是'WIN'场景.您构建了所有可能结果的分支,将WIN的总数相加,然后进行有机会获得最多胜利的移动.

使树像这样:

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 )

非常伪代码.

我认为你不需要在记忆中保留一棵树.您只需要实现一个类似于以下内容的递归函数:

Move getBestMove(Board state, boolean myTurn)

然后你只需递归,直到你达到胜利,失败或平局状态.

如果你把它写在纸上,那么随着时间的推移,调用堆会看起来像一棵树.你应该返回导致对手(绝对/最有可能)失去的节点的移动(即使他也使用getBestMove进行游戏)

对于状态空间少但是井字棋,你可以简单地做一个全面的查找表最好的动作!:-)