石头剪子布最优策略的线性解法

• 2020 年 3 月 27 日
• 筆記

石头剪子布属于一种 zero-sum game，即一个人的 loss 是另一个人的 gain。

这个问题可以有多种解法，我们可以选择 linear programming 的方法：

设我们要求解的变量为：x = [U, R, P, S] U 是期望的效用，R 是出石头的概率，P 是出布的概率，S 是出剪子的概率。 我们的目标是在一组限制条件下，最大化 U。

这组限制条件由石头剪子布的 reward 矩阵 A 决定： 例如，有矩阵 A ：

则限制条件为：

以及：R + P + S = 1。

结合前面几篇介绍 cvxopt 的文章看，我们可以将上图这个问题转化为带有 c，G，h，A，b 的约束问题格式：

所以可以得到：

有个 c，G，h，A，b 的数值，就可以调用 cvxopt 进行求解此优化问题，最后 solution 里面的 x 中后三项就是要求的概率。