C++围棋程序实现报告
别妄想泡我
975次浏览
2021年01月18日 14:48
最佳经验
本文由作者推荐
深圳刻章-新年祝贺语
TCP-IP
协议与网络编程课程设计
一、软件背景介绍
围棋是一项广有裨益的智力竞技运动，它集休闲娱乐、陶冶性情、
修心养性于一身，是
中华文 化的瑰宝，是人类智慧的最高象征之一。围棋经历了数千年，久盛不衰，且至今还在
不断发展。
现在的人工智能科学研究在它面前显得很是稚嫩，
因而值得将它作为重要的研究
对象。
在人工智能领域内，博弈是很重要的一个研究分支。通过对博弈的研究，可以解决很
多实际问题，
使计算机智能向人类智能迈进。
计算机国际象棋和计算机围棋一直是人工智能
的热门课题，< br>而围棋程序的编制被称作人工智能的
“试金石”
，
是人工智能技术的一大难题，
它将会在今后相当长的时期内哺育着人工智能科学的成长。
计算机围棋是计算机博弈 研究的一个重要分支，
是当前人工智能研究的热点之一，
一直
以来吸引着大量的研究人 员，
产生了较大的社会影响和学术影响。
由于围棋变化复杂、
棋理
深奥，是一种高智能的活动，
因而围棋的计算机博弈设计难度较大，
同时计算机围棋热点问
题的研究为人工智能带来了崭新的方法和理论。
计算机围棋的研究和实现需要多门学科的知 识交叉，
至少会涉及到围棋、
计算机、
数学、
生物、逻辑学、军事学、教育、 心理学乃至哲学等领域，因此其发展具有重要的研究价值和
应用价值。
本系统是基于
C++
编程语言的立足于“人―人”围棋对弈系统的设计与实现，具有围棋
记谱、打谱 、查看定式、最终评分等功能，是一个适宜在计算机上联网的“人―人”的对弈
系统。
围棋胜负判断与局面分析功能子系统是围棋对弈系统的重要组成部分。
围棋胜负自动判
断是一 个实用的围棋对弈系统所应具有的功能。
在现实的围棋胜负判断中，
往往需要一个裁
判 员通过做棋来判断棋局最终的胜负。
如果有一个客观、
准确的围棋自动判断胜负系统，
一
方面可以省时省力，
一方面可以做到客观公正。但实现一个具有人
（裁判员）一样的 判断能
力的胜负判断系统，
存在着许多困难和挑战。
本系统通过建立棋局的记录来判断 棋盘上每一
点的归属，
从而确定棋局中双方地域，
故能够对提掉死子后的终局棋盘用中 国规则判断胜负；
通过建立棋子的影响模型、
力学模型以及度量公式，
将棋子向棋盘其 它部分辐射的影响量化，
从而判断对弈双方的影响领域。
论文主要介绍了围棋对弈系 统中胜负判断与局面分析功能子系统具有的功能，
论述了子
系统的开发和实现的过程。
该围棋游戏的主界面如图
1
。
- 1 -
TCP- IP
协议与网络编程课程设计
图
1
围棋主界面
二、核心算法思想
该围棋软件主要是由以下三种算法组成的：
1
、使每个棋子周围产生某种影 响，这种影响随着距离的增加而减少，用一定的公式计
算叠加种影响，
以判断形势和估计着点的 价值。
这与围棋的棋理相通，
即对于每个棋子可估
算其“势力”
。此中就有著 名的“气位”理论。
2
、建立模式库，贮存了大量模式（定式、棋形等）
， 以供匹配。这其实涉及到围棋的许
多棋谚与棋理。如“二子头必扳”
、
“镇以飞应”< br>、
“断从一边长”
、三子正中、点方等等。这
些都是根据围棋的具体情况而设计 的。
3
、
对目标明确的局部，用人工智能中的搜索法探求其结果。
（一）围棋局面分析功能的实现
这里定义了
Stone
的数据结构，
用于记录每一点与棋盘上已落棋子的距离和受到的影响
值，定义如下：
Public Type Stone
Value As Integer
Distance As Integer
End Type
- 2 -
TCP-IP
协议与网络编程课程设计
需要定义显示地域时的棋谱
Public Map(1 To 19, 1 To 19) As Stone
，用于记录最
后的累加影响。其中
Map
上每一点
Map
（
i
，
j
）的
Distance
与
value
的关系为：
Value = 2
的
(6
- Distance)
次方。
Map
（
i
，
j
） 的最终影响要通过计算影响模型，递减定律以及反射
定律，经过度量公式计算，大于定值
A的点显示为黑棋地域，小于
-A
的点显示为白棋地域。
（二）
影响模型
由于棋盘上的每个棋子都要对盘面发出影响，
设黑棋影响为正，< br>白棋影响为负。
棋盘上
的每一点要受到多个棋子的累加影响，其中，受到该点最近的棋子 影响最大，依次递减。
设这影响在棋子的紧邻（距离为
1
）
为最大 值
32
，
并随距离增加而按比例衰减，衰减因
子为
1/2
。 就是距离每增加１时影响值减半。
此时一黑子对其周围辐射的影响如图
2
。
1
1 2 1
1 2 4 2 1
1 2 4 8 4 2 1
1 2 4 8 16 8 4 2 1
1 2 4 8 16 32 16 8 4 2 1
1 2 4 8 16 32 64 32 16 8 4 2 1
1 2 4 8 16 32 16 8 4 2 1
1 2 4 8 16 8 4 2 1
1 2 4 8 4 2 1
1 2 4 2 1
1 2 1
1
图
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
）中。
（三）力学模型
棋盘上的每一个棋子，
都向周围四个方向发出影响，
通过这种影响实现对空点的占领和棋子之间的相互作用，
这种影响可以被视为一种控制力，沿四个方向大小相等，而黑白棋
子产生的控制力符号相反。
控制力产生后，
沿它的方向向前传播，
其传播方式 遵守如下规律：
1
、递减规律
控制力遇到一个点后，
力 的大小被减弱，
符号方向不变地继续向前传播。
如果遇到空点，
- 3 -
TCP-IP
协议与网络编程课程设计
减弱后的控制力变为原来的一个常数 倍（取
1/2
）
，该常数被称为传播率；如果遇到有子点，
沿原方向的控制力 消减。棋子（
i
，
j
）在传播过程中，如遇到另一棋子（
m
，
n
）
，则同方向
的距离
distance+2
，即受到的 影响值减
1/4
倍。
2
、反射定律
由于在围棋 中边角更容易受到棋子的影响，有
“金角银边”之称。
故在实现时设计了反
射定律。< br>控制力到达棋盘边缘后，
会被反射回来，
该反射力与原控制力方向相反，
符号相 同，
大小为原控制力的一个常数倍，
该常数被称为反射率。
实现时，
棋子（
i
，
j
）
在传播过程中，
利用
row
，
column
双重循环，如遇到
row=1
或
19
，则 同方向的距离
distance-
︱
row-i
︱；
如遇到
column=1
或
19
，则同方向的距离
distance-
︱< br>column-j
︱。每一个点都受到四个方
向的控制力的作用，任一方向的控制力的大 小是这个点所受这个方向所有控制力的代数和。
在实际计算时，取：
（
1
）任意棋子产生的初始控制力的大小为
64
；
（
2
）黑子的影响为正、白子的影响为负；
（
3
）传播率为
1/2
；
（
4
）反射率为
1
；
3
、度量公式
在得到任一棋盘状态下个空点影响的分布图后，
可以 由这些影响值经过计算得到一些棋
盘状态的深层信息，一些常用的度量公式如下。
设 一个点受到的四个控制力大小为：向上
F0
，向右
F1
，向下
F2< br>，向左
F3
。
总力：
F=F0+F1+F2+F3
表示一个点受到某一方影响的度量。
F
﹥
0
：受黑的影响强一些；
F
﹤
0
：受白的影响强一些；
F
＝
0
：
双方的影响基本平衡。
4
、判定双方的势力范围
对于每一点，它受到的总控制力
F=F0 +F1+F2+F3
，当｜
F
｜大于某一数值
n
时，将其显
示为地域。当
F
﹥
0
时受黑的影响强一些，该点能被黑方所控制，作为黑方实 地，显示为黑
方地域，反之，为白棋的势力范围。在显示中规定：如果该点所受四个方向的力均大于0
，
且
F
大于
20
，则该点为黑方势力范围。对于白方 的势力范围有类似的判断规则。
（四）围棋胜负的判断方法
双方下子完毕的棋局，计算胜负采用数子法。
先将双方死子全部清理出盘外，然后对
一方的活棋（包括活棋围住的点）以子为单位进行计数。
双方活棋之间的空点各得一半，
一个点即为一子。
胜负的基准以棋局总点数 的一半
180
又
1/2
点为归本数。凡一方活棋与
所属空点的总和大 于此数者为胜，小于此数者为负，等于此数者为和。
- 4 -
TCP- IP
协议与网络编程课程设计
三、核心算法流程图
（一）判定双方的势力范围
对于每一点，它受到的总控制力
F=F0+F1 +F2+F3
，当｜
F
｜大于某一数值
n
时，将其显
示为地 域。当
F
﹥
0
时受黑的影响强一些，该点能被黑方所控制，作为黑方实地，显 示为黑
方地域，反之为白棋的势力范围。在显示中规定：如果该点所受四个方向的力均大于
0< br>，且
F
大于
20
，
则该点为黑方势力范围。
对于白方 的势力范围有类似的判断规则。
双方的势力范
围的实现流程图如图
3
。
画出显示地域用棋盘
是
否
画出对弈双方棋子
反射定律
双
方
势
力
范
围
处
于
边
或
角
行
数
<
=
1
9
否
列
数
<
=
1
9
传播中受到
否
是
其它子阻挡
是
影
响
范
围
内
影响模型
结
束
图
3
局面分析实现流程图
递减定律
度
量
公
式
显
示
势
力
画出双方控制地域
（二）判断围棋输赢
这里定义了
Item
的数据结构，用于记录每一枚棋子的颜色及搜索的状态：
Public Type Items
Value As Integer
Checked As Boolean
End Type
- 5 -
TCP-IP
协议与网络编程课程设计
定义终局棋谱数组：
Public m_GameOverMap(1 To 19, 1 To 19) As Items
，终局的每
一结点存储为
Item
结构，记 录每一点的归属。对待盘棋局（用
m_Map
（
19
，
19
）记录）上
每一点用循环扫描，记录每一点是哪一方的领域。
下图为判断围棋胜负的流程图。
否
是
是
黑
否
是
否
该黑方落子
是
结
束
显示胜负
图
4
胜负判断实现流程图
- 6 -
判
断
胜
负
判
断
胜
负
行数
<= 19
行数〈
= 19
列数
<= 19
列数〈
= 19
否
被同色棋包围
被同色棋子围
计
为
单
官
计
为
单
官
确定该点颜色
白
总
数
减
1
填
入
白
子
总
数
加
1
填
入
黑
子
单官为奇数
总
数
加
1
总
数
减
1
帖
子
计
算
TCP- IP
协议与网络编程课程设计
四、源代码
下面给出的是实现联网对战游戏的源代码：
#include
#include
#include
#pragma once
#include
using namespace std;
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
struct point
{
int p_x;
int p_y;
int color;
};
struct _node
{
point data;
_node* next;
_node* pre;
};
class CChessPos
{
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
#include
#include
#if _MSC_VER > 1000
//x
坐标，
1-19
间的整数
//y
坐标，
1-19
间的整数
//
所放棋子颜色，
1
为黑，
2
为白
//
访问标识，用于递归算 法
//
该位置所在矩形区域
//
该位置状态标识
//
该位置坐标
//
指向该位置的四个邻接点
- 7 -
TCP- IP
协议与网络编程课程设计
#pragma once
#endif // _MSC_VER > 1000
const int DIE = 0;
//
表示空位或死棋
const int BLACK = 1;
const int WHITE = 2;
const int EDGE = 3;
class MyList
{
public:
};
struct _state
//
保存棋盘中每个格子的临时状态，以判别处于该位置的棋子是否能存活
{
};
struct _statenode
{
};
class MyStack
{
public:
_statenode* head;
_state s;
_statenode* next;
int x;
//
在棋盘中的横坐标
int y;
//
在棋盘中的纵坐标
int fangxiang;
int color;
int footprint;
int dead;
//
处于此格子的棋子可能死亡
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(*format)(void* e,void* steptag),int step);
void del();
//
删除链表最后一个元素
void clearList();
//
清空链表
bool searchele(int x, int y);//
遍历链表
//
黑棋
//
白棋
//
边界以外
- 8 -
TCP-IP
协议与网络编程课程设计
};
};
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::OnFilePrintSetup)
int size;
//
堆栈大小
MyStack();
virtual ~MyStack();
void init();
//
初始化
void push(_state* s);
//
入栈
_state* pop();
//
出栈
bool isEmpty();
//
判断是否为空
void print();
//
输出
END_MESSAGE_MAP()
public:
CAboutDlg();
//{{AFX_DA
TA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
}}
// Dialog Data
// Attributes
public:
CPoint pointBegin;
int nDistance;
int nRadium;
int r;
int nCount;
//
左上角坐标
//
每格间距
//
点的半径
//
围棋半径
//
下的数目
//
当前围棋子所在矩形
//
点标志
//
吃掉前的标志
//
存放水平方向的点标志之间的关系
//
存放竖直方向的点标志之间的关系
//
棋盘边界宽度
//
前次位置标志备份
CRect m_rectEllipse[19][19];
int nSign[21][21];
int nOldSign[21][21];
int nChainRow[19][20];
int nChainCol[20][19];
int nBorder;
int nBackSign[21][21];
int nBackTwoTimesBeforeSign[21][21]; //
前两次位置标志备份
int nBackThreeTimesBeforeSign[21][21]; //
前两次位置标志备份
int nBackOldSign[21][21];
int nBackChainRow[19][20];
int nBackChainCol[20][19];
int nBackCount;
int nBackCountTwoTimesBefore;
//
前两次统计备份
- 9 -
TCP- IP
协议与网络编程课程设计
{
};
class MyStack
{
public:
_statenode* head;
int size;
//
堆栈大小
MyStack();
virtual ~MyStack();
UINT
m_timer;
BOOL m_fAlternate;
BOOL m_fClear;
//
计时器标志
_state s;
_statenode* next;
CBitmap m_BitmapToLeft;
CRect m_rectBitmapToLeft;
int m_nBitmapToLeftHeight;
int m_nBitmapToLeftWidth;
CPoint pointForGoPrompt;
CPoint pointForRegret;
//
下子提示点
//
悔棋按钮
//
显示统计时白棋标志的位置
//
非法提示
//
白子统计
//
黑子统计
//
白子统计备份
//
黑子统计备份
//
非法走步标志
//
只许悔棋一次
CPoint pointForWhiteCalculate;
CPoint pointForBlackCalculate;
CPoint pointForIllegal;
int nCalculateWhite;
int nCalculateBlack;
int nBackCalculateWhite;
int nBackCalculateBlack;
BOOL fIllegal;
BOOL fRegretOnlyOnce;
//
位图有关定时器有关
//================================== =============//
//============================ ===================//
CBitmap m_BitmapToRight;
CRect m_rectBitmapToRight;
int m_nBitmapToRightHeight;
int m_nBitmapToRightWidth;
struct _statenode
// Operations
public:
virtual BOOL OnNewDocument();
virtual void Serialize(CArchive& ar);
- 10 -