fivedlg.cpp

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

// fiveDlg.cpp : implementation file
//

#include "stdafx.h"
#include "five.h"
#include "fiveDlg.h"
#include <math.h>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif


/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
	
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CFiveDlg dialog

CFiveDlg::CFiveDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CFiveDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CFiveDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	
	disScope = false;

	pWeight[0] = 0;
	pWeight[1] = 5;
	pWeight[2] = 50;
	pWeight[3] = 500;
	pWeight[4] = 3000;
	pWeight[5] = 0;
	pWeight[6] = 0;
	pWeight[7] = 0;

	cWeight[0] = 0;
	cWeight[1] = 5;
	cWeight[2] = 50;
	cWeight[3] = 500;
	cWeight[4] = 10000;	//如果往下扩展了4步后,电脑有活四或冲四,则电脑必胜,因为下一步是电脑落子
	cWeight[5] = 0;
	cWeight[6] = 0;
	cWeight[7] = 0;
	


}

void CFiveDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CFiveDlg)
	DDX_Control(pDX, IDC_PROGRESS1, m_progress);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CFiveDlg, CDialog)
	//{{AFX_MSG_MAP(CFiveDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_WM_TIMER()
	ON_WM_LBUTTONDOWN()
	ON_WM_KEYDOWN()
	ON_WM_CLOSE()
	ON_MESSAGE(WM_HOTKEY , OnHotKey)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CFiveDlg message handlers

BOOL CFiveDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	RECT rect;
	CClientDC dc(this);
	int width = dc.GetDeviceCaps(HORZRES);
	int height = dc.GetDeviceCaps(VERTRES);
	int aa = WIN;
	GetWindowRect( &rect );
	width = ( width - (WIDTH+10))/2 ;
	height = (height - (HEIGHT+100))/2 ;
	MoveWindow( width , height , WIDTH+10 , HEIGHT+100 ,true);
	m_progress.MoveWindow(5 , 40*N+50 , WIDTH-10 , 10 ,true);

	mdc = new CDC;
	mdc1 = new CDC;
	mdc->CreateCompatibleDC(&dc);
	mdc1->CreateCompatibleDC(&dc);
	purple = new CBitmap;
	green = new CBitmap;
	bgbmp = new CBitmap;
	temp = new CBitmap;
	temp->CreateCompatibleBitmap(&dc,WIDTH,HEIGHT+60);

 	purple->LoadBitmap(IDB_PURPLE);
	green->LoadBitmap(IDB_GREEN);
	bgbmp->LoadBitmap(IDB_BACK);

	mdc->SelectObject(temp);
	SetTimer(1,500,NULL);

	init();
	RegisterHotKey(m_hWnd , 0xb4e1 , 0 , VK_F1);
	RegisterHotKey(m_hWnd , 0xb4e2 , 0 , VK_F2);
	RegisterHotKey(m_hWnd , 0xb4e3 , 0 , VK_F3);
	RegisterHotKey(m_hWnd , 0xb4e4 , 0 , VK_F4);
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CFiveDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CFiveDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		draw();
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CFiveDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CFiveDlg::init()
{
	
	int i , j;
	for(i=0;i<N;i++)         
		for(j=0;j<N;j++)
			board[i][j] = 2;
	
	memset(&win , 0 , sizeof(win));
	memset(&ptable , 0 , sizeof(ptable));
	memset(&ctable , 0 , sizeof(ctable));

	
	count = 0;
	//以下设置获胜组合表,i表示行(即y坐标),j表示列(即x坐标)
	for(i=0;i<N;i++)				//设置水平方向的获胜表
		for(j=0;j<N-4;j++)
		{
			for(k=0;k<5;k++)
			{
				ptable[j+k][i][count] = true;
				ctable[j+k][i][count] = true;
			}
			count++;
		}	
	for(i=0;i<N;i++)				//设置垂直方向的获胜表
		for(j=0;j<N-4;j++)
		{
			for(k=0;k<5;k++)
			{
				ptable[i][j+k][count] = true;
				ctable[i][j+k][count] = true;
			}
			count++;
		}
	for(i=0;i<N-4;i++)				//正对角线    
		for(j=0;j<N-4;j++)
		{
			for(k=0;k<5;k++)
			{
				ptable[j+k][i+k][count] = true;
				ctable[j+k][i+k][count] = true;
			}
			count++;
		}
	for(i=0;i<N-4;i++)          //反对角线
		for(j=N-1;j>=4;j--)
		{
			for(k=0;k<5;k++)
			{
				if(j-k<0)
					AfxMessageBox("");
			
				ptable[j-k][i+k][count] = true;
				ctable[j-k][i+k][count] = true;
			}
			count++;
		}

	for(i = 0; i < N; i++)
	{
		xlimit[i].left = N+1;
		xlimit[i].right  = -1;
		ylimit[i].top = N+1;
		ylimit[i].bottom = -1;
	}
/*	CString str;
	str.Format("count = %d" , count);
	MessageBox(str);
*/	
	if(rand()%2==0)
	{
		computer = true;
		player = false;
	}
	else 
	{
		player = true;
		computer = false;
	}
	left = right = top = bottom = CENTER;
	ccount = 0;
	pcount = 0;
	start = true;
	over = false;
	pwin = false;
	cwin = false;
	tie = false;
	calnum = 0;
		
	path = "";
	canEnter = 4;
	setSearchOrd();	//设置搜索路径
	searchSum = CHESSSUM;

}

void CFiveDlg::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
//	m_progress.SetPos(m_progress.GetPos()+10);

	CClientDC dc(this);

//	dc.SetBkMode(TRANSPARENT );
	if(!over)		//是否已经结束，如果是，判断结果
	{
		if(computer && start)
		{
			putCpuChess(CENTER , CENTER);
			start = false;
			computer = false;
			player = true;
			ccount = 1;
			CString str;
			str.Format("C:(%2d,%2d)   " , CENTER , CENTER);
			path += str;
			canEnter--;
		}
		for(int i=0;i<=1;i++)
			for(int j=0;j<WIN;j++)
			{
				if(win[i][j] == 5)
					if(i==0)      
					{
						
						pwin = true;
						over = true;
						break;
					}
					else           
					{
						cwin = true;
						over = true;
						break;
					}
				if(over)
				{			
					break;
				}
			}
	}
	
	draw();
	CDialog::OnTimer(nIDEvent);
}
//搜索时使用的电脑落子函数
bool CFiveDlg::layCpuChess(int x , int y)
{
	board[x][y] = 1;
	for(int i=0;i<WIN;i++)
	{
		if(ctable[x][y][i] && win[1][i] != 7)
		{
			if(++win[1][i] == 5)
				return true;
		}
		if(ptable[x][y][i])
		{
			win[0][i]=7;
		}
	}
	return false;
}
//搜索时使用的玩家落子函数
bool CFiveDlg::layPlayerChess(int x , int y)
{
	board[x][y] = 0;
	for(int i=0;i<WIN;i++)
	{
		if(ptable[x][y][i] && win[0][i] != 7)
		{
			if(++win[0][i] == 5)
				return true;		
		}
		if(ctable[x][y][i])
		{
			win[1][i]=7;
		}
	}
	return false;
}
//

//如果玩家有了活四或冲四,找到这种获胜组合中的最后一个落子点
void CFiveDlg::findLastOne(int &x , int &y , int winIndex) 
{
	for(x=0; x<N; x++)
	{
		for(y=0; y<N; y++)
		{
			if(ptable[x][y][winIndex] && board[x][y] == 2)
			{
				return;
			}
		}
	}
}

//电脑的实际落子函数
bool CFiveDlg::putCpuChess(int x , int y)
{
	int i;
	board[x][y] = 1;
	//设置棋盘上棋子的边界
	if( x < left )
		left = x;
	if( x > right)
		right = x;
	if( y < top)
		top = y;
	if( y > bottom)
		bottom = y;

	//把搜索序列中相应的项去掉
	for(i=0;i<searchSum;i++)
	{
		if(searchOrd[i].x == x && searchOrd[i].y == y)
		{
			break;
		}
	}
	//前移
	for(; i<searchSum-1; i++)
	{
		searchOrd[i] = searchOrd[i+1];
	}
	searchSum--;


	for(i=0;i<WIN;i++)
	{
		if(ctable[x][y][i] && win[1][i] != 7)
		{
			if(++win[1][i] == 5)
				return true;
		}
		if(ptable[x][y][i])
		{
			win[0][i]=7;
		}
	}

	
	updateScope(x , y);

	return false;
}
//玩家实际落子函数,返回-1表示玩家获胜,>=0的整数表示相应获胜组合已经有4个子,
//-2表示需要计算,-3表示玩家落子后,电脑有活四或冲四
int CFiveDlg::putPlayerChess(int x , int y)
{
	int i;
	int ret = -2;	//-2表示需要用博弈算法考虑怎样落子
	if( x < left )
		left = x;
	if( x > right)
		right = x;
	if( y < top)
		top = y;
	if( y > bottom)
		bottom = y;
	board[x][y] = 0;

	//把搜索序列中相应的项去掉
	for(i=0;i<searchSum;i++)
	{
		if(searchOrd[i].x == x && searchOrd[i].y == y)
		{
			break;
		}
	}
	//前移
	for(; i<searchSum-1; i++)
	{
		searchOrd[i] = searchOrd[i+1];
	}
	searchSum--;
	//
	for(i=0;i<WIN;i++)
	{
		if(ptable[x][y][i] && win[0][i] != 7)
		{
			if(++win[0][i] == 5)
				return -1;		//返回-1表示player赢了
			if(win[0][i] == 4)
			{
				ret = i;		//如果用户已有4,则返回这个获胜组合的号码
			}	
		}
		
		if(ctable[x][y][i])
		{
			win[1][i]=7;
		}
		if(win[1][i] == 4)		//电脑有活四或冲四
		{
			return -3;
		}
		
	}
	updateScope(x , y);
	return ret;	
}
//棋局的估值函数
int CFiveDlg::getValue()
{
	int cpu = 0 , user = 0;	
	char *pwin , *cwin;
	bool three , liveThree;
	pwin = &win[0][0];
	cwin = &win[1][0];
	int i , j;
	calnum++;	//计算的棋局数加1

/*	for(k = 0; k <WIN; k++)
	{
			
		cpu += cWeight[ *cwin++ ];
		user+= pWeight[ *pwin++ ];
//		cpu += cWeight[ win[1][k] ];
//		user+= pWeight[ win[0][k] ];
	}
*/
	three = liveThree = false;

	for(i = 0; i<N; i++)	//搜索行
	{
		for(j = 1; j <N; j++)
		{	
			if(*cwin == 3)
			{
				three = true;
				j++;
				cwin++;
				if(*cwin == 3)
				{
					liveThree = true;
				}
				cwin++;
				for(k = 1 ; k<5 && j<N; k++)
				{
							
				}
			}
		}	
	}

	return cpu - user;
}

//取子节点的最小值
int CFiveDlg::getMin(int depth ,  int parentMax)
{

	char backup_win[2][WIN];
	char backup_board[N][N];
	XLIMIT backup_xlimit[N];
	YLIMIT backup_ylimit[N];

	int oldleft = left, oldright  = right, oldtop  = top, oldbottom = bottom;
	//备份数据	
	memcpy(backup_xlimit , xlimit , sizeof(xlimit));
	memcpy(backup_ylimit , ylimit , sizeof(ylimit));
	memcpy(backup_win , win , sizeof(win));
	memcpy(backup_board , board , sizeof(board));
	
	int pmax  = -10000, cmax = -10000;
	bool first = true;
	int x , y ,z;
	int i;
	int min = INT_MAX  , submax ;
	CPoint *ind = &searchOrd[0];	//查找路径索引
	if(depth == 2)				//第2层
	{
	
		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;