首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >围棋规则的计算机实现

围棋规则的计算机实现

作者头像
窗户
发布2018-02-07 14:36:15
1.4K0
发布2018-02-07 14:36:15
举报
文章被收录于专栏:窗户窗户

  提到这个名字,很多人会想到前段时间让全世界振奋的围棋人工智能Alphago,想曾经我也了解过一些围棋的AI。我也正想花点时间说说alphago相关的东西,包括alphago的架构以及模型引申等,不过这篇文章里我只说围棋规则的实现,和人工智能无关。

规则

  说到围棋规则的实现不得不先说围棋规则,一般来说,至少有三种围棋规则:中国规则,日本规则,应氏规则。其实还有中国古代规则,和这三种规则都有一点差别。应氏规则和中国规则实际差距非常非常小,小到很多人认为可以忽略不计。但中国规则和日本规则的差别有些大,个人认为中国规则更科学,日本规则不收单官导致了很多问题,比如盘角曲四算死棋(这一点个人觉得挺让人吐血,因为如果盘角曲四和双活同在,那盘角曲四的死毫无道理),再比如不提三目(这个简直就是强盗逻辑了,至于什么叫不提三目,请自行搜索)。从这一点上,至少中国规则不会导致这样的争议,一切实战解决。另外一点,日本规则的双活不算目,这个给计算机数目带来了问题,并且不容易解决。所以,本篇还是基于中国规则。

基本数据结构

  很自然的就可以想到,可以用一个19X19的二维数组来代表棋盘上当前的棋面(一般称枰面)。棋盘上的每个点可以有三种状态:无子、黑子、白子。那么,这个19X19的二维数组就是基本的数据结构。

下棋

  从第一步开始,黑白轮流下,无论对于谁下,其实都是要判断这个二维数组所下坐标下的点的状态是不是无子,如果不是无子,当然是不允许下的。

  另外一点,还有一个气紧的问题,就是说,把自己的一块棋走成没有气是不允许的(应氏规则除外,它可自杀),除非可以吃子。气紧和吃子最终可以归结为一个算法:判断连通的一块棋有没有气。这里连通的一块棋是狭义的,只是通过横竖紧密的连在一起的才是一块棋。

  如上图,左边7个黑子紧密的连在一起,我们称之未一块。右边这个中心标记为红色的黑子,却不是属于这一块的。

  看起来稍微形式化一点的定义如下:

  先定义坐标相邻,(A,B)与(C,D)相邻的意思是A=C且|B-D|=1,或者B=D且|A-C|=1

  坐标(A,B)所在的一块棋是一个坐标的集合S;

  坐标(A,B)在S内,坐标(C,D)与(A,B)相邻,并且(C,D)坐标上有棋子且棋子颜色和(A,B)一致,那么(C,D)也在S内。

  以上的内容很像连通图的定义,实际上,如果把相邻的同色子的连线当成图的边,那么连通的一块棋实际上就是连通图,那么判断一块棋有没有气可以利用连通图的遍历,只是如果发现在遍历的过程中找到一颗棋子有气,那么整块棋子都有气。

  要注意打劫,打劫的时候不可立即回提。

  如上图即为打劫。

  打劫至少有两种简单的判断手段:

  (1)当出现提1子时,记录当前子的坐标和提子的坐标;若下棋的时候,只提一子,并且上一步对方也是提一子,并且当前子的坐标就是上一步提子坐标,当前提子坐标就是上一步下的棋子坐标,那么则是打劫回提,是犯规的。

  (2)每一步都记录当前的棋面。如果当前下完棋子之后,棋面和上一步没下时一模一样,则是打劫回提。

  打劫是一种绝对需要避免的同局再现,至于三劫、四劫、长生、双提这一类导致无胜负的局面,则可以用记录每一次的棋面,然后与几次之前的进行对比,如果存在相同,也就是同局再现,可以判断是无胜负,基本同判断打劫的算法2,只是不是和上一步的比。

计算

  最终计算胜负的时候,自动算十分复杂,之前网络上的围棋对战平台程序也是反复改进了很久才准确。我们这里只讨论手动的方式。

  首先是点掉死子。手动一个个的点掉死子自然可以,但效率太低,一般都是一点就点掉“连同”的一片死子。

  如图中两块死子,是希望清除其中一个子就清除掉所有其他“连通”的。

  这里的连通概念和上面连通的一块棋有点不同,这里的连通是同一个颜色或者空格在一起的一块,而之前的只强调一个颜色的一块。

  比如上面的图的上面那块权掉白棋死子所在的连通块是5个白子加旁边六个空格。

  其实依然是图,只是遍历图的时候边的定义改了一下,之前是相邻棋子颜色相同则是边,现在是相邻两个左边不出现不是死子颜色的是边。

  这样就可以遍历死子,确定一个死子坐标,就可以扫掉所有与之“相连”的死子。

  点掉所有死子之后数空定胜负。数空还是利用连通图,只是这里连同图指的是空格。如果空格的连通图在遍历中发现只和黑子相邻则是黑子的空,只和白子相邻则是白子的空,和黑白都有相邻则是公气,计算时得一方一半才可。数空是要依次遍历所有的空格连通图,直到整个棋盘上所有的空格都属于某个遍历出来的连通图。

遍历连通图

  上面基本所有的算法都可以归结于连通图的遍历。图的遍历一般有深度遍历和广度遍历,围棋这里算连通图采用广度遍历比较方便。

  需要一个数据结构来记录哪些坐标被遍历过了,防止重复遍历,每次遍历了坐标之后就记录下,这个数据结构以二维数组最合适。

  建立一个空队列,然后把开始遍历的第一个坐标进队。

  从遍历的第一个位置开始,每次把这个位置相邻的坐标中所有与之相连并且没有遍历过的点(注意相连在不同的判断里意义不同)进队,并把当前坐标出队,同时记录该坐标已遍历。

  如此循环,直到队空,则已遍历了整个连通图。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-09-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档