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

2020-03-26 22:01:49 浏览数 (1)

石头剪子布属于一种 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 中后三项就是要求的概率。

0 人点赞