|
搜索(Search)
棋局估值(Position evaluation)
开局库(Opening book)
置换表(Transposition table)
棋步排序(Move ordering)
终局(Endgame)
1)搜索(Search)
当今所有强大的黑白棋程序，都是通过向前搜索许多步来确定棋局的最佳棋步：“如果我下这一步，他会下那一步，然后我再下那一步……，那么对我来说棋局有多大的优势？”所谓最佳棋步，就是下了这步棋后，对手下最佳应对、程序又下最佳应对……，最终会产生最佳棋局。这就是所谓的极大极小值搜索(minimax search)：对于程序来说，每步棋之后的棋局优势，程序是将其极大化，对手是将其极小化。
很明显，即使是很少的几步棋，所搜索的棋局数量也会急剧上升。在大多数中局棋局中，双方每步棋都有大约10步棋可选。只要前瞻9步(用程序员术语来说就是搜索深度为9)，就需要搜索10亿(10^9)个棋局。幸运的是，有研究表明，程序要找出最佳棋步，并不需要考虑所有这些棋局。一种被称为α-β剪枝(alpha-beta pruning)的程序取而代之，它大大减少所测试的棋局数量。这是70年代中期由唐纳德·克努特(Donald Knuth，中文名高德纳)和其他一些人发明的。其主要思路如下：对于我所考虑的一步棋，只要看到对手有步很强的应对，足以证明我这步棋不可能是最佳棋步，就没必要再去搜索其他更强的应对——因为我无论如何也不会去走这个变化。在有效情况下，这一简单的观察将大大减少需要搜索的棋局数量。所有强大的黑白棋程序(以及其他棋盘游戏程序，如国际象棋和跳棋)，都采用了这种算法的各种变形。典型情况下，Zebra前瞻9步只须考虑100 000~500 000个棋局；相对于不用α-β剪枝算法时需要考虑1 000 000 000个棋局而言，是大大减少了。 Zebra使用的是一种叫渴望负搜索(aspiration nega-scout)的变形，它是由亚历山大·赖讷费尔德(AlexanderReinefeld)发明的。
除了alpha-beta剪枝算法之外，Zebra还使用一种选择搜索机制。其思路非常简单，类似于人类棋手的思考方法：在大多数棋局中，许多棋步明显是坏棋，只需前瞻到足以判断出坏棋就可以了。其实现方式如下：当Zebra对棋局搜索12步时(即前瞻12步)，它先对所有棋步搜索4步，然后舍弃看起来相当坏的棋步，再对剩余的棋步搜索12步。关于由搜索4步来预测12步的可靠性，有大量的统计数字可作为“相当坏”的判别依据。该过程称为多重概率剪枝(Multi Prob-Cut)，是由迈克尔·布罗(Michael Buro)发明的。本例中使用了“剪枝对”4/12，对应于搜索深度3~18，Zebra使用15对不同的剪技对。
上述搜索算法使Zebra在中局能前瞻18~27步，经常能发现一些只有顶级计算机对手才能察觉到的诡秘战术陷阱。它的搜索速度达到大约是中局1 300 000~1 500 000棋局/秒、终局4 000 000~7 000 000棋局/秒。 (这些数据是在AMD雷鸟/1.33GHz上获得的。)
2)棋局估值(Position evaluation)
黑白棋程序所掌握的黑白棋知识，决定了程序的性能，这也是Zebra最重要的部分；如果程序无法解读所面临的棋局，再完美的搜索算法也无助于事。
高水平的人类棋手在中局总是努力增大行动力(mobility)、减少边缘子(frontier disc)数量，同时兼顾考虑边角结构。这些衡量标准如何写入程序呢？最成功的方法是把棋局分解成许多局部结构，这也是Zebra所使用的方法。对于每一个局部结构，如各行、各列、长度4~8的对角线、3x3角(例如a1、a2、a3、b1、b2、b3、c1、c2、c3)、5x2角(例如a1、a2、b1、b2、c1、c2、d1、d2、e1、e2)、以及边+相邻星位(例如a1、a2、a3、a4、a5、a6、a7、a8、b2、b7)，Zebra都会赋予一个对应的估值。为了评估整个棋局的价值，将上述局部结构对应的46个估值相累加；如果棋手下棋具有奇偶性(parity)，还要加上相应的附加值；其结果就是对局双方最终棋子数之差的估值。
估值函数中所使用的一系列模式(pattern)，表明程序所掌握的黑白棋知识，因此选择好的模式相当重要。另一方面是速度，复杂的模式会使程序变慢。Zebra所选用的模式可以十分快速地进行运算，而且很强大，足以牢固掌握有关棋局方面的知识。
现在主要的难题是：需要给许许多多不同的局部模式赋予对应的估值——仅仅是边就有3321个不同的边结构，如果算上所有的结构，会有上万个。更槽糕的是，不同结构所对应的估值又是和对局的不同阶段紧密相关的。毫无疑问，为所有结构评定估值的过程必须能自动完成。其实现过程是先获得大量高手对局的数据库，再计算出所有对局中每个阶段各个结构的统计数据。Zebra花了大约一周的时间，分析了100 000个对局，给1 000 000个不同的盘面模式评定了合适的估值。
3)局库(Opening book)
Zebra拥有一个包含经分析对局的大型数据库，在开局阶段(有时还会延伸到中局)用来选择棋步。开局库包含大约35 000个优秀对局，其中大约5 000个对局是由IOS上一些最优秀棋手所下的，其余的是由Zebra自己和自己对弈产生的。虽然程序自我对弈的设置各不相同，但是大多数对局的中局搜索深度都达到22步、胜负正确(WLD-correct)棋步达到28个空格。
开局库所含棋局的一些统计数据：
空格数 精确比分(Exactscore) 胜负正确(Win/loss/draw)
<= 23 100% 100%
24 30% 100%
25 14% 100%
26 12% 100%
27 12% 100%
28 11% 100%
29 0.6% 33%
30 0.5% 0.9%
31 0.5% 0.5%
32 0.4% 0.4%
33 0.4% 0.4%
4)置换表(Transposition table)
不同的下棋顺序经常会出现同一个棋局，Tiger开局定式就是这样的一个例子，它可以由f5-d6-c3-d3-c4下成，也可以由f5-d6-c4-d3-c3下成。两种下棋顺序的结果是同一个棋局，这就称为置换(Transposition)。为了避免多次搜索同一个棋局，Zebra将搜索过程中遇到的大多数棋局，都贮存在一个置换表中(用散列表数据结构来实现)。对于每个局面，Zebra的估值和搜索到的最佳棋步都被保存起来。在中局阶段，典型情况下可减少深度搜索时间20~50%。在终局阶段，置换的情况更普遍，其好处就更大了。
5)棋步排序(Move ordering)
对于α-β剪枝(alpha-beta pruning)，最先搜索棋局的最佳棋步是很有必要的。Zebra使用多种不同的启发式来达到这一目的：对于每一步棋，贮存了这步棋的“杀手应对(killer response)”——如果对手下星位(X-square)g2，我明显应该先看看能否占角h1、以及占角是否明智。另一种有用的启发式是先完成浅度搜索；在开始搜索12步之前，程序先对棋局搜索2步。在浅度搜索之后，找出看起来最好的棋步。相对于完全搜索来说，浅度搜索所花时间明显可以忽略不计。
6)终局(Endgame)
由于临近终局时双方棋手可下的棋步减少，Zebra在终局阶段可以搜索得更深远些。在势均力敌的对局中，当盘面还剩下25~35步棋可下时，Zebra通常就能判断出谁会获胜。在一边倒的对局中，Zebra会更早作出判断。完美下法(perfect-play)比分较比较难计算，但一般在盘面还剩下23~28步棋可下时也能计算出。
中局所使用的搜索算法同样适用于终局；但棋局估值功能会被关闭，因为所有变化都一直搜索到双方无棋可下为止。在真正开始终局搜索之前，使用多重概率剪枝(Multi Prob-Cut)的一种变形来初步判断比分，并找出看起来最好的棋步。 | 
窥视卡
雷达卡
楼主
显身卡