profit/loss 游戏中最佳预期数量的算法

Question

我最近遇到了以下问题，

"You have a box which has G green and B blue coins. Pick a random coin, G gives a profit of +1 and blue a loss of -1. If you play optimally what is the expected profit."

我正在考虑使用蛮力算法，其中我考虑了绿色和蓝色硬币组合的所有可能性，但我确信必须有更好的解决方案（B 和 G 的范围是从 0 到 5000 ).另外，最佳播放是什么意思？这是否意味着如果我选择所有蓝色硬币然后我会继续玩直到所有绿色硬币也被选择？如果是这样那么这意味着我不应该考虑绿色和蓝色硬币的所有可能性？

Answer 1

这个答案是错误的；请参阅 Paul Hankin 的反例答案和适当的分析。 我将此答案留在这里作为我们所有人的学习示例。

假设你的选择只是什么时候停止捡硬币，只要G > B你就继续。那部分很简单。如果您从 G < B 开始，那么您永远不会开始绘图，您的收益为 0。对于 G = B，没有任何策略会给您带来数学优势；那里的增益也是0.

对于预期的奖励，分两步进行：

(1) 任何平局序列的期望值。递归地执行此操作，计算第一次绘制时获得绿色或蓝色的机会，然后计算新状态 (G-1, B) 或 (G, B-1) 的预期值。您很快就会看到任何给定开奖号码的期望值（例如第 3 次开奖的所有可能性）与原始值相同。

因此，您对任何平局的预期值为 e = (G-B) / (G+B)。您的总体预期值为 e * d，其中 d 是您选择的抽奖次数。

(2) 预计中奖次数是多少？在 G = B 之前，你希望画多少次？我将把它留作学生的练习，但请注意之前递归执行此操作的想法。您可能会发现将游戏状态描述为 (extra, total) 更容易，其中 extra = G-B 和 total = G+B。

说明性练习：给定 G=4，B=2，你在前两次抽到 GG（然后停止游戏）的机会是多少？这样做的好处是什么？这与每次平局的 (4-2)/(4+2) 优势相比如何？

Answer 2

简单直观的答案：

您应该先估算一下蓝色和绿色硬币的总数。每次选择后，您将更新此估算值。如果您估计在任何时候蓝色硬币多于绿色硬币，您应该停止。

示例：

你开始，然后选择一枚硬币。它是绿色的，所以你估计 100% 的硬币都是绿色的。你选择蓝色，所以你估计 50% 的硬币是绿色的。您选择另一个蓝色硬币，因此您估计 33% 的硬币是绿色的。根据您的估计，此时已经不值得玩了，所以您停止了。

Answer 3

"obvious" 答案是只要绿色硬币多于蓝色硬币就玩。其实，这是错误的。例如，如果有 999 个绿色硬币和 1000 个蓝色硬币，这是一个预期利润的策略：

Take 2 coins
If GG -- stop with a profit of 2
if BG or GB -- stop with a profit of 0
if BB -- take all the remaining coins for a profit of -1

由于第一种和最后一种可能性都以接近 25% 的概率出现，因此您的总体预期约为 0.25*2 - 0.25*1 = 0.25

这只是一个极端例子中的简单策略，表明问题并不像乍看起来那么简单。

一般来说，g绿色硬币和b蓝色硬币的期望由递归关系给出：

E(g, 0) = g
E(0, b) = 0
E(g, b) = max(0, g(E(g-1, b) + 1)/(b+g) + b(E(g, b-1) - 1)/(b+g))

出现最后一行的最大值是因为如果玩的是-EV，那么你最好停下来。

这些递归关系可以在 O(gb) 时间内使用动态规划求解。

from fractions import Fraction as F

def gb(G, B):
    E = [[F(0, 1)] * (B+1) for _ in xrange(G+1)]
    for g in xrange(G+1):
        E[g][0] = F(g, 1)
    for b in xrange(1, B+1):
        for g in xrange(1, G+1):
            E[g][b] = max(0, (g * (E[g-1][b]+1) + b * (E[g][b-1]-1)) * F(1, (b+g)))
    for row in E:
        for v in row:
            print '%5.2f' % v,
        print
    print
    return E[G][B]

print gb(8, 10)

输出：

 0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
 1.00  0.50  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
 2.00  1.33  0.67  0.20  0.00  0.00  0.00  0.00  0.00  0.00  0.00
 3.00  2.25  1.50  0.85  0.34  0.00  0.00  0.00  0.00  0.00  0.00
 4.00  3.20  2.40  1.66  1.00  0.44  0.07  0.00  0.00  0.00  0.00
 5.00  4.17  3.33  2.54  1.79  1.12  0.55  0.15  0.00  0.00  0.00
 6.00  5.14  4.29  3.45  2.66  1.91  1.23  0.66  0.23  0.00  0.00
 7.00  6.12  5.25  4.39  3.56  2.76  2.01  1.34  0.75  0.30  0.00
 8.00  7.11  6.22  5.35  4.49  3.66  2.86  2.11  1.43  0.84  0.36

7793/21879

由此可见，玩8绿10蓝币的期望是正的(EV=7793/21879 ~= 0.36)，甚至玩2绿3蓝的币(EV)也是正期望=0.2)

profit/loss 游戏中最佳预期数量的算法

Algorithm for optimal expected amount in a profit/loss game

algorithm

probability