最大最小化

最大最小化（minimax / minmax）係博弈論講到嘅一種策略，討論人工智能嗰陣成日提及，可以用嚟教電腦做決策。廣義嚟講，用最大最小化做決策，旨在想令到某啲「最大數值」有咁細得咁細，當中「最大數值」可以係對手嘅最大報償，或者係自己嘅「最大後悔值」呀噉。

2023 年喺澳門一間賭場影到嘅相；企响門口嘅賭客：「嗯... 我選擇入去賭，最高可以帶嚟幾大嘅後悔呢？」

背景概念

内文：博弈論同博弈策略

睇埋：馮紐曼同風險管理

最大最大化

表 1：出紅咭定出藍咭好？

	阿 B 出紅	阿 B 出藍
阿 A 出紅	0, 0	0, 0
阿 A 出藍	-100, 100	100, -100

首先，要講講最大最大化策略（maximax）——做法係「諗吓每個選項嘅最高報償，再揀最高報償值最高嗰個」。想像依家有一場零和博弈，兩位博弈者，佢哋各自手上揸住一張藍色咭同一張紅色咭，喺每場對局當中，佢哋要同時將其中一張咭擺上檯，遊戲噉玩：

1. 如果 A 君出咗紅咭，無論 B 君出邊張咭都好，兩人打和。
2. 如果 A 君出咗藍咭嘅話...
   • 如果 B 君出嘅係紅咭，噉 B 君贏 100 文港紙。
   • 如果 B 君出嘅係藍咭，噉 A 君贏 100 文港紙。

場博弈嘅報償矩陣係好似表 1 噉嘅樣。當中 (x, y) 結果表示「A 君贏 x 咁多錢而 B 君贏 y 咁多錢」。假如 A 君跟從最大最大化嘅法則行事，佢會永遠選擇出藍咭：對佢嚟講，出紅咭嘅最大可得係 0，而出藍咭嘅最大可得係 100 文港紙。假如 A 君按噉嘅法則行事，B 君可以利用佢嘅單純—— B 君可以選擇永世出紅咭，噉佢就永世都贏錢。由此可見，最大最大化有個缺點：決策者冇考慮到對手會點反應；呢種策略因此畀人話佢本質上就係唔理性嘅，只有極天真（例如細路）或者極肯博嘅決策者，先會採取噉嘅策略。

用數學符號表述嘅話，maximax 決策法則如下：

${\underline {v_{i}}}=\max _{a_{i}}\max _{a_{-i}}{v_{i}(a_{i},a_{-i})}$，當中

• i 係做緊決策嗰位博弈者嘅「ID 冧把」。
• $-i$ 表示 i 以外嘅所有博弈者。
• $a_{i}$ 係指由 i 採取嘅行動。
• $a_{-i}$ 係指由其他博弈者採取嘅行動。
• $v_{i}$ 係 i 嘅價值函數。

最小最大化

表 2：部老虎機咁著數，賭唔賭？

	贏	輸
賭	+10,000	-1
唔賭	0	0

跟住，又思考吓最小最大化策略（maximin） ——做法係「諗吓每個選項嘅最低報償，再揀最低報償值最高嗰個」。想像依家阿明去賭場賭錢，佢搵到一部異常咁著數嘅老虎機：賭客贏咗可以賺到 10,000 文港紙咁多，而輸咗就只會損失 1 文（睇表 2 個矩陣），由阿明嘅角度睇——

1. 「唔賭」嘅最低可得係 0；
2. 「賭」嘅最低可得係 -1（損失 1 文）；

根據最小最大化，阿明理應選擇「唔賭」——但係一般認為，喺呢個情境下阿明係應該「去賭」至最著數。Maximin 嘅決策方法用數學符號表達如下：

${\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}$

相對於最大最大化嘅過度樂觀，最小最大化被認為係悲觀得滯，決策者彷彿假定咗自己永遠只會得到最壞結果，呢種思考法亦被指係唔理想嘅策略。

後悔模型

内文：後悔 (決策論)

睇埋：機會成本

表 3：好唔好抌錢做研發？

	研發成功	研發失敗
抌錢	r-c	-c
唔抌	0	0

表 4：抌錢做研發嘅「後悔矩陣」

	研發成功	研發失敗
抌錢	0	c
唔抌	r-c	0

「後悔嘅最大最小化」呢種決策方式，被指係有別於太樂觀嘅 maximax 同埋太悲觀嘅 maximin。

• Maximax：對每個選項，淨係睇佢嘅報償最高係幾多，揀對自己最有利嗰個。
• Maximin：對每個選項，淨係睇佢嘅報償最低係幾多，揀對自己最有利嗰個。

後悔最大最小化原則源自匈牙利裔美國數學家馮紐曼嘅研究。依家想像一間企業，佢哋要決定「係咪要抌本做研發」，假設研發嘅成本係 c 咁多，假如研發成功，會為間企業帶嚟 r 咁多嘅利潤，而假如研發失敗，間企業唔會得到任何嘅利潤，只會損失抌咗落去做研發嗰筆錢，即係好似表 3 所示。

• 跟 maximax 嘅決策者：只要 r > c 就無論如何都要做研發。
• 跟 maximin 嘅決策者：無論如何都唔肯做研發。

後悔最大最小化原則就比較複雜：首先，思考後悔嘅概念，後悔好似經濟學講嘅機會成本，講緊「如果揀咗呢個選項，會錯過啲乜」——假如想研發嗰樣嘢係掂嘅，但係間企業冇郁手研發，佢哋會錯失得到 r-c 嘅機會，而假如想研發嗰樣嘢係唔掂嘅，但係間企業郁手研發，佢會錯失 c 咁多嘅成本。如果將呢套思考畫做一個「後悔矩陣」，會好似表 4 所表示嘅噉。

後悔最大最小化原則講緊嘅，就係決策者要盡可能減少（最小化）自己嘅「最高後悔值」：攞每一個選項嚟睇，決策者要睇下嗰個選項最高可以帶嚟幾高嘅後悔值，然後佢會揀「最高後悔值」最低嗰一個；喺做研發嗰個例子當中，如果 r 數值夠大（r - c > c），間企業會選擇郁手做研發，而如果 r 數值唔夠大（r - c < c），佢哋就唔會郁手做研發。用數學符號嚟表達嘅話，後悔最大最小化原則可以噉嚟表述：

${\underline {v_{i}}}=\min _{a_{i}}\max _{a_{-i}}{R(a_{i},a_{-i})}$，

當中 $R$ 就係指後悔值。好似後悔 minimax 噉樣嘅決策方式，被認為係比較理性嘅做法。

靠電腦計

依幅圖局部描繪井字過三關嘅決策樹。最頂係初始狀態，下一行係「行咗第一步」後嘅可能狀態，再下一行係「行咗第二步」後嘅可能狀態... 如此類推。

睇埋：遞歸 (電腦科學)同遊戲 AI

遊戲人工智能相關嘅工作，不時會教電腦用最大最小化做決策。如果要教電腦喺一場兩人對局嘅零和遊戲當中做最大最小化運算，可以大致想像以下噉嘅演算法，下便呢段虛擬碼界定咗一個叫 minmax 嘅子程序：

 子程序 minmax 如下——
 
 如果終結條件已經達到（例如已經摷咗 5 步）
   終結子程序，畀返分數 score 出嚟。
 
 如果係 max 緊（最大化緊）
   設最佳分數 = 負無限大
   將手上嘅可能選項逐個逐個攞嚟睇
     試吓行嗰一步，
     攞住呢個狀態，做一次 minmax，min 緊（呢度用咗遞歸），得出 score
     設最佳分數 = max(score, 最佳分數)
   畀返 最佳分數做 output
 
 如果係 min 緊（最小化緊）
   設最佳分數 = 正無限大
   將手上嘅可能選項逐個逐個攞嚟睇
     試吓行嗰一步，
     攞住呢個狀態，做一次 minmax，max 緊（呢度用咗遞歸），得出 score
     設最佳分數 = min(score, 最佳分數)
   畀返 最佳分數做 output

上述嘅演算法教電腦將可能發生嘅情境冚唪唥睇晒佢。噉嘅演算法淨係適用於一啲簡單嘅遊戲，例如井字過三關就可以用呢種演算法解決。如果係稍為複雜啲嘅遊戲——例如西洋棋或者圍棋呀噉，呢種演算法就應付唔嚟，做唔到喺夠短嘅時間內計出答案。

睇睇

• Alpha-beta 剪枝
• 蒙地卡羅樹搜尋
• 以牙還牙
• 遞歸算法

參考

註釋：

引述咗嘅文獻同網頁：

再睇

• （英文） Mishra, A. K., & Tsionas, M. G. (2020). A minimax regret approach to decision making under uncertainty. Journal of Agricultural Economics, 71(3), 698-718.
• （英文） Musman, S., & Turner, A. J. (2018). A game-oriented approach to minimizing cybersecurity risk. Safety and Security Studies, 27.
• （英文） Minmax 演算法嘅簡單動畫，YouTube 視頻，成條片都係以圖像化方式展示 minmax 演算法，冇語音。