在制作井字游戏机器人时,我在尝试理解“树”时遇到了巨大的障碍。我理解这个概念,但我不知道如何实现它们。
有人可以向我展示一个如何为这种情况生成树的示例吗?或者关于生成树的好教程?我想最困难的部分是生成部分树。我知道如何实现生成整棵树,但不知道它的一部分。
想象一下,在井字棋盘上的任何一点,每一个可能的动作都是一个分支。董事会的当前状态是根。一动即为枝。现在假装(一次一个)每个分支都成为当前状态。每个可能的移动都会成为一个新的分支。树的叶子是当最后一步走完并且棋盘已满时。
您需要一棵树的原因是,一旦构建完成,您需要找出哪个分支具有最多的叶子,这些叶子是“获胜”场景。您建立所有可能结果的分支,将获胜的总数相加,然后采取有机会获得最多胜利的举动。
使树像这样:
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 )
非常伪代码。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)