数风·数林 | 炉石传说中的概率（声控篇）
文 / 慵懒之龟
引 / 北大数院人
声控是炉石传说最大的魅力所在，也是技术的重要一部分。肩负全村人的希望的乱斗，下螺丝的时候给它指定一个目标，再下四个我就是狗的130系列（笔者最近打JJC被130从万军中抓走High巨人已经两次了）……最难以捉摸的大概就是这种玄学，其中又以随机分配伤害的情形最为复杂（而上面举例的情形对应的概率则比较容易计算）。
暑假里，一位炉石主播在微博上问了这样一个问题：
场上一个大表哥，两个两血生物（没有法强），打一个火山喷发，大表哥被打死的概率是多少？
在炉石传说中，随机分配伤害的逻辑是这样的：在所有合法目标中等概率地选择一个目标，然后对这个目标造成一点伤害。然后如果这个目标的生命值变为0，它就不再是合法目标。如此循环直至打完规定的伤害或者场上不再有合法目标。（如果实际情况与之不符……那就是阿三程序猿的错）
这个问题相当复杂，所以我们就先来看一个简单的问题吧。
在很久很久以前，有个史学家：
这家伙发现了一条萌萌哒精灵龙。
后来年轻的法师打一个寒冰箭解了史学家，场上剩一条精灵龙；
最后法师决定碰碰运气，打一个奥术飞弹。
这三点伤害会随机分配到英雄和精灵龙身上。那么，精灵龙被打死的概率是多少呢？（默认英雄的生命值高于3）
呃，这个确实是很久很久以前的问题了，简直和炉石传说一样古老。当年引起过热烈的讨论，热烈的程度大概相当于这个版本对侏儒吸血鬼的收益的大讨论……
那么我们怎么计算呢？先给两个不正经的方法：
方法一：要么打死，要么没打死。二分之一，送分题！（如果真的这么回答，估计要被打死）
方法二：分别标记三点伤害的目标：龙龙人，龙人龙，人龙龙，人人人，人人龙，人龙人，龙人人。一共七种情况，七分之三！（来自NGA上的帖子，自称概率学忘得差不多了只会最简单的办法）
好了，我们开始变得正经了。先说答案：二分之一。（先打死再说）
分析一：如果按照方法二的列举。第一种情形，前两下打龙的概率是四分之一，然后就一定打人，所以概率是四分之一。其他六种情形的概率都是八分之一。所以龙被打死的概率是二分之一。
分析二：我们可以认为龙的血量也高于三点，算它被打至少两下的概率。稍微想一想就会发现这样的转化对问题的结论没有影响。这样转化以后，我们发现龙如果不死，就是人至少被打两下，按照对称性，这和龙至少被打两下的概率是一样的。然后这两者的发生概率一样而且又是互补的事件，自然概率都是二分之一。
我们看到，虽然分析二很简便，基本没有计算，但却只适用于幸运二选一的情况，不能用来算大表哥的存活率。分析一的列举方法则过于繁琐，如果我们要用来算大表哥的存活率，就十分恐怖。那我们怎么办？
我们可以借助现代化的装备。拜托，你不是用纸笔打炉石的吧！接下来就轮到（非阿三）程序猿出场了——但是，程序猿也要先有个思路啊，怎么办呢？
方法一：我们可以采用概率的频率定义。模拟大量次数，然后统计大表哥的存活次数。这很Coooooooool！
在一百万次试验中大表哥存活了 996728 次，果然大地的守护者是没那么容易入土的。
方法二：我们可以逐步简化问题。打 14 点的问题比打 15 点简单，打 13 点的又比打 14 点的简单。如果我们有一种办法最终归结到打一点，那就一眼就能看出答案了。
我们可以利用全概率公式，如果已知第一下打了谁，不就可以归结为少打一点的问题了吗？基于这个想法，我们有了下面的代码。
我们算出大表哥存活的概率为 0.9966315820624765，和前面模拟的结果相对照，应该没有太大问题。
当然，我们在面对这样的局势的时候，可以根据这样的概率计算决定要不要拼一把，但是对于欧皇和非酋来说，这些都是没有意义的。打死或者没打死，不是二分之一吗？（滑稽）
然后，我们还可以分析一下另一个问题：
那是一个上了逗鱼时刻的悲惨故事。
双方空场，任务贼铺了4个5/5（任务贼削了大快人心）。于是萨满打了一张火山喷发。
结果，火山喷发打出了接近生而平等的效果，一个都没有打死……
那么这个概率大概是多少呢？
笔者用方法一进行了数次100000次的模拟，一个都没打死的次数大约在5800-6000。我们应该可以放心的认为这个概率大约是5.9%——在那之前笔者已经用方法二开始运行了，但是答案过了5分钟还没有出来……
对此我们进行一下分析，可以发现，方法二对于一些简单的场面进行了太多次数的重复计算。这就是程序低效的根源。
那我们可以怎样进行优化呢？我们可以开一个中间结果储存器，保存中间结果；如果要计算的场面已经在计算过的中间结果里面了，我们就可以直接拿出这个结果，不需要进行重复计算，这就是记忆化搜索的思想。但是这个储存器的实现需要一些更高级的数据结构方面的技巧，比如对整个场面信息进行打包并Hash，笔者很懒就没有去做（才不是因为我不会）……
又过了5分钟，结果出来啦，和我们的预期还是很接近的：0.05873199552297592。
祝大家早日学会声控，让对面打出奥术影袭和火山平等（啦啦啦：自作聪明）~
☞ 曲面论
算法数学之美微信公众号欢迎赐稿
稿件涉及数学、物理、算法、计算机、编程等相关领域。
稿件一经采用，我们将奉上稿酬。
投稿邮箱：[email protected]