登录 注册

第二届(2014)中国杭州国际棋文化峰会

《计算机围棋与围棋棋谱搜索》-刘知青

发布时间:2014-12-10 16:15:00.0    来源:

计算机围棋与围棋棋谱搜索

刘知青

Abstract

本文从宽泛的角度讨论计算机围棋的意义与范畴,介绍计算机围棋技术在棋文化上的众多潜在应用。在此基础上,本文阐述围棋棋谱搜索的目标与意义,讨论计算机技术在围棋棋谱搜索上的应用,并详细介绍一款基于棋型匹配的围棋棋谱搜索系统。

 

    1 计算机围棋的意义与范畴

自从我们2011 年出版了专著巜现代计算机围棋基础》一书之后,见到了很多关心计算机围棋的人士,收到了很多计算机围棋爱好者的邮件。他们都会恭维我一番,告诉我读过这本书,知道计算机围棋就是使用计算机来下围棋。受限于场合、交情等诸方面原因,我一般只能唯唯诺诺,请他们多提意见而已,无法一一做完整详细的答复。杭州国际棋文化峰会是个很好的平台与机会,让我相对深入地讨论计算机围棋的意义与范畴。

我受的教育与我从事的研究工作都是属于计算机科学中的人工智能领域。在这个领域中最近有个提法,即计算机围棋是当前人工智能领域研究的重大挑战。解决围棋博奕问题不仅仅是逻辑分析判断,也需要强大形状识别与评估。这涉及众多计算机科学中前沿的智能技术,其中包括大数据处理,模式识别,机器学习,专家系统,大规模并行计算等等。因此,围棋是推动人工智能技术发展,测试人工智能技术成果的良好平台。

从宽泛的角度来讲,计算机围棋远远不只局限于人机对奕,可以覆盖围棋文化的方方

面面。现在已有的计算机围棋应用就有很多:包括互联网围棋在线对奕系统,职业围棋选手等级分计算系统,围棋终局后的死活与胜负判断系统等等。本文在以下部分将介绍计算

机技术在围棋对奕之外的更多应用。其重点是讨论一个基于棋型匹配的围棋棋谱搜索系统,围棋棋谱搜索是使用计算机围棋技术发扬围棋文化的典型实例。

 

2 计算机围棋技术的应用

计算机围棋技术能为围棋文化的发扬光大做很多很多的事情,这既是机遇,又是挑战,也是商机。从机遇上看,计算机围棋技术近年来有了长足的发展,为整个围棋界提供了很多创新的机会,这些创新工作将为围棋文化的传播与发展,提供便利,提高效率。从挑战上看,我们为围棋文化所做的每一件创新工作,背后都有困难且复杂的技术问题要解决,常常需要应用最前沿的人工智能技术,例如最近流行的大数据分析与机器学习方法。从商机上看,每一项创新服务,每一项效率改善,都必定附带经济价值与商业机会,围棋上的技术创新与效率改善也不例外。当然,如何把握商业机会,如何实现经济价值,是另外一个话题了。

我们认为,计算机围棋技术在围棋文化上至少有以下三个方面的应用:围棋对弈,围棋学习,以及围棋文化研究。在围棋对弈方面,智能技术已经可以解决很多局部的围棋博

弈问题:例如,官子问题,死活问题,近似形势判断,落子推荐等等。很多局部围棋问题的计算机职能解决方法已经达到或接近职业选手的水平。

在围棋学习方面,计算机围棋技术可以在多方面辅助围棋指导教师,帮助学习围棋的孩子:其中包括具体围棋知识的辅导与练习,孩子围棋水平的自动评判与弱点的自动识别,自动匹配学习围棋孩子的围棋水平,与其在相同的对弈水平上对弈等等。计算机智能技术应用于围棋学习与普及可以有三大优势:1)降低围棋学习的门槛,3)提高围棋学习的效率,2)维护围棋学习者的信心,提高围棋学习者的成就感。

在围棋文化研究方面,计算机围棋技术可以提供必要的技术工具与科技手段,帮助文化研究的有效开展。围棋文化研究的开展也将有助于对弈与学习等其它方面。我们认为计

算机智能技术可以简化海量围棋棋谱的准确搜索,为围棋文化与研究,围棋学习与对弈,提供一个坚实的基础数据平台。下面我们就着重讨论一个基于棋形匹配的海量围棋棋谱搜

索系统。

3 围棋棋谱搜索的目标与意义

在围棋漫长的历史发展过程中,围棋文献与围棋棋谱起了至关重要的作用。其中,围棋棋谱是围棋文献的基础素材,围棋文献是围棋棋谱的总结与抽象。对于某一古代棋谱,

后人可能会有与前人不同的研究与理解。因此,相比之下,围棋棋谱比围棋文献更客观,更具体,其研究价值也就更重要。

现有的围棋棋谱管理软件,只对棋谱数据做了收集,整理,标注。这些简单的围棋棋谱技术处理完全无法满足实用要求。形状的识别与评判是围棋的核心之一,实用而有效的

围棋搜索也必然是基于围棋形状匹配的搜索。因此,围棋棋谱搜索的目标,就是任给一个围棋全盘或者局部的形状,在围棋棋谱库中搜索形状匹配的棋谱。由于每个棋谱包含几百

个全盘围棋形状,围棋棋谱库中通常包含几十万个棋谱,即包含上亿个全盘围棋形状,以及更多数量级的局部围棋形状。因此,围棋棋谱库是个海量数据库。

这样一个建立在海量数据库上的围棋棋谱搜索系统具有重大的实际意义:从古至今的所有围棋棋谱以及相关的围棋形状,通过该系统在互联网上的搜索引擎,可以被准确且方便地搜索到。围棋职业选手可以方便地研究围棋的当前潮流、对手的风格;围棋业余爱好者可以方便地学习与研究定式的变化、手筋的选点;初学围棋的孩子可以方便地学习模仿围棋高手的落子;围棋研究者可以根据其具体研究课题分析比较围棋文化的历史演变。

4 计算机围棋技术应用于棋谱搜索

基于棋形进行围棋棋谱搜索的关键是棋形的定量比较。从数学上看,任给二个围棋盘面A 与B,我们需要比较A 与B 之间是否匹配。我们可以进一步通过数值定量地衡量A

与B 之间的匹配程度,记为M(A;B),其数值范围在[0; 1],越大表示匹配程度越高。对于任何一个给定的查询盘面Q,我们就可以每个棋谱盘面P,使用匹配度M(P;Q) 为P进行评分,再根据评分进行排序,就可以准确搜索出匹配的棋谱了。

当然,上述的匹配过程只是一个总体算法,实际应用过程中仍然有众多的实际问题要解决,例如存储效率,搜索时间效率等等。由于这些涉及底层技术细节,超出了本i 次棋

文化峰会的主旨范围,就忽略不具体讨论了。

5 围棋棋谱搜索系统

我们下面实际看看这个围棋棋谱搜索系统。我们的第一个例子是中国流布局:在此盘面下搜索得出五个落子选点,及其相应的分值。

 

选择任何一个推荐的落子选点可以查看相关的棋谱盘面。例如,如果我们选择查看C点所对应的相关棋谱,会搜索到大量的匹配棋谱,其中二个显示如下:

 

 

在下面的这个例子中,棋盘的左上角出现了一个双飞燕的变化,白棋粘上后,轮到黑棋落子。我们在这个盘面上搜索黑棋的得出五个落子选点,我们会得到下面的结果:

 

如果我们选择查看A 点所对应的相关棋谱,会搜索到大量的匹配棋谱,其中二个显示如下,包括完全匹配的棋谱,也包括部分匹配的棋谱:

 

如果我们选择查看B 点所对应的相关棋谱,也会搜索到大量的匹配棋谱,但在此情况下,只有部分匹配,没有全盘匹配,其中二个显示如下:

 

6 结束语

计算机围棋不仅仅是围棋对弈,计算机围棋智能技术可以在多方面促进围棋文化的传播,提高学习围棋,研究围棋的效率。本文阐述了围棋棋谱搜索的目的与意义,详细讨论

了一款基于围棋棋形匹配的海量围棋棋谱搜索系统,希望对围棋博弈,围棋学习,以及围棋文化研究起到积极的促进作用。