The tree for alpha-beta pruning is usually implicit. It is a way of preventing your AI search algorithm from wasting time on bad solutions. Here is the pseudocode from Wikipedia:
function alphabeta(node, depth, α, β, Player)
if depth = 0 or node is a terminal node
return the heuristic value of node
if Player = MaxPlayer
for each child of node
α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Beta cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Alpha cut-off *)
return β
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)
The function recursively evaluates board positions. The "node" is the current position, and where it says "for each child of node" is where you generate new board positions resulting from each possible move at the current one. The depth parameter controls how far ahead you want to evaluate the tree, for analyzing moves to an unlimited depth might be impractical.
Still, if you have to build a tree of some given depth before pruning it for educational purposes, the structure for a tree with nodes that can have variable numbers of children is very simple and could look something like this:
struct Node
{
Node ** children;
int childCount;
double value;
};
Node * tree;
Here children is a Node array with childCount members. Leaf nodes would have childCount=0. To construct the tree, you would search the availabile board positions like this:
Node * CreateTree(Board board, int depth)
{
Node * node = new Node();
node.childCount = board.GeAvailableMoveCount();
node.value = board.GetValue;
if (depth > 0 && node.childCount > 0)
{
node.children = new Node * [node.childCount];
for (int i = 0; i != node.childCount; ++i)
node.children[i] = CreateTree(board.Move(i), depth - 1);
}
else
{
node.children = NULL;
}
return node;
}
void DeleteTree(Node * tree)
{
for (int i = 0; i != tree.childCount; ++i)
DeleteTree(tree.children[i]);
delete [] tree.children; // deleting NULL is OK
delete tree;
}
