如图所示,此即为日本动漫棋魂中的千年佐为,也就是SAI。众所周知,围棋的规则相比于中国象棋,国际象棋等等都简单许多,真是因为更简单的规则,才诞生 了更复杂的逻辑。目前的围棋AI还很不行,最NB的应该是日本人做出的后又经过众多中国的围棋爱好者改进之后的AI——首谈,其水平号称是国际大师的水 平,其实际水平估计也就是业余一段左右(比我的水平还是要稍微高一点点的样子)。而且,只要在其中下出一些“非主流布局”,比如神马天元+五五啊,宇宙流 之类的,手谈基本上就GAME OVER了。
目前在OJ(Online Judge)上还没有类似的围棋的全面模拟算法,局部的还是有,这是因为围棋的规则如果包括一些不常见的,比如盘角曲四啊,三劫循环等等,也是很难用计算 机模拟出的,而一些著名的围棋模拟软件(比如在线的TOM啊,弈城啊等等)又无法开源,在CSDN上和PUDN上又基本上是工程级别的项目,鲜有直接的核 心算法。多亏了一个叫荷蒲的网站,我看其作者应该也是围棋爱好者吧,他自己建立了一个网站,主要是在网上接一些项目,由于他本人喜欢围棋,故也创办了“荷 蒲围棋”,并向广大的围棋爱好者提供了关于模拟算法的一些思路。但是,关于三劫循环等等,还是没有列出来。
这 一期的Round,我只给出一些主要的函数以及成员变量,函数与函数之间没有明显的先后关系,但是,每一个函数可以实现一些主要功能,在以后封装的时候也 很好解决。该思路一共分为六个部分,关于吃子的那个部分利用了递归的思想解决了对于“一片棋”的气眼的计算。在统计谁是获胜方时,不能单一地像黑白棋一样 来分别统计黑子和白子的数目,因为其中有些空缺的地方需要判断是黑方还是白方或者既不是黑方又不是白方的,这样描述起来还是有些麻烦。
更多地关于该源码的解析(比如具体的数目问题)以及关于源码在其它功能的拓展和完善,我有待联系荷蒲的作者之后再予以补充。
以下,我分为六大块来解析“荷蒲”先生的源码:
1
//
1、首先定义围棋子信息
2
3
#define EDGE 23
//
棋盘最大格数
4
#define MAXMM 500
//
最大手数
5
//
color表示棋子颜色,x,y表示在棋盘上的坐标
6
//
num表示下子的顺序。=0表示提前摆放的子。
7
//
zt 表示棋子状态
8
//
qs 表示棋子的气数
9
//
sm 表示有说明信息
10
11 typedef
struct qizi
12 {
13
int color,x,y,num,zt,qs,sm;
14 }qizi;
15
16
//
吴昊评述:这个用法比较不常见,意义是为这个实例化的结构体定义新的成员变量。
17
qizi qipu[MAXMM];
//
棋谱信息
18
qizi qipan[EDGE][EDGE];
//
棋盘信息
19
20
//
2、紧接着要考虑的是下棋相关信息。
21
//
吴昊评述:这里的定义比较复杂,作者考虑了人机对战以及非人机对战中的总共四种情况,并且有学习和联系模式,有围棋中需要的计时器,最后还在规则上考虑了中国规则,日本规则等等(中日韩三国的围棋规则有不同,比如在盘角曲四的处理上),但是,很多成员变量只是为了以后代码的扩充作准备的,在后面的代码 描述中并没有出现。
22
int nk=
0;
//
显示棋子序号,nk=2显示序号,1=气数
23
int BoardLines=
19;
//
棋盘线数,默认19
24
bool ComputerPlaying;
//
1=该计算机下 0=人下
25
bool Computerp1=
0;
//
1=计算机下黑 0=人下
26
bool Computerp2=
0;
//
1=计算机下白 0=人下
27
int PlayType=
0;
//
2=人-人,1=人-计算机,13=人-网络,0=没有开始,-1=删除棋盘上死子,-2=暂停,3=布黑子,4=布白子,9=演示,11=学习
28
int PlayType1=
0;
//
2=人-人,1=人-计算机,13=人-网络,0=没有开始,-1=删除棋盘上死子,-2=暂停,3=布黑子,4=布白子,11=学习
29
int MoveCount,MoveCount1;
//
计步器,记录落子手数,自然顺序
30
int Playnum=
0,Playnum1=
0;
//
要标识的围棋手数,下棋顺序
31
int CurrentX;
//
记录热子X坐标,
32
int CurrentY;
//
记录热子Y坐标
33
char CurrentWho;
//
记录当前棋子颜色,0=黑 1=白 2=空(终局等,待写)
34
char CurrentWho1;
//
备份上一次CurrentWho
35
int timew=
0,timeb=
0;
//
计时器设定数据
36
int sdy1=
0,sdy2=
0;
//
学习功能上使用
37
int gz;
//
规则0=中国规则,1=日本规则,2=应氏规则
38
bool plays1=
true;
//
学习持黑
39
bool plays2=
false;
//
学习持白
40
41
//
3、围棋电子棋盘的数据初始化。
42
//
数据初始化
43
44
void wqinit(
void)
45 {
46 BoardLines=
19;
//
19X19路标准围棋盘
47
MoveCount=
0;
//
一步棋未下,自然顺序
48
MoveCount1=
0;
//
一步棋未下
49
ComputerPlaying=
1;
//
默认电脑执黑先行
50
CurrentWho=
0;
//
默认黑先; 黑方=0;白方=1;空方=2;
51
CurrentX=
0;
//
当前一步棋的X坐标,水平从左至右为1...19
52
CurrentY=
0;
//
当前一步棋的Y坐标,垂直从上到下为1...19
53
timew=
0,timeb=
0;
54 Playnum=
0;
//
下棋顺序
55
Playnum1=
0;
56
//
下面是棋盘初始化
57
for (
int i=
0;i<=BoardLines;i++)
58
for (
int j=
0;j<=BoardLines;j++)
59 {
60 qipan[i][j].color=
2;
61 qipan[i][j].x=
0;
62 qipan[i][j].y=
0;
63 qipan[i][j].num=
0;
64 qipan[i][j].zt=
0;
65 }
66
67
//
清空棋谱记录,全部设为无效点。QiPu[0][x]留作它用
68
for (
int i=
0;i<
500;i++)
69 {
70 qipu[i].color=
2;
71 qipu[i].x=
0;
72 qipu[i].y=
0;
73 qipu[i].num=
0;
74 qipu[i].zt=
0;
75 qipu[i].sm=
0;
76 qpsm1[i].n=
0;
77 qpsm1[i].t=
0;
78 strcpy(qpsm1[i].sm,
"
/
");
79 }
80 }
81
82
/*
83
4、根据围棋规则编写的一些相关处理函数模块
84
围棋棋子的吃子,是根据围棋棋子的气数来计算的。气数为0的棋子应当从棋盘上拿掉。
85
围棋气数的计算问题,应当说是围棋软件的核心问题。
86
"气"是指棋子在棋盘上可以连接的交叉点,也是棋子的出路。
87
围棋的气数计算,要考虑一个围棋子的连通问题。
88
下面的图形中,交叉点的X代表棋子的气,
89
*/
90
91
92 [图1]
93 图1中右上角的黑子,有两个交叉点和它的直线相接,因此它有两口气。左上角的黑子有三口气,而下边的黑子有四口气。
94
95
96
97 [图2]
98 图2中右边的黑子有四口气,中间连接在一起的两个黑子有六口气,而右边连接在一起的三个黑子有八口气。连接在一起的棋子越多,气也越多。
99
100
101
102 [图3]
103 图2中同样是四个连接在一起的黑子,左边的四个黑棋有十口气,中间的黑棋只有九口气,而右边的黑棋仅有八口气。
104 从上面分析,可以得出,计算一个棋子的气,还有分析该棋子周围的情况,因此我们利用递归函数来解决围棋气数的计算。实现方法看下面程序断(这一点可以采用递归思想来解决)。 另外,注意下面三个函数是互相嵌套的关系,第二个函数利用第一个函数来递归地求出“一片棋”中的气的多少,第三个函数将第二个函数算出的气数存储在成员变量qs中,以便于最后的提子中调用。
105
106
int go[EDGE][EDGE];
107
108
/*
109
表示棋盘 其中第0路和第20路为沉余数据
110
在 (X,Y)下黑子
111
go[x][y]=0;// 0表示黑
112
在 (X,Y)下白子
113
go[x][y]=1;// 1表示白子
114
在 (X,Y)提子
115
go[x][y]=2; //2表示空子
116
当前棋步脱先pass则 当前棋步 X坐标=0,y=0
117
否则 1<=x<=19, 1<=x<=19,
118
*/
119
120
int gokong[EDGE][EDGE];
//
0=该空点未曾计算过气,1=已计算,避免重复计算公气
121
int gozi[EDGE][EDGE];
//
0=该子未计算串气,1=已计算,避免重复计算同一个子的气
122
int goqi;
//
气数
123
//
以上变量声明为全局变量
124
125
void str_qi(
int x,
int y,
int hb)
126 {
127
//
本函数计算 x,y 处的hb颜色棋子的气
128
gozi[x][y]=
1;
//
标记本子已经计算过气
129
///
//右临子
130
if (x+
1<=
19)
//
如果没有超出棋盘边线
131
{
132
if ((go[x+
1][y]==
2)&&(gokong[x+
1][y]==
0))
133
//
如果右临点为空并且该点未曾计算过气则
134
{
135 goqi++;
//
气数加一
136
gokong[x+
1][y]=
1;
//
标记本空点已经计算过气
137
}
138
else
if ((go[x+
1][y]==hb)&&(gozi[x+
1][y]==
0))
139
//
否则如果右临点为和本子同色子并且该子未曾计算过气则
140
str_qi(x+
1,y,hb);
//
递归调用到右临子
141
}
142
///
//左临子
143
if (x-
1>=
1)
//
果没有超出棋盘边线
144
{
145
if ((go[x-
1][y]==
2)&&(gokong[x-
1][y]==
0))
146
//
如果左临点为空并且该点未曾计算过气则
147
{
148 goqi++;
//
气数加一
149
gokong[x-
1][y]=
1;
//
标记本空点已经计算过气
150
}
151
else
if ((go[x-
1][y]==hb)&&(gozi[x-
1][y]==
0))
152
//
否则如果左临点为和本子同色子并且该子未曾计算过气则
153
str_qi(x-
1,y,hb);
//
递归调用到左临子
154
}
155
///
/下临子
156
if (y-
1>=
1)
//
如果没有超出棋盘边线
157
{
158
if ((go[x][y-
1]==
2)&&(gokong[x][y-
1]==
0))
159
//
如果下临点为空并且该点未曾计算过气则
160
{
161 goqi++;
//
气数加一
162
gokong[x][y-
1]=
1;
//
标记本空点已经计算过气
163
}
164
else
if ((go[x][y-
1]==hb)&&(gozi[x][y-
1]==
0))
165
//
否则如果下临子点为和本子同色子并且该子未曾计算过气则
166
str_qi(x,y-
1,hb);
//
递归调用到下临子
167
}
168
///
/上临点
169
if (y+
1<=
19)
//
如果没有超出棋盘边线
170
{
171
if ((go[x][y+
1]==
2)&&(gokong[x][y+
1]==
0))
172
//
如果上临点为空并且该点未曾计算过气则
173
{
174 goqi++;
//
气数加一
175
gokong[x][y+
1]=
1;
//
标记本空点已经计算过气
176
}
177
else
if ((go[x][y+
1]==hb)&&(gozi[x][y+
1]==
0))
178
//
否则如果上临点为和本子同色子并且该子未曾计算过气则
179
str_qi(x,y+
1,hb);
//
递归调用到上临子
180
}
181 }
182
183
int str_lib(
int x,
int y,
int hb)
184 {
185
int i,j;
186
for (i =
1; i <=
19; i++)
187
for (j =
1; j <=
19; j++)
188 {
189 gozi[i][j] =
0;
//
初始化变量,表示该子未计算串气
190
gokong[i][j] =
0;
//
初始化变量,表示该空点未计算串气
191
}
192 goqi=
0;
//
串气初值
193
str_qi(x,y,hb);
//
调用串气子程序
194
return(goqi);
//
全局变量goqi带回串气值
195
}
196
197
void suanqi(
void)
198 {
199
int i,j,cc,qq;
200
for (i =
1; i <=
19; i++)
201
for (j =
1; j <=
19; j++)
202 {
203 go[i][j]=qipan[i][j].color;
204 }
205
for (i =
1; i <=
19; i++)
206
for (j =
1; j <=
19; j++)
207 {
208
if (go[i][j]!=
2)
209 {
210 cc=go[i][j];
211 qq=str_lib(i,j,cc);
212 qipan[i][j].qs=qq;
213 }
214 }
215 }
216
217
/*
218
5、围棋的提子(吃子)
219
提子:就是把没有气的棋子从棋盘上拿掉。
220
下面函数实现提子功能。
221
*/
222
223
void chizi(
void)
224 {
225
int i,j,qq,cc;
226 suanqi();
227
for (i =
1; i <=
19; i++)
228
for (j =
1; j <=
19; j++)
229 {
230 qq=qipan[i][j].qs;
231 cc=qipan[i][j].color;
232
233
//
吴昊评述:这里,提子的同时需要满足(1)该子的气没有了(2)该子为对手的,记得国际象棋中有一个方法叫ByWho,这里同理,同时,我们没有必要当心被提掉的子会对将来正要被提掉的子构成威胁,因为,qq这个成员变量。
234
if (qq==
0 && cc!=
2 && cc!=CurrentWho)
235 {
236 qipan[i][j].color=
2;
237 qipan[i][j].x=i;
238 qipan[i][j].y=j;
239 qipan[i][j].num=
0;
240 qipan[i][j].zt=
0;
241 }
242 }
243 }
244
245
//
围棋程序设计的核心,基本完成,下面是输赢的判断问题。
246
/*
247
6、围棋胜负判断
248
围棋盘上共有三百六十一个交叉点,一盘棋的胜负就是由对局双方所占据的交叉点的多少所决定的。更精确地说就是由双方活棋所占据的地域的大小来决定的。一个交叉点为一子,每方以一百八十又二分之一子为归本数,超过此数者为胜,不足此数者为负。
249
按我国现行的围棋规则规定,由于黑棋先走,有一定的先手威力,应由执黑的一方贴出2(3/4)子。所以黑所占的地域必须超过183(1/4)子(180 (1/2)+2(3/4))才能取胜。比如黑棋数出来有185个子,即黑棋1(3/4)子。而白方的地域只要超过177(3/4)子 (180(1/2)-2(3/4))即可获胜。
250
251
252
下面函数实现计算围棋的地域功能。在计算前,应当先去掉围棋中的死子。
253
*/
254
255
//
计算围棋的地域
256
int sum[
3];
//
sum[0]=黑子数量,sum[1]=白子数量
257
258
int summ(
void)
259 {
260
int i=
0,j=
0,c=
2,k=
2;
261
//
计数白子,黑子,空白的数目
262
sum[
0]=
0;
263 sum[
1]=
0;
264 sum[
2]=
0;
265
for (i=
1;i<=
19;i++)
266 {
267
268
//
从最外层开始搜索
269
k=qipan[i][
1].color;
270
for (j=
1;j<=
19;j++)
271 {
272 c=qipan[j][i].color;
273
switch (c)
274 {
275
case
2:
276
if (k==
2) sum[
2]++;
277
else sum[k]++;
278
break;
279
case
0:
280
if (k==
0)
281 {
282 sum[c]++;
283 }
284
else
if(k==
2)
285 {
286 sum[c]=sum[c]+sum[
2]+
1;
287 k=c;
288 sum[
2]=
0;
289 }
290
else
if(k==
1)
291 {
292 sum[c]++;
293 k=c;
294 sum[
2]=
0;
295 }
296
break;
297
case
1:
298
if (k==
1)
299 {
300 sum[c]++;
301 }
302
else
if(k==
2)
303 {
304 sum[c]=sum[c]+sum[
2]+
1;
305 k=c;
306 sum[
2]=
0;
307 }
308
else
if(k==
0)
309 {
310 sum[c]++;
311 k=c;
312 sum[
2]=
0;
313 }
314
break;
315 }
316 }
317 }
318
return sum[
0];
319 }