# Creating a minimax tree recursively

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.

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.

1. 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.

• Thank you for the lucid description, especially on the stack overflow part and the overwhelming heap problem. When you say "Perhaps you'd be able to reuse some of the old space as you go, discarding weaker paths" this part I still have problem understanding but I guess that is totally different topic ( I might have to do some research on this area). Commented Aug 19, 2016 at 3:46

## 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.

• Thank you Edward. Sorry for the late response I was working on the writing minimax algorithm during this time. Thank you for your constructive answer. Commented Aug 26, 2016 at 6:16
• In regards to constexpr when you say "the advantage is that the value has an associated type." What do you really mean by this? Commented Aug 26, 2016 at 21:17
• What I mean is that if you write #define FOOBAR 5 it is not actually a variable and therefore FOOBAR is whatever type 5 is (by default, an integer). If what you really want is a size_t as with this code, then the way to do that is to use a constexpr to let the compiler know the intended type and allowing it to check for the usual rules according to the specified type. Commented Aug 26, 2016 at 21:24
• In other word to associate SIZE with with const size_t type, rather then no type? Since #define is just a macro with no type associated with it. Commented Aug 26, 2016 at 21:30
• Basically, yes, you've got it. Commented Aug 26, 2016 at 21:32