本帖最后由 cdswmj 于 2013-1-25 01:38 编辑
说说电脑围棋(一)
五十年代末的时候人工智能专家预测过个10来年电脑会跟人脑一样聪明,但是至少到现在,电脑下围棋比人脑还差得远 。
电脑下不过人脑可能有两种原因,一是电脑还不能处理围棋的复杂度,二是电脑围棋不受重视。电脑围棋确实比较难以上手,开发一个围棋程序需要较高的围棋棋力,软件开发经验和人工智能背景。尽管如此,电脑围棋研究已经有40年了,现在包括剑桥和微软研究院在内的多个研究组都在研究电脑围棋的算法,特别是大家熟知的应昌期先生的百万美元悬赏更是在上世纪末掀起了一股电脑围棋热,可惜如今最好的电脑程序棋力还低于业余初段,远没达到应先生战胜职业棋手的标准,只能眼睁睁地看着百万奖金在2000年过期。
那么电脑围棋到底复杂在哪里?深蓝可以战胜象棋世界冠军,为什么围棋程序不行?电脑围棋和电脑象棋有什么区别?
电脑象棋的基础是树搜索,简单地说就是根据当前棋局状态,先试一下可能的每一步,然后试一下每一步对手的应手,针对对手的应手再决定你的下一步,如此下去直到终盘。大家可以把这个过程想像成建立了一个树状结构,树的第一层是本方下一步,树的第二层是对方应手,树的底部是棋局最终结果。根据最终结果,象棋程序就可以选择当前情况下最佳的下一步。当然这棵树奇大无比,目前计算机还不能算到底部,通常必须停止在中间某层。程序停止往下算的时候,因为棋局尚没结束,对该层的每种状态(或者树分支)必须做一下形势判断。电脑
象棋的判断函数是基于盘面的子力和对王的相对位置,准确度相当高而且耗时少,再加上深蓝每秒钟可以评价两亿个盘面状态,使得计算机可以准确地算出去15,6步,而人脑要想在一盘棋里自始至终保持这样的算度,几乎是不可能的。
围棋棋手的思路和电脑象棋的算法还是比较接近的:搜索和评价,但是围棋高手能够很快地去掉绝大部分搜索分支,并且对难以定量的棋形和味道,有常人难以理解的判断。赵治勋在评价老对手小林光一的时候说:他对棋形有特殊的感觉,总是能够很快找到棋局的重点,从而把时间花在需要的地方。虽然快速缩小搜索空间是围棋对弈必须的技能,不可忽视的是这样思考的结果往往会漏掉看似无理其实绝妙的招数。被称为千古奇局的棋圣施襄夏让张振西四子局,其中的强扭活羊头至今为人津津乐道;无独有偶,小李飞刀李世石近期也曾上演过强征活子的一幕。电脑围棋如果采用电脑象棋同样的搜索方法,会不会找到职业棋手的盲点,从而超过职业棋手呢?答案是遥遥无期!
沈括在《梦溪笔谈》中论及围棋时说“大约连书万字四十三,即是局之大数。” 古人的数学还是很牛的,假定终局时棋盘上每个点有独立的黑,白,空三种状态, 棋盘状态就有3的361次方,约为10的172次方,也就是连书万字四十三。因为棋盘每个点状态不能独立,科学家估算围棋的状态空间约为10的160次方,而象棋的状态空间只有10的123次方。 围棋一盘棋平均可着点是200,而象棋只有40,如果围棋采用上面描述的搜索方法,算出10步的话,就要评价200^10个状态,是象棋的900多万倍(40^10) 。
如果围棋只是状态空间大也好办,因为根据摩尔定律,计算机的速度每18个月翻一倍,这样总有一天计算机会超过人类。但是计算机面临的更大的挑战是盘面状态评价,围棋一手棋不但会改变局部,还会影响全局,一手棋的价值有时在当前形势下不明显,却在几十手后凸显出来。当专业棋手夸奖一手棋味道好的时候,业余棋手却感受不到他的味道,计算机则更难把味道转换成评价值。事实上人类对形状和模式有特殊的辨别能力,而计算机则需要存贮大量数据和进行复杂的计算,但仍然远达不到人类大脑的辨识能力,因此评价棋盘状态是电脑围棋发展的真正瓶颈。9X9围棋的状态空间是10^85次方,复杂度小于国际象棋,然而迄今为止9X9电脑围棋仍然落后人脑。
基于以上原因目前多数围棋程序没有使用电脑象棋的搜索方法来利用计算机的计算能力,而是把开发者的围棋知识直接写到程序中辅以少量的局部搜索和模式数据库。开局时使用定式库,中盘利用模式库和搜索把棋子分块,对每块棋判断死活,如果是本方死活不明块,判断是否需要补强,如果是对方死活不明块,判断是否可以进攻,哪些地域是自己控制的,哪些是对方控制的,哪些是双方都有机会。完成棋盘状态判断后,程序选择一个目标:攻击,补强或者占地。对每一个目标,有一个模式库建议可行的下一步。计算计围棋的收官研究相对较好,使用的技术是把整个棋盘分块,由于棋近结束,变化很少,每块相对独立,只要在块内搜索即可,计算机的收官技术已经达到职业棋手水平,另外封闭空间的死活研究也达到了职业棋手水平。 |