Creating a minimax tree recursively

Question

I am currently working on creating a tree (this is my learning process of creating a minimax tree and am starting towards minimax tree from here) with multiple nodes recursively.

Can anyone please determine if the algorithm is correct? From my perspective and couple of test (using print, count and gdb), I think I am creating the tree that I want, which looks like this:

The code for this tree:

#include <iostream>
#include <vector>
#define SIZE 3 //  this is number of child nodes a node will have

using namespace std;

struct Node{

    std::vector<Node*> v_node;
    std::vector<int> my_vec;
    int val;
};

class Tree{

    Node *root;
    int size;
    int count;

    void create_tree(Node *n, int size){
        if(size == 0) return;

        count++;
        for(int i = 0; i < SIZE; i++){
            Node * node = new Node;
            node->v_node.resize(SIZE, nullptr); 
            node->my_vec.resize((size-1), n->my_vec[0]-1); // decrease val of vector by 1 in each level
            node->val   = i;
            n->v_node[i] = node; 
            create_tree(node, size-1); // recursively call
        }   
    }      

public:

    Tree(int s){
        size = s;
        root = new Node; 
        root->v_node.resize(SIZE, nullptr);
        root->my_vec.resize(s, 36);
        root->val = 0;
        count = 0;
    }
    void ct(){
        create_tree(root, size);
    }
    int get_node_count(){
        return count;
    }
};

int main(){

    Tree t(4); // 
    t.ct();

    std::cout << "Node count = " << t.get_node_count() << std::endl;

}

My core questions are:

1. Do you think using for loop inside recursive function a good idea?

2. I know that recursion have limits. When I do ulimit -s it gives me around 8000. This means that if I am using minimax for complex games like chess this might cause stack overflow. This gives me hint that this algorithm that I wrote is not good. Can you comment on this?

3. I know I need to do the delete for releasing the resource, and for that I am planning to use unique_pointer later.

Answer 1

Your questions

1. Do you think using for loop inside recursive function a good idea?

There are circumstances where it might be problematic, but this doesn't seem to be one of them.

2. I know that recursion have limits. When I do ulimit -s it gives me around 8000. This means that if I am using minimax for complex games like chess this might cause stack overflow. This gives me hint that this algorithm that I wrote is not good. Can you comment on this?

This is a depth recursion. Meaning that if you are adding twelve nodes with a SIZE of 3, you will only make three recursive calls at any one time. One for the root, one for the three second level nodes (three different calls, but each finishes before the next one starts), and one for the nine third level nodes. To overwhelm a stack limit of 80 because of recursive calls with a SIZE of 2, you'd have to add something like a septillion (\$10^{24}\$ nodes. A tree with a depth of 8000 would be gigantic. You'd run out of heap (memory used to allocate variables with new) long before you ran out of stack.

With chess in particular, I would expect each node to be a move. The depth would be the length of the game in moves. According to Wikipedia, the longest game was 269 moves. So you are nowhere close to the stack limit of 8000 even if you double that to 538.

Of course, you might have problems with the heap limit, as such a data structure would be huge. Perhaps you'd be able to reuse some of the old space as you go, discarding weaker paths.

You also might consider adding the ability to reduce SIZE as you go. Note that in the early to mid-game you have many decisions. As you get to the end game, you have fewer and fewer pieces and therefore fewer decisions.

Managing size

        if(size == 0) return;

then

            node->my_vec.resize((size-1), n->my_vec[0]-1); // decrease val of vector by 1 in each level

and

            create_tree(node, size-1); // recursively call

The first time that you use size, you use its actual value. After that, you use size-1 twice inside the loop and never use size directly again. If instead, you say

        size--;

after the first time and before the loop, you can just use the new value of size in the loop. The compiler will probably optimize out the subtraction. But this way you can write the simpler size rather than size-1.

Answer 2

Here are some things that, in addition to the other review, may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. In this program, especially, it's completely simply to eliminate because the namespace is already explicitly specified every place it's needed.

Prefer constexpr to old-style #define

Rather than using a #define for SIZE the code could use a constexpr:

constexpr size_t SIZE{3}; //  this is number of child nodes a node will have

It doesn't make a huge difference here, but generally the advantage is that the value has an associated type.

Use appropriate data structures

The code implies that there are only and exactly 3 children nodes for each node, but the data structure is a std::vector<Node*> with a #define SIZE 3. This means that the size is set at compile time, but that there is no explicit prohibition to having 2 or 5 or more children. Better would be to define the variable as std::array<Node*, 3> v_node;. This would also eliminate both of the resize calls associated with the v_node variable.

Be careful with signed versus unsigned

The code currently contains this line:

    for(int i = 0; i < SIZE; i++){

But would it ever make sense for either i or SIZE to be negative? Probably not, in my view, which means that it would likely make more sense, considering how they're used, to have both declared as size_t types

Prefer modern initializers for constructors

The constructor could use the more modern initializer style rather than the old style you're currently using. Instead of this:

Tree(int s){
    size = s;
    root = new Node; 
    root->my_vec.resize(s, 36);
    root->val = 0;
    count = 0;
}

You could write this:

Tree(int s) : 
    root{new Node},
    size{s},
    count{0}
{
    root->my_vec.resize(s, 36);
    root->val = 0;
}

This could be even more simplified by implementing the following suggestion.

Rely on constructors to always create valid objects

By defining constructors for classes such as Node, you can assure that any Node object is actually valid; that is, it has a consistent internal state, according to whatever that might mean for your code. In this particular case, defining a constructor for Node makes much of the rest of the code much simpler. For example, we might move from a struct to a class definition like this:

class Tree;


class Node{
    std::array<Node*, 3> v_node;
    std::vector<int> my_vec;
    int val;
public:
    friend class Tree;
    Node(size_t count, size_t vecsize, int myval) :
        v_node{},
        my_vec(count, vecsize),
        val{myval}
    {}
};

Now the Tree constructor could be this:

Tree(int s) : 
    root{new Node{s, 36, 0}},
    size{s},
    count{0}
{ }

And the loop within create_tree reduces to just a few lines:

for(size_t i = 0; i < SIZE; i++){
    n->v_node[i] = new Node{size-1, n->my_vec[0]-1, i};
    create_tree(n->v_node[i], size-1); 
}

This same general principle also means that it makes little sense to have separate constructor and initialization calls. So instead of this in main:

Tree t(4);
t.ct();

It should just be this:

Tree t(4);

And the Tree constructor would be this:

Tree(int s) : 
    root{new Node{s, 36, 0}},
    size{s},
    count{0}
{ 
    create_tree(root, size);
}

The ct function would simply be eliminated.

Avoid memory leaks

You've already mentioned this in your problem statement, but for the benefit of other readers, the current version of the program leaks memory. Two approaches would be to either add a destructor to each of the classes, or better, to convert from raw pointers to std::shared_ptr.

Algorithm correctness

Because the code is not really complete, (that is, the tree contains no meaningful data), it's difficult to say. It constructs some tree, but whether it's a minimax tree is difficult to say outside of the context in which it will be used.