对大家来说，象棋残局库现在应该已经不是什么陌生的东西了吧。当年吴韧博士通过建立残局库证明了炮高兵单仕相例胜士象全，这个结论轰动一时，其中一盘例局被称为《上帝是怎样下棋的》。一开始很多人都是不信的，但现在几乎没人说这种话了。现在残局库不断发展，一些更复杂的结论都出现了，相比之下，炮高兵单仕相例胜士象全早就不算什么了。但是对于人脑来说，尝试消化吸收炮高兵单仕相例胜士象全的解法依然是很困难的。

我并不是想在这里拆解残局，否则直接发到象棋吧也就是了。我是想要介绍一下残局库的基本原理。
如何建立一个炮兵单仕相对士象全的残局库呢？
首先要列举出炮兵单仕相对士象全及其衍生局的所有可能局面。这里的衍生局指的是经过吃子以后可能形成的局面，例如红方吃掉黑方一象衍生出炮兵单仕相对单缺象，黑方再反吃红兵又衍生出炮单仕相对单缺象，等等。
顺便提一句，“局面”这个概念除了包括棋子的摆放位置以外，还应该包括当前轮到谁走。也就是说，相同的棋子摆放位置，轮到红方走和轮到黑方走算两个不同的局面。
列举并存储这些局面需要相当的存储空间，所以要建残局库，需要强大的硬件支持。限于存储空间，建立十几个子的残局库已经很困难，估计硬件水平的提升不会没有上限，所以想要建立全32子的残局库是没有可能的。
列出的这些局面里，有一些是红方已经获胜的，即轮到黑方走，黑方已经被将死或困毙。我们把这些局面标记为“红胜0步”。
当然炮兵单仕相对士象全是不存在黑胜可能的，如果要建立的双方都有进攻子力残局库，那么就要双向考虑了。
然后检索所有轮到红方走棋的局面。如果某个局面下，红方可以走一步棋，使局面演化成“红胜0步”局面，那么这个局面就标记为“红胜1步”。
接下来检索轮到黑方走棋，而又未被标记过的局面。如果某个局面下，黑方无论怎么走，局面都会演化成“红胜1步”局面，那么这个局面就标记为“红胜2步”。
依此类推……
检索轮到红方走棋，而又未被标记过的局面。如果某个局面下，红方可以走一步棋，使局面演化成“红胜2n步”局面，那么这个局面就标记为“红胜2n+1步”。
检索轮到黑方走棋，而又未被标记过的局面。如果某个局面下，黑方无论怎么走，局面都会演化成“红胜≤2n+1步”局面，那么这个局面就标记为“红胜2n+2步”。
直到某一轮检索时，发现本轮检索完之后，没有新增加的标记局面，那么这个检索过程可以就结束了。
剩下还没有被标记过的局面，一律被标记为“和棋”。
这样残局库建立完成，我们就可以用它来解残局了。
如果我们的初始局面被标记为“红胜75步”，那么就会发现，红方目前可以走的所有着法里，有一种（或并列几种）着法可以使局面演化成“红胜74步”，而其他着法则可能导致和棋，或者导致红方要超过76步以上才能获胜。所以能使局面演化成“红胜74步”的着法就是当前红方的最佳着法。
然后轮到黑方走，黑方目前可以走的所有着法里，有一种（或并列几种）着法可以使局面演化成“红胜73步”，而其他着法则可能导致红方少于71步即可获胜。所以能使局面演化成“红胜73步”的着法就是当前黑方的最佳着法。
依此类推，一直演化到“红胜0步”，对局结束。把这75步串联起来，就是这个残局的一条主线解法。

当然，实际残局库还有其他问题需要考虑，例如棋例问题，出现循环局面应该判和棋还是一方必须变着？西洋棋残局库没有这种问题，因为西洋棋规则是所有的循环一律判和棋。但是象棋的棋例裁决是一个编程难点。
另外残局库还分为DTC和DTM两种模式，上面所讲的思路是DTM模式，DTC模式是局面分为若干个层次，然后最优着法的选择原则不再是最快获胜，而是最快降阶。
这些问题不再详述。

除了象棋残局以外，这种思想可以用在其他很多地方。
例1
过河问题：有三个人带着三个鬼要过一条河，现在只有一条船，可以乘坐两人/两鬼/一人一鬼，人和鬼都会划船。如果在某一岸，鬼的数量多于人的数量，鬼就会把身边的人吃掉。其他情况下，人鬼都可以相安无事。怎样才能顺利渡河？

把所有可能的局面列举出来，一共只有32种，人力就可以做到。
每个局面可以用三位数字来表示，第一个数字表示起点处人的数量（0~3），第二个数字表示起点处鬼的数量（0~3），第三个数字表示船的位置（1表示船在起点，0表示船在终点）例如起始局面就记作331，目标局面记作000。
根据规则，其中有一些局面出现了某一岸鬼比人多的情况，导致失败，我们首先把这些局面排除掉，在步数一栏标记-1。这种局面共12，还剩20个局面。
我们的最终目标是形成000局面，因此在这个局面的步数一栏标记0。当然001局面也可以标记0，不过没有什么意义，因为这个局面是走不出来的。
接下来，我们检索一下，有哪些局面可以在一步之内走到000局面的，显然我们只要检索船在起点的局面即可。检索出111、021、011这三个局面，在步数一栏标记为1，顺便记下它们下一步最佳选择的局面编号32。
再检索哪些局面可以形成刚才这三个被标记为1的局面，这次只要检索船在终点的局面即可。只检索出010一个局面，在步数一栏标记为2，它下一步可以走到11号或14号，并列最佳，任选其一即可。
依此类推，一直检索下去：
还剩下3个局面没有标记步数，这些局面就是死局了。很好理解这三个局面为什么无解：330，人和鬼都在起点，船自己跑到终点了，等于没船；301和030，人都在一岸，鬼都在另一岸，船在人这边，现在人只要过去就等于送死。这三个局面同样标记为-1。

残局库建立完成，现在就可以查找解法了。
初始局面是1号，需要11步，根据“下一步”的指引，解法依次是1（331）→19（310）→2（321）→20（300）→3（311）→27（110）→6（221）→30（020）→13（031）→31（010）→11（111）→32（000）

过河问题2：一个猎人带着一条狗，两个大人各带两个孩子一起过河，现在只有一条船，可以乘坐两人/一人一狗。其中只有猎人和两家的大人会划船。如果猎人不在场，狗会咬人；如果某家大人不在，另一家大人就会欺负他的孩子。怎样才能顺利渡河？
所有可能的局面有288种（如果考虑对称性是140种，但是这里就不管对称性了），依然是人力可以做到的。其中大量局面都会出现狗咬人或大人欺负孩子的情况，把这些排除掉之后还剩84种。因为表格太长了，我把这那些局面标注之后隐藏掉，只展示剩下的84种。
需要17步，解法依次是1（1112121）→253（0012120）→37（1012121）→254（0012110）→2（1112111）→150（1112000）→3（1112101）→168（1102000）→6（1112001）→258（0012000）→111（0012101）→276（0002000）→114（0012001）→282（0001000）→30（1101001）→252（0100000）→36（1100001）→288（0000000）

过河问题3：一个猎人带着一条狗，两个大人各带一个孩子一起过河，现在只有一条船，可以乘坐两人/一人一狗。其中只有猎人和其中一家的大人会划船。如果猎人不在场，狗会咬人；如果某家大人不在，另一家大人就会欺负他的孩子。怎样才能顺利渡河？
所有可能的局面有128种，排除狗咬人，大人欺负孩子的局面之后还剩下44种。
初始局面是1号局面，可以看出是无解的。
这道题目是网上一些无良人士乱改出来的，珍爱生命，远离无良改题。

作业：小卡、阿之、小陌、傀儡四人要一起过河，傀儡带着一箱粽子，小陌带着一箱月饼。现在只有一条船，可以乘坐两人/一人一箱，四个人都会划船。如果傀儡不在，小卡和小陌会偷吃粽子；如果小陌不在，小卡和傀儡会偷吃月饼；如果小卡不在，傀儡和小陌会欺负阿之。怎样才能顺利渡河？

迷宫1：
迷宫的解法：在靠近迷宫出口一格标记1，与1相邻而又未被标注的格子标注2，与2相邻而又未被标注的格子标注3，依此类推。
直至全部标记完成。
从入口开始，朝着数字减少的方向走即可，这就是一条最短路线。

1

迷宫2：
这个迷宫和上一个迷宫的区别在于它不是方方正正的，没有天然的一个个方格，但依然可以做一下划分，人为地把它分成若干格。划分没有固定的方法，总之以看起来方便为原则，未必要划分成特别规则的形状，疏密程度也不特别重要。
当然，如果你就只把一个迷宫划分成两块，从原理上说，是没错，先经过2号格，再经过1号格到达终点。可问题是，这两个格子的形状依然很复杂，在2号格内部具体怎么走？在1号格内部具体又怎么走？相当于问题依然没有解决。反过来说，格子划分得无限密集，标记起来又费劲了。
迷宫解法如下：

在前面一例规则形状的迷宫中，如果存在多条路径，按照这种方法解出来的路径一定是最短路径；但是在后面一例不规则形状迷宫中，只能说解出来的是“经过格子数”最少的路径，是否最短就不好说了，毕竟每个格子的大小还不相同。
当然这就不是算法的问题了，即使是画两条曲线，让你比较它们的长短，这本身也不见得是个很容易的任务。

猫捉老鼠1
初始位置如图所示，老鼠先走，双方交替行动，每次走一格，不允许原地不动。老鼠在1号位的时候，猫不允许吃老鼠。
问：猫能吃到老鼠吗？
前面的例子，过河问题以及迷宫都是单人任务，中间不存在双方博弈。而这道题目就不同了，猫和老鼠的任务目标是完全相反的，猫要抓住老鼠，而老鼠则要尽可能躲避猫。但是因为老鼠没有反杀猫的能力，所以并不存在经典意义上的“胜利”条件，只能谋求“守和”。至于说，对于老鼠守和就是胜利，那是另一个层面上的问题，这就有点类似于胡规的“和棋黑胜”了。
从某种意义上讲，这个题目除了规模很小以外，在要素上比较接近开篇提到的炮兵单仕相对士象全了，士象全方同样也没有反杀炮兵方的能力，目标就只是守和。
对了，规则中提到的“老鼠在1号位的时候，猫不允许吃老鼠”要怎样理解？因为这是原话，所以我就直接搬了过来。我认为最自然的理解就是类似于军旗里的行营，一方占据了1号位，另一方就不允许进入。有人说，猫和老鼠可以在1号位共存，只是不能吃而已。如果按照这种规则，结果会有很大差别，这个我们后面再说
用3位数字表示每种局面，第1位表示猫在几号位，第2位表示老鼠在几号位，第3位表示行动方，1表示轮到猫行动，0表示轮到老鼠行动。
结果如下：
可以看出，猫能抓住老鼠的局面是相当少的，在步数一栏中出现的最大的数字也就是3而已，可以说，如果老鼠不是主动送到猫旁边，猫几乎是没有可能抓住老鼠的。
初始局面猫2鼠3，老鼠先手，也就是第45号局面，猫是抓不住老鼠的。

作业：上述题目中如果去掉1号位的保护规则，猫能吃到老鼠吗？需要多少步？