alpha-beta-prune

                                Alpha-Beta Prune

A. Second Edition
In A.I. there is a class of algorithm dealing with opponents' strategy. e.g. Two players are playing chess and their

strategy are conflicting. One wants to achieve highest, one wants to achieve lowest. So, we can use a MinMax tree to

represent their playing strategy. I want to overwrite this edition since there is no need to keep a buggy version.

In this revised version, I fixed the bugs that only alpha or beta prune is executed in one single call. It actually again

negate my assertion that alpha-beta-prune cannot be executed at same time. They are executed alternatively.

B.The problem

The MinMax tree can be quite deep in case of non-trivial game. So, breadth-first search won't work here. However depth-first search
may lead to very deep searching. Therefore a bounded DFS is a common choice.
Then should all nodes be visited? The answer is no because there are many nodes unnecessary for visiting and this technique is called
alpha-beta pruning.

1. There is a common illusion that we first generate a n-ply minmax tree and then apply alpha-beta prune. No, we generate

tree and apply alpha-beta prune at same time! Otherwise it is a redundant operation.

2. Can you invoke alpha prune and beta prune at same time at a certain moment? No, they cannot happen at the same time.

But they can happen alternatively.

3. Should you change your DFS algorithm? No, basically you are still following DFS, except that you are using alpha-beta in

a style of heuristic manner.

4. After prune, what should I return? A signal indicating prune happened? In principle, you can return anything indicating

a prune happened and searching of tree nodes below are finished. However, in order to be in consistency with algorithm of

DFS, we can return the last value triggering pruning since it would be discarded eventually.

5. Does prune happen on same tree node if applying from right-to-left instead of left-to-right? No. The prune is different

but the final minmax tree would be same since pruning doesn't change the structure of tree, but just smartly ignore some

tree node without visiting them because you know it won't change the results.
6. Is it easy to implement? Yes or no, to me, it takes me a couple of days to really understand the algorithm, including
　
those principles above. And one of the biggest issue is how to vividly output a tree and output the pruned tree?

C.The idea of program
　
Basically I just follow the recursive DFS algorithm. Originally I even have the illusion that I may need a "depth" to help
　
me to see if pruning happens on ancestor or descendant. Later I realized this is non-sense since prune won't happen on
　
those descendant nodes of a sibling of that node. Another illusion is that I anticipate that I may need a double link list
　
to help me traverse tree when pruning. Later I revert to DFS recursion and algorithm becomes simple and clear. (Someone may
　
argue about higher efficiency of iteration against recursion. I should say programmer's efficiency is more important than
　
performance for this kind of problem because you see it is very easy to fall into a trap of pointer or whatever.)

D.The major functions

Originally I designed a double-link list pointer "previous", "next", "parent" to ease the traverse of tree. And there is

some tricky issues I want to mention. According to my "bible" (c++ stl), some template container may dynamically adjust

its internal storage which will cause all pointers, references to become invalid. i.e. it is dangerous to directly use

pointer to "set or multiset". For list, vector, deque, if you insert element in the middle, it will also cause some pointers

invalid. So, I was very careful to only use "push_front" or "push_back" for deque. However, later doubly-link list is not

used and this issue becomes useless. Still it is worth to make a note.

E.Further improvement

The following morning I added a redundant function "minmax" in order to test my AI assignment of figure 4.24 on p158 of which

the requirement is to minmax tree and alpha-beta prune it. I don't have time to write a "readfromfile" method which is

equally awkward in my opinion because you need to give the data in pre-order, so, I just hand-coded the tree.

　

F.File listing
1. alpha-beta.cpp
file name: alpha-beta.cpp

#include <deque>
#include <iostream>
#include <ctime>
#include <string>
#include <cstdio>
#include <cstdlib>


using namespace std;

int index=0;

struct TreeNode;

typedef deque<TreeNode> NodesType;

const int MaxBranchNumber=4;
const int DefaultAlphaValue=-1000;
const int DefaultBetaValue=1000;
const int MaxSearchLevel=5;

enum TreeNodeType
{
    MaxNode, MinNode
};

char* nodeName[2]= {"MaxNode", "MinNode"};

//assume max is root
struct TreeNode
{
    friend void displayTree(const TreeNode& node);
    friend void displayQueue(const deque<TreeNode>& sonQueue);
    friend ostream& operator <<(ostream& os, const TreeNode& node)
    {
        os<<"name:"<<node.name<<endl;
        os<<"number of sons:"<<node.sons.size()<<endl;
        os<<"node type:"<<((node.nodeType==MaxNode)?"MaxNode":"MinNode")<<endl;
        return os;
    }

    deque<TreeNode> sons;
    TreeNodeType nodeType;
    string name;
    int data;
    int minmax();
    int pruneTree(int alpha, int beta, int level) const;
    TreeNode prune();
    void populate(int level);
    void addSon(const TreeNode& oneSon);
};



TreeNode TreeNode::prune()
{
    int value, current;
    TreeNode result;
    if (nodeType==MaxNode)
    {
        current=DefaultAlphaValue;
    }
    else
    {
        current=DefaultBetaValue;
    }

    for (NodesType::const_iterator it=sons.begin(); it!=sons.end(); it++)
    {
        value=(*it).pruneTree(DefaultAlphaValue, DefaultBetaValue, 0);
        if ((nodeType==MaxNode&&value>current)||(nodeType==MinNode&&value<current))
        {
            result=*it;
            current=value;
        }
    }
    return result;
}

int TreeNode::minmax()
{
    int value=-1, result=-1;
    if (sons.size()==0)
    {
        return data;
    }
    for (deque<TreeNode>::iterator it=sons.begin(); it!=sons.end(); it++)
    {
        value=(*it).minmax();
        if (result==-1)
        {
            result=value;
        }
        else
        {
            if (nodeType==MaxNode)
            {
                if (value>result)
                {
                    result=value;
                }
            }
            else
            {
                if (value<result)
                {
                    result=value;
                }
            }
        }
    }
    data=result;
    return result;
}

int TreeNode::pruneTree(int alpha, int beta, int level) const
{
    int value, result;
    if (sons.size()==0||level==MaxSearchLevel)
    {
        return data;
    }
    if (nodeType==MaxNode)
    {
        result=alpha;
    }
    else
    {
        result=beta;
    }

    for (NodesType::const_iterator it=sons.begin(); it!=sons.end(); it++)
    {
        value=(*it).pruneTree(alpha, beta, level+1);
        if (nodeType==MaxNode)
        {
            if (value>beta)
            {
                return value;
            }
            if (value>result)
            {
                result=value;
            }
        }
        else
        {
            if (value<alpha)
            {
                return value;
            }
            if (value<result)
            {
                result=value;
            }
        }
    }
    return result;
}



void displayQueue(const deque<TreeNode>& sonQueue)
{
    deque<TreeNode> myqueue;
    if (sonQueue.empty())
    {
        return ;
    }
    for (deque<TreeNode>::const_iterator it=sonQueue.begin(); it!=sonQueue.end(); it++)
    {
        cout<<(*it).name<<"="<<(*it).data<<"("<<nodeName[(*it).nodeType]
            <<(*it).sons.size()<<"), ";

        myqueue.insert(myqueue.end(), (*it).sons.begin(), (*it).sons.end());
    }
    cout<<"\n";
    displayQueue(myqueue);
//	cout<<"\n";
}

void displayTree(const TreeNode& node)
{
    //TreeNode ptr=node;
    cout<<node.name<<"="<<node.data;
    cout<<"("<<nodeName[node.nodeType]<<node.sons.size()<<") "<<"\n";
    displayQueue(node.sons);
//	cout<<"\n";

}


void TreeNode::addSon(const TreeNode& oneSon)
{
    char nameBuf[10];
    TreeNode son=oneSon;
    if (son.name=="")
    {
        sprintf(nameBuf, "A%d", ++index);
        son.name=string(nameBuf);
    }
    if (nodeType==MaxNode)
    {
        son.nodeType=MinNode;
    }
    else
    {
        son.nodeType=MaxNode;
    }
    sons.push_back(son);
}

void TreeNode::populate(int level)
{
    int number, i;
    TreeNode oneSon;

    number=rand()%MaxBranchNumber;
    if (number==0||level==0)
    {
        data=rand()%20;
        return;
    }

    for (i=0; i<number; i++)
    {
        oneSon.data=-1;
        addSon(oneSon);
        sons[i].populate(level-1);
    }

}

void construct424(TreeNode& root)
{
    TreeNode node;
    deque<TreeNode>::iterator it, sonIt, sonsonIt;
    node.name="B";
    node.data=-1;
    root.addSon(node);
    node.name="C";
    node.data=-1;
    root.addSon(node);
    //level 2
    it=root.sons.begin();//
    node.name="D";
    node.data=3;
    (*it).addSon(node);

    //it++;
    node.name="E";
    node.data=5;
    (*it).addSon(node);

    it++;
    node.name="F";
    node.data=-1;
    (*it).addSon(node);
    sonIt=(*it).sons.begin();
    node.name="I";
    node.data=-1;
    (*sonIt).addSon(node);
    sonsonIt=(*sonIt).sons.begin();
    node.name="M";
    node.data=0;
    (*sonsonIt).addSon(node);
    node.name="N";
    node.data=7;
    (*sonsonIt).addSon(node);

    node.name="J";
    node.data=5;
    (*sonIt).addSon(node);


    node.name="G";
    node.data=-1;
    (*it).addSon(node);

    //sonsonIt=(*sonIt).sons.begin();
    sonIt++;
    node.name="K";
    node.data=7;
    (*sonIt).addSon(node);
    node.name="L";
    node.data=8;
    (*sonIt).addSon(node);

    node.name="H";
    node.data=4;
    (*it).addSon(node);

}

int main()
{
    //srand(time(0));
    TreeNode tree;//, temp;
    tree.name=string("A");
    tree.data=-1;
    //tree.depth=0;
    //tree.parent=NULL;
    tree.nodeType=MaxNode;
    construct424(tree);
    //tree.populate(5);
    cout<<"before pruning the tree is like this:\n";
    displayTree(tree);
    cout<<tree.prune()<<endl;
    //temp=tree.prune();
    //cout<<temp;

    cout<<"and with minmax it like this:\n";
    cout<<tree.minmax()<<endl;
    displayTree(tree);

    return 0;
}


2. The result is like following:(How to understand the format? Each line output is one level of tree. The display of a node is

at this sequence: name, data (Min-Max-Type, number of son nodes)

before pruning the tree is like this:
A=-1(MaxNode2)
B=-1(MinNode2), C=-1(MinNode3),
D=3(MaxNode0), E=5(MaxNode0), F=-1(MaxNode2), G=-1(MaxNode2), H=4(MaxNode0),
I=-1(MinNode2), J=5(MinNode0), K=7(MinNode0), L=8(MinNode0),
M=0(MaxNode0), N=7(MaxNode0),
name:C
number of sons:3
node type:MinNode

and with minmax it like this:
4
A=4(MaxNode2)
B=3(MinNode2), C=4(MinNode3),
D=3(MaxNode0), E=5(MaxNode0), F=5(MaxNode2), G=8(MaxNode2), H=4(MaxNode0),
I=0(MinNode2), J=5(MinNode0), K=7(MinNode0), L=8(MinNode0),
M=0(MaxNode0), N=7(MaxNode0),
Press any key to continue