fivedlg.cpp

人工智能中可以实现智能的五子棋算法

			if(board[x][y] == 2)
			{
				//如果电脑下一招后，用户再下一招就赢了，返回最小值，
				//表示电脑的这招棋对电脑非常不利
				if(layPlayerChess(x , y))
				{
					return INT_MIN;
				}

				//更新搜索范围
				updateScope( x , y);

				if( x < left )
					left = x;
				if( x > right)
					right = x;
				if( y < top)
					top = y;
				if( y > bottom)
					bottom = y;
				if(first)
				{
					first = false;
					min = getMax(depth+1 , min , z , z );
				//	min = getValue();
				}
				else
				{
					submax = getMax(depth+1 , min , z , z );
				//	submax = getValue();		
					if(submax < min)
					{
						min = 	submax;								
					}
				}
				
				if(min <= parentMax)//剪枝
				{
			 //			cutnum++;
						return min;
				}
				//恢复
				left = oldleft;
				right = oldright;
				top = oldtop;
				bottom = oldbottom;

				memcpy(win , backup_win , sizeof(win));
				memcpy(board , backup_board , sizeof(board));
				memcpy(xlimit , backup_xlimit , sizeof(xlimit));
				memcpy(ylimit , backup_ylimit , sizeof(ylimit));
			}
		}	
		if(min == INT_MIN)
			AfxMessageBox("min == INT_MIN");
		return min;

	}
	else			//第4层
	{
		for(i  = 0; i < searchSum ; i++)
		{
			x = ind->x;
			y = ind->y;
			ind++;
//			if(x < left-2 || x > right+2 || y < top-2 || y > bottom+2)
//				continue;
			if(		x < xlimit[y].left || x > xlimit[y].right
				||	y < ylimit[x].top  || y > ylimit[x].bottom )
				continue;
			if(board[x][y] == 2)
			{
			//	layPlayerChess(x , y);
				if(layPlayerChess(x , y))
				{
					return INT_MIN;
				}
					
				if(first)
				{
					first = false;
					min = getValue();//调用评价函数
				}
				else
				{
					submax = getValue();//调用评价函数	
					if(submax < min)
					{
						min = 	submax;					
					}
				}
				if(min <= parentMax)//剪枝
				{
			 //		cutnum++;
					return min;
				}
	//				memcpy(ptable , backup_p , sizeof(ptable));
	//				memcpy(ctable , backup_c , sizeof(ctable));
				memcpy(win , backup_win , sizeof(win));
				memcpy(board , backup_board , sizeof(board));
			}
			
			
		}
	}
	return min;
}

//取子节点的最大值，实验落子顺序是从中间往四周扩散
int CFiveDlg::getMax(int depth  , int parentMin , int &nextx , int &nexty)
{
 
	char backup_win[2][WIN];
	char backup_board[N][N];
	int oldleft = left, oldright  = right, oldtop  = top, oldbottom = bottom;
	XLIMIT backup_xlimit[N];
	YLIMIT backup_ylimit[N];

	//备份数据
	memcpy(backup_win , win , sizeof(win));
	memcpy(backup_board , board , sizeof(board));
	memcpy(backup_xlimit , xlimit , sizeof(xlimit));
	memcpy(backup_ylimit , ylimit , sizeof(ylimit));
	int x , y;
	int i;
	bool first = true;
	int max = INT_MIN+2 , submin ;
	CPoint *ind = &searchOrd[0];		//查找路径索引
	if(depth == 1)		//深度1
	{
		m_progress.SetRange(0 , searchSum);
		m_progress.SetPos(0);
		for(i  = 0; i < searchSum ; i++)
		{
			m_progress.SetPos(m_progress.GetPos()+1);
			x = ind->x;
			y = ind->y;
			ind++;
//			if(x < left-2 || x > right+2 || y < top-2 || y > bottom+2)
//				continue;
			if(		x < xlimit[y].left || x > xlimit[y].right
				||	y < ylimit[x].top  || y > ylimit[x].bottom )
				continue;
			if(board[x][y] == 2)
			{
		/*		if(x<0 || y<0)
				{
					AfxMessageBox("");
				}
		*/		if(layCpuChess(x , y))	//如果电脑放下一个旗子就赢了，则立即返回
				{
					memcpy(win , backup_win , sizeof(win));
					memcpy(board , backup_board , sizeof(board));
			//		AfxMessageBox("COMPUTER win");
					nextx = x;
					nexty = y;
					return INT_MAX;
				}
				//更新范围
				updateScope( x , y);
				if( x < left )
					left = x;
				if( x > right)
					right = x;
				if( y < top)
					top = y;
				if( y > bottom)
					bottom = y;
				if(first)
				{
					first = false;
					max = getMin(depth+1 , max);
					nextx = x;
					nexty = y;
				}
				else
				{
					submin = getMin(depth+1 , max);				
					if(submin > max)
					{
						max = 	submin;	
						nextx = x;
						nexty = y;
					}
				}
				//恢复
				left = oldleft;
				right = oldright;
				top = oldtop;
				bottom = oldbottom;

				
				memcpy(win , backup_win , sizeof(win));
				memcpy(board , backup_board , sizeof(board));
				memcpy(xlimit , backup_xlimit , sizeof(xlimit));
				memcpy(ylimit , backup_ylimit , sizeof(ylimit));
			}
				
		}
		//如果玩家已经有了三三,则此时得到的最大值一定是INT_MIN,所以这时候电脑认输
		if(max == INT_MIN)
		{
			over = true;
			pwin = true;
		//	MessageBox("You win");
		}
	}
	else			//深度3
	{
		for(i  = 0; i < searchSum ; i++)
		{
			x = ind->x;
			y = ind->y;
			ind++;
//			if(x < left-2 || x > right+2 || y < top-2 || y > bottom+2)
//				continue;
			if(		x < xlimit[y].left || x > xlimit[y].right
				||	y < ylimit[x].top  || y > ylimit[x].bottom )
				continue;
			if(board[x][y] == 2)
			{
	/*			if(x<0 || y<0)
				{
					AfxMessageBox("");
				}
	*/			if(layCpuChess(x , y))	//如果电脑放下一个旗子就赢了，则立即返回
				{
				//	memcpy(win , backup_win , sizeof(win));
				//	memcpy(board , backup_board , sizeof(board));		
					return INT_MAX;
				}


				//设置范围
				updateScope( x , y);
				if( x < left )
					left = x;
				if( x > right)
					right = x;
				if( y < top)
					top = y;
				if( y > bottom)
					bottom = y;
				if(first)
				{
					first = false;
					max = getMin(depth+1 , max);
				}
				else
				{
					submin = getMin(depth+1 , max);
			//		submin = getValue();
					if(submin > max)
					{
						max = 	submin;												
					}

				}
				
				if(max >= parentMin)//剪枝
				{
				//	cutnum++;
					return max;
				}
					//恢复
				left = oldleft;
				right = oldright;
				top = oldtop;
				bottom = oldbottom;

				memcpy(win , backup_win , sizeof(win));
				memcpy(board , backup_board , sizeof(board));	
				memcpy(xlimit , backup_xlimit , sizeof(xlimit));
				memcpy(ylimit , backup_ylimit , sizeof(ylimit));
			} 			
		}
		
//		if(max == INT_MIN)
//			AfxMessageBox("max == INT_MIN");
	}
	return max;
}

void CFiveDlg::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	int x , y;
	int winIndex;
	if(!over)
		if(player)
		{
			if(point.x<WIDTH && point.y<HEIGHT)	//首先获得落子坐标
			{
				
				m = (int)floor(point.x/40);
				n = (int)floor(point.y/40);
				if(board[m][n] != 2)  
				{
				//	CDialog::OnLButtonDown(nFlags, point);
					return;
				}
									
				pcount++;
				
				CString str; 
				str.Format("P:(%2d,%2d)   " , m , n);
				path += str;
				if(--canEnter == 0)
				{
					canEnter = 4;
					path += "\r\n";
				}
				
				winIndex = putPlayerChess(m , n);
				
				if(winIndex == -1)	//返回-1表示用户赢了
				{
					pwin = true;
					over = true;
			//		CDialog::OnLButtonDown(nFlags, point);
					return;
				}			
				
				draw();	//先画上用户棋子
				
				if(ccount + pcount == CHESSSUM)	//如果下满则平
				{
					tie = true;
					over = true;
		//			CDialog::OnLButtonDown(nFlags, point);
					return;
				}
				player = false;      
				computer = true;

		/////////////////////////////////////////显示需要等待
				CClientDC dc(this);
				
				mdc->BitBlt(0 , 0 , WIDTH , 60 , NULL , 0 , 0 , WHITENESS   );
				mdc->TextOut((WIDTH - 170),0,		"F2: restart ");
				mdc->TextOut((WIDTH - 170),15,"F3: display steps");
				mdc->TextOut((WIDTH - 170),30,"F4: display search scope");
				mdc->TextOut(10,0,"Please wait..");
				dc.BitBlt(0 , HEIGHT , WIDTH , 50 , mdc , 0 , 0 , SRCCOPY);
		/////////////////////////////////////////
				calnum = 0;
				cutnum = 0;
				if(start)		//如果是刚开始
				{
					if(board[CENTER][CENTER] == 2)	//如果玩家没有在中心落子,则电脑落在此处
					{
						x = y = CENTER;
					}
					else
					{
						getMax(1  , 0 , x , y );							
					}
					start = false;		//开始标记设为false
				}
				else if(winIndex == -3)	//玩家落子后,电脑仍有四,搜索找到并获胜!
				{
					findCPUlast(x , y);
				}
				else if(winIndex == -2  )	
				//如果用户没有活四或冲四 , 或者电脑也没有活四或冲四,则用博弈算法找最佳落子点
				{	 
					getMax(1  , 0 , x , y );
					//这是可能发现玩家已经有三三,此时自动认输
					if(over)
						return;
				}
				else 	//此时winIndex>=0,表示玩家已有活四或冲四,winIndex记录了玩家所在的胜利编号
				{
					findLastOne(x , y , winIndex);
				}
				putCpuChess(x , y);	//电脑落子
				ccount++;
					
				//记录路径
				str.Format("C:(%2d,%2d)   " , x , y);
				path += str;
				if(--canEnter == 0)
				{
					canEnter = 4;
					path += "\r\n";
				}
				if(ccount + pcount == CHESSSUM)	//如果下满则平
				{
					tie = true;
					over = true;
			//		CDialog::OnLButtonDown(nFlags, point);
					return;
				}

				player = true;      //转换
				computer = false;
		
			}
		}
 
//	CDialog::OnLButtonDown(nFlags, point);
}

void CFiveDlg::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags) 
{
	// TODO: Add your message handler code here and/or call default
	if(nChar == VK_ESCAPE)
		PostMessage(WM_CLOSE);
	CDialog::OnKeyDown(nChar, nRepCnt, nFlags);
}

void CFiveDlg::OnClose() 
{
	// TODO: Add your message handler code here and/or call default
	delete purple;
	delete green;
	delete bgbmp;
	delete temp;
	delete mdc;
	delete mdc1;
	::UnregisterHotKey(m_hWnd , 0Xb4e1);
	::UnregisterHotKey(m_hWnd , 0Xb4e2);
	::UnregisterHotKey(m_hWnd , 0Xb4e3);
	::UnregisterHotKey(m_hWnd , 0Xb4e4);
	CDialog::OnClose();
}

 

void CFiveDlg::draw()
{	
	CClientDC dc(this);
	mdc1->SelectObject(bgbmp);
	mdc->BitBlt(0,0,WIDTH,HEIGHT,mdc1,0,0,SRCCOPY);
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		{
			if(board[i][j] == 0)  
			{
				mdc1->SelectObject(green);
				mdc->BitBlt(i*40+2,j*40+2,36,36,mdc1,0,0,SRCCOPY);
			}
			if(board[i][j] == 1)  
			{
				mdc1->SelectObject(purple);
				mdc->BitBlt(i*40+2,j*40+2,36,36,mdc1,0,0,SRCCOPY);
			}
		}
	//下面写字
		
	mdc->BitBlt(0 , HEIGHT , WIDTH , 60 , NULL , 0 , 0 , WHITENESS   );
	mdc->TextOut((WIDTH - 170),HEIGHT,	"F2: restart ");
	mdc->TextOut((WIDTH - 170),HEIGHT+15,"F3: display steps");
	mdc->TextOut((WIDTH - 170),HEIGHT+30,"F4: display search scope");
	if(pwin)
		mdc->TextOut(10  ,HEIGHT,"Win! Press F2 to restart!");
	else if(cwin)
		mdc->TextOut(10  ,HEIGHT,"Lose! Press F2 to restart!");
	else if(tie)
		mdc->TextOut(10  ,HEIGHT,"Draw! Press F2 to restart!");
	else
		mdc->TextOut(10  ,HEIGHT,"It's your turn!");
	//---------------------------------------------------------------------------------//
	//以下为调试用
	//画出搜索区域
	if(disScope)	//如果需要显示搜索范围，则便利区域界限数组，并画出来
	{
		for(i = 0; i< N; i++)
		{
			if(xlimit[i].left<N )
			{
				mdc->Rectangle(40*xlimit[i].left+10 , 40*i+10  , 40*xlimit[i].left+30 , 40*i+30);
			}
		}
		for(i = 0; i< N; i++)
		{
			if(ylimit[i].bottom>-1 )
				mdc->Rectangle(40*i+10  , 40 *ylimit[i].bottom +10 , 40*i+30  , 40 *ylimit[i].bottom +30);
		}
		for(i = N-1; i>-1; i--)
		{
			if(xlimit[i].right>-1 )
				mdc->Rectangle(40 *xlimit[i].right+10 , 40*i+10 , 40 *xlimit[i].right+30 , 40*i+30);
		}
		for(i = N-1; i>-1; i--)
		{
			if(ylimit[i].top<N )
				mdc->Rectangle(40*i+10 , 40 *ylimit[i].top+10 , 40*i+30 , 40 *ylimit[i].top+30 );
		}
	}
	///////

	CString str;
	str.Format("eveluated %d nodes!"  , calnum );
	mdc->TextOut(10,HEIGHT+30,str);
//	mdc->TextOut(10 , 10 , str);
	//---------------------------------------------------------------------------------//
	dc.BitBlt(0,0,WIDTH,HEIGHT+45 , mdc,0,0,SRCCOPY);
}
//如果电脑有了活四或冲四,找到这种获胜组合中的最后一个落子点
void CFiveDlg::findCPUlast(int &x, int &y)
{
	for(int i = 0; i < WIN; i++)
	{
		if(win[1][i] != 4)
			continue;
		for(x=0; x<N; x++)
		{
			for(y=0; y<N; y++)
			{
				if(ctable[x][y][i] && board[x][y] == 2)
				{
					return;
				}
			}
		}
	}
}
//设置搜索路径
void CFiveDlg::setSearchOrd()
{
	int x , y , i ,j , k = 1;
	searchOrd[0].x = searchOrd[0].y = CENTER;
	//搜索的顺序是从中心顺时针向四周扩展
	for(j = 1; j < CENTER+1; j++)
	{
		x = CENTER-j;
		y = CENTER-j;
		for(i = 0; i < j*2; i++)
		{
			
			searchOrd[k].x = x;
			searchOrd[k].y = y;
			x++;
			k++;
		}
		for(i = 0; i < j*2; i++)
		{		
			searchOrd[k].x = x;
			searchOrd[k].y = y;
			y++;
			k++;
		}
		for(i = 0; i < j*2; i++)
		{
			
			searchOrd[k].x = x;
			searchOrd[k].y = y;
			x--;
			k++;
		}
		for(i = 0; i < j*2; i++)
		{
			
			searchOrd[k].x = x;
			searchOrd[k].y = y;
			y--;
			k++;
		}
		
	}
	return;

}

	//设置棋子范围
void CFiveDlg::updateScope(int x , int y)
{
	int i;
	for(i = -2; i < 3; i++)
	{
		if(y+i > -1 && y+i < N)
		{
			if(x<3)						//左边界
				 xlimit[y+i].left = 0;
			else if(x-2 < xlimit[y+i].left)
				xlimit[y+i].left  = x-2;
	

			if(x>N-3)					//右边界
				xlimit[y+i].right = N-1;
			else if(x+2 > xlimit[y+i].right)
				xlimit[y+i].right = x+2;
		}

		if(x+i > -1 && x+i < N)
		{
			if(y<3)						//上边界
				ylimit[x+i].top = 0;
			else if(y-2 < ylimit[x+i].top)
				ylimit[x+i].top = y-2;

			if(y>N-3)					//下边界
				ylimit[x+i].bottom = N-1;
			else if(y+2 > ylimit[x+i].bottom)
				ylimit[x+i].bottom = y+2;
		}
	}
}

LRESULT CFiveDlg::OnHotKey(WPARAM wParam , LPARAM lParam)
{
	if(wParam == 0xb4e1)		//按f2重新开始
	{		
		MessageBox("按F2重新开始\r\n按F3显示棋谱\r\n按f4切换显示搜索范围");
	}
	else if(wParam == 0xb4e2)		//按f2重新开始
	{		
		init();	
	}
	else if(wParam == 0xb4e3)	//按f3显示棋谱
	{
		MessageBox(path);

	}
	else if(wParam == 0xb4e4)	//按f4切换是否显示搜索范围
	{	
		disScope = !disScope;
	}
	return 0;
}