« December 2016 | Main

January 16, 2017

10 连抽保底的概率模型

网游里有很多抽卡、开箱子之类的赌性玩法,在最开始,游戏设计者实现的时候,仅仅给这些抽取概率简单的设置了一个值。比如抽卡抽出橙卡的概率是 10% ,那么就是说,玩家每次抽一张卡,有 90% 的可能是白卡,10% 的可能是橙卡。

但大 R 玩家是大爷,需要小心伺候。如果感受不好,人跑了就亏大了。概率这个东西靠改进伪随机数发生器是解决不了体验问题的,大爷要是连抽 20 张都出不来橙卡,那是要怒删游戏的。

连抽 20 张 10% 概率橙卡一张都抽不到的机会多不?一张抽不中的概率是 0.9 ,20 张都抽不中的概率是 0.9 ^20 = 12.2% 。这可不算小数字啊。平均 8 个大 R 就会碰到一次,一下子赶跑了 1/8 的金主,这个责任小策划可担当不起。

所以、一般网游都会用各种规则来避免玩家出现连抽不中的尴尬。例如,我忘记是谁发明的 10 连抽规则:如果你购买一个大包连抽 10 次,我在规则上就保证里面一定至少有一张橙卡。实现它应该并不困难,按常规概率生成 10 张的卡包,如果里面没有橙卡,那么我加一张即可。

但如果我想把 10 抽保底的规则惠及日常抽卡的玩家该怎么做呢?

就是说,我希望任何玩家任何时候,接连抽了 10 张卡,我都想保证这 10 张卡里至少有一张橙卡。

首先,要说明的一点:如果你同时想保证橙卡掉落率是 10% ,也就是在极大范围内,比如系统投放了一万张卡片中,其中要有一千张橙卡。那么同时保证每 10 张卡里有至少一张橙卡的话,结果一定是完全不随机的,也就是必须每抽 9 张白卡,必出一张橙卡。

所以、如果即想要随机(出橙卡的概率稳定),又想有 10 张出一张的保底,那么橙卡投放量是一定超过 1/10 的。

我们之前的游戏用了个很粗暴的方案:记录玩家已经连续几次没有抽中,如果连续次数超过 9 ,就必给他一张橙卡。为什么我说这个方案粗暴,因为它其实破坏了抽卡的自然体验。虽然玩家的确更高兴了,但是概率却很不自然。不自然的方案(其实是生硬的打了个补丁)实现起来还容易出错,我们前段时间就因为实现 bug 多发放了很多稀有物品,这个 bug 就不展开说了。

下面来看看,为什么这么做不自然。

假设橙卡的掉率是 10% ,那么你在获得一张橙卡后,再抽下一张橙卡的概率就是 0.1 。下一张是白卡,再下一张是橙卡的概率是 0.9 * 0.1 ,下两张是白卡,第三张是橙卡的概率是 0.9^2 * 0.1 ……

后续有 10 张及 10 张以上的概率总共有多少呢?我算了一下,大约是 35% 左右。

我们把抽到两张橙卡之间会抽取到的白卡张数排成一个数列的话,这个数列的值的范围是 0 到正无穷。是的,非洲酋长可能永远抽不到橙卡。当然这只是理论值。

如果你读过大学,学的是理工科,没有逃课的话,就应该知道,这个数列是大致符合指数分布的。指数分布正是用来表示独立随机事件发生的时间间隔的。

当我们把这个数列中大于 9 的数字都强行改成 9 ,那么 9 的出现频率就陡然跳变,这是极不自然的。(分布不平滑)


从一致分布的随机数,转换为指数分布的随机数非常简单。如果你懒得自己推导,那么可以在爆栈网上找到公式

让我们回答前面的问题,如果我希望获得一个大约每 10 张卡里出一张橙卡的随机数列,除了每次 random 一个 [0,10) 的整数,判断证书是不是 0 以外,还有一个方法。那就是每次抽到一个橙卡后,都从一个指数分布的随机数列中取一个值出来,作为接下来会抽取到白卡的张数。按这个张数去发放白卡,等计数器减到 0 ,就发一张橙卡给玩家。这个白卡张数的数值范围是 [0, inf) 。

用 lua 实现的话,大概是这样的:

math.floor(math.log(1-math.random()) * (-rate)) 其中 rate = 10 。

好了,如果我们想加上 10 张保底,又想让间隔大致符合指数分布怎么办?简单:

function erand(rate)
    while true do
        local p = math.floor(math.log(1-math.random()) * (-rate))
        if p < rate then
            return p
        end
    end
end

让产生出来的数字小于 10 的时候重来一次就好了。如果你担心这里死循环(实际并不会),也可以加上循环上限:

function erand(rate)
    for i = 1, 100 do  -- 100 可以随便写
        local p = math.floor(math.log(1-math.random()) * (-rate))
        if p < rate then
            return p
        end
    end
    return rate-1
end

当然,一旦加上了 10 张保底,单张出橙卡的概率就大大增加了,增加到多少呢?大约是 21%。如果你希望保持 10% 左右的投放率,那么保底张数大约应该设置在 23 张左右。


ps. 今天在公司群里讨论这个问题时,雷先生提了这么一个问题,说是可以用来做数值策划的面试题:

已知橙卡的抽取率是 10% ,抽一次卡是 1 块钱;而 10 连抽的包可以帮你按同样概率连抽 10 次,但如果没有抽到橙卡的话,系统会补偿一张橙卡给你,换掉 10 张白卡中的一张。

假设白色一文不值,只有橙卡值钱。

那么请问:这个 10 连抽的包到底价值多少?

January 14, 2017

豆豆的日常

云豆两岁的日常:

奶奶:10 点了,豆豆该睡觉了。

豆豆:要听咕哩咕哩。

奶奶:ipad 没电了。

(ipad 电量 1%)

豆豆:ipad 真没电了。

奶奶:听小兔子好吗?

豆豆:(拧开开关)小兔子不好听。(关上)

豆豆:ipad 没电了、手机也没电了、奶奶唱歌。

奶奶:唱什么?

豆豆:门前大桥下……

奶奶:我不记得歌词了。

豆豆:(唱)门前大桥下,游过一群鸭…… 不记得歌词了。

豆豆:奶奶唱,(唱)小燕子、 穿花衣,年年春天来这里~

奶奶:你不是会唱吗?

豆豆: 奶奶唱小燕子, 豆豆睡觉。

奶奶:(唱)小燕子 穿花衣 年年春天来这里~ Zzz...

豆豆:奶奶睡着啦。

January 08, 2017

在 Unity3D 的 Mono 虚拟机中嵌入 Lua 的一个方案

很多使用 Unity3D 开发的项目,都不太喜欢 C# 这门开发语言,对于游戏开发很多人还是更喜欢 Lua 一些。而 Lua 作为一门嵌入式语言,嵌入别的宿主中正是它说擅长的事。这些年,我见过许多人都做过 U3D 的 Lua 嵌入方案。比如我公司的阿楠同学用纯 C# 实现了一个 Lua 5.2 (用于在 U3D web 控件中嵌入 Lua 语言的 UniLua );还有 ulua slua wlua plua xlua ... 数不胜数。我猜测,a-z 这 26 个字母早就用完了。

上面提到的项目的作者不少是我很熟悉的朋友,我们公司现在的 U3D 游戏也由同事自己实现了一套差不多的东西。所以我曾了解过这些方案。但我一直觉得这些方案要么做的过于繁琐,要么有些细节上不太完备,总是手痒想按自己的想法搞搞看。

Mono 和 C 通讯使用 P/Invoke ,用起来不算麻烦,但是要小心暗地里做的 Marshal 的代价,特别是对象传递时装箱拆箱的成本。Lua 和 C 通讯有一套完善的 C API ,但完全正确使用并不容易。核心难点是 Mono 和 Lua 各有一套自己的异常机制,让它们协调工作必须很小心的封装两个语言的边界,不要让异常漏出去。我在 2015 年写过一篇 Blog 做过相关讨论

我认为简单且完备的 Mono / Lua 交互方案是这样的:

当一边要和另一边通讯时,这和 C/S 结构的相互通讯并没有本质区别,都是发送一串数据到对方虚拟机。这种抽象方式要比 Mono 和 C 交互用的 P/Invoke 或是 Lua 的一堆 C API 要简洁的多。通常说来,一切的跨虚拟机通讯,都仅可以看成是一次异地函数调用。只要约定发送的数据串的第一项是一个函数,而后续内容是调用的参数即可。

所以 Mono 和 Lua 的交互方案就简化成了,如何从一边发送一串数据,这串数据中可以包含两边都认可的基本数据类型,如数字、字符串、布尔量,也可以包含某个虚拟机中的对象。我们并不需要真的把本地的一个对象的数据内容全部序列化成串发送给对端,而只需要给将发出的本地对象附上一个数字 id ,对端记录下 id ,等后面真的需要操作这个远程对象时,再将 id 发送回去即可。

要调用的函数本身也是一个本地对象。对于 Lua ,函数本来就是 first class 的,而 Mono 这边则可以统一给一个 Delegate 来做此媒介。

以 Mono 调用 Lua 为例,我们用事先获取到的 Lua 函数对象 id ,加上调用参数,将这一系列数据组织在一个不需要特别做 Marshal 的 struct 中,把这个 struct 通过 P/Invoke 传给 C 层;然后 C 函数调用一个写好的 Lua 函数把 struct 的内容置入 Lua VM 。然后在 Lua VM 中,用事先定义好的流程去处理它,通常的处理方式就是将第一个函数对象压栈,用后面的数据做参数调用它。最后,取得函数调用的返回值,再将返回值编码成 Mono 可操作的 struct 返回。

之所以是通过一个 struct 转换,而不是像很多别的封装方案那样把 lua 的 C API 导成 C# 的 API 直接操作 Lua 虚拟机。是因为从设计层面看,我们需要提高这个模块的内聚性,让和 Lua 交互层和 Mono 有最少的接口(减少耦合)。另,Lua 的 API 原本是供 C 使用的,对于异常处理有一套独特的规则;而掺入 Mono 这个东西后,我们又需要异常不外溢。把 struct 压入 Lua 虚拟机的过程可以用唯一一个 lua 函数做到,更方便限制住任何可能产生的异常。

Lua 调用 Mono 会稍微麻烦一点,需要定义一个 Delegate ,然后再把需要调用的 C# 函数/类等都按此 Delegate 做一些封装。好在 C# 有完善的反射机制来做这件事,若想提高效率的话,还可以有别的优化手段,比如为需要导出的类做代码生成。因为嵌入 Lua 的目的是将多变的业务放到更灵活的 Lua 语言中去编写,而 C# 这边的代码相对固定,在项目中后期基本不会有太多变化,这些优化手段都是值得在项目前期进行的。

注:这里从 Mono 返回字符串部分要小心处理。因为 Mono 向外传递字符串有额外的开销,最好能做到不传字符串时,可以没有这个开销。


这个周末,我花花整整一天的时间来实现上面的想法。代码放在了 github 上 。它可以在 mono 上编译运行,暂时没有文档,但是整个结构很简单,使用范例在 test.cs 里也基本展示出来了。

这里花去不少篇幅完成的工作是两个不同虚拟机间的对象相互引用。之前在 xlua 的项目 issue 中做了一些讨论

一个虚拟机的对象,如果传递到另一边,需要在本地做一个强引用,防止被 gc 掉。当对方不再使用这个对象后,可以解除这个强引用。对于远程对象,在本地都是记录一个 id 。Lua 和 C# 都有发现一个对象不再使用的能力,Lua 利用的是弱表,C# 有 Weak Reference 。以 Lua 为例,我们将远程对象放在弱表中,以 id 去索引;同时再把远程对象的 id 都收集在一个集合里。只需要定期检查 id 集合中有哪些 id 于弱表中查询不到了,它们就是不再使用的远程对象。

固然,还可以用 __gc 方法在远程代理对象被回收时获知信息,但我并不推荐这种做法。加上 __gc 方法会为 gc 流程增加许多不必要的负担,而且这些方法的调用时机很难主动掌控,最终你还是只会在 __gc 方法中登记一下 id ,和上面提到的主动比对弱表的方案并没有获得任何好处。

真正难处理的地方在于两个虚拟机间对象的循环引用。

假设 mono 中有一个对象 A 被传递到 Lua ,Lua 中为之生成了代理 A' ;Lua 中有另一个对象 B 传递给 Mono ,Mono 为之生成了代理对象 B' 。

如果 mono 中 A 引用了 B' ,同时 Lua 中 B 引用了 A' ,则造成了循环引用。由于 Lua 中的 A' 不回收的话,Mono 不能回收 A ;同理 Mono 中的 B' 不回收的话, Lua 中也会一直持有 B 的强引用。所以 A B 两个对象即使没有任何别的地方使用它们了,也无法被回收掉。

回收这类循环引用的对象也并非没有办法。如果虚拟机具备一种能力,可以获知一个对象是否只被特定东西(在这里指外部虚拟机)引用住,那么就可以很简单的解决这个问题。

当 Mono / Lua 发现,某些对象仅存在外部引用,那么就将这些对象设置成一个特殊状态(可以是引用次数加一,也可以是放在一个特殊集合中);一旦某个对象被设置了两次特殊状态(双方都不再引用),就可以真的清除它们。

我对 C# 不太熟悉,不知道如何做到这点;但 Lua 做这件事情非常容易。

一种方法是,自己遍历虚拟机,但不遍历导出对象的集合,所有没有遍历到的,但存在于这个集合中的对象,就是仅有外部引用的。遍历虚拟机对 Lua 来说不是难事,我在两个过去的项目中分别用 LuaC 各实现过一遍。

还有一种取巧的方法需要利用 Lua 的 ephemeron table 。当我们需要检测一个对象是否只有外部引用时,可以先把它从引用表里移除,移到一个 ephemeron table 中。这个 table 的结构是 obj : { obj } 这个样子。对于 { obj } 这个 value 可以加上 __gc 方法。如果 obj 没有额外的引用,那么 __gc 会被调用。我们可以把 obj 移到另一个叫做坟场的 table 中复活。这样 obj 就没有真的被清理掉了。

不过采用这个方法时,要特别留意 weak table (ephemeron table) 在工作时,会让暂时移除的 obj 处于一种中间状态 ,即不在 weak table 中,__gc 也还没有被调用,也就是没来得及移到坟场。

仅使用 Lua 这种检测能力,就足以消除循环引用。当我们找到只有外部引用的对象,就可以认为在当次 gc 循环结束后,这批对象没有内部引用了,它们只有外部引用,且相互间可能有联系(即前面说的, A B 间有循环引用)。

这批对象暂时不能从 Lua 中删除,因为 C# 一侧可能还持有它们的引用,日后会访问它们。但 Lua 中目前已经没有引用了,可以把这些对象的删除请求发送给 Mono 。Mono 收到后,可以解除这批对象的外部引用(解开循环引用),等待 GC 工作;如果其中有对象真的被回收,再通知 Lua 真的删除掉。如果 C# 还在继续引用,则通知 Lua 把对象全部从坟场取回。

方案细节在前面给出的 issue 中已经讨论的足够多了,这里不再展开。


我们真的需要这么细致的管理双向引用么?

在我们自己的项目中,并没有做这些复杂处理。这是因为,一旦在 C# 中加入 Lua ,就暗示着把业务逻辑搬到了 Lua 中写。在 Mono 和 Lua 两边都存在业务逻辑且交叉引用的情况本身就是很不合理的。更多的情况是,Mono 负责和引擎底层沟通,所有的引擎对象都是由 Lua 通过中间城命令 C# 去创建的;当 Lua 层不再使用这些对象后,再通知删除。C# 本身并没有业务层去引用这些对象。Lua 和 C# 应该是应该上下层清晰的关系,而不应该是混杂在一起的并列关系。

所以我推荐的做法是,只有 Lua 可以长期持有 Mono 中的 C# 对象,而 Mono 中只可以短期持有 Lua 层的对象(不超过游戏中的一帧)。这样,Lua 就有权利主动清理那些自己并不持有的本地对象而不需要通知 Mono 了,这种单边关系便不会产生循环引用。

Mono 中唯一可能长期持有的 Lua 对象唯有一些重要的回调函数,比如在每个游戏逻辑帧内都去调用一次 Lua 里定义好的 update 函数。而这种 Lua 函数对象,只需要让 Lua 自己长期保有引用(比如放在全局表里)就可以了。

即使真的想做出一套完备的 Mono 和 Lua 间的对象双向引用关系,我也推荐用最简单的方案,基础方案中不去考虑循环引用的问题。而可以单独写一个模块来解开潜在的循环引用,这个模块性能不是主要考虑问题,在合适的时候(比如 loading 场景时)启动检查即可。


最后简单说说我周末实现的这套 sharplua 。它提供了在 Mono 中创建出一个 Lua 虚拟机,并可以从 C# 调用 Lua 函数,获取返回值的能力。同时,Lua 代码中也可以调用由 C# 注入的 C# 函数。

SharpLua 类即对应一个 lua 5.3 虚拟机,需要传入第一个 lua 文件名启动它。这个 lua 文件中必须 require "sharplua" 这个模块,辅助完成初始化工作。sharplua 这个 lua 模块中有部分是用来管理 mono 和 lua 间数据交换的内部函数,供底层工作时使用;还有一些提供给 lua 业务层使用的 api ,方便回调 C# 函数。

C# 这边只有三个 API 用来和 Lua 通讯。

可以通过 SharpLua.GetFunction 从 Lua 虚拟机的全局表中获得一个以字符串命名的全局函数。这是一切逻辑的起点。之所以不提供更多的获取 Lua 内部数据的 C# API 是因为,其他的需求都可以通过你自己写一个 Lua 全局函数来完成,C# 只需要调用它就可以了。

SharpLua.CallFunction 可以用来调用一个 Lua 函数,携带任意参数,可获得任意返回值。为了实现简单,这里限制了一次函数调用最多传 255 个参数,返回值不能超过 256 个。

注意,返回值也可以是一个 Lua 函数对象。所以你可以写一个 Lua 全局函数来返回 Lua 虚拟机中的其它函数。而参数则可以是任意对象,除了数字、字符串等这些 Mono 和 Lua 都有的基本类型外,还可以传入之前的获取的 Lua 对象以及 C# 的任意 Class 对象。这里约定了一种指定的 Delegate ,一旦把它传个 Lua ,Lua 可以通过 sharplua.call 来回调它,从而可以做到 Lua 向 C# 通讯。具体用法可以参考 test.cs ,虽然这里是手写了一个 Delegate 供 Lua 调用,但是你可以继续完善它,比如使用 C# 的反射能力去间接调用任何你想调用的 C# 函数,也可以为 C# 类做一些代码生成工作,生成函数以这个 Delegate 的形式注入 Lua 。

最后一个 API 是 SharpLua.CollectGarbage 。它会从 Lua 虚拟机中收集那些曾经传给 Lua 的 C# 对象中,哪些 Lua 已经不再使用,好让 Mono 这边可以解除引用让 Mono 的 GC 可以正确工作以回收掉它们。

SharpLua 它整个实现简单易读,对外接口也很少。稍加封装,就可以嵌入 Unity3D 中使用。如果有同学有兴趣继续完善,欢迎提 PR 。


有几点是可以继续做的。

  1. C# 的字符串最好能 marshal 成 Unicode ,然后在 Lua 里转换成 utf8 ;还有相关的反向处理。

  2. 在 marshal 字符串的时候,如果发现是短字符串,可以在 mono 和 lua 间同步一张不太大的字符串表,只在第一次传递的时候对 string 做 marshal ,之后相同的字符串都查表传 id ,减轻 string 传递的负担。