隔空棋

lulijie

n*n的棋盘，甲乙玩一种游戏，规则如下：
1. 甲乙两人轮流往棋盘上放棋子，每次放一个棋子在格子上。
2. 放棋子的位置不限，但不能和棋盘上已放的棋子相邻（前后左右斜角一步的地方都算相邻），也不能放在有棋子的格子上。
3.谁最后无棋可放就算输。
－－－－－－－－－－－－－－－－－－
请问：对于特定的n，先行方胜，还是后手方胜？有没有什么规律？
显然n＝2，n＝3都是先先行方胜。

lulijie

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

phileas

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

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

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

lulijie

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

lulijie

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

lulijie

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

phileas

nim值法的优势在于，通过子游戏的值能很快得到母游戏的值。
在两维的情况下，一次操作并不一定会把整个棋盘变成两个或多个互不相关的子游戏。
所以计算nim值的计算量并不小，可能仅比穷举稍微少一点点。

但是nim值法仍然有其优势，就是当两个人用多个棋盘下棋时，直接把nim值异或就可以解决。

考虑了一下两维甚至多维的编程：把棋盘上的一格对应到两进制数的一位，如果允许下在某格，那么该位为1；如果不允许下在某格，那么该位为0；这样，任何棋盘状态都能一一对应到非负整数。每下一手，是把数字中若干位从1变成0。

用这个状态编码的方式编程，应该并不困难，也不容易出错。

lulijie

对于n=4，先手方败。
直接在棋盘上试，很容易就可解出。
第一步（先手方）根据对称性只有3种放法，后手方接着都可以走成使：  剩下互不相关的全等的两段，稳稳获胜。
但若用状态的递推或Nim值法，觉得解出n=4都异常麻烦。不知有没有好的方法。

wwd_meng

为啥要扩大到（n+2）＊（n+2）？

superacid

原帖由 noski 于 2009-10-10 01:04 发表
偶数的没看出来规律，感觉先下会输，明天再想。。

已经是1点了...