alpha_beta.cpp

人智经典算法的实现

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

struct TreeNode{        //定义树节点类型
	string  Name;         //节点名字
	int Value;                //节点的估计值
	vector<int> vect;    //存放子节点下标
	bool haveValue;
	bool isMax;
	bool isMin;
	int dad;    //存放每一个节点的父亲节点在vector中的下标
};

vector<TreeNode> vec;
int  n=0;                     //用于记录要添加子节点的母节点编号
int  cut(TreeNode & t)         //用于剪枝的递归函数
{
	if(t.isMax)
	{
		if(t.vect.size()==0)
			return  t.Value;
		else {
			int max=-10000;
			int herecut=-1;
			for(vector<int>::size_type i=0;i<t.vect.size();i++)
			{
				vec[t.vect[i]].Value=cut(vec[t.vect[i]]);
				vec[t.vect[i]].haveValue=true;
				if(max<vec[t.vect[i]].Value)
				{
					  max=vec[t.vect[i]].Value;
			    	  t.Value=max;
		           	  t.haveValue=true;
					  int d=t.dad;
					  while(d!=-1)
					  {
							if(vec[d].isMin&&vec[d].haveValue&&vec[d].Value<max)
							{
								herecut=i;
								break;
							}
							d=vec[d].dad;
					  }
				 }
		    	if(herecut!=-1&&herecut+1<t.vect.size())
				{
					   cout<<"剪枝 :"<<t.Name<<":";
						for(vector<int>::size_type k=herecut+1;k<t.vect.size();k++)
						{cout<<vec[t.vect[k]].Name;}
						cout<<endl;
				}
						if(herecut!=-1)   break;
			}
			
				 return t.Value;
	    }
	}
	else if(t.isMin)
	{
		int min=10000;
		int herecut=-1;
		for(vector<int>::size_type i=0;i<t.vect.size();i++)
		{
			vec[t.vect[i]].Value=cut(vec[t.vect[i]]);
			vec[t.vect[i]].haveValue=true;
			if(min>vec[t.vect[i]].Value)
			{
				min=vec[t.vect[i]].Value;
				 t.Value=min;
		         t.haveValue=true;
				int d=t.dad;
						while(d!=-1){
							if(vec[d].isMax&&vec[d].haveValue&&vec[d].Value>min)
								{
									herecut=i;
									break;
								}
								d=vec[d].dad;
						}
		  	}
		   if(herecut!=-1&&herecut+1<t.vect.size())
			{
				cout<<"剪枝 :"<<t.Name<<":";
				for(vector<int>::size_type k=herecut+1;k<t.vect.size();k++)
				{cout<<vec[t.vect[k]].Name;}
				cout<<endl;
		   }
				if(herecut!=-1)    break;
		}
		 return t.Value;
	}
}

int main(){
	char   fileName[50];
	cin>>fileName;
    ifstream fin(fileName);
	if(!fin){
		cout<<"文件打开失败"<<endl;
		return 0;
	}
	char Str[30];
	while(fin>>Str){                                    //读入建树的循环
		if(strcmp(Str,"ROOT")==0)     
		{
			fin>>Str;
			TreeNode t;
			t.Name=Str;
			t.haveValue=false;
			t.isMax=true;
			t.isMin=false;
			t.dad=-1;
			vec.push_back(t);
			fin>>Str;
		}
		else if(strcmp(Str,"END")==0)
		{
			fin>>Str;
			if(strcmp(Str,"VALUE")==0)
				break;
			for(vector<int>::size_type i=0;i<vec.size();i++)
			{
				if(vec[i].Name==Str)
					n=i;
			}
		}
		else 
		{
			TreeNode t;
			t.Name=Str;
			t.haveValue=false;
			if(vec[n].isMax) 
			{t.isMax=false;
			t.isMin=true;}
			else
			{t.isMax=true;
			t.isMin=false;}
			t.dad=n;
			vec.push_back(t);
			vec[n].vect.push_back(vec.size()-1);
		}
	}
	while(fin>>Str)                        //为叶节点读入估计值的过程
	{
		if(strcmp(Str,"End")==0)
			break;
		for(vector<int>::size_type i=0;i<vec.size();i++)
		{
			int val=0;
			if(vec[i].Name==Str)
			{
				fin>>val;
			    vec[i].Value=val;
				vec[i].haveValue=true;
			}
		}
	}
//以上步骤已经将该博弈树的相关信息包括叶节点的估计值、父子关系存入一个vector之中，下面实现剪枝过程（先实现一个极大极小过程）
	   int res=cut(vec[0]);
	   cout<<"根节点:"<< vec[0].Name<<endl;
	   cout<<"倒推值:"<<res<<endl;
	   int m=0;
	   for(vector<int>::size_type i=0;i<vec[0].vect.size();i++)
	   {
		   if(vec[0].Value==vec[vec[0].vect[i]].Value)
		   {  m=i;break;}
	   }
	   cout<<"应走路径:"<<vec[vec[0].vect[m]].Name<<endl;

	   int y;
	   cout<<"请输入任意整数以结束程序"<<endl;
	   cin>>y;
	return 0;
}