tic_mfcdlg.cpp

由MFC实现的一字棋

	
    for (int i=0; i<9; i++) 
	{
        if (Chess[i] == PLAYER)
            DrawX (pDC, i);
        else if (Chess[i] == COMPUTER)
            DrawO (pDC, i);
    }
	
    pDC->SelectObject (pOldPen);
}

//********************************************************************************************************
//完成功能：初始化棋盘
//*********************************************************************************************************
void CTic_MFCDlg::Reset()
{
	for(int i=0; i<9; i++)
	{
		Chess[i] = EMPTY;
	}
	Invalidate ();

}

//********************************************************************************************************
//完成功能：计算机先走
//*********************************************************************************************************
void CTic_MFCDlg::OnStartCom() 
{

	Reset();
	turn = COMPUTER;
	UpdateData(true);
	SearchDepth = m_dept;
	CClientDC dc (this);
	int result;
	AlphaBeta(Chess,SearchDepth,COMPUTER,-100,100,&result);
	Chess[result] = turn;
	PutAChess(&dc,result);
	

}

//********************************************************************************************************
//完成功能：玩家先走
//*********************************************************************************************************
void CTic_MFCDlg::OnStartPly() 
{

	Reset();
	turn = PLAYER;
	UpdateData(true);
	SearchDepth = m_dept;
}


//********************************************************************************************************
//完成功能：根据输入棋盘，判断当前棋盘的结果，COMPUTER胜？PLAYER胜？平局？
//参数：    board:待评估棋盘
//返回：    -1表示：尚未结束
//			0 表示：平局
//			1 表示：PLAYER胜
//			2 表示：COMPUTER胜
//*********************************************************************************************************
int CTic_MFCDlg::isWin(int curPos)
{
	int link;
	int i;
	int j;
	
	
	//判断左上右下斜线是否有三子连线
	link = 0;
	i = curPos/3;
	j = curPos - i*3;
	while (i>=0&&j>=0)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			i--;
			j--;
		}
		else
			break;
	}
	i = curPos/3+1;
	j = curPos - (curPos/3)*3+1;
	while (i<3&&j<3)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			i++;
			j++;
		}
		else
			break;
	}
	if (link >= 3)
		return Chess[curPos];
	
	//判断右上左下斜线是否有三子连线
	link = 0;
	i = curPos/3;
	j = curPos - i*3;
	while (i<3&&j>=0)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			i++;
			j--;
		}
		else
			break;
	}
	i = curPos/3-1;
	j = curPos - (curPos/3)*3+1;
	while (i>=0&&j<3)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			i--;
			j++;
		}
		else
			break;
	}
	if (link >= 3)
		return Chess[curPos];
	
	//判断横向是否有三子连线
	link = 0;
	i = curPos/3;
	j = curPos - i*3;
	while (j>=0)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			j--;
		}
		else
			break;
	}
	i = curPos/3;
	j = curPos - (curPos/3)*3+1;
	while (j<3)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			j++;
		}
		else
			break;
	}
	if (link >= 3)
		return Chess[curPos];
	
	//判断纵向是否有三子连线
	link = 0;
	i = curPos/3;
	j = curPos - i*3;
	while (i>=0)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			i--;
		}
		else
			break;
	}
	i = curPos/3+1;
	j = curPos - (curPos/3)*3;
	while (i<3)
	{
		if( Chess[i*3+j] == Chess[curPos] )
		{
			link++;
			i++;
		}
		else
			break;
	}
	if (link >= 3)
		return Chess[curPos];
	
	//检查是否是平局
	for(i = 0;i<9;i++)
	{
		if(Chess[i]==EMPTY)
			break;
	}
	if(i == 9)
		return 0;


	return -1;
	
}

//********************************************************************************************************
//完成功能：放下一个棋子，将turn值在COMPUTER和PLAYER之间交替
//参数：    Pos:待放棋子的位置
//*********************************************************************************************************
void CTic_MFCDlg::PutAChess(CDC *pDC,int Pos)
{
	//改变turn && 打印棋盘
	if (turn == PLAYER)
	{
		turn = COMPUTER;
		DrawX(pDC,Pos);
	}
	else if (turn == COMPUTER)
	{
		turn = PLAYER;
		DrawO(pDC,Pos);
	}
	int result = isWin(Pos);
	if (result == 0)
	{
		MessageBox (_T ("     平局！       "), _T ("Game Over"),MB_ICONEXCLAMATION | MB_OK);
		turn = -1;
	}
	else if (result == PLAYER)
	{
		MessageBox (_T ("    玩家胜！       "), _T ("Game Over"),MB_ICONEXCLAMATION | MB_OK);
		turn = -1;
	}
	else if (result == COMPUTER)
	{
		MessageBox (_T ("    电脑胜！       "), _T ("Game Over"),MB_ICONEXCLAMATION | MB_OK);
		turn = -1;
	}
}

//********************************************************************************************************
//完成功能：根据输入棋盘，判断当前棋盘的估价值，估价函数为课本P129所讲：
//			若是MAX的必胜局，则e = +INFINITY，这里为+60
//			若是MIN的必胜局，则e = -INFINITY，这里为-20，这样赋值的原因是机器若赢了，则不考虑其它因素。
//			其它情况，棋盘上能使CUMPUTER成三子一线的数目为e1
//					  棋盘上能使PLAYER  成三子一线的数目为e2，
//					  e1-e2作为最终权值
//参数：    board:待评估棋盘
//返回：    评估结果
//*********************************************************************************************************
int CTic_MFCDlg::evaluate(int board[])
{
	int i,a,b,c;
	int result = 0;

	for( i=0; i<8; ++i ) 
	{
		a = winPattern[i][0];
		b = winPattern[i][1];
		c = winPattern[i][2];
		//机器现三子连珠，赋60作无穷大
		if(board[a]==COMPUTER&&board[b]==COMPUTER&&board[c]==COMPUTER)
			result+=60;
		//否则，权值加1
		else if((board[a]==COMPUTER||board[a]==EMPTY)&&(board[b]==COMPUTER||board[b]==EMPTY)&&(board[c]==COMPUTER||board[c]==EMPTY))
			result++;

		//玩家出现三子连珠，赋-20作无穷小
		if(board[a]==PLAYER&&board[b]==PLAYER&&board[c]==PLAYER)
			result-=20;
		//否则，权值减1
		else if((board[a]==PLAYER||board[a]==EMPTY)&&(board[b]==PLAYER||board[b]==EMPTY)&&(board[c]==PLAYER||board[c]==EMPTY))
			result--;
	}
	return result;
}

//********************************************************************************************************
//完成功能：根据输入棋盘，搜索深度，及其他参数，给出一个相应的最优解，存入result中。
//参数：    board :待评估棋盘
//			Depth :搜索深度
//			turn  :当前是机器走(MAX结点)还是玩家走(MIN结点)
//			Alpha :alpha值，第一次调用默认-100
//			Beta  :beta值，第一次调用默认+100
//			result:输出结果
//返回：    若当前点为MAX节点，则返回alpha值；
//			若当前点为MIN节点，则返回beta值
//*********************************************************************************************************
int CTic_MFCDlg::AlphaBeta(int Board[], int Depth, int turn, int Alpha, int Beta, int *result)
{
	int score;
	if (Depth == 0)
		return evaluate(Board); // 叶子节点返回估值
	if (turn == PLAYER) // 此句用于判断当前节点是何种节点
	{ // turn=PLAYER表示极小值的节点
		for (int i=0;i<9;i++) // 对每一可能的走法m
		{
			// 生成新节点
			if(Board[i] == EMPTY)
			{
				Board[i] = turn; 
				score =AlphaBeta(Board, Depth-1, COMPUTER, Alpha, Beta, result); // 递归搜索子节点
				Board[i] = EMPTY; // 撤销搜索过的节点
				if (score < Beta)
				{
					Beta = score ; // 取极小值
					if (Alpha >= Beta)
						return Alpha ; // 剪枝,抛弃后继节点
				}
			}	
		}
		return Beta ; // 返回最小值
	}
	else
	{ // 取极大值的节点
		for (int i=0;i<9;i++) // 对每一可能的走法m
		{
			// 生成新节点
			if(Board[i] == EMPTY)
			{
				Board[i] = turn;
				score =AlphaBeta(Board, Depth-1, PLAYER, Alpha, Beta, result) ; // 递归搜索子节点
				Board[i] = EMPTY; // 撤销搜索过的节点
				if (score > Alpha)
				{
					if (Depth == SearchDepth)
						*result = i;
					Alpha = score ; // 取极大值
					if (Alpha >= Beta)
						return Beta ; // 剪枝,抛弃后继节点
				}
			}
		}
		return Alpha ; // 返回最大值
	}
}