魔方吧·中文魔方俱乐部

标题: 隔空棋 [打印本页]

作者: lulijie 时间: 2009-10-10 00:11:13 标题: 隔空棋

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

作者: superacid 时间: 2009-10-10 00:29:05

这道题还是挺简单的，把棋盘扩充为(n+2)×(n+2)的，
然后每个棋子看成是3×3大小的，就简单多了，其他就不用多说了

作者: lulijie 时间: 2009-10-10 00:34:22

当把棋子看成3*3的时候对自己不利，他可以把棋子放到只相当于2*3，或2*2的位置；
还是有变数的。

作者: noski 时间: 2009-10-10 00:45:46

当n为奇数的时候，先行方把棋子放在棋盘的正中，然后后手方每放一个棋子，先行方都在其中心对称的地方放一个，这样，先行方必胜。

作者: lulijie 时间: 2009-10-10 00:54:17

noski火眼金睛。
n为偶数呢？

作者: noski 时间: 2009-10-10 01:04:19 标题: 回复 5# 的帖子

偶数的没看出来规律，感觉先下会输，明天再想。。

作者: superacid 时间: 2009-10-10 01:54:09

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

已经是1点了...

作者: wwd_meng 时间: 2009-10-10 07:01:11

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

作者: lulijie 时间: 2009-10-11 17:00:38

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

作者: phileas 时间: 2009-10-11 21:06:18

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

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

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

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

作者: lulijie 时间: 2009-10-13 00:08:44

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

作者: lulijie 时间: 2009-10-13 00:17:55

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

作者: lulijie 时间: 2009-10-13 00:27:33

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

作者: phileas 时间: 2009-10-13 12:16:59

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

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

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

作者: lulijie 时间: 2009-10-13 22:08:35

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

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)