VC++源碼分析 - 中國象棋源碼分析

VC++源碼分析 - 中國象棋源碼分析

下載自

http://www.newxing.com/Code/VC/game/1750.html

運行界面如下；

看下類圖；

資源；

主對話框；

源碼說明：

本人機對弈程序采用了多種搜索算法.以下是本程序主要的類說明:
1.CEveluation類:估值類,對給定的棋盤進行估值.


2.CMoveGenerator類:走法產生器,對給定的棋盤局面搜索出所有可能的走法.


3.CSearchEngine類:搜索引擎基類.
4.CNegaMaxEngine類:負極大值法搜索引擎.
5.CAlphaBetaEngine類:采用了Alpha-Beta剪枝技術的搜索引擎.
6.CFAlphaBetaEngine類:fail-softalpha-beta搜索引擎.
7.CHistoryHeuristic類:歷史啟發類.
8.CAlphabeta_HHEngine類:帶歷史啟發的Alpha-Beta搜索引擎.
9.CAspirationSearch類:渴望搜索引擎.
10.CIDAlphabetaEngine類:迭代深化搜索引擎.
11.CMTD_fEngine類:MTD(f)搜索引擎.
12.CTranspositionTable類:置換表.
13.CAlphaBeta_TTEngine類:加置換表的Alpha-Beta搜索引擎.
14.CPVS_Engine類:極小窗口搜索引擎.
15.CNegaScout_TT_HH類:使用了置換表和歷史啟發的NegaScout搜索引擎.
本程序還具有悔棋,還原功能,還可以記錄走法.

那麼該源碼可以參照寫各類搜索引擎；

下面看下其部分代碼；主對話框類；

可以看到最多的函數類別是各種菜單的消息映射函數；如下；

BEGIN_MESSAGE_MAP(CChessDlg, CDialog)
	//{{AFX_MSG_MAP(CChessDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_WM_LBUTTONDOWN()
	ON_WM_LBUTTONUP()
	ON_WM_MOUSEMOVE()
	ON_COMMAND(IDM_SETCHESSBOARD, OnSetchessboard)
	ON_COMMAND(IDM_SET, OnSet)
	ON_COMMAND(IDM_ABOUT, OnAbout)
	ON_COMMAND(IDM_OPENFILE, OnOpenfile)
	ON_COMMAND(IDM_SAVEFILE, OnSavefile)
	ON_COMMAND(IDM_SCBOVER, OnScbover)
	ON_COMMAND(IDM_RPAWN, OnRpawn)
	ON_COMMAND(IDM_RCANON, OnRcanon)
	ON_COMMAND(IDM_RCAR, OnRcar)
	ON_COMMAND(IDM_RHORSE, OnRhorse)
	ON_COMMAND(IDM_RELEPHANT, OnRelephant)
	ON_COMMAND(IDM_RBISHOP, OnRbishop)
	ON_COMMAND(IDM_RKING, OnRking)
	ON_COMMAND(IDM_BPAWN, OnBpawn)
	ON_COMMAND(IDM_BCANON, OnBcanon)
	ON_COMMAND(IDM_BCAR, OnBcar)
	ON_COMMAND(IDM_BHORSE, OnBhorse)
	ON_COMMAND(IDM_BELEPHANT, OnBelephant)
	ON_COMMAND(IDM_BBISHOP, OnBbishop)
	ON_COMMAND(IDM_BKING, OnBking)
	ON_COMMAND(IDM_DELETE, OnDelete)
	ON_WM_RBUTTONDOWN()
	ON_WM_LBUTTONDBLCLK()
	ON_WM_CLOSE()
	ON_COMMAND(IDM_CLEARCB, OnClearcb)
	ON_COMMAND(IDM_NEWGAME, OnNewgame)
	ON_BN_CLICKED(IDC_BTNCOMPUTER, OnBtncomputer)
	ON_BN_CLICKED(IDC_BTNUNDO, OnBtnundo)
	ON_BN_CLICKED(IDC_BTNREDO, OnBtnredo)
	ON_LBN_DBLCLK(IDC_LISTCHESSRECORD, OnDblclkListchessrecord)
	ON_BN_CLICKED(IDC_BTN_STOP, OnBtnStop)
	ON_LBN_SELCHANGE(IDC_LISTCHESSRECORD, OnSelchangeListchessrecord)
	ON_COMMAND(IDM_PREVIEW, OnPreview)
	ON_COMMAND(IDM_PREVIEWOVER, OnPreviewover)
	ON_COMMAND(IDM_HELP, OnHelp)
	ON_COMMAND(IDM_INVERSECB, OnInversecb)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

在對話框初始化函數中載入棋盤；

	BITMAP BitMap;
	m_BoardBmp.LoadBitmap(IDB_CHESSBOARD);
	m_BoardBmp.GetBitmap(&BitMap); //取BitMap 對象
	m_nBoardWidth=BitMap.bmWidth;  //棋盤寬度
	m_nBoardHeight=BitMap.bmHeight;//棋盤高度

如上；棋盤是一個位圖；

在對話框構造函數中創建三個重要的用於思考的對象：<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHByZSBjbGFzcz0="brush:java;"> m_pSE=new CNegaMaxEngine;//創建負極大值搜索引擎 m_pMG=new CMoveGenerator;//創建走法產生器 m_pEvel=new CEveluation; //創建估值核心
鼠標左鍵彈起時將用戶走法壓棧；也就是說用戶走法用棧存儲；

//---------將用戶走法壓棧---------
		m_cmBestMove.From.x=m_ptMoveChess.x;
		m_cmBestMove.From.y=m_ptMoveChess.y;
		m_cmBestMove.To.x=x;
		m_cmBestMove.To.y=y;
		m_cmBestMove.nChessID=m_MoveChess.nChessID;
		m_umUndoMove.cmChessMove=m_cmBestMove;
		m_umUndoMove.nChessID=m_byChessBoard[y][x];
		m_stackUndoMove.push(m_umUndoMove);
		//--------------------------------

......
typedef struct
{
short nChessID; //表明是什麼棋子
CHESSMANPOS From;//起始位置
CHESSMANPOS To; //走到什麼位置
int Score; //走法的分數
}CHESSMOVE;

......

CHESSMOVE m_cmBestMove;

CHESSMOVE是一個結構體；

......

stack m_stackUndoMove;//記錄走法的棧，便於悔棋

......

m_stackUndoMove是一個棧；

走法產生器；

根據不同的子判斷落點是否符合中國象棋規則；例如象，往四個方向走田字：

void CMoveGenerator::Gen_ElephantMove(BYTE position[10][9],int i,int j,int nPly)
{
	int x,y;
	
	//插入右下方的有效走法
	x=j+2;
	y=i+2;
	if(x<9 && y<10 && IsValidMove(position,j,i,x,y,m_nUserChessColor))
		AddMove(j,i,x,y,nPly,position[i][j]);
	
	//插入右上方的有效走法
	x=j+2;
	y=i-2;
	if(x<9 && y>=0 && IsValidMove(position,j,i,x,y,m_nUserChessColor))
		AddMove(j,i,x,y,nPly,position[i][j]);
	
	//插入左下方的有效走法
	x=j-2;
	y=i+2;
	if(x>=0 && y<10 && IsValidMove(position,j,i,x,y,m_nUserChessColor))
		AddMove(j,i,x,y,nPly,position[i][j]);
	
	//插入左上方的有效走法
	x=j-2;
	y=i-2;
	if(x>=0 && y>=0 && IsValidMove(position,j,i,x,y,m_nUserChessColor))
		AddMove(j,i,x,y,nPly,position[i][j]);
}

搜索引擎基類；其他搜索引擎繼承此類；

//Download by http://www.NewXing.com
// SearchEngine.h: interface for the CSearchEngine class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SEARCHENGINE_H__7A7237B9_0908_45D8_B102_94E342B174A5__INCLUDED_)
#define AFX_SEARCHENGINE_H__7A7237B9_0908_45D8_B102_94E342B174A5__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "Eveluation.h"
#include "MoveGenerator.h"
#include "GradientProgressCtrl.h"

//搜索引擎的基類
class CSearchEngine  
{
public:
	CSearchEngine();
	virtual ~CSearchEngine();

public:
	virtual SearchAGoodMove(BYTE position[10][9])=0;        //走下一步
	CHESSMOVE GetBestMove(){return m_cmBestMove;};			//得到最佳走法
	UNDOMOVE GetUndoMove(){return m_umUndoMove;};			//得到悔棋走法
	void SetSearchDepth(int nDepth){m_nSearchDepth=nDepth;};//設定最大搜索深度
	void SetEveluator(CEveluation* pEval){m_pEval=pEval;};  //設定估值引擎
	void SetMoveGenerator(CMoveGenerator* pMG){m_pMG =pMG;};//設定走法產生器
	void SetThinkProgress(CGradientProgressCtrl* pThinkProgress){m_pThinkProgress=pThinkProgress;};
															//設定顯示思考進度的進度條
	void SetUserChessColor(int nUserChessColor){m_nUserChessColor=nUserChessColor;};
															//設定用戶為黑方或紅方

	void UndoChessMove(BYTE position[10][9],CHESSMOVE* move,BYTE nChessID);//悔棋
	void RedoChessMove(BYTE position[10][9],CHESSMOVE* move);              //還原

protected:
	int IsGameOver(BYTE position[10][9],int nDepth);//判斷是否已分勝負
	BYTE MakeMove(CHESSMOVE* move);				    //根據某一走法產生走了之後的棋盤
	void UnMakeMove(CHESSMOVE* move,BYTE nChessID); //恢復為走過之前的棋盤	

public:
	int m_nUserChessColor;

protected:
	CGradientProgressCtrl* m_pThinkProgress;
								    //用以顯示思考進度的進度條指針
	BYTE CurPosition[10][9];		//搜索時用於記錄當前節點棋盤狀態的數組
	CHESSMOVE m_cmBestMove;			//記錄最佳走法
	UNDOMOVE m_umUndoMove;
	CMoveGenerator* m_pMG;			//走法產生器
	CEveluation* m_pEval;			//估值核心
	int m_nSearchDepth;				//最大搜索深度
	int m_nMaxDepth;				//當前搜索的最大搜索深度
};

#endif // !defined(AFX_SEARCHENGINE_H__7A7237B9_0908_45D8_B102_94E342B174A5__INCLUDED_)

CoolButton類；用於繪制主界面左下角的四個按鈕；可以參照寫自己的cool 按鈕類；

//Download by http://www.NewXing.com
// CoolButton.cpp : implementation file
//

#include "stdafx.h"
#include "CoolButton.h"

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

/////////////////////////////////////////////////////////////////////////////
// CCoolButton

CCoolButton::CCoolButton()
{
#ifdef XS_FLAT_BUTTON
	m_MouseOnButton=FALSE;
#endif

	m_hIcon=NULL;
	m_cyIcon=0;
	m_cxIcon=0;
}

CCoolButton::~CCoolButton()
{
}


BEGIN_MESSAGE_MAP(CCoolButton, CButton)
	//{{AFX_MSG_MAP(CCoolButton)
	ON_WM_MOUSEMOVE()
	ON_WM_KILLFOCUS()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CCoolButton message handlers

void CCoolButton::DrawItem(LPDRAWITEMSTRUCT lpDIS) 
{
	// TODO: Add your code to draw the specified item
	CDC * pDC=CDC::FromHandle(lpDIS->hDC);
	
	unsigned int  IsPressed =(lpDIS->itemState&ODS_SELECTED);
	unsigned int  IsFocused =(lpDIS->itemState&ODS_FOCUS);
	unsigned int  IsDisabled =(lpDIS->itemState&ODS_DISABLED);

	CRect itemRect = lpDIS->rcItem;

#ifndef XS_FLAT_BUTTON
	if(IsFocused)
	{
		CBrush br(RGB(0,0,0));
		pDC->FrameRect(&itemRect,&br);
		itemRect.DeflateRect(1,1);
	}
#endif
	//Fill with bkcolor
	CBrush br(GetSysColor(COLOR_BTNFACE));
	pDC->FillRect(&itemRect,&br);

	//Is pressed?
	if(IsPressed)
	{
#ifdef XS_FLAT_BUTTON
		//淺邊界筆
		CPen penBtnHiLight(PS_SOLID,0,GetSysColor(COLOR_BTNHILIGHT));
		//陰影筆
		CPen penBtnShadow(PS_SOLID,0,GetSysColor(COLOR_BTNSHADOW));
		
		//繪邊界陰影
		pDC->SelectObject(penBtnShadow);
		pDC->MoveTo(itemRect.left,itemRect.bottom-1);
		pDC->LineTo(itemRect.left,itemRect.top);
		pDC->LineTo(itemRect.right,itemRect.top);
		//繪淺邊界
		pDC->SelectObject(penBtnHiLight);
		pDC->MoveTo(itemRect.left,itemRect.bottom-1);
		pDC->LineTo(itemRect.right-1,itemRect.bottom-1);
		pDC->LineTo(itemRect.right-1,itemRect.top-1);
#else
		CBrush brBtnShadow(GetSysColor(COLOR_BTNSHADOW));
		pDC->FrameRect(&itemRect,&brBtnShadow);
#endif
	}
	else//沒按下
	{
		CPen penBtnHiLight(PS_SOLID,0,GetSysColor(COLOR_BTNHILIGHT));
		CPen pen3DLight(PS_SOLID,0,GetSysColor(COLOR_3DLIGHT));
		CPen penBtnShadow(PS_SOLID,0,GetSysColor(COLOR_BTNSHADOW));
		CPen pen3DDKShadow(PS_SOLID,0,GetSysColor(COLOR_3DDKSHADOW));

#ifdef XS_FLAT_BUTTON
		if(m_MouseOnButton==TRUE)
		{
			pDC->SelectObject(penBtnHiLight);
			pDC->MoveTo(itemRect.left,itemRect.bottom-1);
			pDC->LineTo(itemRect.left,itemRect.top);
			pDC->LineTo(itemRect.right,itemRect.top);
			//
			pDC->SelectObject(penBtnShadow);
			pDC->MoveTo(itemRect.left,itemRect.bottom-1);
			pDC->LineTo(itemRect.right-1,itemRect.bottom-1);
			pDC->LineTo(itemRect.right-1,itemRect.top-1);
		}
#else
		pDC->SelectObject(penBtnHiLight);
		pDC->MoveTo(itemRect.left,itemRect.bottom-1);
		pDC->LineTo(itemRect.left,itemRect.top);
		pDC->LineTo(itemRect.right,itemRect.top);

		pDC->SelectObject(pen3DLight);
		pDC->MoveTo(itemRect.left+1,itemRect.bottom-1);
		pDC->LineTo(itemRect.left+1,itemRect.top+1);
		pDC->LineTo(itemRect.right,itemRect.top+1);

		pDC->SelectObject(pen3DDKShadow);
		pDC->MoveTo(itemRect.left,itemRect.bottom-1);
		pDC->LineTo(itemRect.right-1,itemRect.bottom-1);
		pDC->LineTo(itemRect.right-1,itemRect.top-1);

		pDC->SelectObject(penBtnShadow);
		pDC->MoveTo(itemRect.left+1,itemRect.bottom-2);
		pDC->LineTo(itemRect.right-2,itemRect.bottom-2);
		pDC->LineTo(itemRect.right-2,itemRect.top);
#endif
	}

#ifndef XS_FLAT_BUTTON
	//
	if(IsFocused)
	{
		CRect focusRect = itemRect;
		focusRect.DeflateRect(3,3);
		pDC->DrawFocusRect(&focusRect);
	}
#endif
	
	//獲取文本
	CString title;
	GetWindowText(title);

	//繪制圖標
	if(m_hIcon!=NULL)
	{
		CRect iconRect = lpDIS->rcItem;
		//根據標題是否存在來設置不同的圖標位置
		if(title.IsEmpty()==TRUE)
		{
			iconRect.left+=((iconRect.Width()-m_cxIcon)/2);
		}
		else
		{
			iconRect.left+=6;
		}
		iconRect.top+=((iconRect.Height()-m_cyIcon)/2);
	
		if(IsPressed)iconRect.OffsetRect(1,1);


		pDC->DrawIcon(iconRect.TopLeft(),m_hIcon);
	}
	//繪標題
	CRect captionRect = lpDIS->rcItem;
	captionRect.left+=m_cxIcon;
	
	if(title.IsEmpty()==FALSE)
	{
		pDC->SetBkMode(TRANSPARENT);
		captionRect.OffsetRect(0,-1);
		
		if(IsPressed)
			captionRect.OffsetRect(1,1);

		if(IsDisabled)
		{
			captionRect.OffsetRect(1,1);
			pDC->SetTextColor(GetSysColor(COLOR_BTNHILIGHT));
			pDC->DrawText(title,-1,captionRect,DT_SINGLELINE|DT_CENTER|DT_VCENTER);
			captionRect.OffsetRect(-1,-1);
			pDC->SetTextColor(GetSysColor(COLOR_BTNSHADOW));
			pDC->DrawText(title,-1,captionRect,DT_SINGLELINE|DT_CENTER|DT_VCENTER);
		}
		else
		{
			pDC->DrawText(title,-1,captionRect,DT_SINGLELINE|DT_CENTER|DT_VCENTER);
		}
	}
}

#ifdef XS_FLAT_BUTTON
void CCoolButton::OnMouseMove(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	
	CWnd* pWnd;
	CWnd* pParent;

	CButton::OnMouseMove(nFlags, point);

	pWnd=GetActiveWindow();
	pParent=GetOwner();
	if((m_MouseOnButton==FALSE)&&(GetCapture()!=this)&&
		((pWnd!=NULL)&&(pWnd->m_hWnd==pParent->m_hWnd)))
	{
		SetCapture();
		SetFocus();
		m_MouseOnButton=TRUE;
		Invalidate();
		UpdateWindow();
	}
	else
	{
		CRect rc;
		GetClientRect(&rc);
		if(!rc.PtInRect(point))
		{
			m_MouseOnButton=FALSE;
			Invalidate();
			UpdateWindow();
			ReleaseCapture();
		}
	}
}
#endif

#ifdef XS_FLAT_BUTTON
void CCoolButton::OnKillFocus(CWnd* pNewWnd) 
{
	CButton::OnKillFocus(pNewWnd);
	
	// TODO: Add your message handler code here
	if(m_MouseOnButton==TRUE)
	{
		m_MouseOnButton=FALSE;
		Invalidate();
		UpdateWindow();
	}
}
#endif

void CCoolButton::SetIcon(HICON hIcon, BYTE cx, BYTE cy)
{
	m_hIcon  = hIcon;
	m_cxIcon = cx;	
	m_cyIcon = cy;
}

BOOL CCoolButton::SubclassDlgItem(UINT nID, CWnd *pParent)
{
	BOOL retValue=CButton::SubclassDlgItem(nID,pParent);

	LONG bs=::GetWindowLong(m_hWnd,GWL_STYLE);
	bs|=BS_OWNERDRAW;
	::SetWindowLong(m_hWnd,GWL_STYLE,bs);

	return retValue;
}

余下的有空再分析吧；

搜索算法是利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。
搜索算法實際上是根據初始條件和擴展規則構造一棵“解答樹”並尋找符合目標狀態的節點的過程。

Minimax算法又名極小化極大算法，是一種找出失敗的最大可能性中的最小值的算法。Minimax算法常用於棋類等由兩方較量的游戲和程序，這類程序由兩個游戲者輪流，每次執行一個步驟。我們眾所周知的五子棋、象棋等都屬於這類程序，所以說Minimax算法是基於搜索的博弈算法的基礎。該算法是一種零總和算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，而另一方則選擇令對手優勢最小化的方法。