探索五子棋先手必胜

Allis, Louis Victor在1994年用编程证明了五子棋无禁手规则下黑先必胜。如果放到现在做，第一反应肯定用与alphago类似的深度学习做，但是Allis在他的年代电脑算力相对不足，他通过穷举了所有的可能来实现。五子棋与围棋一个很大的差别是，围棋的落子可能选点是361减去当前手数（近似），而五子棋一方可能只有一两个。根据实际经验，黑棋下到某一阶段，可以在对白起持续产生威胁的情况下获胜，这时候黑棋的选点为持续生成活三或者冲4，白棋的选点是堵住黑棋，有限的选点让穷举成为可能。所以我当时的第一想法是，先写一个解残局的机器，然后人为分类开局的几步，当到了一定深度用残局机去判断是否成立，不行的话再增加深度，把所有可能放到数据库里，运行的时候在数据库里搜索。想法很好，但其实在写残局机的时候就遇到了最终也没解决的问题——跑的速度太慢。然而我自己觉得已经很难再继续剪枝，所以分析一下过程与最终问题。

先对残局机有个大概的定义。残局机下黑棋必须持续对白棋产生威胁，直到有连成五个子，如果黑棋的无论下哪里都没有活三或者冲四，则认为是无法产生威胁而失败。首先给程序搭个框架：

注意的是，这里在循环里调了递归，position对应着所以可能的位置（1：电脑ÿ