Reusable AI Game Tree

Question

Problem

I needed a minimax game tree so that it can reuse the already generated valid moves, after pruning the moves already made. Unlike Binary Tree, a game tree can have multiple child nodes corresponding to the possible moves. I want to generate new leaf nodes in the background level-wise, so that time delay during best-move is reduced. In recursive minimax routine, every tree is pain-stakingly generated for every move ; however control of end-moves or repeated moves are also difficult.

My Solution

This game tree, besides reusability, will also allow integrating opening moves and end-moves easily . Smart-pointers have been used for auto garbage collection, although they may be slightly time expensive, they will help avoid memory leaks in the long run since the number of nodes will run into 10-100 thousands. A snapshot of the diagnosis ( shown below) has been to taken to ensure that all unnecessary branches have been pruned properly and reference counts are compared.

Since this is a prototype program, all the ingredients is realized in a single cpp file . I want to improve further ( especially the pruning part), hence inputs are welcome.

Some basic structs:

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);
            }

    }

};

Some helper functions:

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 and test evaluation functions:

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;
}

New leaf node generation function:

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);
}

Test functions:

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;
}

Memory diagnosis snapshot showing drop in ref counts after pruning:

Answer 1

Constructors

You should make use of the constructor initializer list in your constructors. Currently, your constructors will default construct all the members of the class, then some of those newly constructed members get their values replaced (via assignment) in the constructor body. These can be combined using the constructor initializer list. For example:

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

You also repeat yourself. The node_t constructor gives the board_ member a unique board_t member. Then in the tree_t constructor, you reassign that pointer value with a new one. It is also unnecessary to reset a newly constructed weak_ptr.

Coding style

The main problem I have with the style of the code is the lack of curly braces on some of your multiple line block statements. For example, the for loop in tree_t::reset. The language doesn't require them, since there is only one statement in the body of the for loop, but including them makes the code easier to comprehend and reduces the chance of odd errors later when code is added or edited.

You usually pass shared pointers by reference, but in a few cases you're making copies. You'll want to check those to see if the copy is right, or if you could use a reference, or if in the following assignments you may benefit from using std::move instead of a copy assignment.

Code

In MiniMax, you're abusing the conditional operator by using it as an if statement. The code would be clearer if you used an if rather than the ?: operator with embedded assignments, or (since you're assigning to the same variable) assign the result of the conditional (score = maximizing ? std::max(score, val) : std::min(score, val)). My personal preference would be to use a nested if here since you'll usually be assigning score to itself.

The Evaluate function has issues (local array could be static const, potential access outside of array bounds if it is called too often), but it appears to be a test function that is in sore need of an update.