C++围棋程序实现报告(共20页).doc

《C++围棋程序实现报告(共20页).doc》由会员分享，可在线阅读，更多相关《C++围棋程序实现报告(共20页).doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上一、软件背景介绍围棋是一项广有裨益的智力竞技运动，它集休闲娱乐、陶冶性情、修心养性于一身，是中华文化的瑰宝，是人类智慧的最高象征之一。围棋经历了数千年，久盛不衰，且至今还在不断发展。现在的人工智能科学研究在它面前显得很是稚嫩，因而值得将它作为重要的研究对象。在人工智能领域内，博弈是很重要的一个研究分支。通过对博弈的研究，可以解决很多实际问题，使计算机智能向人类智能迈进。计算机国际象棋和计算机围棋一直是人工智能的热门课题，而围棋程序的编制被称作人工智能的“试金石”，是人工智能技术的一大难题，它将会在今后相当长的时期内哺育着人工智能科学的成长。计算机围棋是计算机博弈研究的

2、一个重要分支，是当前人工智能研究的热点之一，一直以来吸引着大量的研究人员，产生了较大的社会影响和学术影响。由于围棋变化复杂、棋理深奥，是一种高智能的活动，因而围棋的计算机博弈设计难度较大，同时计算机围棋热点问题的研究为人工智能带来了崭新的方法和理论。计算机围棋的研究和实现需要多门学科的知识交叉，至少会涉及到围棋、计算机、数学、生物、逻辑学、军事学、教育、心理学乃至哲学等领域，因此其发展具有重要的研究价值和应用价值。本系统是基于C+编程语言的立足于“人人”围棋对弈系统的设计与实现，具有围棋记谱、打谱、查看定式、最终评分等功能，是一个适宜在计算机上联网的“人人”的对弈系统。围棋胜负判断与局面分析功

3、能子系统是围棋对弈系统的重要组成部分。围棋胜负自动判断是一个实用的围棋对弈系统所应具有的功能。在现实的围棋胜负判断中，往往需要一个裁判员通过做棋来判断棋局最终的胜负。如果有一个客观、准确的围棋自动判断胜负系统，一方面可以省时省力，一方面可以做到客观公正。但实现一个具有人（裁判员）一样的判断能力的胜负判断系统，存在着许多困难和挑战。本系统通过建立棋局的记录来判断棋盘上每一点的归属，从而确定棋局中双方地域，故能够对提掉死子后的终局棋盘用中国规则判断胜负；通过建立棋子的影响模型、力学模型以及度量公式，将棋子向棋盘其它部分辐射的影响量化，从而判断对弈双方的影响领域。论文主要介绍了围棋对弈系统中胜负判断

4、与局面分析功能子系统具有的功能，论述了子系统的开发和实现的过程。该围棋游戏的主界面如图1。图1 围棋主界面 二、核心算法思想该围棋软件主要是由以下三种算法组成的：1、使每个棋子周围产生某种影响，这种影响随着距离的增加而减少，用一定的公式计算叠加种影响，以判断形势和估计着点的价值。这与围棋的棋理相通，即对于每个棋子可估算其“势力”。此中就有著名的“气位”理论。2、建立模式库，贮存了大量模式（定式、棋形等），以供匹配。这其实涉及到围棋的许多棋谚与棋理。如“二子头必扳”、“镇以飞应”、“断从一边长”、三子正中、点方等等。这些都是根据围棋的具体情况而设计的。3、 对目标明确的局部，用人工智能中的搜索法

5、探求其结果。（一）围棋局面分析功能的实现这里定义了Stone的数据结构，用于记录每一点与棋盘上已落棋子的距离和受到的影响值，定义如下： Public Type Stone Value As Integer Distance As IntegerEnd Type需要定义显示地域时的棋谱Public Map(1 To 19, 1 To 19) As Stone ，用于记录最后的累加影响。其中Map上每一点Map（i，j）的Distance与value的关系为：Value = 2 的 (6 - Distance)次方。Map（i，j）的最终影响要通过计算影响模型，递减定律以及反射定律，经过度量公式计

6、算，大于定值A的点显示为黑棋地域，小于-A的点显示为白棋地域。（二） 影响模型由于棋盘上的每个棋子都要对盘面发出影响，设黑棋影响为正，白棋影响为负。棋盘上的每一点要受到多个棋子的累加影响，其中，受到该点最近的棋子影响最大，依次递减。设这影响在棋子的紧邻（距离为1）为最大值32，并随距离增加而按比例衰减，衰减因子为1/2。就是距离每增加时影响值减半。此时一黑子对其周围辐射的影响如图2。11 2 11 2 4 2 11 2 4 8 4 2 11 2 4 8 16 8 4 2 11 2 4 8 16 32 16 8 4 2 11 2 4 8 16 32 64 32 16 8 4 2 11 2 4 8

7、 16 32 16 8 4 2 11 2 4 8 16 8 4 2 11 2 4 8 4 2 11 2 4 2 11 2 11图2 系统使用的影响模型 影响模型的实现，采用循环嵌套，对一已落的棋子（i，j），计算其对周边的影响，定义变量row，column，对于满足i-6=row=i+6, i-6=column=i+6的点，（row，column）的距离distance为row-i+column-j，并记录到显示棋谱Map（19，19）中。（三）力学模型棋盘上的每一个棋子，都向周围四个方向发出影响，通过这种影响实现对空点的占领和棋子之间的相互作用， 这种影响可以被视为一种控制力，沿四个方向大小

8、相等，而黑白棋子产生的控制力符号相反。控制力产生后，沿它的方向向前传播，其传播方式遵守如下规律：1、递减规律控制力遇到一个点后，力的大小被减弱，符号方向不变地继续向前传播。如果遇到空点，减弱后的控制力变为原来的一个常数倍（取1/2），该常数被称为传播率；如果遇到有子点，沿原方向的控制力消减。棋子（i，j）在传播过程中，如遇到另一棋子（m，n），则同方向的距离distance+2，即受到的影响值减1/4倍。2、反射定律由于在围棋中边角更容易受到棋子的影响，有“金角银边”之称。故在实现时设计了反射定律。控制力到达棋盘边缘后，会被反射回来，该反射力与原控制力方向相反，符号相同，大小为原控制力的一个常

9、数倍，该常数被称为反射率。实现时，棋子（i，j）在传播过程中，利用row，column双重循环，如遇到row=1或19，则同方向的距离distance-row-i；如遇到column=1或19，则同方向的距离distance-column-j。每一个点都受到四个方向的控制力的作用，任一方向的控制力的大小是这个点所受这个方向所有控制力的代数和。在实际计算时，取：（1）任意棋子产生的初始控制力的大小为64；（2）黑子的影响为正、白子的影响为负；（3）传播率为1/2；（4）反射率为1；3、度量公式在得到任一棋盘状态下个空点影响的分布图后，可以由这些影响值经过计算得到一些棋盘状态的深层信息，一些常用的

10、度量公式如下。设一个点受到的四个控制力大小为：向上F0，向右F1，向下F2，向左F3。总力：F=F0+F1+F2+F3表示一个点受到某一方影响的度量。 F0：受黑的影响强一些； F0：受白的影响强一些； F0： 双方的影响基本平衡。4、判定双方的势力范围对于每一点，它受到的总控制力F=F0+F1+F2+F3，当F大于某一数值n时，将其显示为地域。当F0时受黑的影响强一些，该点能被黑方所控制，作为黑方实地，显示为黑方地域，反之，为白棋的势力范围。在显示中规定：如果该点所受四个方向的力均大于0，且F大于20，则该点为黑方势力范围。对于白方的势力范围有类似的判断规则。（四）围棋胜负的判断方法双方下子

11、完毕的棋局，计算胜负采用数子法。 先将双方死子全部清理出盘外，然后对一方的活棋（包括活棋围住的点）以子为单位进行计数。 双方活棋之间的空点各得一半，一个点即为一子。 胜负的基准以棋局总点数的一半180又1/2点为归本数。凡一方活棋与所属空点的总和大于此数者为胜，小于此数者为负，等于此数者为和。三、核心算法流程图（一）判定双方的势力范围对于每一点，它受到的总控制力F=F0+F1+F2+F3，当F大于某一数值n时，将其显示为地域。当F0时受黑的影响强一些，该点能被黑方所控制，作为黑方实地，显示为黑方地域，反之为白棋的势力范围。在显示中规定：如果该点所受四个方向的力均大于0，且F大于20，则该点为黑

12、方势力范围。对于白方的势力范围有类似的判断规则。双方的势力范围的实现流程图如图3。双 方 势 力 范 围处于边或角画出显示地域用棋盘画出对弈双方棋子 是 否 反射定律行数=19列数=19 传播中受到其它子阻挡 否是否 影响范围内 是递减定律影响模型度 量 公 式显 示 势 力画出双方控制地域结束图3 局面分析实现流程图（二）判断围棋输赢这里定义了Item的数据结构，用于记录每一枚棋子的颜色及搜索的状态：Public Type Items Value As Integer Checked As BooleanEnd Type定义终局棋谱数组：Public m_GameOverMap(1 To 1

13、9, 1 To 19) As Items，终局的每一结点存储为Item结构，记录每一点的归属。对待盘棋局（用m_Map（19，19）记录）上每一点用循环扫描，记录每一点是哪一方的领域。 下图为判断围棋胜负的流程图。 计 为 单 官确定该点颜色总 数 加 1填 入 黑 子单官为奇数该黑方落子是判 断 胜 负行数 = 19列数 = 19被同色棋包围否判 断 胜 负 行数= 19列数= 19 否 是被同色棋子围计 为 单 官 是白 总 数 减 1 填 入 白 子 黑 否帖 子 计 算总 数 减 1显示胜负 否 是总 数 加 1结 束 图 4 胜负判断实现流程图四、源代码下面给出的是实现联网对战游戏的

14、源代码：#include MyStack.h#include MyList.h#include MyOutFunction.h#pragma once#include using namespace std;#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000struct pointint p_x; /x坐标，1-19间的整数int p_y; /y坐标，1-19间的整数int color; /所放棋子颜色，1为黑，2为白;struct _nodepoint data;_node* next;_node* pre;class CChessPos

15、public:BOOL visit_for_DeadOrLive;/访问标识，用于递归算法BOOL visit_for_DeleteDead;CRect chessman(CPoint point); /该位置所在矩形区域int nFlag; /该位置状态标识CPoint point; /该位置坐标CChessPos* pLeft; /指向该位置的四个邻接点CChessPos* pRight;CChessPos* pTop;CChessPos* pBottom;CChessPos();virtual CChessPos();#include mscomm.h#include SelectCom

16、m.h#include ChessPos.h#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000const int DIE = 0; /表示空位或死棋const int BLACK = 1; /黑棋const int WHITE = 2; /白棋const int EDGE = 3; /边界以外class MyList public:void init();MyList();virtual MyList();_node* head;_node* now;_node* tail;int size;void add(_node* newNode);

17、void add(int x, int y,int color);bool isEmpty();void printList(); /根据函数format定义的格式遍历链表，step记录结点遍历到了第几个结点void printList(void(*format)(void* e,void* steptag),int step);void del(); /删除链表最后一个元素void clearList(); /清空链表bool searchele(int x, int y);/遍历链表;struct _state/保存棋盘中每个格子的临时状态，以判别处于该位置的棋子是否能存活int x; /

18、在棋盘中的横坐标int y; /在棋盘中的纵坐标int fangxiang;int color;int footprint; int dead; /处于此格子的棋子可能死亡;struct _statenode_state s;_statenode* next;class MyStackpublic:_statenode* head;int size; /堆栈大小MyStack();virtual MyStack();void init(); /初始化void push(_state* s); /入栈_state* pop(); /出栈bool isEmpty(); /判断是否为空void pr

19、int(); /输出;ON_COMMAND(ID_APP_ABOUT, OnAppAbout) /ClassWizard将添加和删除映射宏。/ DO NOT EDIT what you see in these blocks of generated code!/AFX_MSG_MAP /基于标准的文件文档的命令ON_COMMAND(ID_FILE_NEW, CWinApp:OnFileNew)ON_COMMAND(ID_FILE_OPEN, CWinApp:OnFileOpen) /标准的打印设置命令ON_COMMAND(ID_FILE_PRINT_SETUP, CWinApp:OnFile

20、PrintSetup)END_MESSAGE_MAP()public:CAboutDlg();/ Dialog Data/AFX_DATA(CAboutDlg)enum IDD = IDD_ABOUTBOX ;/ Attributespublic:CPoint pointBegin;/左上角坐标int nDistance;/每格间距int nRadium;/点的半径int r;/围棋半径int nCount;/下的数目CRect m_rectEllipse1919;/当前围棋子所在矩形int nSign2121;/点标志int nOldSign2121;/吃掉前的标志int nChainRow

21、1920;/存放水平方向的点标志之间的关系int nChainCol2019;/存放竖直方向的点标志之间的关系int nBorder;/棋盘边界宽度int nBackSign2121;/前次位置标志备份int nBackTwoTimesBeforeSign2121; /前两次位置标志备份int nBackThreeTimesBeforeSign2121; /前两次位置标志备份int nBackOldSign2121;int nBackChainRow1920;int nBackChainCol2019;int nBackCount;int nBackCountTwoTimesBefore;/前

22、两次统计备份CPoint pointForGoPrompt;/下子提示点CPoint pointForRegret;/悔棋按钮CPoint pointForWhiteCalculate;/显示统计时白棋标志的位置CPoint pointForBlackCalculate;CPoint pointForIllegal;/非法提示int nCalculateWhite;/白子统计int nCalculateBlack;/黑子统计int nBackCalculateWhite;/白子统计备份int nBackCalculateBlack;/黑子统计备份BOOL fIllegal;/非法走步标志BOO

23、L fRegretOnlyOnce;/只许悔棋一次/=/位图有关定时器有关/=/CBitmap m_BitmapToRight;CRect m_rectBitmapToRight;int m_nBitmapToRightHeight;int m_nBitmapToRightWidth;CBitmap m_BitmapToLeft;CRect m_rectBitmapToLeft;int m_nBitmapToLeftHeight;int m_nBitmapToLeftWidth;struct _statenode_state s;_statenode* next;class MyStackpu

24、blic:_statenode* head;int size; /堆栈大小MyStack();virtual MyStack();UINT m_timer; /计时器标志BOOL m_fAlternate;BOOL m_fClear;/ Operationspublic:virtual BOOL OnNewDocument();virtual void Serialize(CArchive& ar);CAboutDlg:CAboutDlg() : CDialog(CAboutDlg:IDD)/AFX_DATA_INIT(CAboutDlg)/AFX_DATA_INITvoid CAboutDl

25、g:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CAboutDlg)/AFX_DATA_MAPclass CWQDoc : public CDocumentprotected: / create from serialization onlyCWQDoc();DECLARE_DYNCREATE(CWQDoc)public:virtual BOOL OnNewDocument();virtual void Serialize(CArchive& ar);public:BOOL m_bGam

26、eStartEnable;/开始游戏是否有效BOOL Initialization(); /新建文档初始化函数BOOL m_bEnable;/判断是否可以落子UINT nGameMode;/游戏模式UINT nComNum;/所选择的串口号CMSComm m_MSComm;/定义串口对象m_MSCommBOOL reback; /悔棋enable标识int backup_scene1919; /备份前次场景int cur_scene1919; /当前场景int pre_scene1919; /前次场景int last_scene1919; /上次场景#ifdef _DEBUGvirtual v

27、oid AssertValid() const;virtual void Dump(CDumpContext& dc) const;#endifMyList();virtual MyList();_node* head;_node* now;_node* tail;int size;void add(_node* newNode);void add(int x, int y,int color);bool isEmpty();void printList();/根据函数format定义的格式遍历链表，step记录结点遍历到了第几个结点void printList(void(*format)(v

28、oid* e,void* steptag),int step);void del();/删除链表最后一个元素void clearList();bool searchele(int x, int y);#include PublicStruct.hclass CWeiQi public:CWeiQi();virtual CWeiQi();public:BOOL TiZi(int x,int y);short GetPointType(int x,int y);void ClearNodes();void Init();void Init2();/小棋盘void ClearBoardFlag();

29、protected:class CWeiQ1_0View : public CViewprotected: CWeiQ1_0View();DECLARE_DYNCREATE(CWeiQ1_0View)private:void DrawChessboard(CDC* pDC,CPoint top_left,COLORREF bkcolor,int space, int radius);protected:/AFX_MSG(CWQView)afx_msg void OnLButtonUp(UINT nFlags, CPoint point);afx_msg void OnReback();afx_

30、msg void OnUpdateReback(CCmdUI* pCmdUI);afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct);afx_msg void OnComm(); CChessPos outside;/虚拟棋子位置，用于处理边界问题CPoint origin; /棋盘初始点int nStep; /画笔跳跃步幅int nHost; /落子权标志CChessPos CurPos1919;/用于存储棋盘1919点位信息virtual CWQDoc();#ifdef _DEBUGvirtual void AssertValid() co

31、nst;virtual void Dump(CDumpContext& dc) const;#endifpublic:void reback_scene(int comeback1919);/当前场景恢复到comebackvoid save_scene(int save1919);/保存当前场景到savevoid copy_scene(int from1919, int to1919); /复制场景from到toBOOL compare_scene(int A1919, int B1919);/比较场景A和B，相同-true,不同-falsevoid un_visit();/恢复各位置访问标识

32、void deal_neighbor(CChessPos *mid);/处理mid周围异色棋子void del_dead(CChessPos *dead);/以dead为起点提掉与其相连的同色棋子BOOL dead_or_live(CChessPos *mid);/判断mid是死棋还是活棋void change_nHost();/转换落子权CPoint locate(CPoint pt);/将单击点pt矫正到最近的棋盘点位，返回该点位坐标virtual CWQView();#ifdef _DEBUGvirtual void AssertValid() const;virtual void Du

33、mp(CDumpContext& dc) const;#endifclass CWeiQ1_0Doc : public CDocumentprotected: / create from serialization onlyCWeiQ1_0Doc();DECLARE_DYNCREATE(CWeiQ1_0Doc)/ Attributespublic:virtual BOOL OnNewDocument();virtual void Serialize(CArchive& ar);AFX_VIRTUALpublic:bool m_modified;char* m_openedFilename;My

34、List m_nowlist;/保存棋盘上剩下的棋子的信息int m_qiju2121;/保存棋盘要显示的信息，主要是易于判断吃子MyList m_historylist;/保存曾经走过的每一步int m_radius;int m_space;COLORREF m_bkcolor;CPoint m_topleft;virtual CWeiQ1_0Doc();#ifdef _DEBUGvirtual void AssertValid() const;virtual void Dump(CDumpContext& dc) const;struct pointint p_x;/x坐标，1-19间的整

35、数int p_y;/y坐标，1-19间的整数int color;/所放棋子颜色，1为黑，2为白;class MyList public:void init();MyList();virtual MyList();_node* head;_node* now;_node* tail;int size;void add(_node* newNode);void add(int x, int y,int color);bool isEmpty();void printList(); /根据函数format定义的格式遍历链表，step记录结点遍历到了第几个结点void printList(void(*

36、format)(void* e,void* steptag),int step);void del(); /删除链表最后一个元素void clearList(); /清空列表bool searchele(int x, int y); /搜索链表; / MyOutFunction.h: interface for the MyOutFunction class.#endif / _MSC_VER 1000class MyOutFunction public:static bool saveQipu(MyList list,char* fileName);static char* _CString

37、ToChars(CString string );static bool readQipu(MyList& list, char* fileName);static void initQiju(int qiju2121);static bool moni(int qiju2121, MyList list);static _state* creatState(int x,int y,int color,int fangxiang,int footprint, int dead);/创建一颗棋子static bool isTong(_state go2121,int& x,int& y,int&

38、 end);/判断处于该格子的棋子按某个方向能否走出该格子 /判断goxy能否存活，若不能存活，则将和goxy一起不能存活的子消掉static bool isLive(int go2121,int x, int y, int color);MyOutFunction();virtual MyOutFunction();#endif #if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000struct _state/保存棋盘中每个格子的临时状态，以判别处于该位置的棋子是否能存活int x;/在棋盘中的横坐标int y;/在棋盘中的纵坐标int fan

39、gxiang;/从此格子走向下一格子的方向-1：向右走，2:向左走，3：向上走，4：向下走int color;/此棋子的性质；0：没有棋子，1：黑子，2：白子,3:边界int footprint;/是否来过试探过这颗棋子；1：是，0：否int dead;/处于此格子的棋子可能死亡;struct _statenode_state s;_statenode* next;class MyStackpublic:_statenode* head;int size;/堆栈大小MyStack();virtual MyStack();void init();void push(_state* s);/入栈_state* pop();/出栈bool isEmpty();/判断是否栈为空void print();#if _MSC_VER 1000#pragma once