当道具所占比例达到多少时，就可以无限开路了？
我设计了一个简单的小游戏。这个游戏是在一个无限大的地图上进行的。
一开始整个地图只有【道具】和【障碍】两种格子，而且两种格子是随机生成的（以$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)$区间里。
除了试玩，有什么办法可以判断玩家能否无限开路呢？
如何找到更准确的阈值呢？ 无限开路是怎么定义的。 上面的点评依然不严谨，寥寥数语没法说清楚，于是回贴补充。
首先不存在【无限大的地图】，必需给定地图的确切大小，设为$(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$。 下载这个附件，解压后就可以玩楼主设计的开路游戏了：
玩法介绍：
游戏一开始，玩家就已经在地图的正中央拾起了$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覆盖掉。
页:
[1]