用一个数组来表示棋盘,对于很多游戏来说,就找不到更好的办法了。但是对于像象棋、西洋
跳棋之类在64格棋盘上的游戏来说,有一个高明的技巧——“位棋盘” (首先由苏联的KAISSA制作
组提出),在上世纪60年代末诞生了。
KAISSA是运行在64位处理器上的程序【我很怀疑当时就有64位处理器,或许当时处理器字长的
概念和现在的有所不同】。“64”恰巧是象棋棋盘格子的数目,所以这就有可能让一个字来表示一
个棋盘,以判断某个格子的状态是“是”或者“非”。例如,一个位棋盘可以回答棋盘的每个格子
“是否有白子”。【把位棋盘运用到中国象棋上,这是我将要进行的一个课题,中国象棋的棋盘有
90个格点,可以用3个32位的字来表示。】
因此,一个完整的局面需要用12个位棋盘表示:白兵、白车、黑兵等等。再加上两个用来表示
“所有白子”和“所有黑子”的位棋盘,以加快运算速度。【其实只需要8个就可以了,同一兵种
(不管黑白)用一个位棋盘,一共是6个,再加上代表“所有白子”和“所有黑子”的。做得更过分的
是,有人把象和后并作一个位棋盘,车和后并作一个位棋盘,这样又可以减少一个。如果要表示白
方的象,只要“所有白子”、“所有车或后”的补集(用“非”运算)、“所有象或后”这三个位棋盘
作“与”运算就可以了。】或许你还想用一个位棋盘表示被某种子力攻击到的格子,诸如此类,这
些位棋可以盘灵活运用在着法产生的运算过程中。
位棋盘之所以有效,是因为很多运算可以转化为处理器的一个逻辑指令。例如,假设你需要确
认黑王被白后将军,如果用简单的数组来表示棋盘,那么你需要这样做:
1. 首先找到后的位置,这需要从64个字节中一个一个地找;
2. 然后在后所能走的八个方向找,直到找到王或者找到后走不到的格子为止。
这些运算是相当花费时间的,如果后碰巧是在数组的最后一格,更糟的是,将军只会发生在少
数情况下【这种运算纯粹是白费时间!】。
如果用位棋盘,那你只要这样做:
1. 载入“白方后的位置”的位棋盘;
2. 根据这个位置,从索引数据库中找到被后攻击的位棋盘;
3. 用这个位棋盘和“黑方王的位置”的位棋盘作“与”运算。
如果结果不是零,则说明黑王被白后将军。假设被后攻击的位棋盘是储藏于存储器中的【这是
上面提到的第二步的前提】,那么整个操作只需要3到4个时钟周期【通常计算机执行1条指令需要
1(算术或逻辑运算)到2(寻址操作)个时钟周期】。
【这里允许我发挥一下,原作所说的“从索引的数据库中找到”(即上面提到的第二步),其实并
非是简单的一步,对于后的每个位置,都有一定的攻击格子(从边线到中心依次是21、23、25和27
格),但是要考虑被别的子阻挡的情况,程序无法为所有的情况都作索引,最多只能对某条线(横线、
纵线或斜线)的棋子占有情况作索引,这也需要2
8
= 256 种情况,再加后本身有64种位置,所以即使
这样,数据库中也至少要保存256x64 = 16384个位棋盘。另外,横线、纵线和两条斜线的处理方法各
不相同,横线只要作简单的“移位运算”就可以了,而纵线和两条斜线都要用到“位棋盘旋转”的
技术,为了提高运算效率,程序的复杂程度是惊人的,细节可以参考《对弈程序基本技术》专题之
《数据结构——旋转的位棋盘》一文,文中作者多次提示读者用咖啡来提神,以完成烦琐的程
序。】
再举一个例子,如果在当前的棋盘上,你要产生白马的所有着法,那么你只要找到当与前位置
相关联的“马能走到的格子”的位棋盘,并“与”(AND)上“所有被白方占有的格子”的位棋盘的
补集(就是对这个位棋盘作“非”(NOT)运算),因为马的着法限制仅仅在于它不能去吃自己的子。
【国际象棋比较简单,而中国象棋中还有“绊马腿”的限制(还有象也是),这种情况该怎样使用位棋
盘,也是我将要研究的课题。】
如果你想更详细地了解位棋盘(也只是稍微详细一点而已),可以去看看描述CHESS 4.5 (它是由
美国西北大学开发的)的文章——Peter Frey写的《人脑和电脑的象棋技巧》(Ches Skill in Man and
Machine),现在至少已经出了两版了,分别出版于1977年和1981年。