ticktacktoeview.cpp

这是一字棋的极小极大搜索

	finished=0;
	side=-1;
	step=0;
	manTurn=true;
}

//判断是否棋结束，返回-1表示人赢了，1表示电脑赢了，2表示平局，0表示还没结束，finished为1表示结束
int CTicktacktoeView::Result()
{
	if((chessman[0][0]==1)&&(chessman[0][1]==1)&&(chessman[0][2]==1))
	{ finished=1;return 1;}
	if((chessman[0][0]==-1)&&(chessman[0][1]==-1)&&(chessman[0][2]==-1))
	{ finished=1;return -1;}

	if((chessman[1][0]==1)&&(chessman[1][1]==1)&&(chessman[1][2]==1))
	{ finished=1;return 1;}
	if((chessman[1][0]==-1)&&(chessman[1][1]==-1)&&(chessman[1][2]==-1))
	{ finished=1;return -1;}

	if((chessman[2][0]==1)&&(chessman[2][1]==1)&&(chessman[2][2]==1))
	{ finished=1;return 1;}
	if((chessman[2][0]==-1)&&(chessman[2][1]==-1)&&(chessman[2][2]==-1))
	{ finished=1;return -1;}

	if((chessman[0][0]==1)&&(chessman[1][0]==1)&&(chessman[2][0]==1))
	{ finished=1;return 1;}
	if((chessman[0][0]==-1)&&(chessman[1][0]==-1)&&(chessman[2][0]==-1))
	{ finished=1;return -1;}

	if((chessman[0][1]==1)&&(chessman[1][1]==1)&&(chessman[2][1]==1))
	{ finished=1;return 1;}
	if((chessman[0][1]==-1)&&(chessman[1][1]==-1)&&(chessman[2][1]==-1))
	{ finished=1;return -1;}

	if((chessman[0][2]==1)&&(chessman[1][2]==1)&&(chessman[2][2]==1))
	{ finished=1;return 1;}
	if((chessman[0][2]==-1)&&(chessman[1][2]==-1)&&(chessman[2][2]==-1))
	{ finished=1;return -1;}

	if((chessman[0][0]==1)&&(chessman[1][1]==1)&&(chessman[2][2]==1))
	{ finished=1;return 1;}
	if((chessman[0][0]==-1)&&(chessman[1][1]==-1)&&(chessman[2][2]==-1))
	{ finished=1;return -1;}

	if((chessman[2][0]==1)&&(chessman[1][1]==1)&&(chessman[0][2]==1))
	{ finished=1;return 1;}
	if((chessman[2][0]==-1)&&(chessman[1][1]==-1)&&(chessman[0][2]==-1))
	{ finished=1;return -1;}

	for(int i=0;i<chessman.size();i++)
	{
		for(int j=0;j<chessman[i].size();j++)
		{
			if(chessman[i][j]==0) return 0;
		}
	}
	finished=1;
	return 2;
}

//当前棋盘状态为QP，返回所有可能的走棋后的棋盘状态，ia=-1表示人走棋，ia=1表示电脑走棋
vector< vector< vector<int> > > CTicktacktoeView::NextQP(vector< vector<int> > QP,int ia)
{
	vector< vector< vector<int> > > vnext;//临时存储所有可能的走棋后的棋盘状态
	
	vector< vector<int> > vtemp;//临时存储某种走棋后的棋盘状态
	for(int i=0;i<QP.size();i++)
	{
		for(int j=0;j<QP[i].size();j++)
		{
			vtemp.push_back(QP[0]);vtemp.push_back(QP[1]);vtemp.push_back(QP[2]);

			if(QP[i][j]==0)
			{
				vtemp[i][j]=ia;
				vnext.push_back(vtemp);
			}
			vtemp.clear();
		}
	}
	return vnext;
}

//当前棋盘状态为QP，返回所有可能连线位置均为flag的个数，flag=1为电脑，flag=-1为人
int CTicktacktoeView::OneLineCounter(vector< vector<int> > QP,int flag)
{
	int counter=0;
	if((QP[0][0]==flag)&&(QP[0][1]==flag)&&(QP[0][2]==flag)) counter++;
	if((QP[1][0]==flag)&&(QP[1][1]==flag)&&(QP[1][2]==flag)) counter++;
	if((QP[2][0]==flag)&&(QP[2][1]==flag)&&(QP[2][2]==flag)) counter++;
	if((QP[0][0]==flag)&&(QP[1][0]==flag)&&(QP[2][0]==flag)) counter++;
	if((QP[0][1]==flag)&&(QP[1][1]==flag)&&(QP[2][1]==flag)) counter++;
	if((QP[0][2]==flag)&&(QP[1][2]==flag)&&(QP[2][2]==flag)) counter++;
	if((QP[0][0]==flag)&&(QP[1][1]==flag)&&(QP[2][2]==flag)) counter++;
	if((QP[2][0]==flag)&&(QP[1][1]==flag)&&(QP[0][2]==flag)) counter++;
	return counter;
}

//返回评价函数值：(所有空格上都放上MAX的棋子后三子成一线的总数)-(所有空格都放上MIN的棋子后三子成一线的总数)
int CTicktacktoeView::ValueFuction(vector< vector<int> > QP)
{
	vector< vector<int> > QP_Max,QP_Min;//max computer;min man
	QP_Max.resize(QP.size());
	QP_Min.resize(QP.size());
	for(int k=0;k<QP.size();k++)
	{
		QP_Max[k].resize(QP[k].size());
		QP_Min[k].resize(QP[k].size());
	}
	for(int i=0;i<QP.size();i++)
	{
		for(int j=0;j<QP[i].size();j++)
		{
			if(QP[i][j]==1) {QP_Max[i][j]=1;QP_Min[i][j]=1;}
			if(QP[i][j]==-1) {QP_Max[i][j]=-1;QP_Min[i][j]=-1;}
			if(QP[i][j]==0) {QP_Max[i][j]=1;QP_Min[i][j]=-1;}
		}
	}
	return OneLineCounter(QP_Max,1)-OneLineCounter(QP_Min,-1);
}

//返回电脑走棋时极大搜索某可能状态的评价函数值 当前棋盘状态为QP，搜索深度为depth
int CTicktacktoeView::Max(vector< vector<int> > QP,int depth)
{
	//如果电脑走棋使电脑赢棋,返回评价函数值100
	if((QP[0][0]==1)&&(QP[0][1]==1)&&(QP[0][2]==1)) return 100*depth;

	if((QP[1][0]==1)&&(QP[1][1]==1)&&(QP[1][2]==1)) return 100*depth;

	if((QP[2][0]==1)&&(QP[2][1]==1)&&(QP[2][2]==1)) return 100*depth;

	if((QP[0][0]==1)&&(QP[1][0]==1)&&(QP[2][0]==1)) return 100*depth;

	if((QP[0][1]==1)&&(QP[1][1]==1)&&(QP[2][1]==1)) return 100*depth;

	if((QP[0][2]==1)&&(QP[1][2]==1)&&(QP[2][2]==1)) return 100*depth;


	if((QP[0][0]==1)&&(QP[1][1]==1)&&(QP[2][2]==1)) return 100*depth;

	if((QP[2][0]==1)&&(QP[1][1]==1)&&(QP[0][2]==1)) return 100*depth;

	bool over=true;
	for(int k=0;k<QP.size();k++)
	{
		for(int t=0;t<QP[k].size();t++)
		{
			if(QP[k][t]==0) {over=false;break;}
		}
		if(!over) break;
	}
	if(over) return ValueFuction(QP);//此时棋盘已满,返回此状态的评价函数值
	if(depth==0) return ValueFuction(QP);//已经达到搜索深度,返回此状态的评价函数值
	vector< vector< vector<int> > > vtemp;
	vtemp=NextQP(QP,-1);//找出此状态时人所有走棋后的状态
	int itemp=Min(vtemp[0],depth-1);
	for(int i=1;i<vtemp.size();i++)
	{
		if(itemp>Min(vtemp[i],depth-1)) itemp=Min(vtemp[i],depth-1);
	}
	vtemp.clear();
	return itemp;//返回下一深度人所有走棋状态的评价函数最小值
}

//返回人走棋时极小搜索某可能状态的评价函数值 当前棋盘状态为QP，搜索深度为depth
int CTicktacktoeView::Min(vector< vector<int> > QP,int depth)
{
	//如果人走棋使电脑赢棋,返回评价函数值-100
	if((QP[0][0]==-1)&&(QP[0][1]==-1)&&(QP[0][2]==-1)) return -100*depth;

	if((QP[1][0]==-1)&&(QP[1][1]==-1)&&(QP[1][2]==-1)) return -100*depth;

	if((QP[2][0]==-1)&&(QP[2][1]==-1)&&(QP[2][2]==-1)) return -100*depth;

	if((QP[0][0]==-1)&&(QP[1][0]==-1)&&(QP[2][0]==-1)) return -100*depth;

	if((QP[0][1]==-1)&&(QP[1][1]==-1)&&(QP[2][1]==-1)) return -100*depth;

	if((QP[0][2]==-1)&&(QP[1][2]==-1)&&(QP[2][2]==-1)) return -100*depth;

	if((QP[0][0]==-1)&&(QP[1][1]==-1)&&(QP[2][2]==-1)) return -100*depth;

	if((QP[2][0]==-1)&&(QP[1][1]==-1)&&(QP[0][2]==-1)) return -100*depth;

	bool over=true;
	for(int k=0;k<QP.size();k++)
	{
		for(int t=0;t<QP[k].size();t++)
		{
			if(QP[k][t]==0) {over=false;break;}
		}
		if(!over) break;
	}
	if(over) return ValueFuction(QP);//此时棋盘已满,返回此状态的评价函数值
	if(depth==0) return ValueFuction(QP);//已经达到搜索深度,返回此状态的评价函数值
	vector< vector< vector<int> > > vtemp;
	vtemp=NextQP(QP,1);//找出此状态时电脑所有走棋后的状态
	int itemp=Max(vtemp[0],depth-1);
	for(int i=1;i<vtemp.size();i++)
	{
		if(itemp<Max(vtemp[i],depth-1)) itemp=Max(vtemp[i],depth-1);
	}
	vtemp.clear();
	return itemp;//返回下一深度电脑所有走棋状态的评价函数最大值
}

//寻找两个二维向量不同值所对应的x,y坐标
vector<int> CTicktacktoeView::FindPosition(vector< vector<int> > vec1,vector< vector<int> > vec2)
{
	vector<int> vtemp;
	for(int i=0;i<vec1.size();i++)
	{
		for(int j=0;j<vec1[i].size();j++)
		{
			if(vec1[i][j]!=vec2[i][j]) {vtemp.push_back(i);vtemp.push_back(j);}
		}
	}
	return vtemp;
}

//电脑下棋
void CTicktacktoeView::ComputerDown()
{
	CDC *pDC=GetDC();
	CDC DC;
	if(DC.CreateCompatibleDC(pDC)==FALSE)
		MessageBox("fail to create DC!");

	vector< vector< vector<int> > > vtemp;
	vtemp=NextQP(chessman,1);//返回电脑所有可能的走棋后的棋盘状态
	int itemp;
	vector<int> vposition;
	for(int i=0;i<vtemp.size();i++)
	{
		if(i==0)
		{
			itemp=Max(vtemp[0],myDepth-1);
			vposition=FindPosition(vtemp[0],chessman);
		}
		else if(itemp<Max(vtemp[i],myDepth-1))
		{
			itemp=Max(vtemp[i],myDepth-1);//itemp表示电脑所有可能的走棋后的棋盘状态评价函数的最大值
			vposition=FindPosition(vtemp[i],chessman);//vposition存储电脑应该走棋的x,y坐标
		}
	}
	step++;
	vtemp.clear();
	DC.SelectObject(bmpMax);
	pDC->BitBlt(55+100*vposition[0],30+100*vposition[1],100,100,&DC,0,0,SRCCOPY);//画棋子
	chessman[vposition[0]][vposition[1]]=1;//改变棋盘状态chessman
	manTurn=1;//该人走棋了

	vector<int> vec_manual;//临时存储人走棋的信息
	vec_manual.push_back(1);vec_manual.push_back(vposition[0]);vec_manual.push_back(vposition[1]);
	manual.push_back(vec_manual);//将走棋的步法存入棋谱manual中
	vec_manual.clear();
	
	switch(Result())//Result() 用于判断是否应该结束
	{
	case 1: AfxMessageBox("Computer win!");//棋盘状态为电脑赢，显示消息框
			break;
	case 2: AfxMessageBox("Draw!");//棋盘状态为平局，显示消息框
			break;
	}
}