石頭剪子布最優策略的線性解法

  • 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 中後三項就是要求的概率。