数学研发论坛

 找回密码
 欢迎注册
12
返回列表 发新帖
楼主: KeyTo9_Fans

[原创] 占地游戏的最佳策略

[复制链接]
发表于 2018-5-12 17:59:56 | 显示全部楼层

游戏规则明确一下:
1,空格。游戏开始前,有n个空格排成一排。
2,主格。A或B选定的格子叫主格。
3,副格。与主格相邻的1个或2个的格子叫副格。
4,主格可以是端格,副格也可以是端格。
5,主格只能在空格里选,不能在副格里选,
6,n个空格,双方至少要走n/3次,最多可以走n/2次。
7,每走1次,只有6种效果;
增加3个,消灭2个
增加3个,消灭1个
增加3个,消灭0个
增加2个,消灭1个
增加2个,消灭0个
增加1个,消灭0个





毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-14 09:31:18 | 显示全部楼层
前面提到的每个碎片,假设里面是k个连续空格,我们还需要根据两边端点的归属来分类。比如我们用T表示对应端点为游戏边界,A和B分别表示对应被A或B占用。那么比如TkB表示一个端点属于游戏边界,另外一个端点现在被B占用等。
另外我们知道任意一个局面中,最多使用了两个T.而我们需要计算特殊局面TnT.
局面T1A和T1B,先手可以额外得两格,所以我们可以认为这两个局面是$+-2$,
而局面A2A,A先手可以得到全部四格,B先手可以得到3格而失去1一格,相当于得到2格。所以对应局面是$3+-1$
由此我们得出所有空格不超过两格的局面的固定得分
T1A,T1B: $+-2$
A1A,A1B,B1B,T2A,T2B: $+-3$
A2A:$1+-3$
B2B:$-1+-3$
A2B:$+-4$
但是对于有3个以上空格情况,就有比较复杂的选择了。
比如选手A遇上T3B局面时,她可以转变为TAAAB,也可以转变为T1AAA, 前者固定2格,后者变为$1+-2$
在这个局面和其它局面的不同组合情况,需要做不同的选择,比如
{T3B},自然直接转化为{TAAAB}
而对于局面{T3B, T1B},最优选择是转化为{T1AAA,T1B}
而对于一个复杂局面,最终输赢数目在每类碎片数目充分多时,应该只取决于各类碎片数目的奇偶性
而为了得到最终公式,我们可以首先求出这种极限模式(每类碎片数目充分多),然后再求出那些不符合极限模式的特殊模式(其中有些碎片数目充分小)。
这个方法可以采用类似棋子问题中方法,只是这里状态数更多,分析起来会更加复杂

点评

另外由于所有基本状态分值都不超过4分,而各种组合状态可以最终也会转化为各种基本状态(存在多种选择)。双方会轮流选择各自对自己最有利的情况,所以先手最终得分应该不会小于0但是也无法大于4。  发表于 2018-5-14 11:45
关键是空格不小于3的状态都会出现多种选择,我们需要找出数目充分大模式下通常会被使用的选择以及找到数目不够大时的各种例外情况  发表于 2018-5-14 11:32
是的,这些固定得分的方案本质上只有三类。对于A2A,B2B之类方案,我们可以认为某一方已经获得了一部分固定收益,比如A2A方案A方已经取得了1的固定收益,于是A2A可以转化为AA1A,B2B可以转化为BB1B等。  发表于 2018-5-14 11:30
我觉得只需分$3$类:后手$4$目官子T1A,T1B;后手$6$目官子A1A,A1B,B1B,T2A,T2B,A2A,B2B;后手$8$目官子A2B。  发表于 2018-5-14 10:04

评分

参与人数 1威望 +2 金币 +2 贡献 +2 经验 +2 鲜花 +2 收起 理由
KeyTo9_Fans + 2 + 2 + 2 + 2 + 2 好方法

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-15 09:55:11 | 显示全部楼层
本帖最后由 王守恩 于 2018-5-15 18:07 编辑
王守恩 发表于 2018-5-12 17:59
游戏规则明确一下:
1,空格。游戏开始前,有n个空格排成一排。
2,主格。A或B选定的格子叫主格。


规律好像是这样的,可惜?处对不上。
1,当 n = 2K - 1时,  a(n) = K
01=01
03=03(?)
05=03
07=05(?)
09=05
11=07(?)
13=07
15=08
17=10(?)
19=10
21=11
23=12
25=13
27=14
29=15
31=16
33=17
35=18
..........
2,当 n = 2K - 2时,  a(n) = K
02=02
04=02(?)
06=04
08=05
10=05(?)
12=07
14=07(?)
16=09
18=09(?)
20=11
22=12
24=12(?)
26=14
28=15
30=16
32=17
34=18
36=19
..........
我们的思路跟着后手走,解法会简单些。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-17 13:49:25 | 显示全部楼层
把先手的最佳策略输出来,结果如下:
  1. o
  2. oo
  3. .o.
  4. .oo.
  5. ..o..
  6. o....o
  7. .o...o.
  8. .o....o.
  9. ....o....
  10. ooo.oo.ooo
  11. .....o.....
  12. .o.o.oo.o.o.
  13. .o..o.o.o..o.
  14. ooo.oo..oo.ooo
  15. ooo..o.o.o..ooo
  16. .o...o.oo.o...o.
  17. ........o........
  18. ooooooo.oo.ooooooo
  19. .oo.oo...o...oo.oo.
  20. .....o.o....o.o.....
  21. oo.oooooo.o.oooooo.oo
  22. .o......o....o......o.
  23. .oo.oo..oo.o.oo..oo.oo.
  24. oooooooooooooooooooooooo
  25. oo..oo.oooo.o.oooo.oo..oo
  26. .o...o..o........o..o...o.
  27. .oooooo.oo.o.o.o.oo.oooooo.
  28. ....o..................o....
  29. oo..oo..oo.oo.o.oo.oo..oo..oo
  30. .o...o..................o...o.
  31. .ooooooooooooo.o.ooooooooooooo.
  32. ....o...o..............o...o....
  33. oo..oo..oo.oo.o.o.o.oo.oo..oo..oo
  34. .o...o......................o...o.
  35. .ooooooooooooooo.o.ooooooooooooooo.
  36. ....o...o..................o...o....
  37. oo..oo..oo.oooooo.o.oooooo.oo..oo..oo
  38. .o...o..........................o...o.
  39. .ooooooooooooooo.o.o.o.ooooooooooooooo.
  40. ....o...o......................o...o....
  41. oo..oo..oo.oooooooo.o.oooooooo.oo..oo..oo
  42. .o...o..............................o...o.
  43. .ooooooooooooooooooo.o.ooooooooooooooooooo.
  44. ....o...o..........................o...o....
  45. oo..oo..oo.oooooooooo.o.oooooooooo.oo..oo..oo
  46. .o...o..................................o...o.
  47. .ooooooooooooooooooo.o.o.o.ooooooooooooooooooo.
  48. ....o...o..............................o...o....
  49. oo..oo..oo.oooooooooooo.o.oooooooooooo.oo..oo..oo
  50. .o...o......................................o...o.
  51. .ooooooooooooooooooooooo.o.ooooooooooooooooooooooo.
  52. ....o...o..................................o...o....
  53. oo..oo..oo.oooooooooooooo.o.oooooooooooooo.oo..oo..oo
  54. .o...o..........................................o...o.
  55. .ooooooooooooooooooooooo.o.o.o.ooooooooooooooooooooooo.
  56. ....o...o......................................o...o....
  57. oo..oo..oo.oooooooooooooooo.o.oooooooooooooooo.oo..oo..oo
复制代码

其中,“o”表示这个位置是最佳策略,“.”表示这个位置不是最佳策略。

我们可以看到,从$n=34$开始,先手的最佳策略形成了周期为$8$的固定模式。

不知道这个固定模式会不会一直维持下去,从而不再出现例外情况。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-6 14:14 , Processed in 0.082770 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表