占地游戏的最佳策略

王守恩

游戏规则明确一下：
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个

mathe

前面提到的每个碎片，假设里面是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}
而对于一个复杂局面，最终输赢数目在每类碎片数目充分多时，应该只取决于各类碎片数目的奇偶性
而为了得到最终公式，我们可以首先求出这种极限模式（每类碎片数目充分多），然后再求出那些不符合极限模式的特殊模式（其中有些碎片数目充分小）。
这个方法可以采用类似棋子问题中方法，只是这里状态数更多，分析起来会更加复杂

王守恩

王守恩 发表于 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
..........
我们的思路跟着后手走，解法会简单些。

KeyTo9_Fans

把先手的最佳策略输出来，结果如下：

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$的固定模式。

不知道这个固定模式会不会一直维持下去，从而不再出现例外情况。