alpha_beta.cpp

Alpha_Beta剪枝程序

/*
*	作者:  周勇禄
*	学号:  2005011327
*	班级:  计54
*	联系方式:  [e-mail]
*/

//特殊处理1：读入博弈树的过程中，结点名称对大小写敏感，而root、end、value对大小写不敏感
//特殊处理2：读入博弈树的过程中，给某个结点分配子结点或赋值时，若该结点没有在博弈树已建好的部分中，则报错并退出

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

//数据类型声明
struct Node {
	int value;					//估计值
	string name;				//名称
	int depth;					//深度
	Node* parent;				//双亲结点
	vector<Node*> children;		//子女结点列表
	string next;				//下一步该走的结点名称
};

//常量、变量声明
Node* root;						//根结点
const int MAX = 10000;			//预置极大值
const int MIN = -10000;			//预置极小值

//函数声明
void buildTree();				//读入文件构造博弈树
void Alpha_Beta(Node*);			//扫描博弈树，对相应结点做 Alpha_Beta 剪枝
Node* findNode(Node*, string);	//搜索博弈树，寻找指定名称的结点

//主函数
int main() {
	buildTree();
	Alpha_Beta(root);
	cout << "\n根结点: " << root->name << endl;
	cout << "倒推值: " << root->value << endl;
	cout << "应走的步骤: " << root->next << endl;
	return 0;
}

//函数定义
void buildTree() {				//读入文件构造博弈树
	string fileName;			//文件流
	cout << "博弈树文件名: ";
	cin >> fileName;
	ifstream fin(fileName.data());
	if(!fin) {
		cout << "找不到指定文件!" << endl;
		exit(0);
	}

	root = new Node();			//初始化根结点
	root->parent = NULL;
	root->depth = 0;
	root->value = MIN;
	root->next = "";

	string input;				//读入博弈树
	fin >> input;
	while(_stricmp(input.data(), "value") != 0) {
		if(_stricmp(input.data(), "root") == 0) {	//根结点
			fin >> input;
			root->name = input;
		} else {				//非根结点
			Node* expected = findNode(root, input);
			if(expected == NULL) {					//当前字符串所指定的结点不存在
				cout << "名为 " << input << " 的结点不存在!" << endl;
				exit(0);
			}
			fin >> input;
			while(_stricmp(input.data(), "end") != 0) {	//添加当前结点的子女结点
				Node* child = new Node();
				child->parent = expected;
				child->name = input;
				child->depth = expected->depth + 1;
				child->value = child->depth % 2 == 0 ? MIN : MAX;
				child->next = "";
				expected->children.push_back(child);
				fin >> input;
			}
		}
		fin >> input;
	}
	fin >> input;
	while(_stricmp(input.data(), "end") != 0) {
		Node* expected = findNode(root, input);
		if(expected == NULL) {				//当前字符串所指定的结点不存在
			cout << "名为 " << input << " 的结点不存在!" << endl;
			exit(0);
		}
		int value;
		fin >> value;
		expected->value = value;
		fin >> input;
	}
	fin.close();
}

void Alpha_Beta(Node* node) {		//扫描博弈树，对相应结点做 Alpha_Beta 剪枝
	for (vector<Node*>::iterator it = node->children.begin(); it != node->children.end(); it ++) {
		Alpha_Beta(*it);			//深度优先搜索
		int v = (*it)->value;
		if(node->next == "") {
			node->value = v;
			node->next = (*it)->name;
		} else if(node->depth % 2 == 0 && v > node->value) {	//极大结点
			node->value = v;
			node->next = (*it)->name;
		} else if(node->depth % 2 != 0 && v < node->value) {	//极小结点
			node->value = v;
			node->next = (*it)->name;
		}

		Node* par = node->parent;		//准备剪枝
		while(par != NULL) {
			if((node->depth % 2 == 0 && node->value >= par->value)			//极大结点 >= 祖先的极小结点， Beta 剪枝
				|| (node->depth % 2 == 1 && node->value <= par->value)) {	//极小结点 <= 祖先的极大结点， Alpha 剪枝
					it ++;
					if(it == node->children.end())		//没有其它子结点
						return;

					cout << "剪枝: " << node->name << ": ";		//输出剪枝信息
					while (it != node->children.end()) {
						cout << (*it)->name << " ";
						it ++;
					}
					cout << endl;
					return;
			}

			par = par->parent;						//祖先结点
			if(par != NULL) par = par->parent;
			else break;
		}
	}
}

Node* findNode(Node* node, string name) {		//搜索博弈树，寻找指定名称的结点
	if(node->name == name) return node;
	for(vector<Node*>::iterator it = node->children.begin(); it != node->children.end(); it ++) {
		Node* n = findNode(*it, name);
		if(n != NULL) return n;
	}
	return NULL;
}