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)=表示没有子,
      

网络上有说法

       goxy(x,y)=1  表示有黑子,
       goxy(x,y)=表示有白子,
       goxy(x,y)=表示没有子, 这个也是可以的。


但本人的方法有利于黑白变换,-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点的应氏规则。


 

弈花围棋程序vb原代码

下载地址:

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步下那里最优,黑应该贴几目)

是不可解决的,但战胜人类是必然的。

 

革命尚未成功,电脑还需努力。