加载中…
正文 字体大小:

首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义

(2015-11-29 18:55:02)
标签:

围棋

分类: 其他赛事
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
喆理围棋沙龙由李喆六段发起,清华围棋文化交流与研究基金主办。旨在以沙龙的形 式,吸引志同道合的朋友,从文化、哲学等方面出发,共同思考、交流意见,探寻围棋的价值与本质。关于围棋与数学关系的讨论由来已久。近期,李喆六段完成了 7路盘最优解的证明。在技术层面之外,这一证明同样引发了关于数学思维、计算机技术在围棋问题中运用的讨论。首期沙龙11月28日下午在清华大学举行,就 “棋盘上可被证明的命题”这一主题展开讨论。

本期沙龙三名主讲人分别是李喆六段、北京邮电大学刘知青教授、中南大学数学系武坤教授。李喆 带来7路盘最优解的过程和思考,刘知青教授介绍目前计算机围棋的发展状况和计算机技术为解决围棋问题所能带来的帮助,武坤教授介绍了小棋盘及不规则棋盘的 证明方法。沙龙邀请多名数学、计算机领域的专家对此进行讨论。

李喆:7路盘最优解的过程和思考

之所以研究小棋盘最优解, 是为了通过小棋盘研究,从哲学、数学等方面思考,诸如人与计算机的思维特点、正确的贴目数等问题。关于7路盘的最优解是弱证明,只能说是研究,目前有以下 几个结论:第一,最优解贴9目(4子半);第二,最优解不是唯一的,前3手唯一,前7手导致5个最核心的最优解下法,可参见《围棋天地》;第三,存在许多 不影响最终结果的下法。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

计算机围棋穷尽证明目前大致完成了30个交叉点以内的棋盘,还在算6路盘的最优解。09年两位荷兰棋友发表论文,利用软件计算、人类审校的方法,用计算机算出5*5正方形棋盘、3*10长方形棋盘的最优解,但受限于算法和计算时间,棋盘增大形成瓶颈。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
正 方形棋盘最优解的有效数据较少,因此考虑长方形棋盘最优解数据,从一路棋盘开始。考虑最优解数据时,一方全占棋盘的数据可以选择剔除。近期对第一个规律的 发现:“一路单数路棋盘贴目规律”,在1*5/9/13/17路等棋盘是和棋,平衡贴目数是0。1*7/11/15/19路等棋盘黑胜1子,平衡贴目数是 1(先行多占2点)。于是得出:当n大于等于2时,1*(4n-1)路棋盘黑胜1子,1*(4n+1)路棋盘和棋。偶数棋盘要复杂一些,与奇数盘策略不 同,还要考虑虚手等规则方面的困扰,如一路盘虚手后是否可以提劫。从可知最优解中寻找贴目规律,似乎确实可行?

目前小棋盘最优解证明面临的问题:1、强、弱证明的判定标准是什么?2、证明方法是否存在探索的空间?3、在最强证明(穷尽证明)之外,如何证明封闭区域里对方不能出棋(对终局的判断);4、以7路盘为例,为何开局第1手走1/2/3路不是最优解。
研究方向包括:1、最强证明;2、人机合作与人机对抗;3、小棋盘可借鉴的规律。

小棋盘最优解研究的现状,职业棋手今年的进度是7路棋盘最优解的技术证明,下一关是8路棋盘最优解。智能围棋09年的进度:30交叉点以下棋盘最优解的数据,下一关是6路棋盘最优解。电脑给出的证明较强,棋手给出的证明较弱,棋手与智能围棋合作研究的模式值得探索。

厚 势、阴阳转换、虚实等的转化,是人的一种感觉,能帮助我们来理解棋的方法,但不够科学,如何能用数学精确分析?用习以为常的具体目数来计算是否合理?要找 到确定的计算方法,适合计算机应用的路径,而不能以人类的思维方式来衡量。如“中间开花三十目”,能够用数学方法表达吗?

几个关于围棋可证明命题的猜想:一手棋的价值判断;劫争的价值判断;官子的数学模型;“制造见合”是优势策略的数学证明及应用等等。

理论上如果棋手能确定每手棋的价值,优势策略就应该是,下了A点之后,B和C点的价值一样,之后D和E点一样,以此类推。如何制造见合,棋手有在运用这样的思维,在计算机能否也能应用这种思维方式。

最优解的研究,可帮助提高智能围棋,也能帮助棋手训练。给定一定条件下的判断,可以加强棋手的判断和准确度。

李 喆发言后引起了讨论。随着棋盘的增大,复杂程度大幅增加。王振波教授:围棋的计算复杂性角度,从数学方面来看,处理的一种方式是折中,如8路棋盘,首先不 贴目下能做到执黑必胜,第二步是做到贴目少的情况下必胜,不一定直接求得最优解,而是以剪枝、降低难度来不断接近最优解。

由小川教授:在计算力学方面,通常有两种解法,一种是应力解法,符合逻辑。另一种位移解法,满足一定意义的数学归纳,更容易由计算机识别。

刘知青教授:7路盘最优解的证明,可以从阿尔法贝塔博弈树剪枝方面极大帮助计算机进步,具有里程碑的意义。


首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义


刘知青:7路盘围棋对弈理论值的证明

对弈理论值指的是对弈双方最优下法的情况下的对弈结果,证明有三个层面:
超弱证明:对于起始盘面,确定其对弈理论值。
弱证明:对于起始盘面,确定对弈策略能至少获得对弈理论值(例,国际跳棋Checkers,Schaeffer et al.,2007)。
强证明:对于所有盘面,确定对弈策略获得该盘面的对弈理论值。需要遍历,在任何一条路确保都已证明才行。

规则与不规则围棋棋盘的弱证明(两位荷兰棋友,至多30个落子点,5*6棋盘),证明使用的主要方法:alpha-beta博弈树搜索辅助以NegaScout;领域相关的搜索改进;领域无关的搜索改进。

三大改进方法,初盘情况的改进:通过围棋知识进行初盘博弈树剪枝(例如,在第一步上,为什么四路比三路、二路、一路都好?是否能做落子点相对优劣的比较?)。
终盘情况的改进:通过围棋知识进行博弈树剪枝(例如,什么样的封闭区间就不可能再活棋了?如何尽早地识别终局盘面以及终局盘面内的死活?)。
证明方法的改进:对弈理论值的验证,而不是对弈理论值的发现(alpha-beta博弈树搜索)。

围棋对弈理论值证明的路线图:1、实现围棋alpha-beta博弈树搜索算法。
2、实现领域无关的搜索改进(例如,对称置换表)。
3、实现领域相关的搜索改进(例如,落子点排序,初盘剪枝,区域剪枝)。
4、以李喆7路盘围棋最优解为驱动,运行alpha-beta博弈树搜索算法,其结果或者完整验证对弈理论值为真,或者找出反例。
5、算法的并行化和高性能并行计算环境。

围棋领域的知识对智能围棋的帮助包括:如何能更快识别终局。识别某些局部没有变化。
发 现问题比认识要难的多。例如:6-12目是区间的上下界,区间越窄的话,剪枝越充分,可放弃掉无关的东西。李喆给出的贴9目,就可以充分利用现有结果,拿 它和其他的来进行比较。用排除方法缩小搜索空间。把一些没有出棋的小空间提前算出记下来,类似死活库、象棋的终局库,尽可能帮助计算机剪枝。



首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
武坤:小棋盘及不规则棋盘的证明方法

武坤教授病重手术后也赶来出席,首先进行了“天元,围棋的奇点”展示。
宇 宙本身是最大的一个混沌系统,围棋也是个混沌系统,在宇宙和数学方面做猜想,有个点物质密度无限大,用大爆炸的方式开天辟地。围棋的天元,也许就类似奇 点,不变性在围棋里会有所体现,如贴目。通过小棋盘来进行分析,奇数盘的奇点是天元,而偶数盘还不知道在哪里,就更复杂。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
天元是贴目的根 源,奇数棋盘和偶数棋盘的一个区别在于没有天元。有天元的小棋盘相对简单,所以猜想从奇数小棋盘开始。研究7路盘发现,黑第一手走在天元,结果比白多9 目。通过反证法,去除天元点,发现局面接近于不贴目。以5路盘为例,只要白棋走到对称点上,就会自然形成和棋。在上述对局结果中发现,贴9目的猜想。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

随着棋盘尺寸扩大,贴目值的变化趋势会有三种可能性,根据对局经验,变大的可能性最小。以7路和9路棋盘为例,如用网状座子简化后,第一手走到天元点,最佳下法的棋局黑依然领先白9目,说明对于9路盘,贴目并不随棋盘增大而变小。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
后来发现7路盘的最优解同为9目。李喆六段帮助武坤老师完成了验证。以1*(2n+1)路小棋盘为例,1*(4n-1)路棋盘需要占据天元,结论是黑棋多2 目/1子。而1*(4n+1)路棋盘会形成打劫,无论n的数值是多少,最终双方结果是0目。1*5路盘落子如正弦波,1*9路盘就如两个完整的正弦波。所 以1路奇数棋盘最优解为0~2震荡,即1*7/11/15路盘黑胜1子,1*5/9/13路是0目。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
接下来是3*(2n+1)路棋盘,目前猜测是贴5目。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

 达到5路棋盘时,猜想已经很难完成,目前李喆的意见为贴7目。所以1路棋盘贴目(0/2之间)视为1目,3路盘视为5目,5路盘为7目,7路盘是9目。那 么未来可能更大棋盘都会靠拢在9目左右。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
举几个特殊例子,这俩图围棋软件zen没有给出最好的结果,但是人可以在很短时间内完成计算。

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
另外,围棋盘上极限可以有多少块棋,从63到67块,然后一位棋友短短几天内又把围棋的极限值提高到了69块,数学上的极限值是71块,但目前还没能在棋盘 上找到。
首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
而围棋的嵌套,最复杂的是19层。围棋的难度,想用一个函数来解决所有问题,几乎是不可能的。围棋的变化,目前数学可证明的是10的270次方。

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

假设19路围棋能得出最优解,会有什么样的后果呢?众多嘉宾畅所欲言。

武坤:最优解证明后,对围棋有好有坏。对人工智能的发展有好处。微软也曾投入很多,但最后没有立项。举例来说,如果人工智能攻克围棋,客服的服务就能由电脑 取代人,达到非常高的高度;另个例子,中医相当于医生和病情之间的对弈,医生每个方子就相当于每一手棋,每走一步之后病情都会有新变化,围棋有了突破,也 会有助于医学的发展。

由小川:我以前是象棋校队的,象棋原来有大量的和棋,被电脑攻克后,很多原来约定俗成的和棋谱都被推翻了,布局从根 上就改变了,棋比以前更好看了,顶级棋手很少不用电脑拆棋,电脑的强大推动了象棋技术的进展,带来了积极作用。计算机象棋的强大给象棋带来了技术上的颠覆 和提升,以往被认为均势的局面出现了更多变化的可能,计算机辅助人类可以达到比纯人或纯机更优的策略,从而加快技术的进步历程。不过在残局方面电脑还弱于 人,子越少变化越多。所以电脑和人之间有一个动态平衡,不会使棋手丢掉工作,是相辅相成的。

刘知青:象棋和围棋区别很大,一个是评价函 数,根据一个盘面象棋比较容易评估,看子力,多少子、位置等几个因素,围棋形势判断怎么做不知道,更难。目前计算机对弈主要是用蒙特卡洛算法,基于统计学 概念。第二个是象棋的将、车等很重要的子需要保护,而围棋水无常形,子效是随时在变化的。

由小川:象棋子越少越复杂,当两个棋盘一样大时,复杂程度也趋近于相似。

李喆:围棋强证明(任何局面最优解)出现并非围棋末日,相反,这将促进围棋的新价值的演变。首先人类下围棋的主要目的和价值不仅在竞技胜负,很多对自身的提 高的价值,思维更有价值。而在7路盘,由于人并没有用棋理思维来研究,而是计算为主,所以计算机的佐证没有证明棋理这边的帮助,但是如果在19路盘出现强 证明,会是更好的对围棋价值的佐证。如果电脑能给出最优解,人再去理解,得到的信息会有更坚实的基础。

刘知青:做计算机围棋并不为了战胜 人,目标是通过计算,计算机能达到什么样的智力水平,图灵就证明计算机哪些方面不可解,即使可解,后面还有不可解,天外有天。对于可解的问题,现有的计算 方面,局限性在哪里,以及人脑的局限性在哪里。通过围棋这个很好玩的东西,看看计算机怎么能够应用到更多更好的方面,谷歌、Facebook、微软、百度 都在朝这方面努力。围棋是唯一的、非常好的、古老的、现存的、无法解决的博弈问题。拿围棋来探测计算机技术的界限、人脑界限在哪里。国际跳棋的最优解证明 论文在最顶级的《科学》杂志发表,而围棋的解决公认是难题中的皇冠。即使无法解决19路盘这么复杂的程度,但也不会消减它的重要性。

首期沙龙活动圆满结束,现场座无虚席,气氛热烈,提出了很多问题,也希望各行各业的朋友能够加入,发挥所长。征集问题:棋盘上十大数学命题,欢迎踊跃参加。


到场嘉宾有:
刘知青 北邮九鼎人工智能研究所教授
武坤 中南大学数学系教授
王振波 清华大学数学系教授
由小川 清华大学航空航天学院副教授
韩立新 清华大学哲学系
胡彬 奥地利技术研究院研究员
黎婷初段 欧洲围棋联盟副主席
陈雷 万同搜索CEO
赵守洵五段 围棋TV创始人
胡跃峰五段 围甲武汉三民队
李喆六段 喆理围棋沙龙创始人
向雷 铁路总公司运输处处长
马笑冰四段,王哲明三段,胡文波,沈通,曲华迪,蓝烈,李向军,章云轩等。
希望参加并发言的朋友可以发送邮件至zlweiqi@sina.com并等待组织者邀请。

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义

首期喆理围棋沙龙举行 <wbr>李喆7路盘最优解具有里程碑意义
我的更多文章:

0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有