prune.cpp

alpha and beta pruning 是人工智能方面的很重要的算法

#include<stdio.h>
#include<fstream>
#include<iostream>
using namespace std;
struct Tree                        // define  a data structure: tree
{
	int    value;
	int    children[50];
	int    alpha;
	int    beta;
	int    number_children;    
};
Tree tree[100];  // to present the nodes of this tree
char* outputname;
void Alpha_Beta_Search(int node);  
void Print(int node); // print the order in which the nodes are visited and the intermediate alpha and beta value
ofstream outputfile; 
int Max_value(int node, int alpha, int beta);  //Max  node
int Min_value(int node, int alpha, int beta);  //Min  node
int Max(int a, int b)
{
if (a>b) return a;
else  return b;
}
int Min(int a , int b)
{
if (a<b) return a;
else  return b;
}
void Input(char* filename)  //get the information of an arbitrary search tree
{                    	
	                                             // Open file
    fstream filein;
	filein.open(filename , fstream::in); //"input"
	int size_tree;
	filein >> size_tree;	  // the size of this tree
	while(!filein.eof()) {
		char type;
		filein >> type;
		int id;
		filein >> id;
		int i;
		switch (type) {
		case 'n':  
			filein>>tree[id].number_children;
			for (i=0;i<tree[id].number_children;i++)
				filein>>tree[id].children[i];
			break;
		case 'v':  
			filein>> tree[id].value;
			break;
		}
	
	}
		filein.close();
}
void	Alpha_Beta_Search(int node)
	{
		int value;
		value=Max_value(node, -300, +300);  // initial value of node, alpha and beta
		outputfile<<"value="<<value<<endl;
		
	}
void	Print(int node)  //print the order in which the nodes are visited and the intermediate alpha and beta value
{ 
		outputfile<<node<<" ";
			if(tree[node].alpha==-300)
			outputfile<<"-inf ";
			else  outputfile<<tree[node].alpha<<" ";
			if(tree[node].beta==300)
			    outputfile<<"inf \n";
	        else  outputfile<<tree[node].beta<<" \n ";

	}
	
        int Max_value(int node, int alpha, int beta)  //Max function
	{
		tree[node].alpha = alpha;
		tree[node].beta = beta;
	
		Print(node);
		if (tree[node].number_children == 0)
			return tree[node].value;
		int value = -300;
		for (int i=0; i < tree[node].number_children; i++) {
			value = Max(value, Min_value(tree[node].children[i], tree[node].alpha, tree[node].beta));
			if (value < beta) {
				tree[node].alpha = Max(tree[node].alpha, value);
				Print(node);
			}
			else {
     			Print(node);
				return value;
			}
		}
		return value;
		
}
	int Min_value(int node, int alpha, int beta)  // Min function
	{   
		tree[node].alpha=alpha;
		tree[node].beta=beta;
		Print(node);
		if(tree[node].number_children==0)
			return tree[node].value;
		int value = 300;
		for(int i=0; i<tree[node].number_children; i++){
	 value  = Min (value, Max_value(tree[node].children[i],tree[node].alpha, tree[node].beta));
		   if(value > alpha){
			 tree[node].beta= Min(tree[node].beta,value);
			  Print(node);
						   }
						   else {
							
							   Print(node);
							   return  value;
						   }
					   }
					 
		return value;
		
}
	int main(int argv, char** argc) // main function
	{
		if ( argv != 3 )
		{
			cout<<"error!"<<endl;	//prompt for error
			return 1;
		}
		outputfile.open( argc[2], ios_base::out );
		Input( argc[1] );
		Alpha_Beta_Search(0);
		outputfile.close();
		return  0;
	}