围棋博弈程序的实现与思考（5）——提子算法

提子算法的好坏对整个程序的性能影响是很大的。尽管在实际对局中，提子行为并不经常发生，但每次落子时计算机都得判断是否需要提子。根据围棋规则，可得提子算法的步骤，以黑棋落子为例：

1）依次判断与该落子点相邻的白子所在棋串（棋盘上实线相连的棋子集）的气，如为0，则提走棋串。

2）如果1）中不存在提子行为，则计算该落子点所在棋串的气是否为0，若不为0，则落子合法，若为0则不合法。

这只是个粗略的步骤，其中涉及到两个问题：1）怎样取得棋串。2）怎样计算棋串的气。

一个显而易见的方法是——需要时深搜棋串，顺便求出棋串的气。这个方法的巨大cost也是可以想见的，因为存在大量的重复计算。于是考虑在棋局进行过程中保存棋串的数据结构——一种解决方案是把一个棋串作为一个循环链表，棋子作为链表的结点。这是个不错的方法，因为棋串的合并操作可以方便地进行，但具体实行起来又会碰到些问题需要解决——比如怎样快速地通过一个棋子找到所在的棋串链表。

我的方案显得简单一些，把棋串作为并查集的树形结构，树根的坐标可作为树的标号。同样可以方便地进行棋串合并操作。棋串在棋局进行过程中保存气的坐标，棋串合并时只需作或运算。