论坛 › 难题征解 › 占地游戏的最佳策略

KeyTo9_Fans 发表于 2018-5-10 22:25:37

占地游戏的最佳策略

$A$和$B$两个玩家在玩一个占地游戏。

有$n$个空格子排成一排，

$A$和$B$轮流走，由$A$先走。

如果轮到$A$走，那么由$A$选定一个空格子，然后在这个格子里标上“$A$”，表示这个格子被$A$占领了。

这个占领动作会波及到与之相邻的$2$个格子（如果占领的格子在两端，则是$1$个相邻的格子），

使得相邻的格子也会被标上“$A$”（不管这些格子之前是空格子、被$A$占领、还是被$B$占领，格子里的标记都会变成“$A$”）。

同样地，如果轮到$B$走，那么由$B$选定一个空格子，然后在这个格子里标上“$B$”，表示这个格子被$B$占领了。

同样地，这个占领动作会波及到与之相邻的$1$个或$2$个格子，不管这些相邻的格子之前是空格子、被$A$占领、还是被$B$占领，格子里的标记都会变成“$B$”。

如果某一方走完之后没有空格子了，那么游戏结束。

$A$和$B$都会采取最佳策略使得游戏结束时自己占领的格子数尽可能多，并且这是$A$和$B$的公共知识。

记最终$A$占领的格子数是$a(n)$。

给定$n=1,2,3,...$，问数列$a(n)$是否有通项公式？

#####

手算$a(n)$（$n=1,2,3,...$）的前几项并不难，结果是：

$1, 2, 3, 2, 3, 4, 5, 5$

然后去《在线整数数列百科大全》上搜这串数字，有$2$个结果：

http://oeis.org/search?q=1%2C2%2C3%2C2%2C3%2C4%2C5%2C5&sort=&language=english&go=Search

但都不是我想要的数列。

mathe 发表于 2018-5-11 13:29:28

1,2,3,2,3,4,5,5,5,5,7,7,7,7,8,9,10,9,10
你的计算应该没错

KeyTo9_Fans 发表于 2018-5-11 15:59:54

Number of cells that the first player can capture in the 1-dimensional cell capturing game with n cells
1, 2, 3, 2, 3, 4, 5, 5, 5, 5, 7, 7, 7, 7, 8, 9, 10, 9, 10, 11, 11, 12, 12, 12

以上是$a(1)$到$a(24)$的数据。

$a(25)$算了好几个小时了，还没出结果。

#####

$a(25)$用了$8$个小时终于算完了，结果是$13$。

我的程序对$a(26)$无能为力了（估计需要计算$10$天）。

#####

我改进了程序：
#include<cstdio>
#include<cstring>

const int m=64;

char a,n;

char f(char b,char w)
{
        char s,i,c=0,d=0,e=1,g;
        memcpy(s,a,n);
        if(b>1)c=n;
        for(i=0;i<n;i++)
                if(!a)
                {
                        e=0;
                        a=b;
                        if(i)a=b;
                        if(i<n-1)a=b;
                        g=f(b^3,c);
                        memcpy(a,s,n);
                        if(b>1)
                        {
                                if(g<c)c=g;
                                if(c<=w)return c;
                        }
                        else
                        {
                                if(g>c)c=g;
                                if(c>=w)return c;
                        }
                }
                else
                        if(a<2)d++;
        if(e)return d;
        return c;
}

int main()
{
        for(n=0;n<m;n++)
                printf("%d: %d\n",n,f(1,n));
        return 0;
}
上述C++代码仅运行$1$小时就计算到了$a(32)$，但是继续运行$3$天也只是多算了$5$项，计算到了$a(37)$而已。

该程序的输出结果如下：
0: 0
1: 1
2: 2
3: 3
4: 2
5: 3
6: 4
7: 5
8: 5
9: 5
10: 5
11: 7
12: 7
13: 7
14: 7
15: 8
16: 9
17: 10
18: 9
19: 10
20: 11
21: 11
22: 12
23: 12
24: 12
25: 13
26: 14
27: 14
28: 15
29: 15
30: 16
31: 16
32: 17
33: 17
34: 18
35: 18
36: 19
37: 19
从$a(0)$开始，该数列更新如下：

Number of cells that the first player can capture in the 1-dimensional cell capturing game with n cells
0, 1, 2, 3, 2, 3, 4, 5, 5, 5, 5, 7, 7, 7, 7, 8, 9, 10, 9, 10, 11, 11, 12, 12, 12, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19

继续改进程序：
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int m=96;

char a,n,c;
map<pair<unsigned __int64,unsigned __int64>,char>r;

char f(char b)
{
        unsigned char p={0,0,0,0,0,0,0,0,0,0,0,0},i,j,ps=0,ts=0,h=0;
        unsigned int t={0,0},s2=0,s3=0,s4=0;
        for(i=0;i<n;i++)
                if(!a)
                {
                        for(j=i+1;j<n&&!a;j++);
                        if(j>=n&&!i)s2=3,t=n;
                        else
                                if(j-i<3)
                                        if(j-i<2&&(j>=n||!i))s2++;
                                        else
                                                if(j-i>1&&j<n&&i&&a^a)s4++;
                                                else
                                                {
                                                        if(j-i>1&&b==a&&j<n&&i)h++;
                                                        s3++;
                                                }
                                else
                                        if(j>=n||!i)t=j-i<<1|a==b;
                                        else p=(j-i)*3+(a==b)+(a==b);
                        i=j;
                }
                else h+=a==b&&(!i||a)&&(i>n-2||a);
        sort(p,p+ps),sort(t,t+ts);
        pair<unsigned __int64,unsigned __int64>o;
        for(o.first=s2<<30|s3<<23|s4<<16|t<<8|t,i=0;i<4;i++)o.first=o.first<<8|p;
        for(o.second=0;i<12;i++)o.second=o.second<<8|p;
        if(r.find(o)!=r.end())return b<2?h+r:n-h-r;
        char s,c=0,g;
        memcpy(s,a,n);
        if(b>1)c=n;
        for(i=0;i<n;i++)
                if(!a)
                {
                        a=b;
                        if(i)a=b;
                        if(i<n-1)a=b;
                        g=f(b^3);
                        memcpy(a,s,n);
                        if((b>1)^(g>c))c=g;
                }
        r=b<2?c-h:n-h-c;
        return c;
}

int main()
{
        for(r=n=0;n<m;n++)
                c=f(1),printf(c^n/2+1?"%d: %d\n":"",n,f(1));
        return 0;
}
该程序记录每种碎片组合的结果，以后遇到相同的碎片组合就直接查询之前记录下来的结果，不再重复计算。

于是效率大增，不到$2$小时就计算到了$a(55)=28$，可惜在计算$a(56)$时内存超出了$2GB$，异常退出了。

由于大部分的项都满足$a(i)=\lfloor i/2\rfloor+1$，该程序只输出$a(i)\ne\lfloor i/2\rfloor+1$的特殊项，结果如下：
0: 0
3: 3
4: 2
7: 5
10: 5
11: 7
14: 7
17: 10
18: 9
24: 12
#####

继续改进程序，在内存即将超出时不再存储新的碎片组合的结果，

而是利用已有碎片组合的结果重复计算新的碎片组合的结果，

运行$3$天计算到了$a(67)=34$，依然没有出现新的特殊项。

mathe 发表于 2018-5-11 18:25:20

KeyTo9_Fans 发表于 2018-5-11 15:59
Number of cells that the first player can capture in the 1-dimensional capturing game with n cells
...

你机器的内存不够。a(25)=13，在我的机器上消耗了将近2G内存，而a(26)=14

mathe 发表于 2018-5-11 19:16:27

a(27)=14,机器物理内存被消耗光了，靠虚拟内存支持着竟然跑完了

mathe 发表于 2018-5-11 19:28:49

如果利用对称性应该可以少保存一半状态，不过没有本质提高

mathe 发表于 2018-5-11 19:46:51

到现在为止，先手赢后手都是最多3格

KeyTo9_Fans 发表于 2018-5-11 19:59:13

当$n$是奇数时，至少可以多占$1$格，策略如下：

先占领最中间的格子，把棋盘分成相同大小的两半，然后模仿对方的行棋即可。

mathe 发表于 2018-5-11 20:00:41

奇数好分析，偶数难分析
为了比赛公平，我们应该要求先手贴目，总数奇数格先手需要贴两格，总数偶数格先手需要贴一格，这样就应该是比较公平的比赛了

mathe 发表于 2018-5-12 14:17:09

这个题目双方选择若干步后，会形成很多空白的碎片。每两段碎片之间被占用的格子除了边上两格余下部分都不会再改变，可以不用继续考虑。所以我们只需要考虑剩余各碎片的长度，碎片两端点的当前归属即可。而且比较有用的是不同碎片的顺序对结果也不会影响。另外可以看出，如果剩下所有碎片空白部分长度都不超过3,可以直接贪心法得出最终最优结果。于是我们余下只要搜索各种碎片组合的最优应对方案即可，这种方法应该效率要高很多

查看完整版本: 占地游戏的最佳策略