最大最小化

首先，要理解最大最大化策略（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 君大可以選擇永遠出紅咭，噉佢就會永遠都贏錢。由此可見，最大最大化有個大缺點：決策者並冇考慮到對手會點樣反應；因此，呢種策略被指本質上係唔理性嘅，只有極天真（例如係細路）或者極肯博嘅決策者先會採取噉嘅策略^[1][2]。

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

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

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

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

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

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

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

相對於最大最大化嘅過度樂觀，最小最大化被認為係悲觀得滯，決策者彷彿假定咗自己永遠只會得到最壞結果，呢種思考法亦畀好多人認為係一種唔理想嘅決策方式^[1]。

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

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

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

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

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

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

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

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

遊戲人工智能相關嘅工作，不時都會教電腦用最大最小化嚟做決策^[6]。如果要教電腦喺一場兩人對局嘅零和遊戲當中做最大最小化嘅運算，可以大致想像以下噉嘅演算法，下便呢段虛擬碼界定咗一個叫 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 演算法，冇語音。