??迩来有一个小游戏“羊了个羊”，俄然爆火。它的游戏规则很简略：把堆积在一同的牌从上到下点到暂时卡牌槽里，凑齐相同的三张就能消掉，假定悉数卡牌都消掉游戏就通关了。暂时卡槽一共有7个方位，假定方位都满了，游戏就输了。

?

?

这个游戏第一关非常简略，就像1+1=2相同。第二关难度飙升，直接变成考研。尽管经过共享游戏或许看广告可以有一些辅佐道具，可是仍是有许多人玩了上百局都没有通关。?

?

有小兄弟就问我说：为啥这个游戏这么难玩？它通关的概率究竟有多大呢？经过我三四天的研讨，今日我就把我的研讨作用向我们陈述一下。

?

一. 游戏的方案逻辑

?

在网上有一个大神，把游戏的源代码找到了。

经过分析源代码，咱们可以发现这个游戏的方案大约可以分为三个进程。

?

?首要：在桌面上方案一些卡的方位。

假定卡牌一共有15种，每一种有18张，那么大约方案15×18=270个卡位。每一卡位都有一组坐标（xi，yi，zi），其间xi和yi标明在桌面上的方位，zi标明堆叠的层数， 角标i从1到270。

?

其次：对卡牌进行洗牌。

方案15种不一样的卡牌，每种卡牌18张，调用“乱序”函数，随机打乱270张卡的次序。

?

最终：顺次序把每一张卡放进对应的卡位里。

因为“卡位”和“牌”都现已有了次序，只需把序号相同的牌放在相应的卡位上，就结束游戏的初始化。

?

?

在这个进程中，“方案卡位”的进程是人工结束的，程序员人为的设定好每一个卡的方位，而且每一天替换一次。所以，你会发现卡的摆放非常对称，而且在每一天中固定不变，这就是“每日一关”的意义。?

而“洗牌”的进程是程序随机结束的，所以假定你在一天中打许多局，卡牌的方位不会变，可是每个方位上的卡牌品种是改变的。

?

经过分析程序方案逻辑，咱们会发现：游戏方案者并没有人为的设置妨碍，让玩家无法通关。可是因为它的?婊磁啤埃钩尚矶喙乜ū旧砭褪俏藿獾摹?br>

?

而且，游戏可以通关的概率有多大，和程序员人工方案卡位的方法很有联络。可以愿望：假定程序员把一切的卡平铺在桌面上，那程序100%是有解的。可是假定把一切卡摞成一列，那有解的可以性就微乎其微了。

?

?

二. 对残局的数学分析

?

咱们不妨来分析一个残局，看看游戏有解的概率大约有多少。

?

假定在某一天的游戏中，游戏方案师方案的卡位，最底部的五层是这样的：

?

最底层有一张牌：

在倒数第二层有4张牌：?

在上面又压了4张牌

在上面又压了4张牌

最上面又压了1张牌：

也就是：从最下方到最上方，是1-4-4-4-1的规划，一共有14张牌。

?

假定这个规划位于整个牌堆的最底部，根据解锁的原则，只需点开最上层的1张牌，才干解锁其他牌，所以要想通关，有必要会在某个时刻面临这个残局。

?

那么，面临这样的局势，通关概率大约有多大呢？

?

咱们来核算一下这种牌局通关的必要条件：

?

假定在桌面上的最终14张牌，品种一共有n种。显着，n最小是1（一切卡牌都是同一品种的），最大是14（一切卡牌都是不一样的）。可以愿望：如一切的卡都是同一种，必定可以通关；假定有14种，那必定无法通关。那么，要想通关，这14张卡的品种n最多是几呢？

?

“羊了个羊”是一个三消游戏，要想把n个品种的牌完全消除，牌的个数至少是3n张。也就是：假定残局里每一种牌都是3张，一共3n张，就有可以完全消掉。

?

*假定某种牌有6张，那总的牌数就需要是3n+3张，才有可以完全消除。

?

可是，刚刚还说桌面上只需14张牌，如今又说有3n张，这不是敌对吗？

?

别忘了：暂时卡槽还有一些方位。假定刚好可以通关，3n张卡中有14张在桌面上，余下的3n-14张就大约在暂时卡槽里。

?

还有，暂时卡槽一共只需7个方位，而且装满了牌游戏就结束了，所以暂时卡槽里的储存的牌最多只需6张。

?

这样，咱们就得到了一个中心不等式：

3n-14≤6

?

?这标明：残局中假定有n种牌，那么要想通关，牌的数量至少是3n张，其间有14张在桌面上，余下的牌在暂时卡槽里，而且最多有6张。

?

?

?解上述不等式，一起留心n是一个整数，得到

? n≤6

即：假定牌局的最底层14张牌如我假定摆放，那么牌局有解的必要条件是最终14张牌的品种小于等于6种。

?

有必要留心：即便满足这个条件，牌局仍然不必定有解。可是不满足这个条件，牌局必定是无解的。

?

*在我讲到这个疑问时，许多兄弟说我做错了，因为一共270张牌必定是3个一组消去的，所以最终不可以能剩下不成组的14张牌。其实，这种说法是没有了解我的方案意图。因为程序员的随机乱序，最终14张牌是啥都有可以。可是，假定最终14张牌的品种数剩下6种，那么就必定无法经过消去抵达这个残局，也就是无解的。假定要有解，首要要抵达这个残局，那就有必要满足n≤6的条件。

?

三. 蒙特卡罗办法

?

一共15种牌，每种18张，随机摆放在270个方位上，在最终14个方位上牌的品种数小于6种，概率有多大呢？显着这不是一个好算的数学疑问。

?

不过幸亏，咱们有了核算机，可以经过蒙特卡罗办法得到疑问的估量值。即让核算机随机测验10000次，看看有多少次满足条件，就能预算这个概率了。

?

具体的仿照办法是这样的：

仿照程序代码如下：

?

?

?经过实验，我发如今10000次计算中，底层14张牌的品种小于等于6种的次数大约在40在70次之间。我又把以上的程序循环实施了1000次，得到了在一万局中，“可以有解”的局数的分布联络如下：

?

你会发现：在一万局中，可以有解的局数大约成正态分布，期望数53，标准差7，也就是咱们得出了以下结论：

?

假定游戏最底部的五层如我的方案，那么游戏有解的概率上限均匀值为0.5%。咱们有95%的掌控说：游戏有解的概率上限不跨越0.7%。

?

也就是说，玩1000把，最多也就只需5到7局是“有可以有解”的。实践上，我还只是思考了14张牌的一个残局，真实的游戏牌局比我方案的更坑，有解的概率很有可以再低10到100倍，即0.1%甚至0.01%！

?

游戏之所以不能通关，不是咱们的智商疑问，而是因为程序员偷闲做了个大随机，构成关卡本身无解。

?

?

四. 如何改进程序

?

假定我方案这个游戏，必定不会答应无解的情况发生。我会依照这样的思路方案游戏：

?

第一步：方案卡位次序：

1. 人为设定270个卡位。

*在没有放卡之前，这些卡位都是空的。

?

2. 依照“从上到下“的解锁条件，随机生成一条解锁途径。

*因为同一层卡牌有许多张，解锁的途径也非常多。咱们在这非常多的途径中，让程序随机寻找一条契合规则的途径即可。

?

3. 把解锁途径倒过来，作为卡位的次序。

?

第二步：方案卡牌次序

15种卡牌，每种6组，每组3张，依照同组三张在一同的原则，进行组间乱序摆放。

*和正本程序的差异在于：在咱们的方案中，乱序后的卡牌仍然是三张相同的牌连在一同的。

?

第三步：将一切卡牌顺次放回桌面的对应卡位上

重复随机实施下列操作之一：

1. 取出卡牌序列中一组牌，2张放在暂时卡槽中，另1张顺次放在桌面卡位上。

?

?

2. 将暂时卡槽中随机的一张牌顺次放到桌面卡位上。

?

*其实，这两个进程就是把消除卡片的次序倒过来。留心，在暂时卡槽空的时分只能做第一步，暂时卡槽的牌跨越4张时只能做第二个进程，而且做第一进程时要保证卡槽内不能现已有相同的牌。

?

这样，我方案了一条消除途径（第一步），又依照消除的规则把卡牌一个个倒着放回到途径上（第二步和第三步），所以究竟必定是有解的，而

且，这也并不会降低游戏的可玩性。怎么样，我这个游戏方案师还不错吧！

?

传闻这两天“羊了个羊”因为漫山遍野的批判，现已把游戏难度调低了。我看它选用的办法形似是添加某几种牌的比例，削减另外几种牌的比例。可是这样做就大大降低了游戏性。

?

我仍然主张他们，用我的办法批改一下流戏。

?????