4.7 如何更快地生成走法

既然走法生成算法要执行上万次，几十万次，得到更快的走法生成算法是很多程序员必然思考的问题。

4.7.1 事先生成法

如果在程序启动时，预先生成一个局面的全部走法并保存起来，那么在搜索算法需要一个局面的走法时，就可以直接把这些走法取出来使用，而不是一个一个的去计算。这样可能是最快的走法生成算法了。浪费一些空间来换取时间是经常用到的想法。

那怎么知道搜索时会遇到哪种局面呢，显然在程序启动时是不可能知道的。只有一种可能，就是把所有可能的局面全部都计算一遍，保存所有局面的可能走法。那一盘棋究竟有多少种可能的局面呢？

将有9个位置可去。

两个士（仕）在五个位置上随意摆放，共5×4。

两个象（相）在七个位置上随意摆放，共7×6。

卒可以在半个棋盘上活动，在加上初始位置和本方河界位置，共47。五个卒就是47^5。

车马炮可以走到棋盘任何一个位置，总共可能90^6。

一方棋子的所有可能为：9×(5×4)×(47^5)×(90^6) = 2e22

双方棋子所有可能位置为：（9×(5×4)×(47^5)×(90^6)）^2 = 4 e 44

这只是粗略估计。有很多重复位置被计算进去，如将占据中间位置，则士只能在其他四个位置；将占据九宫上方中间位置，则象只能在其他六个位置。如果车占据九宫一个位置，则将只能在其他八个位置，等等。

4 e 44个局面，实在太多了，不要说计算每一个局面可能的走法，就是存储这些局面都成问题。因此要计算所有局面可能的走法是不太现实的。

4.7.2 位行位列

那有没有可能预先计算个别棋子的走法，尤其是车炮的走法呢？为什么要特别考虑车炮的走法呢？从前面的算法也看出来，马象（相）士（仕）将（帅）卒（兵）的走法都比较简单，除了马有8种可能的位置外，其他都不超过4种可能，计算起来相对不是太困难。车炮的走法比较复杂，可以沿4个方向前进，每个方向都有多种可能，比较耗费时间。如果能预先计算出走法，则在搜索时可以节省很多时间。

车炮走法虽然复杂，但它们都只是沿着直线行走，生成走法时只考虑它所在行和列的情况，而与棋盘其他位置无关。一行有9列，棋子落在这一行有多少种可能的情况出现呢？如图4-8所示的棋盘局面。

将棋盘上有棋子的地方置1，无棋子的地方置0，如图4-9所示。

考察红方河界处的车，可以分别计算出车在四个方向的吃子位置如图4-10所示，如果不能吃子则位置初始化为0。不吃子位置可能很多，因此只计算出一个方向最远（大）的不吃子位置。

有了一个方向不吃子的最大位置，要计算一个方向所有的不吃子位置，依然需要进行一个循环。

但是吃子位置的价值重大。

（1）生成走法时，如果只生成吃子走法，则不需要循环，就可直接得到。在第12章中将要介绍在生成走法时，把吃子走法与不吃子走法分别生成。

（2）判断将军时，特别有效。如果车与对方将在同一行，则只需要判断对方的将是否在车的左右吃子位置即可，不用进行循环判断。

（3）在估值时，要判断一个棋子是否被车保护，则只需要判断该棋子是否在车的行（列）吃子位置，同样省掉一个循环。

每列有两种情况，有棋子和没有棋子，并不区别是哪一个棋子，总共有29=512种可能。即不论棋盘上棋子如何行走，每一行最多只有512种情况。车可能落在这一行的任何一个位置，那么要计算车沿行走棋的复杂度为512×9，车沿行最多有8种可能走法，所以需要辅助存储空间为512×9×8。

同理可以计算出每列需要的辅助空间。一列有10行，车沿列有9种可能走法，所以需要辅助存储空间为1024×10×9。

要能够快速得出车的走法，我们还必须保存每一行每一列的棋子情况，简称行数组和列数组。当一方走棋后，比如开局红方马二进三，有2行和2列发生了变化，必须记录下最新的行列情况。行数组和列数组也是冗余数据结构，要随时保持它和棋盘数组的一致性。

同理可以得到炮的位行位列走法，如图4-11所示。

推而广之，将和卒的走法也只和行列有关，既然保存了行数组和列数组，那我们也可以像车炮一样预先计算出将和卒的走法。