很明显,即使是在仅有很少的几步棋之后,不断上升的局面数量也会快速增长; 在大多数中局局面中,每位棋手每步都大约有10步棋,因此仅仅前瞻九步(用程序员术语来说就是搜索深度为九), 结果就是10亿(10^9)个局面需要研究。幸运的是,数学上可以证明,为了找出最佳棋步,程序不需要考虑所有局面。 取而代之的是使用一种被称为α-β剪枝(alpha-beta pruning)的程序,它是70年代中期由高德纳(Donald Knuth)和其他一些人发明的, 能大大减少需要测试的局面数量。其主要思路如下:针对我的一步棋,如果对手有步很强的回应, 足以证明我所考虑的这步棋不可能是最佳棋步,那么就没必要再去搜索其他更强的回应——因为我无论如何也不会下这个变化。 在有效情况下,这一简单的观察将大大减少需要搜索的局面数量。所有强大的黑白棋程序(以及其他棋盘游戏程序,如国际象棋和跳棋), 都使用这种算法的各种变形。当前瞻9步时,Zebra典型地只需考虑100 000~500 000个局面; 相对于没有α-β剪枝时不得不考虑1 000 000 000个局面,是大大减少了。Zebra使用一种称为渴望负搜索(aspiration nega-scout)的变形, 它是由亚历山大·赖讷费尔德(Alexander Reinefeld)发明的。
除了α-β算法之外,Zebra还使用一种选择性搜索机制。其思路非常简单, 类似于人类棋手的思考方法:在大多数局面中,许多棋步明显是坏棋,只需考虑到足以确定它们是坏棋。 通常的实现方法如下:当局面搜索深度为12时(即向前12步),Zebra先对所有棋步搜索步,然后舍弃搜索4步时看起来相当坏的棋步, 再对剩余的棋步搜索12步。关于搜索4步预测搜索12步结果的准确性,通过产生大量相关统计数字,可以对“相当坏”的概念进行定性(formalize)。 这个程序称为多重概率剪枝(Multi Prob-Cut),是由迈克尔·布罗(Michael Buro)发明的。 上面实例使用了“剪枝对(cut pair)”4/12;对应于搜索深度3~18,Zebra使用15个不同的剪技对。
上述搜索算法使Zebra在中局可以前瞻18~27步,经常能发现一些只有顶级计算机对手才能察觉到的诡秘战术陷阱。 搜索速度大约是中局1 300 000~1 500 000局面/秒、终局4 000 000~7 000 000局面/秒。(这些数据是在AMD雷鸟/1.33GHz上获得的。)