数学研发论坛

 找回密码
 欢迎注册
查看: 540|回复: 23

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

[复制链接]
发表于 2018-5-10 22:25:37 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
$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%2 ... glish&go=Search

但都不是我想要的数列。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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
你的计算应该没错
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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$天)。

#####

我改进了程序:
  1. #include<cstdio>
  2. #include<cstring>

  3. const int m=64;

  4. char a[m],n;

  5. char f(char b,char w)
  6. {
  7.         char s[m],i,c=0,d=0,e=1,g;
  8.         memcpy(s,a,n);
  9.         if(b>1)c=n;
  10.         for(i=0;i<n;i++)
  11.                 if(!a[i])
  12.                 {
  13.                         e=0;
  14.                         a[i]=b;
  15.                         if(i)a[i-1]=b;
  16.                         if(i<n-1)a[i+1]=b;
  17.                         g=f(b^3,c);
  18.                         memcpy(a,s,n);
  19.                         if(b>1)
  20.                         {
  21.                                 if(g<c)c=g;
  22.                                 if(c<=w)return c;
  23.                         }
  24.                         else
  25.                         {
  26.                                 if(g>c)c=g;
  27.                                 if(c>=w)return c;
  28.                         }
  29.                 }
  30.                 else
  31.                         if(a[i]<2)d++;
  32.         if(e)return d;
  33.         return c;
  34. }

  35. int main()
  36. {
  37.         for(n=0;n<m;n++)
  38.                 printf("%d: %d\n",n,f(1,n));
  39.         return 0;
  40. }
复制代码

上述C++代码仅运行$1$小时就计算到了$a(32)$,但是继续运行$3$天也只是多算了$5$项,计算到了$a(37)$而已。

该程序的输出结果如下:
  1. 0: 0
  2. 1: 1
  3. 2: 2
  4. 3: 3
  5. 4: 2
  6. 5: 3
  7. 6: 4
  8. 7: 5
  9. 8: 5
  10. 9: 5
  11. 10: 5
  12. 11: 7
  13. 12: 7
  14. 13: 7
  15. 14: 7
  16. 15: 8
  17. 16: 9
  18. 17: 10
  19. 18: 9
  20. 19: 10
  21. 20: 11
  22. 21: 11
  23. 22: 12
  24. 23: 12
  25. 24: 12
  26. 25: 13
  27. 26: 14
  28. 27: 14
  29. 28: 15
  30. 29: 15
  31. 30: 16
  32. 31: 16
  33. 32: 17
  34. 33: 17
  35. 34: 18
  36. 35: 18
  37. 36: 19
  38. 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

继续改进程序:
  1. #include<map>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;

  6. const int m=96;

  7. char a[m],n,c;
  8. map<pair<unsigned __int64,unsigned __int64>,char>r;

  9. char f(char b)
  10. {
  11.         unsigned char p[12]={0,0,0,0,0,0,0,0,0,0,0,0},i,j,ps=0,ts=0,h=0;
  12.         unsigned int t[2]={0,0},s2=0,s3=0,s4=0;
  13.         for(i=0;i<n;i++)
  14.                 if(!a[i])
  15.                 {
  16.                         for(j=i+1;j<n&&!a[j];j++);
  17.                         if(j>=n&&!i)s2=3,t[0]=n;
  18.                         else
  19.                                 if(j-i<3)
  20.                                         if(j-i<2&&(j>=n||!i))s2++;
  21.                                         else
  22.                                                 if(j-i>1&&j<n&&i&&a[i-1]^a[j])s4++;
  23.                                                 else
  24.                                                 {
  25.                                                         if(j-i>1&&b==a[j]&&j<n&&i)h++;
  26.                                                         s3++;
  27.                                                 }
  28.                                 else
  29.                                         if(j>=n||!i)t[ts++]=j-i<<1|a[i?i-1:j]==b;
  30.                                         else p[ps++]=(j-i)*3+(a[i-1]==b)+(a[j]==b);
  31.                         i=j;
  32.                 }
  33.                 else h+=a[i]==b&&(!i||a[i-1])&&(i>n-2||a[i+1]);
  34.         sort(p,p+ps),sort(t,t+ts);
  35.         pair<unsigned __int64,unsigned __int64>o;
  36.         for(o.first=s2<<30|s3<<23|s4<<16|t[0]<<8|t[1],i=0;i<4;i++)o.first=o.first<<8|p[i];
  37.         for(o.second=0;i<12;i++)o.second=o.second<<8|p[i];
  38.         if(r.find(o)!=r.end())return b<2?h+r[o]:n-h-r[o];
  39.         char s[m],c=0,g;
  40.         memcpy(s,a,n);
  41.         if(b>1)c=n;
  42.         for(i=0;i<n;i++)
  43.                 if(!a[i])
  44.                 {
  45.                         a[i]=b;
  46.                         if(i)a[i-1]=b;
  47.                         if(i<n-1)a[i+1]=b;
  48.                         g=f(b^3);
  49.                         memcpy(a,s,n);
  50.                         if((b>1)^(g>c))c=g;
  51.                 }
  52.         r[o]=b<2?c-h:n-h-c;
  53.         return c;
  54. }

  55. int main()
  56. {
  57.         for(r[make_pair(0,0)]=n=0;n<m;n++)
  58.                 c=f(1),printf(c^n/2+1?"%d: %d\n":"",n,f(1));
  59.         return 0;
  60. }
复制代码

该程序记录每种碎片组合的结果,以后遇到相同的碎片组合就直接查询之前记录下来的结果,不再重复计算。

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

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

#####

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

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

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

点评

需要找台内存大些的服务器才行  发表于 2018-5-11 19:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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

点评

我是深度优先搜索,仅耗$O(n^2)$内存。你的算法不同,所耗内存可能是指数级增长的。  发表于 2018-5-12 21:43
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-11 19:16:27 | 显示全部楼层
a(27)=14,机器物理内存被消耗光了,靠虚拟内存支持着竟然跑完了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-11 19:28:49 来自手机 | 显示全部楼层
如果利用对称性应该可以少保存一半状态,不过没有本质提高
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-11 19:46:51 来自手机 | 显示全部楼层
到现在为止,先手赢后手都是最多3格
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-11 19:59:13 | 显示全部楼层
当$n$是奇数时,至少可以多占$1$格,策略如下:

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

点评

当$n=0,4,10,14,18,24$时,双方使用最佳策略会打平  发表于 2018-5-12 21:39
当n是那些数时,A:B=1:1。  发表于 2018-5-12 09:27
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-11 20:00:41 来自手机 | 显示全部楼层
奇数好分析,偶数难分析
为了比赛公平,我们应该要求先手贴目,总数奇数格先手需要贴两格,总数偶数格先手需要贴一格,这样就应该是比较公平的比赛了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-12 14:17:09 来自手机 | 显示全部楼层
这个题目双方选择若干步后,会形成很多空白的碎片。每两段碎片之间被占用的格子除了边上两格余下部分都不会再改变,可以不用继续考虑。所以我们只需要考虑剩余各碎片的长度,碎片两端点的当前归属即可。而且比较有用的是不同碎片的顺序对结果也不会影响。另外可以看出,如果剩下所有碎片空白部分长度都不超过3,可以直接贪心法得出最终最优结果。于是我们余下只要搜索各种碎片组合的最优应对方案即可,这种方法应该效率要高很多

点评

不是,这种方法我还没有实现  发表于 2018-5-13 10:41
你之前计算到了27项,用的是这个方法吗?你用了这么多内存,是用来保存不同碎片组合的结果吗?  发表于 2018-5-12 21:36
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2018-10-18 08:46 , Processed in 0.099240 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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