可重用AI游戏树

Question

问题

我需要一个极小的游戏树，以便它可以重用已经生成的有效移动，在修剪后，已经做的动作。不像二叉树，游戏树可以有多个子节点对应于可能的移动。我希望在背景层次上生成新的叶节点，这样就可以减少最佳移动期间的时间延迟。在递归的minimax例程中，每一棵树都会痛苦地生成每一个动作；然而，对结束移动或重复移动的控制也是困难的。

我的解决方案

这个游戏树，除了可重用，也将允许集成打开移动和结束移动容易。智能指针已经被用于自动垃圾收集，尽管它们可能有点耗时，但它们将有助于避免长期内存泄漏，因为节点的数量将达到10-100个。对诊断的快照(如下所示)已被捕获，以确保所有不必要的分支都已被正确地修剪，并比较了引用计数。

由于这是一个原型程序，所有的成分都在一个cpp文件中实现。我想进一步改进(特别是剪枝部分)，因此欢迎输入。

一些基本结构：

struct board_t
{
    std::vector<uint8_t> pos;
    board_t()
    {
        pos = std::vector<uint8_t>(25, 0);
    }
};

struct node_t
{
    std::unique_ptr<board_t> board_;
    std::weak_ptr<node_t> parent_;
    std::vector<std::shared_ptr<node_t>> children_;

    node_t()
    {
        board_ = std::make_unique<board_t>();
        parent_.reset();
    }
};

struct tree_t
{
    std::shared_ptr<node_t> root_;

    tree_t()
    {
        root_ = std::make_shared<node_t>();
        root_->board_ = std::make_unique<board_t>();
        root_->parent_.reset();
    }

    tree_t(std::shared_ptr<node_t>& node) :root_(node)
    {
    }

    void reset(std::shared_ptr<node_t>& node)
    {
        DeleteTree(root_, node);

        //delete extra children of root node only
        for (auto& next_node : root_->children_)
            if (next_node != node)
            {
                next_node->board_.reset();
                next_node->parent_.reset();
                std::cout << "1 destroyed\n";
            }

        root_ = node;
        root_->parent_.reset();
    }

private:

    void DeleteTree(std::shared_ptr<node_t>& node, std::shared_ptr<node_t>& new_root)
    {
        if (node->children_.empty())
        {
            while (!node->parent_.expired())
            {
                auto strong = node->parent_.lock();
                node = strong;
                if (strong)
                {
                    strong->board_.reset();
                    strong->parent_.reset();
                    if (!strong->children_.empty())
                    {
                        std::cout << strong->children_.size() << " destroyed\n";
                        strong->children_.clear();
                    }
                }
            }

            return;
        }

        for (auto& next_node : node->children_)
            if (next_node != new_root)
            {
                DeleteTree(next_node, new_root);
            }

    }

};

一些辅助功能：

std::unique_ptr<tree_t>& GetTree()
{
    static std::unique_ptr<tree_t> tree = std::make_unique<tree_t>();
    return tree;
}

std::shared_ptr<node_t>& GetTreeRoot()
{
    return GetTree()->root_;
}

void AddChild(std::shared_ptr<node_t>& node, std::shared_ptr<node_t> parent)
{
    node->parent_ = parent;
    parent->children_.emplace_back(node);
}

void PrintTree(std::shared_ptr<node_t>& node)
{
    for (int i = 0; i < node->children_.size(); i++)
        std::cout << "Node " << node->children_[i].use_count()<<"/"<< node->children_[i]->children_.size() <<"   ";
    std::cout << "\n";

    for (auto& next_node : node->children_)
    {
        PrintTree(next_node);
    }
}

int GetDepth(std::shared_ptr<node_t>& node)
{
    int depth = 1;
    std::weak_ptr<node_t> weak = node->parent_;

    while (!weak.expired())
    {
        weak = weak.lock()->parent_;
        depth++;
    }
    return depth;
}

int MaxDepth(std::shared_ptr<node_t>& node)
{
    static int max_depth = 0;

    if (node->children_.empty())
    {
        max_depth = std::max(max_depth, GetDepth(node->parent_.lock()));
        return  max_depth;
    }

    for (auto& next_node : node->children_)
        MaxDepth(next_node);

    return max_depth;
}

Minimax和测试评估功能：

int Evaluate(std::unique_ptr<board_t>& board, bool maximizing)
{
    static int ptr = 0;  //TEST 
    int arr[] = { 2,1,3,1,-1 ,2,1,3,1,-1 ,1,3,1,-1 ,2,1,3,1,-1 ,1,3,1,-1 ,2,1,3,1,-1 };
    return arr[ptr++];
}

int Minimax(std::shared_ptr<node_t>& node, bool white2max = true)
{
    bool maximizing = (GetDepth(node) % 2 == 1);
    int score = maximizing ? -999 : 999;

    if (node->children_.empty())
    {
        return  Evaluate(node->board_, !maximizing);
    }

    for (auto& next_node : node->children_)
    {
        int val = Minimax(next_node, white2max);
        maximizing ? score = std::max(score, val) : score = std::min(score, val);
    }
    return score;
}

新的叶节点生成功能：

void GenerateNewLeafNodes(std::shared_ptr<node_t>& node)
{
    auto GenerateNewNodes = [](std::shared_ptr<node_t> parent_node)->void
    {
        std::queue<std::unique_ptr<board_t>> positions;
        //TODO void GenerateMoves(parent_node,positions)
        positions.push(std::make_unique<board_t>()); //TEST 
        positions.push(std::make_unique<board_t>()); //TEST 

        while (!positions.empty())
        {
            std::shared_ptr<node_t> node = std::make_shared<node_t>();
            node->board_ = std::move(positions.front());
            node->parent_ = parent_node;
            AddChild(node, parent_node);
            positions.pop();
        }
    };

    if (node->children_.empty())
    {
        return GenerateNewNodes(node);
    }

    for (auto& next_node : node->children_)
        GenerateNewLeafNodes(next_node);
}

测试功能：

void test_build()
{
    AddChild(std::make_shared<node_t>(), GetTreeRoot());
    AddChild(std::make_shared<node_t>(), GetTreeRoot());
    AddChild(std::make_shared<node_t>(), GetTreeRoot());

    auto& root_next1 = GetTreeRoot()->children_[0];


    AddChild(std::make_shared<node_t>(), root_next1);
    AddChild(std::make_shared<node_t>(), root_next1);

    std::cout << "Depth = " << GetDepth(root_next1) << " \n";
    std::cout << "Max_Depth = " << MaxDepth(GetTreeRoot()) << " \n";

    GenerateNewLeafNodes(GetTreeRoot());
    GenerateNewLeafNodes(GetTreeRoot());

    std::cout << "Minmax score = " << Minimax(GetTreeRoot(), true) << " \n";    

    std::cout << "\nTree \n";
    PrintTree(GetTreeRoot());

    //std::cout << " Root " << GetTreeRoot().use_count() << "/ " << GetTreeRoot()->children_.size() << "\n";
    GetTree()->reset(root_next1);  // PRUNING HERE

    std::cout << "\nTree \n";
    PrintTree(GetTreeRoot());
    //std::cout << " Root " << GetTreeRoot().use_count() << "/ " << GetTreeRoot()->children_.size() << "\n";
}

int main()
{
    test_build();
    return 0;
}

内存诊断快照显示剪枝后ref计数下降：

Answer 1

构造函数

您应该使用构造函数中的构造函数初始化程序列表。当前，构造函数将默认构造类的所有成员，然后一些新构造的成员在构造函数体中被替换(通过赋值)。可以使用构造函数初始化程序列表将它们组合起来。例如：

board_t(): pos(25, 0)
{
}

你也要重复一遍。node_t构造函数为board_成员提供了唯一的board_t成员。然后，在tree_t构造函数中，用一个新的指针值重新分配指针值。它也不需要reset一个新构造的weak_ptr。

编码风格

代码样式的主要问题是在一些多行块语句中缺少大括号。例如，for循环在tree_t::reset中。语言不需要它们，因为for循环的主体中只有一条语句，但是包含它们使代码更容易理解，并减少了以后添加或编辑代码时出现奇怪错误的可能性。

您通常通过引用传递共享指针，但在一些情况下，您正在复制。您需要检查这些内容，以确定副本是否正确，或者是否可以使用引用，或者在下面的赋值中，使用std::move而不是副本分配可能会使您受益。

码

在MiniMax中，您通过使用条件运算符作为if语句滥用它。如果您使用的是if而不是带有嵌入式赋值的?:操作符，或者(因为您要分配给相同的变量)，则代码会更清晰一些，或者指定条件的结果(score = maximizing ? std::max(score, val) : std::min(score, val))。我个人的偏好是在这里使用嵌套的if，因为您通常会将score分配给自己。

Evaluate函数存在问题(本地数组可能是static const，如果调用过多，则可能在数组边界之外进行访问)，但它似乎是一个迫切需要更新的测试函数。