go.cpp

围棋人机对弈程序源码 此版本目前还只能下布局阶段

#include "stdafx.h"
#include "Go.h"


//整数集合类---------------------------------------------------------------------------------------

//初始化
CIntGather::CIntGather(){head=NULL;length=0;}

//添加元素
void CIntGather::Add(int elem)
{
	IntElem* now=head;
	while(now)
	{
		if(now->num==elem)return;
		now=now->next;
	}
    now=new IntElem;
	now->num=elem;
	now->next=head;
	head=now;
	length++;
}

//删除元素
void CIntGather::Remove(int elem)
{
    IntElem* dead=head;
	IntElem* prev=head;
	while(dead)
	{
		if(dead->num==elem)
		{
			length--;
			if(dead==head)head=head->next;
			prev->next=dead->next;
			delete dead;
			return;
		}
		prev=dead;
		dead=dead->next;
	}
}

//清空所有元素
void CIntGather::Reset()
{
	IntElem* now;
	while(head)
	{
		now=head;
		head=head->next;
		delete now;
	}
	head=NULL;
	length=0;
}

//清理
CIntGather::~CIntGather(){Reset();}

//整数集合类---------------------------------------------------------------------------------------



//棋串类-------------------------------------------------------------------------------------------

//初始化
CGoString::CGoString(int n,int c)
{
	nEyesNumber=0;//新串必然无眼
	nColor=c;//赋予黑白属性
	Nodes.Add(n);//新串初始节点
}

//棋串类-------------------------------------------------------------------------------------------



//动态棋串集合类-----------------------------------------------------------------------------------

//初始化
CGoStringGather::CGoStringGather(){head=NULL;length=0;}


//添加元素
void CGoStringGather::Add(CGoString* elem)
{
	GoStrElem* now=head;
	while(now)
	{
		if(now->pString==elem)return;
		now=now->next;
	}
    now=new GoStrElem;
	now->pString=elem;
	now->next=head;
	head=now;
	length++;
}

//删除元素
void CGoStringGather::Remove(CGoString* elem)
{
    GoStrElem* dead=head;
	GoStrElem* prev=head;
	while(dead)
	{
		if(dead->pString==elem)
		{
			length--;
			if(dead==head)head=head->next;
			prev->next=dead->next;
			delete dead;
			return;
		}
		prev=dead;
		dead=dead->next;
	}
}

//清空所有元素
void CGoStringGather::Reset()
{
	GoStrElem* now;
	while(head)
	{
		now=head;
		head=head->next;
		delete now;
	}
	head=NULL;
	length=0;
}

//清理
CGoStringGather::~CGoStringGather(){Reset();}

//动态棋串集合类-----------------------------------------------------------------------------------



//定式类-------------------------------------------------------------------------------------------

//初始化
CGoForm::CGoForm()
{
	pConn.CreateInstance("ADODB.Connection");//数据库对象实例化
    try{pConn->Open("Provider=Microsoft.Jet.OLEDB.4.0;Data Source=ds.mdb","","",adModeUnknown);}
	catch(_com_error e)
	{
		CString errormessage;
		errormessage.Format("连接数据库失败!\r\n错误信息:%s",e.ErrorMessage());
        AfxMessageBox(errormessage);//显示错误信息
	}
	pRecs.CreateInstance("ADODB.Recordset");//记录集对象实例化
	for(int i=0;i<4;i++)
	{
		nFormState[i]=BLANK;//定式状态初始值为空
		sFormSteps[i]="";//定式步骤为空
	}
	nActiveForm=0;//当前定式区为空
}

//清理
CGoForm::~CGoForm()
{
	if(pRecs->State)pRecs->Close();//关闭记录集
	pRecs.Release();
	if(pConn->State)pConn->Close();//关闭数据库
	pConn.Release();
}

//将棋步映射为用dir坐标系表示的字符串，若棋步不在相应坐标系内，返回“KO”（KickOut）
CString CGoForm::MapTo(int n,int dir)
{
	int x=n%19;
	int y=n/19;
	CString s="";
	char c;
	switch(dir)
	{
	case LTOP:{if((x>9)||(y>9))return "KO";c=x+'A';s+=c;c=y+'A';s+=c;break;}
	case RTOP:{if((x<9)||(y>9))return "KO";c=18-x+'A';s+=c;c=y+'A';s+=c;break;}
	case LBOT:{if((x>9)||(y<9))return "KO";c=x+'A';s+=c;c=18-y+'A';s+=c;break;}
	case RBOT:{if((x<9)||(y<9))return "KO";c=18-x+'A';s+=c;c=18-y+'A';s+=c;break;}
	}
	return s;
}

//将用dir坐标系表示的字符串映射为棋步
int CGoForm::MapFrom(CString s,int dir)
{
	int x;
	int y;
	int i=s.GetLength();
	switch(dir)
	{
	case LTOP:{x=s[0]-'A';y=s[1]-'A';break;}
	case RTOP:{x=18+'A'-s[0];y=s[1]-'A';break;}
	case LBOT:{x=s[0]-'A';y=18+'A'-s[1];break;}
	case RBOT:{x=18+'A'-s[0];y=18+'A'-s[1];break;}
	}
	return y*19+x;
}

//将str代表的行棋步骤转换为代表其对称步骤的字符串
CString CGoForm::Symmetrical(CString str)
{
	int n=str.GetLength()/2;
	CString newstr="";
	for(int i=0;i<n;i++)
	{
		newstr+=str[i*2+1];
		newstr+=str[i*2];
	}
	return newstr;
}

//检查str代表的行棋步骤是否依照定式
int CGoForm::CheckForm(CString str)
{
	CString sql;
	CString add;
	CString symstr=Symmetrical(str);
	sql.Format("select count(*) as num from ds where (left(steps,%d)='%s' or left(steps,%d)='%s') and len(steps)>%d",
		        str.GetLength(),str,str.GetLength(),symstr,str.GetLength());
	_variant_t var(sql);
	try{pRecs->Open(var,pConn.GetInterfacePtr(),adOpenStatic,adLockReadOnly,adCmdText);}
    catch(_com_error *e){AfxMessageBox(e->ErrorMessage());}  
	var=pRecs->GetCollect("num");
	pRecs->Close();
	return var.iVal;
}

//获得满足条件的下一步定式走法列表
void CGoForm::GetFormNextSteps(CString str,CString term,int dir,CIntGather* pResult)
{
	CString sql;
	_variant_t var;
	CString symstr=Symmetrical(str);
	sql.Format("select * from ds where left(steps,%d)='%s' and %s",str.GetLength(),str,term);
	var.SetString(sql);
	try{pRecs->Open(var,pConn.GetInterfacePtr(),adOpenStatic,adLockReadOnly,adCmdText);}
	catch(_com_error *e){AfxMessageBox(e->ErrorMessage());}  
	while(!pRecs->adoEOF)
	{
		var=pRecs->GetCollect("steps");
		sql=(char *)_bstr_t(var);
		sql=sql.Right(sql.GetLength()-str.GetLength());
		sql=sql.Left(2);
		if(sql=="XX")pResult->Add(361);
		else if(sql!="")pResult->Add(MapFrom(sql,dir));
		pRecs->MoveNext();
	}
	pRecs->Close();
	if(symstr==str)return;
	sql.Format("select * from ds where left(steps,%d)='%s' and %s",str.GetLength(),symstr,term);
	var.SetString(sql);
	try{pRecs->Open(var,pConn.GetInterfacePtr(),adOpenStatic,adLockReadOnly,adCmdText);}
	catch(_com_error *e){AfxMessageBox(e->ErrorMessage());}  
	while(!pRecs->adoEOF)
	{
		var=pRecs->GetCollect("steps");
		sql=(char *)_bstr_t(var);
		sql=sql.Right(sql.GetLength()-str.GetLength());
		sql=Symmetrical(sql.Left(2));
		if(sql=="XX")pResult->Add(361);
		else if(sql!="")pResult->Add(MapFrom(sql,dir));
		pRecs->MoveNext();
	}
	pRecs->Close();
}

//根据当前落子位置更新定式状态及步骤
void CGoForm::UpdateFormState(int n,int color)
{
	CString s;
	for(int i=0;i<4;i++)
	{
        s=MapTo(n,LTOP+i);//将棋步映射为用相应角相对坐标表示的字符串
		if((nFormState[i]!=CLOSED)&&(s!="KO"))//判断落子是否在未进行中的定式区
	    {
		    if(nFormState[i]==color)sFormSteps[i]+="XX";//若连续两手同色，判对方脱先一手
			else nFormState[i]=color;//更新定式状态及步骤
		    sFormSteps[i]+=s;
		    if(CheckForm(sFormSteps[i])==0)//若破坏定式，设置定式状态关闭
			{
				nFormState[i]=CLOSED;
				if(i==nActiveForm-LTOP)nActiveForm=0;
			}
			else nActiveForm=LTOP+i;//若符合定式，设置为当前定式区
	    }
    }
}

//根据定式状态及步骤，选择定式下法
int CGoForm::ChoseFormStep(int color)
{
	CIntGather base;
	CIntGather option;
	CString term;
	CString str;
	IntElem* now;
	int i;
	if(color==BLACK)term="score>'2'";
	else term="score<'4'";
	if(nActiveForm)
	{
        str=sFormSteps[nActiveForm-LTOP];
	    if(nFormState[nActiveForm-LTOP]==color)str+="XX";
        GetFormNextSteps(str,term,nActiveForm,&base);
	    i=base.length;
	    base.Remove(361);
	    if((base.length==i)&&(i!=0))//当前定式区不能脱先
	    {
			now=base.head;
            srand((unsigned)time(NULL));//初始化随机种子
            while((rand()%i)&&(now!=NULL)){now=now->next;i--;}
            if(now)return now->num;
		    return base.head->num;
	    }
	}
    for(i=0;i<4;i++)
	{
        if(i==nActiveForm-LTOP)continue;//跳过当前定式区
		if(nFormState[i]==BLANK)
		{
			option.Add(MapFrom("CD",LTOP+i));
		    option.Add(MapFrom("DC",LTOP+i));
			option.Add(MapFrom("DD",LTOP+i));
		}
	    else if(nFormState[i]!=CLOSED)
		{
			str=sFormSteps[i];
			if(nFormState[i]==color)str+="XX";
			GetFormNextSteps(str,term,LTOP+i,&option);
		}
	}
	//并列当前定式区及其他定式区的所有可选下法并取出随机下法
	option.Remove(361);
	if((base.length==0)&&(option.length==0))return 361;
	i=base.length+option.length;
	now=base.head;
    srand((unsigned)time(NULL));//初始化随机种子
    while((rand()%i)&&(now!=NULL)){now=now->next;i--;}
    if(now)return now->num;
	now=option.head;
	while((rand()%i)&&(now!=NULL)){now=now->next;i--;}
	if(now)return now->num;
	return base.head->num;
}

//定式类-------------------------------------------------------------------------------------------



//棋局类-------------------------------------------------------------------------------------------

//初始化
CGo::CGo()
{
    for(int i=0;i<361;i++)pHolder[i]=NULL;//初始化棋盘
	nSteps=0;
	nHotPlace=361;
	nStage=PROLOG;
	pForm=new CGoForm;
}
	
//清理
CGo::~CGo()
{
    if(pForm)delete pForm; 
}

//重开新局
void CGo::Reset()
{
    for(int i=0;i<361;i++)pHolder[i]=NULL;	//清空棋盘
	Strings.Reset();	//清空棋串列表
	nSteps=0;	//清空棋步

	//清空定式环境
	if(pForm)delete pForm;
	pForm=new CGoForm;

    nHotPlace=361;	//清空状态
}

//检查n点dir方向的落子状态并返回状态值
int CGo::Check(int n,int dir)
{
	int m;
	switch(dir)
	{
	case UP:{if(n<19)return FRAME;m=n-19;break;}
	case DOWN:{if(n>341)return FRAME;m=n+19;break;}
	case LEFT:{if(n%19==0)return FRAME;m=n-1;break;}
	case RIGHT:{if(n%19==18)return FRAME;m=n+1;break;}
	}
	if(pHolder[m]==NULL)return BLANK;
	return pHolder[m]->nColor;
}

//杀掉占据n点的棋串，并更新周边棋串的气，返回杀掉的子数
int CGo::KillString(int n)
{
	CGoString* dead=pHolder[n];
	IntElem* now=dead->Nodes.head;
	int c=dead->nColor;
	int num=dead->Nodes.length;
	int i;
	while(now)
	{
		i=now->num;
		if(Check(i,UP)==1-c)pHolder[i-19]->Breaths.Add(i);
		if(Check(i,DOWN)==1-c)pHolder[i+19]->Breaths.Add(i);
		if(Check(i,LEFT)==1-c)pHolder[i-1]->Breaths.Add(i);
		if(Check(i,RIGHT)==1-c)pHolder[i+1]->Breaths.Add(i);
        pHolder[i]=NULL;
		now=now->next;
	}
	Strings.Remove(dead);
	delete dead;
	return num;
}

//合并分别占据n点和m点的棋串
void CGo::JoinString(int n,int m)
{
	CGoString* dead=pHolder[m];
	CGoString* live=pHolder[n];
	if(dead==live)return;
	IntElem* now=dead->Breaths.head;
	while(now)
	{
		live->Breaths.Add(now->num);
		now=now->next;
	}
	now=dead->Nodes.head;
	while(now)
	{
		pHolder[now->num]=live;
		live->Nodes.Add(now->num);
		now=now->next;
	}
	live->nEyesNumber+=dead->nEyesNumber;
    Strings.Remove(dead);
	delete dead;
}

//判断n点是否合法落子点
BOOL CGo::CanGo(int n)
{
	//非空点及打劫点不允许落子
    if(pHolder[n]||(nHotPlace==n))return FALSE;
	
	//不允许自杀
	int c=nSteps%2;
	int u=Check(n,UP);
	int d=Check(n,DOWN);
	int l=Check(n,LEFT);
	int r=Check(n,RIGHT);
	if(u==BLANK)return TRUE;
	if((u==1-c)&&(pHolder[n-19]->Breaths.length==1))return TRUE;
	if((u==c)&&(pHolder[n-19]->Breaths.length>1))return TRUE;
	if(d==BLANK)return TRUE;
	if((d==1-c)&&(pHolder[n+19]->Breaths.length==1))return TRUE;
	if((d=c)&&(pHolder[n+19]->Breaths.length>1))return TRUE;
	if(l==BLANK)return TRUE;
	if((l==1-c)&&(pHolder[n-1]->Breaths.length==1))return TRUE;
	if((l==c)&&(pHolder[n-1]->Breaths.length>1))return TRUE;
	if(r==BLANK)return TRUE;
	if((r==1-c)&&(pHolder[n+1]->Breaths.length==1))return TRUE;
	if((r==c)&&(pHolder[n+1]->Breaths.length>1))return TRUE;

	return FALSE;
}

//在n点落子并更新棋局各状态
void CGo::Go(int n)
{
	//建立新串
	int c=nSteps%2;
	pHolder[n]=new CGoString(n,c);
	if(Check(n,UP)==BLANK)pHolder[n]->Breaths.Add(n-19);
	if(Check(n,DOWN)==BLANK)pHolder[n]->Breaths.Add(n+19);
	if(Check(n,LEFT)==BLANK)pHolder[n]->Breaths.Add(n-1);
	if(Check(n,RIGHT)==BLANK)pHolder[n]->Breaths.Add(n+1);

	//杀掉敌方死串，判断并设置打劫点
	int kill=0;
	if((Check(n,UP)==1-c)&&(pHolder[n-19]->Breaths.length==1))
		kill+=KillString(n-19);
	if((Check(n,DOWN)==1-c)&&(pHolder[n+19]->Breaths.length==1))
		kill+=KillString(n+19);
	if((Check(n,LEFT)==1-c)&&(pHolder[n-1]->Breaths.length==1))
		kill+=KillString(n-1);
	if((Check(n,RIGHT)==1-c)&&(pHolder[n+1]->Breaths.length==1))
		kill+=KillString(n+1);
	if((kill==1)&&(pHolder[n]->Breaths.length==1))nHotPlace=pHolder[n]->Breaths.head->num;
	else nHotPlace=361;

	//减相邻棋串的气
	if(Check(n,UP)<WHITE)pHolder[n-19]->Breaths.Remove(n);
	if(Check(n,DOWN)<WHITE)pHolder[n+19]->Breaths.Remove(n);
	if(Check(n,LEFT)<WHITE)pHolder[n-1]->Breaths.Remove(n);
	if(Check(n,RIGHT)<WHITE)pHolder[n+1]->Breaths.Remove(n);

    //合并相邻的己方棋串
	if(Check(n,UP)==c)JoinString(n,n-19);
	if(Check(n,DOWN)==c)JoinString(n,n+19);
	if(Check(n,LEFT)==c)JoinString(n,n-1);
	if(Check(n,RIGHT)==c)JoinString(n,n+1);

    //落子完成
	StepList[nSteps]=n;
	nSteps++;
	Strings.Add(pHolder[n]);

	//更新定式状态
	pForm->UpdateFormState(n,c);
}

//程序选步
int CGo::ComputerChoice()
{
	int c=nSteps%2;
	return pForm->ChoseFormStep(c);
}

//棋局类-------------------------------------------------------------------------------------------