|
很多棋友，尤其是一些具有一定水平的棋友，会认为征子只是简单的直线计算。但是这种想法可以说是有些幼稚的。有某些围甲选手在比赛中对于征子问题上也出现过笑话。这也许还可以解释为头脑一时间不清醒：的确如此，我不否认。那么，对于本文之后讨论的问题希望你能看一看，看过之后，我觉得你或许能够稍稍重新审视这个看法。 至少自《忘忧清乐集》开始，历史上就已经出现了关于征子的诘棋。唐明皇游月宫就是一个非常经典的征子诘棋：  正解图如下：  整个过程需要200余手，从左下开始，到左上结束。事实上，有些棋力比较高的棋友不会计算完整个过程，看个棋形大概就可以知道整个征子的过程与走向，可以推断出来最后必然在左上角结束。但是本文的初衷本就不是想给大家欣赏眼花缭乱的征子诘棋，而是想问一句，一个征子何以能够在狭小的棋盘上蜿蜒曲折如此多手？ 其中关隘就在于征子中的一个技巧，叫做“回龙征”。但凡是手数冗长的征子，很难避开这种征子方式。回龙征的最大特点在于，在征子的过程中，征子方向发生了改变。注意唐明皇游月宫的正解图的37到45，由于中间提前安置了数子，使得本应当去往右上的征子方向转向左上，后来又通过类似的方法转向左下，循环往复。这是征子诘棋中的小技巧，通过安放几子起到了征子转向的作用。引龙出水式也有相关技巧（可以阅读关于《忘忧清乐集》的引龙出水式）。我们这里将之用“镜子(Mirror)”来表示，下图是一个典型例子：  其中没有数字的4颗棋子就是所谓的:“镜子”，起到了征子转向的作用（征子其余过程已经省略）。 当然除了这个“镜子”之外，还有很多技巧可以使用。接下来我们进行简单的表述。需要说明的是，以下如非特别提及，全部默认黑棋为征子的一方，白棋为被征子的一方。 (1)黑的选择(Black choice) 在征子过程中，很有可能会出现征子的一方有着不同的将征子进行下去的方式，也就是说黑棋对于征子方向具有选择权。用一个例子说明这个情况：  假设征子从左上绵延至右下。此时黑棋无论走在A位还是B位，都依然是征吃状态（征子其余过程已经省略）。 (2)白的选择(White choice) 在征子过程中，很有可能会出现被征子的一方有着不同的将征子进行下去的方式，也就是说白棋对于征子方向具有选择权。用一个例子说明这个情况：  假设征子从左上绵延至右下。此时棋无论走在A位还是B位，都依然是征吃状态（征子其余过程已经省略）。 (3)联合(Join) 前面两个关注的是征子接触到特定棋形怎样出去，而所谓联合，指的是征子怎么进入到特定棋形。不同路径的征子进入到一个特定棋形依旧是征子，这种棋形叫做联合。举一个例子：   上面两张图展示了一个特定棋形如何起到了联合的作用：有两个征子方向进入这个棋形都可以形成征子。 下面我们从计算复杂度的角度上来思考一下征子的问题。 首先我们来说明，征子的复杂度是多项式空间(PSPACE)[1]的： 在通常情况下，征子过程中每走c步棋白棋被征吃的子就要加长。那么，受限于整个棋盘的大小，征吃的子不会无限延长，因此对于常数c，线性的搜索深度足以实现征子的搜索。但是还需要考虑一些特殊情况，比如在征子过程终遇到了打劫，那么分两种情况： （1）如果有4个劫及以上：此时对于白棋，至少有3个劫可以提，而对于黑棋，每次都只有2个选择。在这种情况下，按照禁全同的规则，必然是黑方先陷入循环，因此黑棋必须另走他处，导致征子失败。 （2) 如果至多3个劫：对于3劫，那么这3劫只有6种状态（001，010，011，100，101，110）。在禁全同规则下，这6种状态遍历过后，白棋必须选择延长征子长度而不能选择提劫。因此计算复杂度时只需要在棋盘大小所限制的复杂度上乘以6倍即可。因此征子的复杂度是多项式空间的。 接下来我们论证征子的复杂度是多项式空间完全(PSPACE-complete)的： 想要论证征子的复杂度是多项式空间完全(PSPACE-complete)的，一种方法就是找到一个已知的多项式空间完全问题（比如QBF(Quantified Boolean Formula)问题），并将其归约到征子问题上。这里简单说下QBF问题，这个问题可以表述为：对于给定的某个含有“存在”和“任意”符号的布尔表达式，判断其是否为真。举一个例子，给定一个布尔表达式：∃x∀y∃z(¬x∧¬y)∨(¬x∧y)∨(¬z∧(¬x∨z))，判断其是否为真，或者说判断：是否存在x使得对于任意y存在z使得(¬x∧¬y)∨(¬x∧y)∨(¬z∧(¬x∨z))成立。 现在我们要说明的关键问题就是，这个QBF问题，是如何能够归约到征子上的。我们对上面那个布尔表达式给出构造：  对于这个构造需要几点说明。 （1）这里的B,W,J,M分别是上文提到的黑的选择(Black choice),白的选择(White choice),联合(Join)和镜子(Mirror)。 （2）图中可见有3个菱形，分别是由BMMJ构成和WMMJ构成。在布尔表达式中，存在∃可以用BMMJ来进行表达，任意∀可以用WMMJ来表达。另外在菱形中间安置了白子，这是用来起到破坏征子的作用。这3个菱形所表达的含义就是∃x∀y∃z。 （3）3个菱形之外的其余部分，就是上述布尔表达式的后半段，也就是(¬x∧¬y)∨(¬x∧y)∨(¬z∧(¬x∨z))。其中，逻辑符号∨被B用来表达，而∧被W用来表达。子表达式分别递归到右上角和右下角。 （4）x,y,z分别代表征子方向向上（如果前面¬，则取相反方向）。 （5）征子过程中的菱形大小以及镜子的摆放位置保证各条征子路径不会相交。 这样的构造方式可以将任意QBF问题归约为一个征子问题。因此，征子问题就是多项式空间完全（PSPACE-complete)问题。 最后我们以一道征子题结束。思考一下，这个局面黑棋先行，能否吃掉下方白棋6子？  参考文献 [1] Crâsmaru, Marcel, and John Tromp. 'Ladders Are PSPACE-Complete.' annual conference on computers (2000): 241-249. |
|
|
