井字游戏AI:如何制作树木? [英] Tic-Tac-Toe AI: How to Make the Tree?

问题描述

制作Tic-Tac-Toe机器人时，我想了解树木"的工作量很大.我理解这个概念，但是我不知道要实现它们.

I'm having a huge block trying to understand "trees" while making a Tic-Tac-Toe bot. I understand the concept, but I can't figure out to implement them.

有人可以向我展示如何在这种情况下生成树的示例吗?还是有关生成树的好教程?我想最困难的部分是生成局部树.我知道如何实现生成整个树，但不生成其中的一部分.

Can someone show me an example of how a tree should be generated for such a case? Or a good tutorial on generating trees? I guess the hard part is generating partial trees. I know how to implement generating a whole tree, but not parts of it.

推荐答案

想象一下，在井字游戏板上的任何时候，每一个可能的动作都是一个分支.董事会的当前状态是根.一招是分支.现在假装(一次一个)，每个分支变为当前状态.每一个可能的举动都会成为一个新的分支.树的叶子是最后一步移动时板子已满的时候.

Imagine that at any point in a tic-tac-toe board, every single possible move is a branch. The current state of the board is the root. One move is a branch. Now pretend (one at a time), that each branch becomes the current state. Each possible move becomes a new branch. The leaf of the tree is when the last move is made and the board is full.

之所以需要一棵树，是因为一旦建立了树，就需要弄清楚哪个分支拥有最多的"WIN"场景.您建立所有可能结果的分支，总计WIN的总数，然后进行有机会以最多的胜利结束的举动.

The reason you need to have a tree, is that once it is built, you need to figure out which branch has the most leaves that are 'WIN' scenarios. You build the branch of all possible outcomes, add up the total number of WINs, and then make the move that has the chance to end up with the most wins.

让树变成这样:

class Node {
public:
   std::list< Node > m_branches;
   BoardState m_board;
   int m_winCount;
}

std::list< Node > tree;

现在，您遍历树中的分支列表，对于每个分支，遍历其分支.这可以通过递归函数来完成:

Now, you iterate through the list of branches in the tree, and for each branch, iterate through its branches. This can be done with a recursive function:

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 )

非常伪代码.

这篇关于井字游戏AI:如何制作树木?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！