一种棋类游戏

056254628 · 发表于 2009-10-11 18:15:20

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

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

mathe · 发表于 2009-10-11 19:53:02

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

056254628 · 发表于 2009-10-11 20:15:36

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

〇〇 · 发表于 2009-10-11 20:41:57

bookmark

mathe · 发表于 2009-10-11 21:30:34

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

〇〇 · 发表于 2009-10-12 10:01:12

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

风云剑 · 发表于 2009-10-12 11:41:53

本帖最后由风云剑于 2009-10-12 11:44 编辑 我搜索出来8×8先手胜

风云剑 · 发表于 2009-10-12 11:52:36

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

mathe · 发表于 2009-10-13 12:03:19

根据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个字节对齐,会降低访问内存的速度.

〇〇 · 发表于 2009-10-13 14:03:35

只能穷举，没有策略？

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 一种棋类游戏

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。