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: