Clever_Stone 慧石围棋程序
作者论文
顾熙杰
1)计算机围棋定式库构造算法研究
2)计算机围棋定式模式匹配算法研究
3) 计算机围棋最最基础的算法介绍
4) 围棋世界只有变式没有定式
5) 弈花围棋程序vb原代码
顾熙杰
本文章供研究计算机围棋的朋友参考,技术含量很低,但要看懂,并且应用,
还需要一定的计算机围棋设计理论基础。
一)手工输入
本软件角定式库大约1半是手工输入的,也就是150000手。
因为计算机难以自动判断形势的优劣。
而编写计算机围棋人机对战软件,必须这样做。
本软件的布局库是使用计算机技术自动生成的,从50000个专业棋手
对局库自动分析形成。
但编写角定式库的全自动构造算法太难,所以只好半自动分析。
半自动就是需要人机配合,而并不是按钮一按就睡觉了。
全自动构造算法太难,如上图,红色圆圈到底属于
左上角的定式呢?还是不是?他可能来自于其他角定式,
也可能属于边定式,
很难用计算机判断。
Type go_JDS_SJK_LX '设计库角定式库类型 FF As Long '父指针 =0表示根节点 -1表示空节点或者被删除节点 根节点父指针=-2 ZZ(1 To 40) As Long '子节点指针 保存下个应手
qq As Integer '定式分期 0,1,2 ts As Integer '定式态势 0=两分 1=黑有利 -1白有利 zx As Integer '本子坐标x zy As Integer '本子坐标y ps As Integer '定式配势点,不属于定式范围内。 0=非配 JJD As Integer '定式紧急度1=一般脱先 2=可脱先 3=不能脱先(默认)
ZS As Integer '子节点数目=下手数目 0=终端节点,定式结束 ' zd As Integer '征子条件 ' zdx As Integer ' zdy As Integer
' EX As Integer '模板最小边界要求 ' EY As Integer '模板最小边界要求 'jsj As Integer '对付电脑对手的特殊招法 sm As String '节点说明 SMEN As String '节点说明英文 ZF As String '字符显示
sbm As Long '定式识别码 yym As Long '定式引用码 ' bzm As String '新增加的摆子信息
End Type
为什么1个节点需要这么多信息,因为这是计算机下围棋模式匹配算法的需要,
否则你就用 UCT算法。
例如,定式分期????
如果不分期,那么计算机1看,定式还没有完成,就接下去下了。
本软件把这个定式的前6手分为0期定式
然后1期定式则可选择角上挡,外面逼,上面压。
然后对不同分期的定式推荐着点的评价值,乘以不同的权重。
例如0期定式 1.20
1期定式 1.10
这样计算机就不会错过脱先而选择下其他的大场了。
二)自动分析棋谱,半自动增加到定式库。
1) 分析SGF棋谱,形成棋谱树
SGF格式并不是严格的树型结构,
SGF格式中,ABC这样不分叉的,为1个树节点。
问题是,他允许黑色节点的子节点可以由同样的
着点A开始。所以说SGF格式并不是严格的树型结构。
大家用软件《玄玄围棋》打开棋谱,
可以发现,下面的图形是树支状的,可以显示整个棋谱,
但棋盘上,A点只能显示1个分支,而不能显示3个,
就是这个原因。
(但本软件的缺点是不能打开大的棋谱,这个是他的优点)
如果允许这样情况发生,定式库就不能构造为树型结构,
结果是数据大量冗余,并且不利于模式匹配的效率。
需要把AAA这3个节点合并。
但现在本软件转换算法效率比较低,不好意思公开啊。
然后八角变换到定式的设计角
For j = 1 To gnow2 x = goGO2(j).zx y = goGO2(j).zy Select Case PP_ds_mbj '注意3、7角的设计 左侧公式和右侧公式相同的是124568
Case 1 '目标角1转换到角1 x1 = x y1 = y Case 2 '目标角2转换到角1 x1 = y y1 = x Case 3 '目标角3转换到角1 可逆转换但算法非对称 左侧公式和右侧公式不相同3/7换 x1 = 20 - y y1 = x Case 4 '目标角4转换到角1 x1 = x y1 = 20 - y Case 5 '目标角5转换到角1 x1 = 20 - x y1 = 20 - y Case 6 '目标角6转换到角1 x1 = 20 - y y1 = 20 - x Case 7 '目标角7转换到角1 可逆转换但算法非对称 左侧公式和右侧公式不相同3/7换 x1 = y y1 = 20 - x Case 8 '目标角8转换到角1 x1 = 20 - x y1 = y End Select
If x1 = 20 Then x1 = 0 y1 = 0 End If
If y1 = 20 Then x1 = 0 y1 = 0 End If
goGO2(j).zx = x1 goGO2(j).zy = y1 Next j
2)棋谱树嫁接到定式树
A)
'把棋谱树当前节点所在的分支嫁接到 定式树
'包括棋谱树当前节点到棋谱根节点及子孙节点
这一模式是把棋谱分支的以前局面全部继承
也就是把红色方框的内容也做为定式的一部分。
Private Sub Command_AUTO_ADD_dqfz_Click() On Error GoTo ErrHandler '把棋谱树当前节点所在的分支嫁接到 定式树 '包括棋谱树当前节点到棋谱根节点及子孙节点
Dim QIPU(-40 To 50000) As go_csgQIPU_LX_csg Dim QIPU_tmNOW As Integer Dim QIPU_max, i, ZZ, FF, Z, findd, n As Long Dim ZS, zs2, zx, zy, xx, yy As Integer Dim DDD(1 To 10000) As Long Dim FFF(1 To 10000) As Long Dim DT, DR As Integer
Dim eee(1 To 10000) As Long Dim mmm(1 To 10000) As Long Dim et, er, jjj As Integer
If goQIPU_max = 0 Then MsgBox "请打开棋谱" Exit Sub End If
If goQIPU_tmNOW = 0 Then MsgBox "请打开棋谱" Exit Sub End If
i = MsgBox("确实要添加节点么?", vbYesNo) If i = vbNo Then Exit Sub End If
'复制棋谱副本 QIPU_max = goQIPU_max QIPU_tmNOW = goQIPU_tmNOW For i = -40 To QIPU_max QIPU(i) = goQIPU(i) Next i
ZZ = PPdqjd_ZZ '棋谱当前节点指针
'删除棋谱傍枝 保留当前分支 Do While (ZZ <> -1 * QIPU_tmNOW) '前棋谱节点向上搜索一直到根节点 FF = QIPU(ZZ).FF ZS = QIPU(FF).ZS For i = 1 To ZS Z = goQIPU(FF).ZZ(i) If Z <> ZZ Then QIPU(FF).ZZ(i) = -1000 End If Next i ZZ = FF Loop
DT = 0 DR = 0 ZS = QIPU(-1 * QIPU_tmNOW).ZS '棋谱基础第1层节点入队 For i = 1 To ZS Z = QIPU(-1 * QIPU_tmNOW).ZZ(i) If Z <> -1000 Then DR = DR + 1 '入队 DDD(DR) = Z '棋谱树节点指针 FFF(DR) = 0 '定式树当前节点指针 0=根节点 End If Next i
jjj = 0 Do While (DT < DR) DT = DT + 1 '棋谱子节点出队 ZZ = DDD(DT) '棋谱树节点指针 FF = FFF(DT) '定式树节点指针 zx = QIPU(ZZ).zx zy = QIPU(ZZ).zy
findd = 0 '判断该节点坐标是否在定式树上 ZS = PPgo_JDS_SJK(FF).ZS For i = 1 To ZS Z = PPgo_JDS_SJK(FF).ZZ(i) If Z <> -1 Then xx = PPgo_JDS_SJK(Z).zx yy = PPgo_JDS_SJK(Z).zy
If xx = zx And yy = zy Then findd = Z Exit For End If End If Next i
If findd <> 0 Then '已经存在 棋谱子节点入队,判断子孙节点情况 ZS = QIPU(ZZ).ZS For i = 1 To ZS Z = QIPU(ZZ).ZZ(i) If Z <> -1000 Then DR = DR + 1 DDD(DR) = Z '棋谱树节点指针 FFF(DR) = findd '定式树节点指针 End If Next i
Else '不存在 嫁接树枝
et = 0 er = 1 '本树枝入队 eee(er) = ZZ '棋谱树节点指针 mmm(er) = FF '定式树节点指针 Do While (et < er)
et = et + 1 '出队 ZZ = eee(et) '棋谱树节点指针 FF = mmm(et) '定式树节点指针 zx = QIPU(ZZ).zx zy = QIPU(ZZ).zy
n = new_KONG_DSK_ZZ_jds() '申请 搜索并返回定式库空数据区指针 n成为当前节点的存贮单元 If n > new_jds_max Then new_jds_max = n End If PPgo_JDS_SJK(n).FF = FF '接在父亲节点上 PPgo_JDS_SJK(n).zx = zx '本节点x坐标 PPgo_JDS_SJK(n).zy = zy '本节点y坐标 PPgo_JDS_SJK(n).qq = 0 '定式分期 0,1,2 PPgo_JDS_SJK(n).JJD = 0 '定式紧急度 1=一般脱先 2=可脱先 3=不能脱先(默认 PPgo_JDS_SJK(n).ts = 0 '定式态势 0=两分 1=黑有利 -1白有利 PPgo_JDS_SJK(n).ps = 0 '定式配势点,不属于定式范围内。 0=非配 1=配势 PPgo_JDS_SJK(n).sbm = n '识别码 PPgo_JDS_SJK(n).yym = 0 '引用码 参考同形但不同顺序形成的定式 jds_sbm(n) = True '识别码已经被使用 ZS = PPgo_JDS_SJK(FF).ZS + 1 '接在父亲树上 PPgo_JDS_SJK(FF).ZS = ZS PPgo_JDS_SJK(FF).ZZ(ZS) = n
ZS = QIPU(ZZ).ZS '棋谱子节点入队 嫁接子孙节点 For i = 1 To ZS Z = QIPU(ZZ).ZZ(i) If Z <> -1000 Then'-1000 表示空节点 er = er + 1 '入队 eee(er) = Z '棋谱树节点指针 mmm(er) = n '定式树节点指针 End If Next i
jjj = jjj + 1 '统计嫁接成功的总节点数目 Loop
End If
Loop
If jjj > 0 Then dsk_CHANGE = True '定式库有修改标志 MsgBox "add= " + CStr(jjj) End If
Exit Sub ErrHandler: '出错信息显示 MsgBox Error$ End Sub
B)
打开的棋谱如上图
应用情况如上图,只提取角部变化,忽略其他角的情况。
也就是把红色方框的内容不看成是定式的一部分。
有些棋友认为,定式应该根据全局选择,
能忽略周围情况提取1个角么?
这个你不需要考虑,就算是经典的角小目高挂托退定式,
也需要根据全局配置,也可能不利啊?
如上图
前提是定式设计局面指针要保证棋谱(局部)和定式完全匹配
'把棋谱树当前节点的子节点嫁接到 定式树当前节点下面
'包括棋谱树当前节点的子孙节点
'不包括棋谱树当前节点到棋谱根节点及节点本身
Private Sub Command_AUTO_ADD_dqzjd_Click() '把棋谱树当前节点的子节点嫁接到 定式树当前节点下面 '包括棋谱树当前节点的子孙节点 '不包括棋谱树当前节点到棋谱根节点及节点本身 Dim QIPU(-40 To 50000) As go_csgQIPU_LX_csg Dim QIPU_tmNOW As Integer Dim QIPU_max, i, ZZ, FF, Z, findd, n As Long Dim ZS, zs2, zx, zy, xx, yy As Integer Dim DDD(1 To 10000) As Long Dim FFF(1 To 10000) As Long Dim DT, DR As Integer
Dim eee(1 To 10000) As Long Dim mmm(1 To 10000) As Long Dim et, er, jjj As Integer
If goQIPU_max = 0 Then MsgBox "请打开棋谱" Exit Sub End If
If goQIPU_tmNOW = 0 Then MsgBox "请打开棋谱" Exit Sub End If
If dqjd_ZZ = -1 Then MsgBox "定式当前节点没有被记录!" Exit Sub End If
If dqjd_ZZ = 0 Then MsgBox "定式当前节点为根节点!" Exit Sub End If
ZZ = PPdqjd_ZZ '棋谱当前节点指针 If goQIPU(ZZ).ZS = 0 Then MsgBox "棋谱当前节点无子节点" Exit Sub End If
Text_fzdqzjddao.Text = CStr(dqjd_ZZ)
i = MsgBox("确实要添加节点么?", vbYesNo) If i = vbNo Then Exit Sub End If
'复制棋谱副本 QIPU_max = goQIPU_max QIPU_tmNOW = goQIPU_tmNOW For i = -40 To QIPU_max QIPU(i) = goQIPU(i) Next i
DT = 0 DR = 0 ZS = QIPU(ZZ).ZS '棋谱当前节点下面第1层节点入队 For i = 1 To ZS Z = QIPU(ZZ).ZZ(i) If Z <> -1000 Then DR = DR + 1 '入队 DDD(DR) = Z '棋谱树节点指针 FFF(DR) = dqjd_ZZ '定式树当前节点指针 End If Next i
jjj = 0 Do While (DT < DR) DT = DT + 1 '棋谱子节点出队 ZZ = DDD(DT) '棋谱树节点指针 FF = FFF(DT) '定式树节点指针 zx = QIPU(ZZ).zx zy = QIPU(ZZ).zy
findd = 0 '判断该节点坐标是否在定式树上 ZS = PPgo_JDS_SJK(FF).ZS For i = 1 To ZS Z = PPgo_JDS_SJK(FF).ZZ(i) If Z <> -1 Then xx = PPgo_JDS_SJK(Z).zx yy = PPgo_JDS_SJK(Z).zy
If xx = zx And yy = zy Then findd = Z Exit For End If End If Next i
If findd <> 0 Then '已经存在 棋谱子节点入队,判断子孙节点情况 ZS = QIPU(ZZ).ZS For i = 1 To ZS Z = QIPU(ZZ).ZZ(i) If Z <> -1000 Then DR = DR + 1 DDD(DR) = Z '棋谱树节点指针 FFF(DR) = findd '定式树节点指针 End If Next i
Else '不存在 嫁接树枝
et = 0 er = 1 '本树枝入队 eee(er) = ZZ '棋谱树节点指针 mmm(er) = FF '定式树节点指针 Do While (et < er)
et = et + 1 '出队 ZZ = eee(et) '棋谱树节点指针 FF = mmm(et) '定式树节点指针 zx = QIPU(ZZ).zx zy = QIPU(ZZ).zy
n = new_KONG_DSK_ZZ_jds() '申请 搜索并返回定式库空数据区指针 n成为当前节点的存贮单元 If n > new_jds_max Then new_jds_max = n End If PPgo_JDS_SJK(n).FF = FF '接在父亲节点上 PPgo_JDS_SJK(n).zx = zx '本节点x坐标 PPgo_JDS_SJK(n).zy = zy '本节点y坐标 PPgo_JDS_SJK(n).qq = 0 '定式分期 0,1,2 PPgo_JDS_SJK(n).JJD = 0 '定式紧急度 1=一般脱先 2=可脱先 3=不能脱先(默认 PPgo_JDS_SJK(n).ts = 0 '定式态势 0=两分 1=黑有利 -1白有利 PPgo_JDS_SJK(n).ps = 0 '定式配势点,不属于定式范围内。 0=非配 1=配势 PPgo_JDS_SJK(n).sbm = n '识别码 PPgo_JDS_SJK(n).yym = 0 '引用码 参考同形但不同顺序形成的定式 jds_sbm(n) = True '识别码已经被使用 ZS = PPgo_JDS_SJK(FF).ZS + 1 '接在父亲树上 PPgo_JDS_SJK(FF).ZS = ZS PPgo_JDS_SJK(FF).ZZ(ZS) = n
ZS = QIPU(ZZ).ZS '棋谱子节点入队 嫁接子孙节点 For i = 1 To ZS Z = QIPU(ZZ).ZZ(i) If Z <> -1000 Then '-1000 表示空节点 er = er + 1 '入队 eee(er) = Z '棋谱树节点指针 mmm(er) = n '定式树节点指针 End If Next i
jjj = jjj + 1 '统计嫁接成功的总节点数目 Loop
End If
Loop
If jjj > 0 Then dsk_CHANGE = True '定式库有修改标志 MsgBox "add= " + CStr(jjj) End If
Exit Sub ErrHandler: '出错信息显示 MsgBox Error$ End Sub
顾熙杰
本文章供研究计算机围棋的朋友参考,技术含量很低,但要看懂,并且应用,
还需要一定的计算机围棋设计理论基础。
一)常见的算法
1)手序匹配 先小目后高挂/ 先高目后小目挂 被认为是2个不同的定式,这样的设计学定式可以,计算机对战不行。
2)图形匹配
方法1,如上图,1行1行压缩编码,成为字符串。
0=空 1=黑 2=白 成为0001202020100020000100020201这样的字符串。
如果10*10,则100个字符组成1个定式局面,
当然了,还需要设计推荐点信息,如0404表示下一手推荐星位,0403表示下一手推荐小目等等。
然后把定式匹配问题转化为字符串匹配问题。
方法2,如上图,从角顶点开始,1圈1圈向外压缩编码,成为字符串。
本方法比方法1好,可以实现局部小模板匹配,例如 8*8,7*7,小正方形模板匹配。
只要比较局面字符串前面部分和定式前面部分。
缺点:没有办法实现本软件的长方形可变模板匹配。
二)本软件的方法
把定式如上9个点使用前面的方法压缩编码为字符串。称为特征向量。
先判断当前局面的特征向量 和定式库特征向量是否匹配,
如果匹配,其他点则一一比较。
也就是说,本软件部分继承了上面的算法,但做了些试探性改进。
缺点是速度慢,优点是算法灵活,进一步改进的空间大。
定式运行库由 向量库和定式库组成,
这样的算法相当于分块查找算法,部分克服了逐点比较速度慢的缺点。
本算法在p4电脑 512m内存,50000手定式库,8个角(4个角)全部
匹配1次,使用时间为1毫秒,基本满足专家系统的需要,
但不能使用在UCT系统,速度太慢。
本算法的优点,可变形模板,
19*19。 则是布局匹配,当然这时候要提取4个角的特征向量。
19*(10-19)则是半局匹配,当然这时候要提取2个角的特征向量。
这样设计可以提高布局库的使用效率。
仅局面一部分匹配就可以了。
定式模板从15*15到 6*6,使用长方形,而不一定是正方形模板。
例如:
上图是本软件定式库没有的(因为多了圆圈1手),但还是能走出点33,托等下法,
因为6*6范围还是匹配的。
本人把6*6=36 15*15= 称为匹配度,匹配度大的,可信度高,匹配度小的,还需要其他算法配合验证评价。
这样设计的另1个优点是,可以实现模糊匹配,
也就是有1-2点不匹配,检查该1-2点的位置等信息,判断是否可以忽略。当然匹配度得降低。
这样设计的另1个优点是,根据需要可增加附加模板,例如对开拆点等。
这样本软件实际使用时候的模板可以如下图。
如上图,由于中间3个子,13*13模板无法匹配成功,
这时候计算机试图用小模板 13+12。12*13匹配,还无法成功,
到9*7,匹配成功,但推荐点位于外侧,起用附加模板。
匹配成功。
红色长方形=主模板
兰色长方形=附加模板
本算法还可以改进为更复杂的模板形式。
例如:推荐点周围6*6全匹配,其他位置使用
辐射函数得到影响评价,进行模糊匹配。
这样实际上实现了边定式(根据角定式库或者布局库),而不需要专门设计 边定式库。
例如:
和下面的图
是匹配的,都是立2拆3边定式,因为下面的2个白子在势上和上面的2个白子是相同的。
还可以从角定式库,布局库自动生成边定式,边模式,5*5模式等等。
本人软件用 1表示黑 -1表示白 所以*-1为黑白转换(同时也是攻防转换)。
Public Sub TJQ_Joseki_MFQ_out_jiao(ByVal wk As Long, ByVal meHB As Long, ByVal jiao As Long, ByVal MAX_kzd As Long, ByVal MINI_kzd As Long) '角定式模仿器角 Dim dsk_II, i, j, k As Long Dim next_TJS, nnnS, findd As Long Dim zx, zy As Long Dim Qx, Qy As Long Dim cccc, qqqq, psps, tsts As Long Dim T_kzd_x, T_kzd_Y As Long Dim JJ, kk As Long Dim dsk_MAX, dsk_INDEX As Long Dim GF, GFs, GFe, GFstep As Long Dim ppQP(1 To 15, 1 To 15) As Long Dim TZma, tt As String Dim TZs, TZe As Long Dim xcd, ycd, ss As Long
Dim DS, DE, DMAX, DH(1 To 2000) As Long
'以有限状态自动机理论为基础的模式匹配算法 '关键参数 'MAX_kzd 最大匹配控制度边界 一般设置为9-11 'mini_KZD 最小控制匹配度边界 一般设置为8-6
Call MBJIAO_TO_jiao1(jiao, 11) '目标角转换到角1进行匹配 结果需要逆向转换(见上一论文的8角变换公式)
'命中概率大的优先测试 If jiao_PPS_lszh_sj(jiao) < jiao_PPS_lszh_gj(jiao) Then '历史上守角方匹配成功次数< 历史上挂角方匹配成功次数 GFs = 1 '先进行挂角测试 GFe = 0 GFstep = -1 Else GFs = 0 '先进行守角测试 GFe = 1 GFstep = 1 End If
For GF = GFs To GFe Step GFstep
Select Case GF Case 0 '我方守角攻防******实现守角功能 * meHB进行黑白转换 For i = 1 To 11 For j = 1 To 11 ppQP(i, j) = meHB * dsJ1_DSgoXY(i, j) Next j Next i Case 1 '敌人守角攻防*******实现挂角的功能 -1 * 进行攻防转换 For i = 1 To 11 For j = 1 To 11 ppQP(i, j) = -1 * meHB * dsJ1_DSgoXY(i, j) Next j Next i End Select
TZma = "" '角1的特征向量 For i = 3 To 5 For j = 3 To 5 If ppQP(i, j) = -1 Then tt = "2" Else tt = CStr(ppQP(i, j)) End If TZma = TZma + tt Next j Next i
'根据特征向量查找索引表 '特征码匹配查找阶段 相当于分段分块查找算法 TZs = 0 For i = 1 To PPgo_JDS_index_max(GF)
If PPgo_JDS_index(GF, i).TZ = TZma Then '特征码匹配成功 TZs = PPgo_JDS_index(GF, i).dhs '该特征的定式索引开始位置 TZe = TZs + PPgo_JDS_index(GF, i).sm - 1 '该特征的定式索引结束位置 Exit For End If
Next i
'不存在符合当前特征的定式 If TZs = 0 Then GoTo next_GF: End If
'优先使敌人前手匹配的先匹配------------------------------- '解决这个问题: 如果局面完全相同而次序不同,能导致 qx,qy的判断失去效果! DMAX = TZe - TZs + 1 DS = 1 DE = DMAX
If PP_dQX = 0 Then '前手敌人PASS
For dsk_INDEX = TZs To TZe dsk_II = PPgo_jdsdh(dsk_INDEX) DH(DS) = dsk_II DS = DS + 1 Next dsk_INDEX DS = 1 DE = DMAX
Else
For dsk_INDEX = TZs To TZe dsk_II = PPgo_jdsdh(dsk_INDEX) Qx = PPgo_JDS_YXK(dsk_II).Qx Qy = PPgo_JDS_YXK(dsk_II).Qy
If Qx = md_QX And Qy = md_QY Then '从上往下 敌人前手匹配的 DH(DS) = dsk_II DS = DS + 1 Else DH(DE) = dsk_II '从下往上 敌人前手不匹配的 DE = DE - 1 End If
Next dsk_INDEX DS = 1 DE = DMAX
End If
'使用可变形的控制模板----------------------- nnnS = 0
For T_kzd_x = MAX_kzd To MINI_kzd Step -1 '控制模板的X边界 For T_kzd_Y = MAX_kzd To MINI_kzd Step -1 '控制模板的y边界
BIG_INDEX_max = 0 '和当前特征初步匹配的大角定式数目
For dsk_INDEX = DS To DE '扫描正个定式库中 特征码符合当前特征的定式
dsk_II = DH(dsk_INDEX) '根据特征向量查找定式库索引号 加快查找速度
If PPgo_JDS_YXK(dsk_II).big = 1 Then BIG_INDEX_max = BIG_INDEX_max + 1 '和当前特征初步匹配的大角定式数目 BIG_INDEX_dh(BIG_INDEX_max) = dsk_II '和当前特征初步匹配的大角定式代号 GoTo next_INDEX: End If
For j = 1 To T_kzd_x For k = 1 To T_kzd_Y If ppQP(j, k) <> PPgo_JDS_YXK(dsk_II).QPxy(j, k) Then GoTo next_INDEX: '发现不匹配 End If Next k Next j
Qx = PPgo_JDS_YXK(dsk_II).Qx '前手坐标(相对于待匹配的下一手) Qy = PPgo_JDS_YXK(dsk_II).Qy '紧急角定式推荐点使用该信息
If Qx > T_kzd_x Or Qy > T_kzd_Y Then '敌人前手坐标位于定式模扳外侧 取消紧急状态 Qx = 0 Qy = 0 End If
next_TJS = PPgo_JDS_YXK(dsk_II).ZS '下一手匹配的推荐数目
For j = 1 To next_TJS '扫描下一全部应手
zx = PPgo_JDS_YXK(dsk_II).ZZ(j).zx zy = PPgo_JDS_YXK(dsk_II).ZZ(j).zy
If zx = 0 Then '0=pass 不属于定式范围内(但构造定式树) 取消该推荐 GoTo next_TJ: End If
cccc = PPgo_JDS_YXK(dsk_II).ZZcc(j) '当前推荐ZX ZY手 位于定式库的指针
psps = PPgo_JDS_YXK(cccc).ps ' 定式配势点, 0=非配 1=配势 配势点不属于定式范围内(但构造定式树)
If psps = 1 Then '配势点不属于定式本身 取消该推荐 GoTo next_TJ: End If
If zx >= T_kzd_x And zy >= T_kzd_Y Then '推荐点完全位于定式模扳外侧 取消该推荐 GoTo next_TJ: End If
If zx >= T_kzd_x Then '推荐点x位于定式模扳外侧,加大X侧的模扳长度 For JJ = T_kzd_x + 1 To zx + set_J_FUJ_KZD For kk = 1 To zy + 2 If ppQP(JJ, kk) <> PPgo_JDS_YXK(dsk_II).QPxy(JJ, kk) Then GoTo next_TJ: '发现不匹配 End If Next kk Next JJ ElseIf zy >= T_kzd_Y Then '推荐点y位于定式模扳外侧,加大y侧的模扳长度 For JJ = 1 To zx + 2 For kk = T_kzd_Y + 1 To zy + set_J_FUJ_KZD If ppQP(JJ, kk) <> PPgo_JDS_YXK(dsk_II).QPxy(JJ, kk) Then GoTo next_TJ: '发现不匹配 End If Next kk Next JJ End If
'保存匹配的下一手信息,供进一步分析使用 qqqq = PPgo_JDS_YXK(cccc).qq '定式分期 0,1,2 tsts = PPgo_JDS_YXK(cccc).ts '定式态势 0=两分 1=黑有利 -1白有利 xcd = PPgo_JDS_YXK(cccc).xcd '开拆点 ycd = PPgo_JDS_YXK(cccc).ycd '开拆点
nnnS = nnnS + 1 jiao_cb1ppZZ(jiao, nnnS).zx = zx '需要逆向转换的数据 jiao_cb1ppZZ(jiao, nnnS).zy = zy
'下一手信息,供进一步分析使用 jiao_cb1ppZZ(jiao, nnnS).qq = qqqq '定式分期 0,1,2
jiao_cb1ppZZ(jiao, nnnS).xcd = xcd '开拆点 jiao_cb1ppZZ(jiao, nnnS).ycd = ycd '开拆点
If GF = 0 Then jiao_cb1ppZZ(jiao, nnnS).ts = tsts '守角方同色 定式态势 0=两分 1=黑有利 -1白有利 ElseIf GF = 1 Then jiao_cb1ppZZ(jiao, nnnS).ts = -1 * tsts '守角方同色 挂角方异色 定式态势 0=两分 1=黑有利 -1白有利 End If
jiao_cb1ppZZ(jiao, nnnS).ppD = T_kzd_x * T_kzd_Y '匹配度 jiao_cb1ppZZ(jiao, nnnS).Qx = Qx '前手坐标(相对于待匹配的下一手) jiao_cb1ppZZ(jiao, nnnS).Qy = Qy '紧急角定式推荐点使用该信息
next_TJ: Next j
If nnnS > 0 Then '发现有匹配 GoTo next_OVEE_WORK: End If
next_INDEX: Next dsk_INDEX '扫描正个定式库 Next T_kzd_Y '控制模板的y边界 Next T_kzd_x '控制模板的X边界
'-------------------------------------------------------------------------------- next_OVEE_WORK:
jiao_PPS(jiao) = nnnS '角匹配数目
'对模版要求为大角的进行大角匹配算法 If BIG_INDEX_max > 0 Then Call TJQ_Joseki_big_out_jiao(wk, meHB, jiao, GF) End If
'连同大角匹配算法一起推荐 If jiao_PPS(jiao) > 0 Then '发现有匹配 If GF = 0 Then jiao_PPS_sj(jiao) = jiao_PPS(jiao) '守角方匹配成功次数 ElseIf GF = 1 Then jiao_PPS_gj(jiao) = jiao_PPS(jiao) '挂角方匹配成功次数 End If Exit For '退出扫描算法 End If
next_GF: Next GF
'对开拆点调整位置 For i = 1 To jiao_PPS(jiao)
jiao_cb1ppZZ(jiao, i).TZ = 0
If jiao_cb1ppZZ(jiao, i).xcd = 1 Then '开拆点 zx = jiao_cb1ppZZ(jiao, i).zx zy = jiao_cb1ppZZ(jiao, i).zy
findd = 0 '扫描右侧 For j = zx To zx + 1 For k = 1 To 6 If ppQP(j, k) <> 0 Then findd = 1 Exit For End If Next k If findd = 1 Then Exit For Next j
If findd = 1 Then ss = zx - 1 '右侧非空,回退1路 Else ss = zx End If
findd = 0 '扫描左侧 For j = ss - 1 To ss For k = 1 To 6 If ppQP(j, k) <> 0 Then findd = 1 Exit For End If Next k If findd = 1 Then Exit For Next j
If findd = 1 Then '左侧非空 jiao_cb1ppZZ(jiao, i).ppD = -1 '连拆1也没有,取消该点的推荐 Else jiao_cb1ppZZ(jiao, i).TZ = 1 jiao_cb1ppZZ(jiao, i).zx = ss End If
ElseIf jiao_cb1ppZZ(jiao, i).ycd = 1 Then zx = jiao_cb1ppZZ(jiao, i).zx zy = jiao_cb1ppZZ(jiao, i).zy
findd = 0 For j = 1 To 6 '扫描下侧 For k = zy To zy + 1 If ppQP(j, k) <> 0 Then findd = 1 Exit For End If Next k If findd = 1 Then Exit For Next j
If findd = 1 Then ss = zy - 1 '下侧非空,回退1路 Else ss = zy End If
findd = 0 For j = 1 To 6 '扫描上侧 For k = ss - 1 To ss If ppQP(j, k) <> 0 Then findd = 1 Exit For End If Next k If findd = 1 Then Exit For Next j
If findd = 1 Then '上侧非空 jiao_cb1ppZZ(jiao, i).ppD = -1 '连拆1也没有,取消该点的推荐 Else jiao_cb1ppZZ(jiao, i).TZ = 1 jiao_cb1ppZZ(jiao, i).zy = ss End If
End If
Next i
End Sub
顾熙杰
泰山(陈志行教授,中山大学)崩了以后,中国的电脑围棋开始落后于世界了,差距会越来越大,原因同足球,凡是2个人以上的项目,中国都不行,现在的电脑围棋需要小组合作开发了,1个人,不管使用什么算法,都不可能战胜专业棋手。
只有沿着陈志行教授的专家系统和uct,MC 算法2条大路同时前进,不断改进,才可能成功。这个1个人明显是无法完成的。
1)棋盘和棋子的表示
棋盘
goxy(0 to 20,0 to 20),为什么不是1-19呢,这个为了方便算气,0和20表示棋盘边,初始化=2,始终不变。
goxy(x,y)=1 表示有黑子,
goxy(x,y)=-1 表示有白子,
goxy(x,y)=0 表示没有子,
网络上有说法
goxy(x,y)=1 表示有黑子,
goxy(x,y)=2 表示有白子,
goxy(x,y)=0 表示没有子,
这个也是可以的。
但本人的方法有利于黑白变换,-1*就表示黑白变换,省下一大堆编码,特别是计算机对战程序.
学习软件么,上面2中方法差别不大。
什么位(bit)棋盘什么的,是内存很小时候的方法,很麻烦。
落子
(zx,zy,zhb,zxx) 开始设计的时候不要管zxx,这个记录棋谱显示的文字用的。
ZX=坐标
ZY=坐标
ZHB 1表示下黑子 -1表示下白子
这个是基本的。
扩展的 -2表示删除棋子 2表示该节点没有棋子,只有信息文字 0表示PASS。
本软件ZX=0 ZY=0 ZHB=0 表示PASS。当然应该zhb=1表示黑PASS zhb=-1表示白PASS,本软件不区分谁PASS。
本软件是基于轮流落子设计的,这个是个问题。当黑子连下的时候,需要插入白PASS,这个是惨痛教训,
修改数据结构还要修改数据库,修改怕出现错误!因为当时计划设计成计算机对战程序,根本没有想到教学
应用。
本软件本来只有(ZX,ZY)没有ZHB,轮流落子,不支持删除棋子。 教训大家一定要吸取,就算你是计算机对战程序,
设计专家系统的时候,要利用现有的SGF资源自动提取数据,也会碰到麻烦。
2)棋串的表示 (关键在建立串子指针和子串指针)
3)画棋盘和棋子
4)鼠标落子
5)下子
6)禁着点判断
具体请参考本人2000年作品弈花围棋程序vb原代码
本软件的一段代码,看懂看不懂,看看。
为什么 ByVal wk As Integer,因为搜索程序(人机对战)需要,如果打谱什么的,根本不需要
Sub PPgo_zxzy2(ByVal wk As Integer, ByVal zx As Integer, ByVal zy As Integer, ByVal zhb As Integer) '下子程序'内存下子数据改变模块 核心模块
'主界面输入输出模块使用 根据规则可能允许块子自杀
Dim i, J As Integer Dim QS As Integer Dim CH, ch2 As Integer Dim ZS As Integer Dim XX, YY As Integer Dim CHB As Integer Dim kc As Integer Dim dqc As Integer Dim oldzs As Integer Dim FINDD As Integer Dim mm, k As Integer Dim ccc, hhh(1 To 4) As Integer Dim kz, old_zz, old_yz, new_zz, new_yz As Integer Dim cc As Integer Dim ypdCQ(1 To 150) As Integer '避免重复计算串气 Dim TSC(1 To 150) As Integer '避免重复串合并 Dim bwc As GO_bwc_LX
PP_can_sikao = False '计算机可以开始思考标志 防止时序数据不同步产生错误 pptz_NOW = 0 '当前手提子数 PPgo_NOW(wk) = PPgo_NOW(wk) + 1 '当前第几手 PPgoGO(wk, PPgo_NOW(wk)).zx = zx '记录落子循序 记谱使用 PPgoGO(wk, PPgo_NOW(wk)).zy = zy PPgoGO(wk, PPgo_NOW(wk)).hb = zhb
If zhb = 2 Then '只有信息 Exit Sub End If
If zhb = 0 Then '没有棋子 Exit Sub End If
If zhb = -2 Then '删除棋子 PPgoXY(wk, zx, zy).hb = 0 Call PP_redo_chuan(wk) '扫描棋盘重新建立棋串信息 Exit Sub End If
If zx <= 0 Or zy <= 0 Then zx = 0 zy = 0 End If
If zx >= 20 Or zy >= 20 Then zx = 0 zy = 0 End If
If zx = 0 Or zy = 0 Then 'pass GoTo NEXTDO: End If
'同色串合并---左边 右边 上边 下边 ,------------------------------------------------------------------------- ccc = 0
'搜索傍边的同色串
If PPgoXY(wk, zx - 1, zy).hb = zhb Then kc = PPgoXY(wk, zx - 1, zy).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'搜索傍边的同色串
If PPgoXY(wk, zx + 1, zy).hb = zhb Then kc = PPgoXY(wk, zx + 1, zy).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'搜索傍边的同色串
If PPgoXY(wk, zx, zy - 1).hb = zhb Then kc = PPgoXY(wk, zx, zy - 1).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'搜索傍边的同色串
If PPgoXY(wk, zx, zy + 1).hb = zhb Then kc = PPgoXY(wk, zx, zy + 1).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'-------------------------------------------------------
kz = 0 '申请存储单元 搜索空子保存新子的数据 For i = 1 To 361 If PPgo_chuan_zz(wk, i).zx = 0 Then kz = i Exit For End If Next i
'-------------------------------------------------------
If ccc = 0 Then '没有傍边的同色串,创立新串 kc = 0 For i = 1 To c_CHan_max '申请存储单元 搜索空串保存数据 If PPgo_chuan(wk, i).ZS = 0 Then kc = i Exit For End If Next i
'建立串子指针 PPgo_chuan(wk, kc).ZS = 1 PPgo_chuan(wk, kc).hb = zhb PPgo_chuan(wk, kc).zz = kz '长子指针 PPgo_chuan(wk, kc).YZ = kz '幼子指针
'建立新子存储单位 PPgo_chuan_zz(wk, kz).zx = zx PPgo_chuan_zz(wk, kz).zy = zy PPgo_chuan_zz(wk, kz).Znext = 0
'建立子串指针 PPgoXY(wk, zx, zy).hb = zhb PPgoXY(wk, zx, zy).CH = kc dqc = kc '当前新建立的串 Else '有傍边的同色串,进行串合并
'------------------------------------------------------- '串合并 kc = hhh(1) old_zz = PPgo_chuan(wk, kc).zz '长子指针 old_yz = PPgo_chuan(wk, kc).YZ '幼子指针 cc = old_yz '第1个串的幼子指针 For i = 2 To ccc '旧串合并 dqc = hhh(i) new_zz = PPgo_chuan(wk, dqc).zz '长子指针 new_yz = PPgo_chuan(wk, dqc).YZ '幼子指针 PPgo_chuan_zz(wk, old_yz).Znext = new_zz old_yz = new_yz '幼子指针向后面串移动 PPgo_chuan(wk, dqc).ZS = 0 '释放一个旧串存储单元 Next i
'新子串加入合并-------------------------------------------------------
PPgo_chuan(wk, kc).YZ = kz '幼子指针 PPgo_chuan_zz(wk, old_yz).Znext = kz '新子连接在旧串后面
'建立新子存储单位 PPgo_chuan_zz(wk, kz).zx = zx PPgo_chuan_zz(wk, kz).zy = zy PPgo_chuan_zz(wk, kz).Znext = 0
'建立子黑白 PPgoXY(wk, zx, zy).hb = zhb
dqc = kc '当前新合并的串
'---------------------------------------------------------- Do '修改合并串的子串指针 zx = PPgo_chuan_zz(wk, cc).zx zy = PPgo_chuan_zz(wk, cc).zy PPgoXY(wk, zx, zy).CH = dqc cc = PPgo_chuan_zz(wk, cc).Znext Loop While (cc <> 0)
End If
Dim findd0, findd1 As Integer
'重新计算周围串的气,左边 右边 上边 下边 ,如果气=0 杀敌串-------------------------------------------------------------------------- findd0 = 0 findd1 = 0
If PPgoXY(wk, zx - 1, zy).hb = -zhb Then CH = PPgoXY(wk, zx - 1, zy).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(wk, CH) '判断下子后敌人临串的气 If QS = 0 Then bwc = PPgo_bwcDH(wk, CH) '求包围串代号 Call ppgo_kill_chuan(wk, CH) '杀敌串 For i = 1 To bwc.cs ch2 = bwc.CH(i) Call PPgo_chuanqi(wk, ch2) '重新计算包围串的气 Next i findd0 = 1 ElseIf QS = 1 Then findd1 = 1 End If ypdCQ(CH) = 1 '标记该串气已判断 End If End If
If PPgoXY(wk, zx + 1, zy).hb = -zhb Then CH = PPgoXY(wk, zx + 1, zy).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(wk, CH) '判断下子后敌人临串的气 If QS = 0 Then bwc = PPgo_bwcDH(wk, CH) '求包围串代号 Call ppgo_kill_chuan(wk, CH) '杀敌串 For i = 1 To bwc.cs ch2 = bwc.CH(i) Call PPgo_chuanqi(wk, ch2) '重新计算包围串的气 Next i findd0 = 1 ElseIf QS = 1 Then findd1 = 1 End If
ypdCQ(CH) = 1 '标记该串气已判断 End If End If
If PPgoXY(wk, zx, zy - 1).hb = -zhb Then CH = PPgoXY(wk, zx, zy - 1).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(wk, CH) '判断下子后敌人临串的气 If QS = 0 Then bwc = PPgo_bwcDH(wk, CH) '求包围串代号 Call ppgo_kill_chuan(wk, CH) '杀敌串 For i = 1 To bwc.cs ch2 = bwc.CH(i) Call PPgo_chuanqi(wk, ch2) '重新计算包围串的气 Next i findd0 = 1 ElseIf QS = 1 Then findd1 = 1 End If ypdCQ(CH) = 1 '标记该串气已判断 End If End If
If PPgoXY(wk, zx, zy + 1).hb = -zhb Then CH = PPgoXY(wk, zx, zy + 1).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(wk, CH) '判断下子后敌人临串的气 If QS = 0 Then bwc = PPgo_bwcDH(wk, CH) '求包围串代号 Call ppgo_kill_chuan(wk, CH) '杀敌串 For i = 1 To bwc.cs ch2 = bwc.CH(i) Call PPgo_chuanqi(wk, ch2) '重新计算包围串的气 Next i findd0 = 1 ElseIf QS = 1 Then findd1 = 1 End If ypdCQ(CH) = 1 '标记该串气已判断 End If End If
ppGO_atari = 0 If findd0 = 0 And findd1 = 1 Then ppGO_atari = 1 End If
'本新着子串--------------------------------------------------------------------------
QS = PPgo_chuanqi(wk, dqc) '计算新下子串气数目 If QS = 0 Then bwc = PPgo_bwcDH(wk, dqc) '求包围串代号 Call ppgo_kill_chuan(wk, dqc) '合法自杀=应氏规则 For i = 1 To bwc.cs ch2 = bwc.CH(i) Call PPgo_chuanqi(wk, ch2) '重新计算包围串的气 Next i End If
'--------------------------------------------------------------------------
NEXTDO: Call PPgo_jilu_daoshu(wk, PPgo_NOW(wk)) '记录倒数10手的棋型,劫禁判断使用使用 能判断 单劫 3-4劫循环
'标记热子 '标记下一步的劫禁着点 只能判断单劫 因为有可能发送到思考区,而思考区使用简单判断法
If zx = 0 Then '当前手pass PPgo_jjzd(wk).zx = 0 '当前手不产生下着的禁着点 PPgo_jjzd(wk).zy = 0 Exit Sub End If
If pptz_NOW <> 1 Then '当前手不是提了1个子 PPgo_jjzd(wk).zx = 0 '当前手不产生下着的禁着点 PPgo_jjzd(wk).zy = 0 Exit Sub End If
If QS <> 1 Then '当前手不是建立了1口气的串 PPgo_jjzd(wk).zx = 0 '当前手不产生下着的禁着点 PPgo_jjzd(wk).zy = 0 Exit Sub End If
ZS = PPgo_chuan(wk, dqc).ZS If ZS <> 1 Then '当前手不是建立了1个子的串 PPgo_jjzd(wk).zx = 0 '当前手不产生下着的禁着点 PPgo_jjzd(wk).zy = 0 Exit Sub End If
PPgo_jjzd(wk).zx = PPgo_chuan(wk, dqc).QDZXY(1).zx '标记下一步的劫禁着点=建立了1口气的串的气点 PPgo_jjzd(wk).zy = PPgo_chuan(wk, dqc).QDZXY(1).zy
End Sub
Function PPgo_chuanqi(ByVal wk As Integer, ByVal ccc As Integer) As Integer
'计算气数目和气点坐标 子数
Dim cc As Integer Dim i, J As Integer Dim XX, YY As Integer Dim QQQ, zzz As Integer Dim Q(0 To 20, 0 To 20) As Integer Dim QD(1 To 100) As GO_ZXY_TYPE
cc = PPgo_chuan(wk, ccc).zz '长子指针
zzz = 0 QQQ = 0 Do
XX = PPgo_chuan_zz(wk, cc).zx YY = PPgo_chuan_zz(wk, cc).zy
If PPgoXY(wk, XX - 1, YY).hb = 0 Then '左边空位 If Q(XX - 1, YY) = 0 Then '如果该点没有算过气 QQQ = QQQ + 1 Q(XX - 1, YY) = 1 '标记该点已经算过气 QD(QQQ).zx = XX - 1 '气点坐标 QD(QQQ).zy = YY End If End If
If PPgoXY(wk, XX + 1, YY).hb = 0 Then '右边空位 If Q(XX + 1, YY) = 0 Then '如果该点没有算过气 QQQ = QQQ + 1 Q(XX + 1, YY) = 1 '标记该点已经算过气 QD(QQQ).zx = XX + 1 '气点坐标 QD(QQQ).zy = YY End If End If
If PPgoXY(wk, XX, YY - 1).hb = 0 Then '上边空位 If Q(XX, YY - 1) = 0 Then '如果该点没有算过气 QQQ = QQQ + 1 Q(XX, YY - 1) = 1 '标记该点已经算过气 QD(QQQ).zx = XX '气点坐标 QD(QQQ).zy = YY - 1 End If End If
If PPgoXY(wk, XX, YY + 1).hb = 0 Then '下边空位 If Q(XX, YY + 1) = 0 Then '如果该点没有算过气 QQQ = QQQ + 1 Q(XX, YY + 1) = 1 '标记该点已经算过气 QD(QQQ).zx = XX '气点坐标 QD(QQQ).zy = YY + 1 End If End If
zzz = zzz + 1 cc = PPgo_chuan_zz(wk, cc).Znext
Loop While (cc <> 0)
PPgo_chuanqi = QQQ '返回气数目 PPgo_chuan(wk, ccc).ZS = zzz '子数 PPgo_chuan(wk, ccc).QS = QQQ '串的气数目
If QQQ > 5 Then '由于搜索算法限制,最多返回5个气点坐标 ,这个对打谱没有用的 QQQ = 5 End If
For i = 1 To QQQ PPgo_chuan(wk, ccc).QDZXY(i) = QD(i) '返回气点坐标 Next i
End Function
网络上可看到递归算法算气的,代码很简单,但效率低下,本软件尽量不使用递归算法,
实在搞不清楚,才使用递归。
大部分使用循环,对列,栈来实现。递归算法算气请参考
其中算气的一段实际上是本人10年前(2000)在
smiling小组发表的C语言代码,看上去和本人写的一模一样。其中需要改进的地方是棋盘边应该
使用特殊标记,
这样就不用判断
if(x+1)<=19 then不需要了
if(x-1)>=1 then不需要了
if(y+1)<=19 then不需要了
if(y-1)>=1 then不需要了
怎样表示棋盘边呢?
for i=0 to 20
GOXY(0,i)=2
GOXY(20,i)=2
GOXY(i,0)=2
GOXY(i,20)=2
next i
当然现在用VB表示,学C的应该很容易看懂的,注意了这里2表示非空,如果0=黑 1=白 2=空,那么设置为3就可了,
这里的代码是 1=黑 -1=白 0=空。
本人大学自考C语言考了96分,做书上的题目还可以,但编写围棋程序,老是出错,没有办法,改行VB了。
现在想起是错误的选择,人机对战,VB很难编写。不过用VB编写教学软件实在很方便。
网络上有一大堆中小学灭火机器人的C代码,是本人写的。
禁着点判断法则
Function PPgo_jzdPD2(ByVal wk As Integer, ByVal zx As Integer, ByVal zy As Integer, ByVal zhb As Integer) As Integer '禁止着点判断函数 '核心模块
'主界面输入输出模块使用 能判断3-4劫循环 根据规则可能允许块子自杀
Dim i, J As Integer Dim QS As Integer Dim CH As Integer Dim ZS As Integer Dim XX, YY As Integer Dim CHB As Integer Dim kc As Integer Dim dqc As Integer Dim oldzs As Integer Dim FINDD As Integer Dim k As Integer Dim ccc, hhh(1 To 4) As Integer Dim kz, old_zz, old_yz, new_zz, new_yz As Integer Dim cc As Integer Dim KKK, mm As Integer
Dim ypdCQ(1 To 150) As Integer '避免重复计算串气 Dim TSC(1 To 150) As Integer '避免重复串合并
'CjzdWK = -1 -1号工作区分配给禁着点判断函数
PP_can_sikao = False '计算机可以开始思考标志 防止时序数据不同步产生错误
PPgo_jzdPD2 = 0 '不是禁着点
If zx <= 0 Or zy <= 0 Then 'pass不是禁着点 PPgo_jzdPD2 = 0 '不是禁着点 Exit Function End If
If PPgoXY(wk, zx, zy).hb <> 0 Then '这里已经有子 禁着点 PPgo_jzdPD2 = 1 Exit Function End If
'从数据区拷贝数据---------------------------------------------
For i = 0 To 20 For J = 0 To 20 PPgoXY(CjzdWK, i, J) = PPgoXY(wk, i, J) '棋盘黑白空局面 Next J Next i
For i = 1 To c_CHan_max PPgo_chuan(CjzdWK, i) = PPgo_chuan(wk, i) '棋串基本信息 Next i
For i = 1 To 361 PPgo_chuan_zz(CjzdWK, i) = PPgo_chuan_zz(wk, i) '棋串基本信息棋串存贮单元 Next i
PPgo_NOW(CjzdWK) = PPgo_NOW(wk)
PPgo_NOW(CjzdWK) = PPgo_NOW(CjzdWK) + 1 '当前第几手
'同色串合并---左边 右边 上边 下边 ,------------------------------------------------------------------------- ccc = 0
'搜索傍边的同色串 If PPgoXY(CjzdWK, zx - 1, zy).hb = zhb Then kc = PPgoXY(CjzdWK, zx - 1, zy).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'搜索傍边的同色串
If PPgoXY(CjzdWK, zx + 1, zy).hb = zhb Then kc = PPgoXY(CjzdWK, zx + 1, zy).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'搜索傍边的同色串
If PPgoXY(CjzdWK, zx, zy - 1).hb = zhb Then kc = PPgoXY(CjzdWK, zx, zy - 1).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'搜索傍边的同色串 If PPgoXY(CjzdWK, zx, zy + 1).hb = zhb Then kc = PPgoXY(CjzdWK, zx, zy + 1).CH If TSC(kc) = 0 Then '该串号未记录 ccc = ccc + 1 hhh(ccc) = kc TSC(kc) = 1 '标记该串已经记录 End If End If
'-------------------------------------------------------
kz = 0 '申请存储单元 搜索空子保存新子的数据 For i = 1 To 361 If PPgo_chuan_zz(CjzdWK, i).zx = 0 Then kz = i Exit For End If Next i
If ccc = 0 Then '没有傍边的同色串,创立新串 kc = 0 For i = 1 To c_CHan_max '申请存储单元 搜索空串保存数据 If PPgo_chuan(CjzdWK, i).ZS = 0 Then kc = i Exit For End If Next i
'建立串子指针 PPgo_chuan(CjzdWK, kc).ZS = 1 PPgo_chuan(CjzdWK, kc).hb = zhb PPgo_chuan(CjzdWK, kc).zz = kz '长子指针'幼子指针 PPgo_chuan(CjzdWK, kc).YZ = kz
'建立新子存储单位 PPgo_chuan_zz(CjzdWK, kz).zx = zx PPgo_chuan_zz(CjzdWK, kz).zy = zy PPgo_chuan_zz(CjzdWK, kz).Znext = 0
'建立子串指针 PPgoXY(CjzdWK, zx, zy).hb = zhb PPgoXY(CjzdWK, zx, zy).CH = kc dqc = kc '当前新建立的串 Else '有傍边的同色串,进行串合并
'------------------------------------------------------- '串合并 kc = hhh(1) old_zz = PPgo_chuan(CjzdWK, kc).zz '长子指针 old_yz = PPgo_chuan(CjzdWK, kc).YZ '幼子指针 cc = old_yz '第1个串的幼子指针 For i = 2 To ccc '旧串合并 dqc = hhh(i) new_zz = PPgo_chuan(CjzdWK, dqc).zz '长子指针 new_yz = PPgo_chuan(CjzdWK, dqc).YZ '幼子指针 PPgo_chuan_zz(CjzdWK, old_yz).Znext = new_zz old_yz = new_yz '幼子指针向后面串移动 PPgo_chuan(CjzdWK, dqc).ZS = 0 '释放一个旧串存储单元 Next i
'新子串加入合并-------------------------------------------------------
PPgo_chuan(CjzdWK, kc).YZ = kz '幼子指针 PPgo_chuan_zz(CjzdWK, old_yz).Znext = kz '新子连接在旧串后面
'建立新子存储单位 PPgo_chuan_zz(CjzdWK, kz).zx = zx PPgo_chuan_zz(CjzdWK, kz).zy = zy PPgo_chuan_zz(CjzdWK, kz).Znext = 0
'建立新子黑白 PPgoXY(CjzdWK, zx, zy).hb = zhb
dqc = kc '当前新合并的串
'---------------------------------------------------------- Do '修改合并串的子串指针 zx = PPgo_chuan_zz(CjzdWK, cc).zx zy = PPgo_chuan_zz(CjzdWK, cc).zy PPgoXY(CjzdWK, zx, zy).CH = dqc cc = PPgo_chuan_zz(CjzdWK, cc).Znext Loop While (cc <> 0)
End If
'重新计算周围串的气,左边 右边 上边 下边 ,如果气=0 杀敌串----------------------------------------------------------------------------
pptz_NOW = 0
If PPgoXY(CjzdWK, zx - 1, zy).hb = -1 * zhb Then CH = PPgoXY(CjzdWK, zx - 1, zy).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(CjzdWK, CH) '判断下子后敌人临串的气 If QS = 0 Then Call ppgo_kill_chuan(CjzdWK, CH) End If ypdCQ(CH) = 1 '标记该串气已判断 End If End If
If PPgoXY(CjzdWK, zx + 1, zy).hb = -1 * zhb Then
CH = PPgoXY(CjzdWK, zx + 1, zy).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(CjzdWK, CH) '判断下子后敌人临串的气 If QS = 0 Then Call ppgo_kill_chuan(CjzdWK, CH) End If ypdCQ(CH) = 1 '标记该串气已判断 End If End If
If PPgoXY(CjzdWK, zx, zy - 1).hb = -1 * zhb Then
CH = PPgoXY(CjzdWK, zx, zy - 1).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(CjzdWK, CH) '判断下子后敌人临串的气 If QS = 0 Then Call ppgo_kill_chuan(CjzdWK, CH) End If ypdCQ(CH) = 1 '标记该串气已判断 End If End If
If PPgoXY(CjzdWK, zx, zy + 1).hb = -1 * zhb Then
CH = PPgoXY(CjzdWK, zx, zy + 1).CH If ypdCQ(CH) = 0 Then '如果本次未判断过该串的气 QS = PPgo_chuanqi(CjzdWK, CH) '判断下子后敌人临串的气 If QS = 0 Then Call ppgo_kill_chuan(CjzdWK, CH) End If ypdCQ(CH) = 1 '标记该串气已判断 End If End If
'自杀合法性判断-------------------------------------------------------------
QS = PPgo_chuanqi(CjzdWK, dqc) '计算新下子串气数目 ZS = PPgo_chuan(CjzdWK, dqc).ZS '判断子数
If QS = 0 Then If gui_ZE = 0 Or gui_ZE = 1 Then '"根据中国规则(日本规则)" + vbCrLf + "禁止自杀!" PPgo_jzdPD2 = 2 Exit Function ElseIf gui_ZE = 2 Or gui_ZE = 3 Then If ZS = 1 Then '"根据应氏规则(顾氏规则)" + vbCrLf + "禁止颗子自尽! PPgo_jzdPD2 = 3 Exit Function Else '块子自尽 'Call ppgo_kill_chuan(CjzdWK, dqc) 'MsgBox "自杀" PPgo_jzdPD2 = 10 '根据应氏规则 块子自尽 Exit Function End If End If End If
'劫禁着点判断------------------------------------------------------------------------ '判断单劫,3劫,4劫和互提2子 并没有判断全部的可能情况,属于简化法则 不完全判断法,没有判断全部历史局面的同型 '估计出现违法的概率在1/亿 以下。
If pptz_NOW <= 0 Or pptz_NOW >= 3 Then '不是提了1-2个子 PPgo_jzdPD2 = 0 '不是禁着点 Exit Function End If
If ZS <= 0 Or ZS >= 3 Then '不是建立了1-2个子的串 PPgo_jzdPD2 = 0 '不是禁着点 Exit Function End If
If gui_ZE <> 4 Then '不是电脑规则
KKK = 8 'kkk=8能判断单劫,3劫,4劫和互提2子,如果kkk=2 则只能判断单劫
'劫禁着点判断,禁止全局同型再现法则,不完全判断法。没有判断全部历史局面的同型 k=360 If PPgo_NOW(wk) >= 8 Then For i = 1 To KKK If i Mod 2 = 1 Then '不完全判断法
mm = (PPgo_NOW(wk) - i) Mod 8 '因为使用循环队列的形式存贮倒数棋形 If mm <= 0 Then mm = mm + 8 End If
'分块扫描,在当前子周围,发现棋型产生变化可能性大,加快运算速度
'--------------------------------------------------------- FINDD = 0 For J = zx To 19 '右下角 For k = zy To 19 If PPgoXY_daoshu(wk, mm, J, k) <> PPgoXY(CjzdWK, J, k).hb Then FINDD = 1 '发现棋型产生变化 为非劫禁 Exit For End If Next k If FINDD = 1 Then Exit For End If Next J
'--------------------------------------------------------- If FINDD = 0 Then For J = zx To 1 Step -1 '左上角 For k = zy To 1 Step -1 If PPgoXY_daoshu(wk, mm, J, k) <> PPgoXY(CjzdWK, J, k).hb Then FINDD = 1 '发现棋型产生变化 为非劫禁 Exit For End If Next k If FINDD = 1 Then Exit For End If Next J End If
'--------------------------------------------------------- If FINDD = 0 Then For J = zx To 1 Step -1 '左下角 For k = zy To 19 If PPgoXY_daoshu(wk, mm, J, k) <> PPgoXY(CjzdWK, J, k).hb Then FINDD = 1 '发现棋型产生变化 为非劫禁 Exit For End If Next k If FINDD = 1 Then Exit For End If Next J End If
'--------------------------------------------------------- If FINDD = 0 Then For J = zx To 19 '右上角 For k = zy To 1 Step -1 If PPgoXY_daoshu(wk, mm, J, k) <> PPgoXY(CjzdWK, J, k).hb Then FINDD = 1 '发现棋型产生变化 为非劫禁 Exit For End If Next k If FINDD = 1 Then Exit For End If Next J End If
'--------------------------------------------------------- If FINDD = 0 Then '没有发现不同形的地方=全局同型再现 If i <= 2 Then PPgo_jzdPD2 = 4 '1劫循环 Exit Function
ElseIf i <= 6 Then PPgo_jzdPD2 = 5 '3劫循环 Exit Function Else PPgo_jzdPD2 = 6 '4劫循环或者互提2子 Exit Function End If End If
End If Next i End If
ElseIf gui_ZE = 4 Then '是电脑规则,则使用简易判断法,只能判断单劫,等效于上面设置了kkk=2
'劫禁着点判断简易法则------------------------------------------------------------------
If PPgo_jjzd(wk).zx = 0 Then '上一手没有标记劫禁着点 PPgo_jzdPD2 = 0 '不是禁着点 Exit Function End If
If pptz_NOW <> 1 Then '当前手不是提了1个子 PPgo_jzdPD2 = 0 '不是禁着点 Exit Function End If
If QS <> 1 Then '当前手不是建立了1口气的串 PPgo_jzdPD2 = 0 '不是禁着点 Exit Function End If
If ZS <> 1 Then '当前手不是建立了1个子的串 PPgo_jzdPD2 = 0 '不是禁着点 Exit Function End If
If PPgo_jjzd(wk).zx = zx And PPgo_jjzd(wk).zy = zy Then '上一手标记的劫禁着点 PPgo_jzdPD2 = 4 '是禁着点 Exit Function End If
End If
PPgo_jzdPD2 = 0 '不是禁着点
End Function
顾熙杰
本文章从计算机围棋的思考方法着手,得到十分奇怪的结论,信则有,不信则无。
围棋世界只有变式没有定式,
只有骗招没有正招,
只有偏分没有两分。
上面3个定式是两分定式吧????
如果连这3个也不两分,也就不存在两分了吧。
事实是
黑不利0.72目
黑不利0.1目
黑不利1.75目
结论:
围棋世界只有变式没有定式,
只有骗招没有正招,
只有偏分没有两分。
这个结论你问专业棋手,他们也是这样回答的。
另外,使用本软件分析得到结论,
非对称守角比对称守角有利,
也就是小目比星位有利,
这个近几年(2010)小目逐渐回归,
也许专业棋手也有此感觉吧。
由于本软件评价函数还十分简单,所以结论还不可靠,
有待进一步研究。
本软件支持黑贴8点的应氏规则。
下载地址:
http://pan.baidu.com/s/1eQvF8no
2000年编写的,本人作品,本人第1个VB程序,
就是围棋程序,当时没有利用任何电脑围棋
方面的参考资料,
难度可以想象,当时还没有读自考计算机专业,连数据库都没有学会。
但还是实现了人机对战。水平太低,大家别笑话。
刚学围棋编程的VB爱好者,可以参考,毕竟实现了,
算气,提子,禁着点判断等基本功能。
后来读了计算机专业,总算学会了搜索算法。
现在明白了,计算机围棋太难了,必须要成立小组才行,1个人,
没有办法战胜专业棋手。
搞个学习软件,本人只能这个水平了。
2000年,专业棋手让手谈16个子,本人可让23个。其中还有1局让23子的下成了4劫循环,
这是本人唯一的一盘4劫循环。
2013年,本人可让银星10,7个子,但银星13本人只能让3个,进步超出本人估计。
虽然日本棋院给5段,本人评他1K-1D之间。
本人预测2050年左右,计算机将战胜人类。
陈志行教授的专家系统(手谈)是一个顶峰,
uct算法是一个顶峰,
未来的计算机围棋必须是专家系统和搜索2合一的算法,也必须由小组合作开发,
必须利用网络并行阵列的大规模计算机技术,
可是国内1大帮人都想走UCT的捷径,这个是邪教。
UCT算法本质还是搜索,难以避免会碰到组合爆炸的难题。
计算机围棋作为数学问题,(第1步下那里最优,黑应该贴几目)
是不可解决的,但战胜人类是必然的。
革命尚未成功,电脑还需努力。