石頭剪子布最優策略的線性解法
- 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 中後三項就是要求的概率。