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>

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

    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

    ¡¡