什么是人机?自从有象棋软件问世以后,网络对局的招数也就越来越精准了。如果你要看完纯机对局以后再看一篇人机高手的对局就会对比发现的人机下棋更人性化。真正的人机高手的过人之处就是在于能把一盘沉闷的棋局下得富有想象力和创造力,既能弥补纯人高手的对局计算深度不够,又能充分展现棋局的大局观。 |
怎样利用软件的层数
到此为止,我们知道的所有搜索算法,都把局面推演到固定的深度。但是这未必是件好事。例如,假设你的程序最多可以用迭代加深的Alpha-Beta算法搜索到5层,那么来看下这几个例子:
2. 现在假设在5层你吃到了兵。程序可能会认为这个局面稍稍有利,并且会这么走下去。然而,如果你看得更深远些,可能会发现吃了兵以后你的后就处于被攻击的状态,完了!
3. 最后,假设你的后被捉了,不管你怎么走,她会在第4层被对手吃掉,但是有一条路线可以让她坚持到第6层。如果你的搜索深度是5,那么后在第4层被吃掉的路线会被检测出来,这些情况会评估成灾难局面,但是唯一能使后在第6层(超出了搜索树)捉到的那条路线,对于电脑来说被吃是不能被发现的,因此它会认为后很安全,从而打一个较高的分数。现在,为了让后被吃的情况排除在搜索树以外,唯一的办法就是调虎离山,这样做是很冒险的--牺牲一些局面,还是有可能让对手犯下错误让你的后溜掉的。那么如果你要通过牺牲一个车来延缓后的被吃呢?对电脑来说,在第4层丢车要比丢后损失小,所以在这个搜索水平上,它情愿丢一个那么大的子,来推迟那个可怜的后的被吃了。(当然在随后一回合里,电脑会发现无论怎么走,它的后会在第4层被吃掉,并且车丢得莫名其妙。)很早以前Hans Berliner就把这个情况称为"水平线效应",这在很大程度上可以通过后面即将介绍的"静态搜索"来改善。
最后要说一句:象棋中的很多局面(其他游戏也一样)太不可预测了,实在很难恰当地评估。评价函数只能在"安静"的局面下起作用,即这些局面在不久的将来不可能发生很大的变化。
静态搜索的最基本的概念是指:当程序搜索到固定深度时(比如6层),我们选择性地继续各条路线,只搜索"非静态"的着法,直到找到静态着止,这样才开始评估。
找到静态局面是需要游戏知识的。例如,什么样的着法可能引起棋盘上子力平衡的巨大改变?对于象棋来说,子力平衡会导致局面的剧烈变化,所以任何改变子力的着法就是--吃(特别是吃主要棋子)、兵的升变都是,而将军也是值得一看的(仅仅是能导致将死的将军)。【译注:我认为任何将军都应该考虑进去,因为它会导致抽吃、长将等决定性局面的产生】。在西洋棋里,吃子和升变【西洋棋的棋子分兵棋(Man)和王棋(King),兵棋冲到底线就变成王棋,因此我断定它是国际象棋的前身】都是选择。在黑白棋中,每一步都必须吃子,并且"子力平衡"【仅仅指目前棋子的多少,它和最终棋子的多少没多大联系】在短时间内翻覆无常,所以可以说它根本不存在"静态局面"!
我自己的程序用了简单的静态搜索,它只考虑所有带吃子着法的线路(在x层完全搜索以后)。由于通常局面下没有太多合理的吃子着法,所以静态搜索的分枝因子非常小(平均在4-6,双方在吃子后会迅速下降到0)。但是,静态搜索算法要分析大量的局面,它可能会占用整个处理器一半以上的时间。当你的程序使用这个方案以前,你要确定你是否需要用它。
当没有吃子发生时,我的程序才开始评价局面。其结果就是将层数固定的搜索树作选择性的扩展,它能克服大多数由"水平线效应"产生的后果。
重要的空着
有个加快象棋程序速度的有效方法,就是引入空着的概念。
简而言之,空着就是自己不走而让对手连走两次。大多数局面中,什么事都不做显然不是办法,你总是必须做点事情来改善局面。(老实说,有一些"走也不是,不走也不是"的局面,空着确实是你的最佳选择,但不能走,但是这种 "被迫移动"(Zugzwang)局面是没有指望的,所以不必对电脑感到失望。)
在搜索中让电脑走空着,可以提高速度和准确性。例如:
2. 假设在静态搜索中,你面对一个只有车吃兵一种吃子着法的局面,然而接下来对手就会走马吃车。你最好不去吃子而走其他不吃子的着法对吗?你可以在静态搜索中插入空着来模拟这种情况,如果在某个局面下空着比其他吃子着法有利,那么你继续吃子就是坏的选择。并且由于最佳着法是静态着法,所以这个局面就是评估函数可以作用的局面。
总的来说,空着启发会减少20%到75%的搜索时间。这当然值得,特别是当你把这个方法用在静态搜索算法上的时候,就像改变"走子的一方"这种代码一样简单,用不了十行就行了。
【很多书上把“空着”这一技术称为“空着启发”(Null-Move Heuristic),本文就是这个意思,事实上在历史表、迭代加深等启发的作用下,空着启发已经意义不大了。现在绝大多数程序都使用了称为“空着的向前裁剪”(Null-Move Forward Pruning)的搜索(它跟空着启发是有区别的),尽管是一种不完全搜索,但它却是诸多向前裁剪的搜索中最有效的一个。】
期望搜索和MTD(f)
普通的老式Alpha-Beta搜索对某个局面最终的"最小-最大"值没有假设。看上去它考虑到任何情况,无论有多反常。但是,如果你有一个非常好的主意(例如由于你在做迭代加深,从而想到前一次的结果),你就会找出那些和你预期的差得远的路线,预先把它们截断。
例如,假设一个局面的值接近于0,因为非常均衡。现在来假设对一个内部结点作先前的评价,它的值在+20,000【这里的单位应该是"千分兵值", 即1000相当于一个兵的价值,那么马和象等于3000,车5000,后9000,其他因素也折算成这个值,而UCI协议中则用"百分兵值",因为没有必要过于精确】,那么你可以有充分信心对它截断。
这就是"期望搜索"(Aspiration Search)背后的思想,一个Alpha-Beta搜索的变种,开始时用-¥到+¥来限定搜索范围,然后在期望值附近设置小的窗口。如果实际数值恰好落在窗口以内,那么你赢了,你会准确无误地找到路线,并且比其他的路线快(因为很多路线都被截断了)。如果没有,那么算法就失败了,但是这个错误是很容易被检测的(因为"最小-最大"值就是其中一条边界),你必须浪费一点时间,用一个更大的窗口重新搜索。如果前面的情况比后面的情况多,那么总体上你还是赢了。很明显,你预先猜的数值越好,这个技术的收效就越大。
在上世纪90年代中期,研究员Aske Plaat把期望搜索拓展为一个逻辑问题:如果你把带期望的Alpha-Beta搜索的窗口大小设定成0,将会发生什么事?它当然永远不会成功。但是如果它成功了,那速度将是惊人的,因为它把几乎所有的路线全都截断了。现在,如果失败意味着实际数值低于你的估计,那么你用稍低点的宽度为零的窗口再试一次,重复下去。这样,你就等于用Alpha-Beta搜索来做某个"最小-最大"值的拆半查找(Binary Search),直到你最终找到那个宽度为零的窗口。
这个伟大的设想发表在一个网站上 http://theory.lcs.mit.edu/~plaat/mtdf.html,它的具体实现称为MTD(f)搜索算法,只有十多行。加上Alpha-Beta搜索和换位表的运用,MTD(f)呈现出惊人的效率,还善于做并行计算。它在"粗糙"(简单且快速)的局面分析中运行得更好,很明显,如果局面评估的最小单位越大(例如从0.001个兵增加到0.1个兵),它搜索的步数就越少。
在Alpha-Beta搜索的变种当中,还有很多具有广泛用途的算法(例如声名狼藉的NegaScout,我宁可给白痴讲广义相对论,也不想给你们讲这些)【之所以说NegaScout名声狼藉,是因为它的发明者Reinefeld首次发表该算法时,程序中有一个致命错误,导致搜索效率大幅度降低,甚至低于普通的Alpha-Beta搜索,如今这个算法更多地被PVS(主要变例搜索)取代,因为它更容易理解】,但是Plaat坚持认为MTD(f)是至今为止效率最高的算法。我就信了他的话,所以我的程序里用了MTD(f),你们可能会感叹这个算法是多么简短啊!
【MTD(f)在整个过程中只使用极小窗口,并且每次都从根结点开始的,这个过程极大程度地依赖于置换表,称为“用存储器增强的试探驱动器”(Memory-enhanced Test Driver,简称MTD),它只需要传递两个参数(深度n和试探值f),故得名为MTD(n,f),缩写为MTD(f)。实际运作中MTD(f)是以迭代的形式收敛的,而不是原作者所说的拆半查找。
在Plaat的文章中,MTD(f)的代码有10行,而跟它异曲同工的算法PVS,则只比普通的Alpha-Beta多了5行左右,因此很奇怪原作者(Laramée)为什么如此看好MTD(f)。MTD(f)在并行计算上确实比PVS有优势,由于Plaat等人拿MTD(f)和PVS算法的比较是在并行机上完成的,才得出MTD(f)优于PVS的结论,而事实上大部分的程序用的都是PVS。】
单步延伸
在我们结束这个主题以前,这是最后一个话题。在象棋中,有些着法明显比其他的好,这样就可能没必要搜索其他的变化了。
例如,假设你在迭代加深过程中正在做深度为N-1的搜索,发现某步的评分为+9000(即你吃了对方的后),而其他都低于0。如果像比赛一样想节约时间,你会跳过前面的N层搜索而对这步进行N层搜索【对于这步来说,搜索加深了一层,对于优势局面来说,优势应该是越来越大的,所以加深一层后评分应通常要高】,如果这步额外搜索的评分不比预期的低,那么你可以假设这步棋会比其他着法都好,这样你就可以提前结束搜索了。(记住,如果平均每层有35种合理着法,那么你就可能节省97%的时间!)
深蓝的小组发展了这个思想并提出了"单步延伸"(Singular Extension)的概念。如果在搜索中某步看上去比其他变化好很多,它就会加深这步搜索以确认里边没有陷阱。(实际过程远比这里说的要复杂,当然基本思想没变。)单步延伸是耗费时间的,对一个结点增加一层搜索会使搜索树的大小翻一番,评估局面的计算量同时也翻一番。换句话说,只有深蓝那种硬件水平才吃得消它,我那笨拙的Java代码肯定不行。但是它的成效是不可否认的,不是吗?
一、机器篇
二、软件篇
软件在人机中很重要,好的软件可以在很低层次得到正解,对于低端机器尤其重要!!!但是最近的四大棋软的棋力可以说是各有所长、难分高下。因此只有选择适合自己的软件就好了!!我个人最近经常使用旋风320,因为它的人机功能确实不错!!!可惜的是它的后台思考不能直接行棋!耽误了一些时间!他的棋路偏窄!有时候只有一种思路,而天机的思路要宽的多,这或许和剪支的多少有关系吧!另外两个软件:大圣由于很依赖机器,俺的低端电脑很少使用!!奇兵中局已经不占有优势,因此一般在残局使用!!!
合理设置软件也很重要。它可以使软件发挥出最大的威力!!软件当然要根据自己的机器来设置,不是千篇一律的!!软件hash值的多少可以自己通过比较得出!!!比如分别设置为32M、64M、96M等,然后找个局面分别测试,最快达到一定层次的就是你的机器的最佳选择!!!我的机器一般用默认的32M。在分析模式下时间一般不用怎么设置,主要设置好层次就可以了。我一般设置13层出子。如果机器好可以设置15层甚至更高!!!在读秒的时候可以设置为40-50秒出子。
三、人篇
(1)1rb1kab2/4a2c1/2n3R2/p1C1p3p/9/4C1P2/P1p1r3P/9/4AR3/2BAK1B2 r
正着:红炮五进四
(2)3ckab2/4a4/4b4/1r6p/4C2r1/p2R2C2/n1P1P3P/N3B2c1/4A4/4KABR1 b
炮8平1弃子入局
(3)3aka3/9/9/R8/2PP2P2/8P/3r5/4B3B/9/c1Cc1K3 b
炮4退5弃子入局
(4)1r2kabr1/4a4/2C1b2c1/p3p3p/1c3n3/2p3R2/P3P3P/N3C1N2/7R1/2BAKAB2 b
炮8平3弃子
(5)1rbaka3/9/2n1b1c2/p3p3p/9/1NR6/P3P1c1n/4C2rN/1C2A4/1RBAK1B2 b
后炮进7
(6)1C2kab2/4a4/3rb3n/9/PNc1c3p/9/6R2/2C1B4/4A4/2B1KA3 r
马八进七
(7)3ak1b2/4ar3/2R3nr1/p1p1p3p/6p2/2PN5/P3P3P/4C1N2/C3A4/2BAK3c r
正解:炮五平八!
因为他只管他范围之内的,其他的他是不管的!也就是说他只管他算到的,算不到的他就无能为力了!如果你的软件能算到13层,那么在这5-6步棋之内的他都没有问题。但是如果超出这个范围他就不管了!!!你整盘棋的输赢他更是不管的!而且贪吃和大局观不强、残局不会赢等更是他的软肋!因此要坚信自己,要有你自己的思路,你要做软件的领导!要软件做你的助手!一开始可能你有些不习惯,而且你棋力也确实不如他,做一个曾经是你领导的人的领导确实是很辛苦的!但是不要怕输棋!时间长了,相信你自己的棋力会大有提高!你慢慢的已经可以胜任做他的领导了!这个时候才是真正的人机,我们初步能达到的还只是机人操作!你想想如果有一天你能做到指挥棋软去战斗,那是多么爽的事情?
四、战略篇
是我的一个实战局面,对手名字记不住了。但是他的快棋是天罡!!!快2600分了,俺的快棋2300分还是用朋友的机器杀上去的呢。所以感觉对手强劲,不宜纠缠。此时天机开局是马8进7,以后对攻复杂,因此我直接选择了车一平四,简化了局面。双方无车,很快在他优势的情况下和棋了!!!
五、实战篇
(一)、开局
1、建议高配置机器先手走中炮或仙人指路布局,因为容易引起复杂对攻,高配置机器的速度优势可以充分发挥!!在复杂对攻中战胜对手!!而低配置机器建议走飞象等士象布局,减少对攻的局面,在平稳的局面下稳持先手,寻找机会,等待对手犯错误而战胜对手是个不错的选择!
2、开局方式不要多而要精!你选择一种适合你的开局,然后一直使用他!比如俺机器不好所以先手只用飞象布局!时间长了可以说几乎所有的应招你全清楚,其中的优劣你可以说了如指掌了,那么布局阶段你怎么可能吃亏呢?
3、下慢棋软件的开局库可以作为参考,但是不可以完全照搬。有的时候软件的开局还是有问题的。比如:旋风的这个局面下开局库居然走车1平6。
2bakabr1/r8/1c4nc1/p3p1p1p/1np6/5NP2/P1P1P3P/N1C1C4/9/R1BAKABR1 b
自己通过实践选出最佳的开局。开始的时候你可能需要软件的开局库,时间长了你就完全可以自己开局了!
(二)、中局
是我昨天下的一盘棋。江湖风雨情(6段)-胜-特洛伊木马(月将) 当时我已经占优了,但是离胜利还远。当时天机考虑的是炮二退七或退八。也没有问题,但是我感觉走车三退五更好,为什么呢?因为通过捉炮我可以活马,把马运到右侧则车马炮三子归边,速胜!!当然对方也可能一时不察,所以着了我的道,能战胜月将我很开心的。以下招法如下:车三退五炮4进1车三平四士5进6马六进七马1进2马七退五炮4平1车四平二炮1进3仕五退六将6平5车二进四将5退1马五进三车2平5车二平四车5进1仕四进五车5平7车四退一车7进2仕五退四
车7退7车四平三
这是今天下的一局棋,江湖风雨情(6段)-胜-杀了你好吗(3段) 是由飞象对左中跑演化而来的。最近对左中跑是输多赢少,很是郁闷。这局决定变招!此局面下天机102的开局库招法是车九进一,通过演变我感觉自己左侧空虚受攻,于是根据自己的理解让软件分析兵七进一,认为还可以,于是第一次改步。破坏了他原来的计划!!r1bakab2/4r4/2n1c4/p3n1p1p/1c7/2B1C1P2/P3P3P/1CN3N2/9/R1BAKA1R1 w
接下来几步形成了这个局面,软件再次考虑车九进一,因为对方很有可能把左车右调,我左侧压力很大再把九路车出来将很难抵挡黑方右侧的进攻。再次被我否定。我决定在他的左侧施加压力以缓解我左侧的压力而走出车二进九的招法。此时软件显示分并不高,只有0.26,但是我坚信自己的策略!接下来黑方没有理睬我,继续贯彻自己的思路,车5平4给我左侧施加压力!!后面软件没有给对方机会,经过交换以后双方残象,但是我的车路和马路都很灵活,多兵占优,此时黑车还在家里!!如果当时不改步则黑车早已经对我展开攻击了!!!
(三)、残局
太长,看不懂
从不知软件为何物
如此好文章,分段贴出,更易于阅读! |
|
怎样利用软件的层数
到此为止,我们知道的所有搜索算法,都把局面推演到固定的深度。但是这未必是件好事。例如,假设你的程序最多可以用迭代加深的Alpha-Beta算法搜索到5层,那么来看下这几个例子:
2. 现在假设在5层你吃到了兵。程序可能会认为这个局面稍稍有利,并且会这么走下去。然而,如果你看得更深远些,可能会发现吃了兵以后你的后就处于被攻击的状态,完了!
3. 最后,假设你的后被捉了,不管你怎么走,她会在第4层被对手吃掉,但是有一条路线可以让她坚持到第6层。如果你的搜索深度是5,那么后在第4层被吃掉的路线会被检测出来,这些情况会评估成灾难局面,但是唯一能使后在第6层(超出了搜索树)捉到的那条路线,对于电脑来说被吃是不能被发现的,因此它会认为后很安全,从而打一个较高的分数。现在,为了让后被吃的情况排除在搜索树以外,唯一的办法就是调虎离山,这样做是很冒险的--牺牲一些局面,还是有可能让对手犯下错误让你的后溜掉的。那么如果你要通过牺牲一个车来延缓后的被吃呢?对电脑来说,在第4层丢车要比丢后损失小,所以在这个搜索水平上,它情愿丢一个那么大的子,来推迟那个可怜的后的被吃了。(当然在随后一回合里,电脑会发现无论怎么走,它的后会在第4层被吃掉,并且车丢得莫名其妙。)很早以前Hans Berliner就把这个情况称为"水平线效应",这在很大程度上可以通过后面即将介绍的"静态搜索"来改善。
最后要说一句:象棋中的很多局面(其他游戏也一样)太不可预测了,实在很难恰当地评估。评价函数只能在"安静"的局面下起作用,即这些局面在不久的将来不可能发生很大的变化。
静态搜索的最基本的概念是指:当程序搜索到固定深度时(比如6层),我们选择性地继续各条路线,只搜索"非静态"的着法,直到找到静态着止,这样才开始评估。
找到静态局面是需要游戏知识的。例如,什么样的着法可能引起棋盘上子力平衡的巨大改变?对于象棋来说,子力平衡会导致局面的剧烈变化,所以任何改变子力的着法就是--吃(特别是吃主要棋子)、兵的升变都是,而将军也是值得一看的(仅仅是能导致将死的将军)。【译注:我认为任何将军都应该考虑进去,因为它会导致抽吃、长将等决定性局面的产生】。在西洋棋里,吃子和升变【西洋棋的棋子分兵棋(Man)和王棋(King),兵棋冲到底线就变成王棋,因此我断定它是国际象棋的前身】都是选择。在黑白棋中,每一步都必须吃子,并且"子力平衡"【仅仅指目前棋子的多少,它和最终棋子的多少没多大联系】在短时间内翻覆无常,所以可以说它根本不存在"静态局面"!
我自己的程序用了简单的静态搜索,它只考虑所有带吃子着法的线路(在x层完全搜索以后)。由于通常局面下没有太多合理的吃子着法,所以静态搜索的分枝因子非常小(平均在4-6,双方在吃子后会迅速下降到0)。但是,静态搜索算法要分析大量的局面,它可能会占用整个处理器一半以上的时间。当你的程序使用这个方案以前,你要确定你是否需要用它。
当没有吃子发生时,我的程序才开始评价局面。其结果就是将层数固定的搜索树作选择性的扩展,它能克服大多数由"水平线效应"产生的后果。
重要的空着
有个加快象棋程序速度的有效方法,就是引入空着的概念。
简而言之,空着就是自己不走而让对手连走两次。大多数局面中,什么事都不做显然不是办法,你总是必须做点事情来改善局面。(老实说,有一些"走也不是,不走也不是"的局面,空着确实是你的最佳选择,但不能走,但是这种 "被迫移动"(Zugzwang)局面是没有指望的,所以不必对电脑感到失望。)
在搜索中让电脑走空着,可以提高速度和准确性。例如:
2. 假设在静态搜索中,你面对一个只有车吃兵一种吃子着法的局面,然而接下来对手就会走马吃车。你最好不去吃子而走其他不吃子的着法对吗?你可以在静态搜索中插入空着来模拟这种情况,如果在某个局面下空着比其他吃子着法有利,那么你继续吃子就是坏的选择。并且由于最佳着法是静态着法,所以这个局面就是评估函数可以作用的局面。
总的来说,空着启发会减少20%到75%的搜索时间。这当然值得,特别是当你把这个方法用在静态搜索算法上的时候,就像改变"走子的一方"这种代码一样简单,用不了十行就行了。
【很多书上把“空着”这一技术称为“空着启发”(Null-Move Heuristic),本文就是这个意思,事实上在历史表、迭代加深等启发的作用下,空着启发已经意义不大了。现在绝大多数程序都使用了称为“空着的向前裁剪”(Null-Move Forward Pruning)的搜索(它跟空着启发是有区别的),尽管是一种不完全搜索,但它却是诸多向前裁剪的搜索中最有效的一个。】