alphabeta1.cpp

用VC实现的

// AlphaBeta1.cpp: implementation of the CAlphaBeta class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "alphabeta.h"
#include "AlphaBeta1.h"
#pragma warning(disable:4786)
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CAlphaBeta::CAlphaBeta()
{
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			this->status[i][j] = 'Y';
		}
	}
	(this->position).first = -10;
	(this->position).second.first = -1;
	(this->position).second.second = -1;
	flag = 0;
}

CAlphaBeta::~CAlphaBeta()
{

}

void CAlphaBeta::extend(char a[3][3])
{
	char** temp = new char*[3];
	char** tmp = new char*[3];
	for(int t=0;t<3;t++)
	{
		temp[t] = new char[3];
		tmp[t] = new char[3];
	}
	for(int m=0;m<3;m++)
	{
		for(int n=0;n<3;n++)
		{
			temp[m][n] = a[m][n];
			tmp[m][n] = a[m][n];
		}
	}
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if('Y'==temp[i][j])
			{
				temp[i][j] = '*';
				pair<pair<pair<char**,int>,pair<int,int> >,queue<pair<pair<char**,int>,pair<int,int> > > >p;
				p.first.first.first = new char*[3];
				for(int c=0;c<3;c++)
				{
					p.first.first.first[c] = new char[3];
				}
				for(int i1=0;i1<3;i1++)
				{
					for(int j1=0;j1<3;j1++)
					{
						p.first.first.first[i1][j1] = temp[i1][j1];
					}
				}
				p.first.first.second = 10;
				p.first.second.first = i;
				p.first.second.second = j;
				queue<pair<pair<char**,int>,pair<int,int> > > q;
				if(q.empty())
				{
					p.second = q;
					tree.push_back(p);
					for(int i1=0;i1<3;i1++)
					{
						for(int j1=0;j1<3;j1++)
						{
							temp[i1][j1] = tmp[i1][j1];
						}
					}
				}
			}
		}
	}

}

void CAlphaBeta::extend_first()
{
	char** temp = new char*[3];
	char** tmp = new char*[3];
	for(int t=0;t<3;t++)
	{
		temp[t] = new char[3];
		tmp[t] = new char[3];
	}
	if(!tree.empty())
	{
		pair<pair<pair<char**,int>,pair<int,int> >,queue<pair<pair<char**,int>,pair<int,int> > > > first = tree.front();
		tree.pop_front();
		queue<pair<pair<char**,int>,pair<int,int> > > q;
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				temp[i][j] = first.first.first.first[i][j];
				tmp[i][j] = first.first.first.first[i][j];
			}
		}
		for(int x=0;x<3;x++)
		{
			for(int y=0;y<3;y++)
			{
				if('Y'!=temp[x][y])
				{
					y++;
				}
				else
				{
					temp[x][y] = 'o';
				}
				int max = 0;
				int min = 0;
				for(int m=0;m<3;m++)
				{
					for(int n=0;n<3;n++)
					{
						if('Y'==temp[m][n])
						{
							temp[m][n] = '*';
						}
					}
				}
				max = this->get_value(temp);
				for(int i1=0;i1<3;i1++)
				{
					for(int j1=0;j1<3;j1++)
					{
						temp[i1][j1] = tmp[i1][j1];
					}
				}
				for(int m1=0;m1<3;m1++)
				{
					for(int n1=0;n1<3;n1++)
					{
						if('Y'==temp[m1][n1])
						{
							temp[m1][n1] = 'o';
						}
					}
				}
				min = this->get_value(temp);
				for(int i2=0;i2<3;i2++)
				{
					for(int j2=0;j2<3;j2++)
					{
						temp[i2][j2] = tmp[i2][j2];
					}
				}
//pair<pair<pair<char**,int>,pair<int,int> >,queue<pair<pair<char**,int>,pair<int,int> > > > first
				pair<pair<char**,int>,pair<int,int> > child;
				child.first.first = tmp;
				child.first.second = max-min;
				child.second.first = x;
				child.second.second = y;
				q.push(child);
			}
		}
		first.second = q;
		tree.push_front(first);
	}
	for(int ii=0;ii<3;ii++)
	{
		delete[] temp[ii];
		delete[] tmp[ii];
	}
	delete[] temp;
	delete[] tmp;
}

void CAlphaBeta::extend_other()
{
	tree.pop_front();
	char** Temp = new char*[3];
	char** tmp = new char*[3];
	for(int t=0;t<3;t++)
	{
		Temp[t] = new char[3];
		tmp[t] = new char[3];
	}
	while(!tree.empty())
	{
		pair<pair<pair<char**,int>,pair<int,int> >,queue<pair<pair<char**,int>,pair<int,int> > > > first = tree.front();

		queue<pair<pair<char**,int>,pair<int,int> > > q;
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				tmp[i][j] = first.first.first.first[i][j];
				Temp[i][j] = first.first.first.first[i][j];
			}
		}	

		for(int x=0;x<3;x++)
		{
			if(1==flag)
			{
				break;
			}
			for(int y=0;y<3;y++)
			{
				flag = 0;
				if('Y'!=Temp[x][y])
				{
					y++;
				}
				else
				{
					Temp[x][y] = 'o';
				}
				int max = 0;
				int min = 0;
				for(int m=0;m<3;m++)
				{
					for(int n=0;n<3;n++)
					{
						if('Y'==Temp[m][n])
						{
							Temp[m][n] = '*';
						}
					}
				}
				max = this->get_value(Temp);
				for(int i1=0;i1<3;i1++)
				{
					for(int j1=0;j1<3;j1++)
					{
						Temp[i1][j1] = tmp[i1][j1];
					}
				}
				for(int m1=0;m1<3;m1++)
				{
					for(int n1=0;n1<3;n1++)
					{
						if('Y'==Temp[m1][n1])
						{
							Temp[m1][n1] = 'o';
						}
					}
				}
				min = this->get_value(Temp);
				if((max-min)<=(this->position.first))
				{
					flag = 1;
					pair<pair<char**,int>,pair<int,int> > child;
					child.first.first = tmp;
					child.first.second = max-min;
					child.second.first = x;
					child.second.second = y;
					q.push(child);
					break;
				}
				for(int i2=0;i2<3;i2++)
				{
					for(int j2=0;j2<3;j2++)
					{
						Temp[i2][j2] = tmp[i2][j2];
					}
				}
				pair<pair<char**,int>,pair<int,int> > child;
				child.first.first = tmp;
				child.first.second = max-min;
				child.second.first = x;
				child.second.second = y;
				q.push(child);
			}
		}
		first.second = q;
		
		int temp = 10;
		flag = 0;
		while(!first.second.empty())
		{
			pair<pair<char**,int>,pair<int,int> > p = first.second.front();
			if(p.first.second<temp)
			{
				temp = p.first.second;
			}
			first.second.pop();
		}
		
		if((this->position.first)<temp)
		{
			this->position.first = temp;
			this->position.second.first = tree.front().first.second.first;
			this->position.second.second = tree.front().first.second.second;
		}
		

		tree.pop_front();
	}
	for(int i=0;i<3;i++)
	{
		if((this->status[i][0]==this->status[i][1])&((this->status[i][0])=='o')&(this->status[i][2]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = i;
			this->position.second.second = 2;
		}
		if((this->status[i][1]==this->status[i][2])&((this->status[i][1])=='o')&(this->status[i][0]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = i;
			this->position.second.second = 0;
		}
		if((this->status[i][0]==this->status[i][2])&((this->status[i][0])=='o')&(this->status[i][1]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = i;
			this->position.second.second = 1;
		}

		if((this->status[0][i]==this->status[1][i])&((this->status[0][i])=='o')&(this->status[2][i]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = 2;
			this->position.second.second = i;
		}
		if((this->status[1][i]==this->status[2][i])&((this->status[1][i])=='o')&(this->status[0][i]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = 0;
			this->position.second.second = i;
		}
		if((this->status[0][i]==this->status[2][i])&((this->status[0][i])=='o')&(this->status[1][i]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = 1;
			this->position.second.second = i;
		}
	}
	if((this->status[0][0]==this->status[1][1])&(this->status[0][0]=='o')&(this->status[2][2]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 2;
		this->position.second.second = 2;
	}
	if((this->status[0][0]==this->status[2][2])&(this->status[2][2]=='o')&(this->status[1][1]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 1;
		this->position.second.second = 1;
	}
	if((this->status[2][2]==this->status[1][1])&(this->status[1][1]=='o')&(this->status[0][0]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 0;
		this->position.second.second = 0;
	}
	if((this->status[2][0]==this->status[1][1])&(this->status[1][1]=='o')&(this->status[0][2]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 0;
		this->position.second.second = 2;
	}
	if((this->status[0][2]==this->status[1][1])&(this->status[1][1]=='o')&(this->status[2][0]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 2;
		this->position.second.second = 0;
	}
	if((this->status[2][0]==this->status[0][2])&(this->status[0][2]=='o')&(this->status[1][1]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 1;
		this->position.second.second = 1;
	}

	for(i=0;i<3;i++)
	{
		if((this->status[i][0]==this->status[i][1])&((this->status[i][0])=='*')&(this->status[i][2]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = i;
			this->position.second.second = 2;
		}
		if((this->status[i][1]==this->status[i][2])&((this->status[i][1])=='*')&(this->status[i][0]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = i;
			this->position.second.second = 0;
		}
		if((this->status[i][0]==this->status[i][2])&((this->status[i][0])=='*')&(this->status[i][1]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = i;
			this->position.second.second = 1;
		}

		if((this->status[0][i]==this->status[1][i])&((this->status[0][i])=='*')&(this->status[2][i]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = 2;
			this->position.second.second = i;
		}
		if((this->status[1][i]==this->status[2][i])&((this->status[1][i])=='*')&(this->status[0][i]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = 0;
			this->position.second.second = i;
		}
		if((this->status[0][i]==this->status[2][i])&((this->status[0][i])=='*')&(this->status[1][i]=='Y'))
		{
			this->position.first = 100;
			this->position.second.first = 1;
			this->position.second.second = i;
		}
	}
	if((this->status[0][0]==this->status[1][1])&(this->status[0][0]=='*')&(this->status[2][2]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 2;
		this->position.second.second = 2;
	}
	if((this->status[0][0]==this->status[2][2])&(this->status[2][2]=='*')&(this->status[1][1]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 1;
		this->position.second.second = 1;
	}
	if((this->status[2][2]==this->status[1][1])&(this->status[1][1]=='*')&(this->status[0][0]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 0;
		this->position.second.second = 0;
	}
	if((this->status[2][0]==this->status[1][1])&(this->status[1][1]=='*')&(this->status[0][2]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 0;
		this->position.second.second = 2;
	}
	if((this->status[0][2]==this->status[1][1])&(this->status[1][1]=='*')&(this->status[2][0]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 2;
		this->position.second.second = 0;
	}
	if((this->status[2][0]==this->status[0][2])&(this->status[0][2]=='*')&(this->status[1][1]=='Y'))
	{
		this->position.first = 100;
		this->position.second.first = 1;
		this->position.second.second = 1;
	}

}

void CAlphaBeta::choose_worst()
{
	if(!tree.empty())
	{
		int temp = 10;
		pair<pair<pair<char**,int>,pair<int,int> >,queue<pair<pair<char**,int>,pair<int,int> > > > first = tree.front();
		while(!first.second.empty())
		{
			pair<pair<char**,int>,pair<int,int> > p = first.second.front();
			if(p.first.second<temp)
			{
				temp = p.first.second;
			}
			first.second.pop();
		}
		tree.front().first.first.second = temp;
		this->position.first = temp;
		this->position.second.first = tree.front().first.second.first;
		this->position.second.second = tree.front().first.second.second;
	}
}

int CAlphaBeta::get_value(char** a)const
{
	int value = 0;
	for(int j=0;j<3;j++)
	{
		if((a[0][j]==a[1][j])&(a[1][j]==a[2][j])&(a[0][j]!='Y'))
		{
			value++;
		}
		if((a[j][0]==a[j][1])&(a[j][1]==a[j][2])&(a[j][0]!='Y'))
		{
			value++;
		}
	}
	if((a[0][0]==a[1][1])&(a[1][1]==a[2][2])&(a[0][0]!='Y'))
	{
		value++;
	}
	if((a[2][0]==a[1][1])&(a[1][1]==a[0][2])&(a[1][1]!='Y'))
	{
		value++;
	}
	return value;
}