当道具所占比例达到多少时，就可以无限开路了？

KeyTo9_Fans

我设计了一个简单的小游戏。

这个游戏是在一个无限大的地图上进行的。

一开始整个地图只有【道具】和【障碍】两种格子，而且两种格子是随机生成的（以$p$的概率生成【道具】，以$(1-p)$的概率生成【障碍】）。

一开始玩家持有的道具数量为$0$，然后玩家选择一个【道具】格子作为起点。

当玩家位于【道具】格子上的时候，玩家可以拾起该道具。

玩家每拾起$1$个道具，那么玩家持有的道具数量加$1$，然后格子里的道具消失，变成【空地】。

当玩家持有的道具数量大于$0$的时候，才可以进入【障碍】格子。

玩家每进入$1$个【障碍】格子，就会消耗掉$1$个道具，然后该障碍消失，变成【空地】。

玩家只能往上下左右$4$个方向移动，并且每次只能移动$1$格。

问道具所占的比例$p$至少是多少，玩家才可以无限开路？

-----

试玩了一下$p=1/8$，开路很轻松。

试玩了一下$p=1/16$，处处被困死。

试玩了一下$p=1/12$，依然处处被困死。

继续二分，试玩$p=1/10$，结果：

虽然每次都被困死，但我觉得这是我运气不好，于是不断重设地图重玩，

终于有一次开出了一条长达$500$多步的路径还没有被困死，而且已经攒了$132$个道具。

因此对于$p=1/10$基本上可以断定：玩家是可以无限开路的。

继续二分，试玩$p=1/11$，结果：

运气爆棚，第一局就直接开出了一条长达$500$多步的路径，而且已经攒了$100$个道具。

因此对于$p=1/11$基本上可以断定：玩家是可以无限开路的。

我现在怀疑之前尝试$p=1/12$的时候，是因为开路经验不足才导致被困死的。

现在我已经攒了$14$个小时的开路经验，开路技术比之前大大提升了。

于是重玩$p=1/12$，发现依然玩不开。

因此$p$的阈值在$(1/12,1/11)$区间里。

除了试玩，有什么办法可以判断玩家能否无限开路呢？

如何找到更准确的阈值呢？

zeroieme

无限开路是怎么定义的。

KeyTo9_Fans

上面的点评依然不严谨，寥寥数语没法说清楚，于是回贴补充。

首先不存在【无限大的地图】，必需给定地图的确切大小，设为$(2n-1)\times(2n-1)$，$n$为正整数。

限定了地图的大小之后，玩家就不能随意设定起点了，起点必需位于第$n$行第$n$列，也就是地图的正中心。

如果第$n$行第$n$列是个障碍，那么这个地图无效，重新随机生成一张新的地图，直到新地图的第$n$行第$n$列是个道具为止。

地图确定之后，那么玩家能否走到地图的边缘是确定的：

有些地图存在可以走到边缘的策略，有些地图则不存在这样的策略。

（补充说明：地图是全开放的，每个格子是什么玩家都能看到）

于是我们就可以计算在第$n$行第$n$列是个道具的前提下，玩家在随机生成的地图上能走到地图边缘的概率，记为$P(n)$。

当$n->\infty$时，$P(n)$有一个极限值，记为$P(\infty)$。

当$P(\infty)>0$时，我们就说【玩家可以无限开路】，

当$P(\infty)=0$时，我们就说【玩家不能无限开路】。

#####

简单来说，就是玩家在随机地图上开路，一直都不会被困死的概率大于$0$。

KeyTo9_Fans

下载这个附件，解压后就可以玩楼主设计的开路游戏了：

carve_out.zip (103.49 KB, 下载次数: 3)

2017-12-3 11:37 上传

点击文件名下载附件

玩法介绍：

游戏一开始，玩家就已经在地图的正中央拾起了$1$个道具，开出了$1$块空地，如下图所示。



只有与空地相邻的格子才可以点击。

点击“☉”可以拾起$1$个道具（拾起后变成空地），

点击“█”可以清除$1$个障碍（需要消耗一个道具）。

点击“放大”、“缩小”可以放大和缩小视野。

键盘按键【上下左右】可以移动视野。

点击“存档”、“读档”可以存储和读取当前的地图状态。

用于存档和读档的文件只有$1$个，均为"rec.txt"。

如果要存多个档，需要手工备份"rec.txt"，否则已有的"rec.txt"会被新存档覆盖。

如果要读别的档，需要将原有的"rec.txt"重命名，然后将需要读取的文件命名为"rec.txt"，不便之处请谅解。

每次运行游戏，使用的都是同一张地图（文件名是"ox.txt"），

该地图的道具所占的比例为$p=1/11$，是可以开到地图边缘的。

由于撤销功能暂未实现，如果不慎点错了，就只能读档了。

因此玩的过程中需要勤存档，以免点错之后只能重玩，不便之处请谅解。

如果"ox.txt"这张地图玩腻了，玩家可以自行设计新的地图，

然后覆盖掉"ox.txt"，重新运行游戏即可。

需要注意的是，地图的大小被锁定为$399\times 399$，

也就是说，"ox.txt"必需包含$399$行，每行$399$个字符，游戏才能正常运行，不便之处请谅解。

#####

楼主在 2017-12-03 11:36 更新了附件，修正了一些bug。

如果在此之前下载了附件，需要重新下载才能把原来的bug覆盖掉。