策略盜取論證

出自維基百科,自由嘅百科全書

策略盜取論證strategy-stealing argument)係組合博弈論入面嘅一個證明技巧,可以攞嚟證明好多二人序貫完全資訊博弈入面,第二個玩家冇包保贏嘅策略

呢種論證嘅流程通常係:

  1. 假設第二個玩家有包保贏嘅策略,
  2. 呢個策略應該可以應對第一個玩家嘅任何策略,
  3. 第一個玩家就可以根據情況「偷」第二個玩家嘅策略嚟自己用,噉就表示第一個玩家有包保贏嘅策略,造成矛盾,因爲冇可能兩個玩家都有必勝策略。

呢個矛盾就顯示,其實第一個玩家有不敗策略。

例子[編輯]

考慮有毒朱古力博弈:而家有一塊長方形、一格格嘅朱古力,其中最左下角嗰格係有毒嘅,食咗就會死。A 同 B 兩個玩家開始玩食朱古力遊戲,由 A 開始,輪流指定一格未食嘅朱古力,並將呢格上方、右方同右上方嘅朱古力冚唪唥食嗮佢,每次起碼都要食一格,直到有人食咗最後一格(亦即係左下角嗰格朱古力)毒死爲止。

喺呢場博弈入面,可以用策略盜取論證證明 A 有必勝策略:假設 B 有必勝策略,如果 A 第一步選擇淨係食右上角一格朱古力嘅話,B 嘅策略應該可以話畀 B 知佢應該指定邊一格朱古力,A 就可以偷取呢個策略,第一步就指定呢一格朱古力,留畀 B 指定另一格嘅朱古力,如此類推,繼續偷取 B 嘅策略。最後,A 可以將成個策略偷過來,策略盜取論證指出,呢個博弈入面,A 先係有必勝策略嗰個,B 將會被毒死。

參考資料[編輯]