How do you make Tree Data Structures in C++?

Question

I'm taking a class in AI Methods along with a friend of mine, and we've partenered for the final project, which is coding Othello & an AI for it using C++ and OpenGL.

So far we have the board and the Othello Engine (I'm using an MVC type approach). But the one thing thats proving difficult to grasp is the AI.

We're supposed to write an AI that uses Alpha-Beta pruning on a tree to quickly calculate the next move it should make.

The concepts of Alpha-Beta pruning, as well as the algorithm for detecting which squares are worth more than others, as far as the game is concerned.

However, my partner nor I have yet to take the data structures class, and as such we don't know how to properly create a tree in C++ or even where to get started.

So my question to you, Stack Overflow is: Where do I get started to quickly (and effectively) write and traverse a Tree for Alpha-Beta Pruning in C++ without using STL. (Our assignment states that we're not allowed to use STL).

Any and all help is appreciated, thank you!

Solution

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

Comments

[Navarr]

But how do you build the tree?

[GManNickG]

You usually do store the tree, because the algorithms are almost always coupled with iterative deepening.

[Don Reba]

@GMan do you store the whole tree for iterative deepining, or just list the leaf nodes?

[GManNickG]

@Don: When I did it, I just stored the tree. It's cheap enough (memory-wise) that you're going to be limited on time more than memory, so you won't get to exhaust the memory. (Make no mistake, though, that it does use lots.) Forward pruning helps significantly, especially for a game with a high branching factor, such as the game I was doing, The Game of the Amazons.