一种棋类游戏

056254628

8*8的国际象棋棋盘，甲乙玩一种游戏，规则如下：
1. 甲乙两人轮流往棋盘上放棋子，每次放一个棋子在格子上。
2. 放棋子的位置不限，但不能和棋盘上已放的棋子相邻（前后左右斜角一步的地方都算相邻），也不能放在有棋子的格子上。
3.谁最后无棋可放就算输。
-------------------------------------
请问是先手方胜，还是后手方胜？

mathe

这个计算机穷举就可以了,状态数不会太多.
估计是先手胜

056254628

2k-1  *   2k-1  都是先胜
2*2 先胜
4*4 先败

〇〇

bookmark

mathe

根据A063443,8*8的情况所有可能出现的局面数目为1355115601,稍微有点多,但是现在的计算机差不多能够处理.而且考虑对称性,大概只需要处理1/8的状态

〇〇

每次最少禁用3个格（角），其次6个格（边）最多禁用9个格

风云剑

我搜索出来8×8先手胜

风云剑

soory，程序有bug，呵呵。改了bug后运行很慢。

mathe

根据5#,状态总数目还是有点多的.为了避免使用外存储器
需要尽量减少状态总数目.所以对于每个状态,和它对称的状态(最多可以有8个)的信息就不要重复存储了.为此我们需要将每个状态映射到一个标准的状态.
在去除对称的状态后,余下状态数目还在170M左右,所以对每个状态数目的信息应该不超过8个字节,不然还难在内存中全部保存信息.而我们还必须使用hash表来保存所有状态,所以比较有难度.
不过比较可喜的是除了保存棋盘本身信息(每个格子是否有子)以外,我们另外只需要一个bit信息来记录对应棋盘是先手还是后手胜.而棋盘上面,任何一个2*2小棋盘里面最多1个棋子(所以最多5种情况).为此,我们可以将棋盘划分成16个互不相交的2*2的小棋盘,这样就可以用一个16为5进制数来保存棋盘状态.(38比特信息),另外加上一个bit用于记录这个棋盘的结果,那么还有25个比特可以用于解决冲突的情况.
不过这种方法下对内存的消耗还是挺大的.为了降低hash表冲突率,我们需要尽量hash表的大小.但是这种方法最多只能使用250M项的hash表.
当然我们可以将hash表每一项改成使用6个字节(48比特).优点是hash表中项的总数可以更大,从而可以降低冲突率,缺点是没有8个字节对齐,会降低访问内存的速度.

〇〇

只能穷举，没有策略？