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.
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.
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