隔空棋

lulijie

10楼用2进制来编码棋盘的局面是可行的方法。
但是也有缺点：
1。有些图形实际上是一样的，但由于在棋盘上位置不同，被变为不同的编码，增加了重复计算。
2。有些图形实际上是互相独立的两部分，可以用两个子图形来处理，但在编码时却变为1个图形，浪费了电脑的计算时间。
－－－－－－－－－－－
所以如何合理的编码以避免重复，以及如何自动区分出可以分开处理的两部分子图形，对于提高电脑的计算速度，我觉得是比较关键的。

lulijie

还有更关键的一点，从小的n值递推到大的n值时，如何保证相同图形编码的同一性。
这需要处理好，否则怎么能将前面计算出的结果应用于后面呢？

lulijie

举个例子：
4*4下   直3图形编码成 0111000000000000      16位2进制数
而到了6*6时，直3图形编码成 0111000000000000000000........     36位2进制数。
实际上它们是相同的图形，但电脑如何判断呢，如何利用4*4下 直3图形已计算出的结果应用于6*6的计算上呢？

phileas

第一解决棋盘扩大的问题。当棋盘从n*n扩大到(n+1)*(n+1)，多出了2n+1个格子，这些格子对应的位就放在两进制数的高位。

第二解决状态是否是独立的多个部分。从任何一位1开始试探相邻的格子，直至找到最大连通分支，去掉该连通分支后，再找剩下的，最终把一个状态分成独立（相互不连通）的多个子游戏。

第三考虑形状相同但是位置不同的问题。其实不仅要考虑位置不同（平移），要是把旋转和反射都考虑进去就更好了。所谓变换，就是把二进制的位换来换去，算法不明，但应该是可行的。不论怎么变换，目标是在最高位形成尽量多的连续的0，这样就可以转化为已经计算过的情况。

lulijie

楼上的几个解决方案有可行性，不过大大增加了程序设计的难度以及减慢了程序的运行速度。
我有个想法，不知是否可行。
对于任意n*n的棋盘，每个格子标以坐标(x,y)
对于所有剩下能放棋子的格子构成的图形，我们只要对这些格子的坐标运用某种方法进行计算，若该方法对于不同的图形计算出的结果不同，对于相同的图形计算出的结果相同，那么这种方法就可以用来区分不同的图形。
我想到   所有这些点（格子）的相互之间的距离的总和   是不是具有区分不同图形的上述这种功能。
还没有证明它。