人工智能導(dǎo)論-第8章-AI博弈

提綱二、博弈策略求解一、博弈論的相關(guān)概念三、博弈規(guī)則設(shè)計四、非完全信息博弈的實際應(yīng)用博弈論的誕生：中國古代博弈思想子曰：飽食終日，無所用心，難矣哉！不有博弈者乎？為之，猶賢乎已。 ——《論語?陽貨》朱熹集注曰：“博，局戲；弈，圍棋也?！?；顏師古注：“博，六博；弈，圍碁也。”古語博弈所指下圍棋，圍棋之道蘊含古人謀劃策略的智慧。略觀圍棋，法于用兵，怯者無功，貪者先亡。 ——《圍棋賦》《孫子兵法》等講述兵書戰(zhàn)法的古代典籍更是凸顯了古人對策略的重視。博弈論的誕生：田忌賽馬……齊將田忌善而客待之。忌數(shù)與齊諸公子馳逐重射。孫子見其馬足不甚相遠(yuǎn)，馬有上、中、下輩。于是孫子謂田忌曰：“君弟重射，臣能令君勝?！碧锛尚湃恢c王及諸公子逐射千金。及臨質(zhì)，孫子曰：“今以君之下駟與彼上駟，取君上駟與彼中駟，取君中駟與彼下駟?！奔锐Y三輩畢，而田忌一不勝而再勝，卒得王千金。于是忌進孫子于威王。威王問兵法，遂以為師。——《史記?孫子吳起列傳》

以己之長攻彼之短表8.1齊威王與田忌進行賽馬中所采取的不同對局博弈論的誕生：現(xiàn)代博弈論的建立博弈論（gametheory），又稱對策論。博弈行為：帶有相互競爭性質(zhì)的主體，為了達(dá)到各自目標(biāo)和利益，采取的帶有對抗性質(zhì)的行為。博弈論主要研究博弈行為中最優(yōu)的對抗策略及其穩(wěn)定局勢，協(xié)助人們在一定規(guī)則范圍內(nèi)尋求最合理的行為方式。1944年馮·諾伊曼與奧斯卡·摩根斯特恩合著《博弈論與經(jīng)濟行為》，以數(shù)學(xué)形式來闡述博弈論及其應(yīng)用，標(biāo)志著現(xiàn)代系統(tǒng)博弈理論的初步形成，馮·諾伊曼被稱為現(xiàn)代博弈論之父。JohnvonNeumann(1903-1957),OskarMorgenstern(1902-1977),TheoryofGamesandEconomicBehavior,PrincetonUniversityPress,1944博弈論的相關(guān)概念：博弈的要素參與者或玩家（player）：參與博弈的決策主體策略（strategy）：參與者可以采取的行動方案，是一整套在采取行動之前就已經(jīng)準(zhǔn)備好的完整方案。某個參與者可采納策略的全體組合形成了策略集（strategyset）所有參與者各自采取行動后形成的狀態(tài)被稱為局勢（outcome）如果參與者可以通過一定概率分布來選擇若干個不同的策略，這樣的策略稱為混合策略（mixedstrategy）。若參與者每次行動都選擇某個確定的策略，這樣的策略稱為純策略（purestrategy）收益（payoff）：各個參與者在不同局勢下得到的利益混合策略意義下的收益應(yīng)為期望收益（expectedpayoff）規(guī)則（rule）：對參與者行動的先后順序、參與者獲得信息多少等內(nèi)容的規(guī)定建模者對參與者（player）規(guī)定可采取的策略集(strategysets)和取得的收益，觀察當(dāng)參與者選擇若干策略以最大化其收益時會產(chǎn)生什么結(jié)果兩害相權(quán)取其輕，兩利相權(quán)取其重博弈論的相關(guān)概念：研究范式博弈論的相關(guān)概念：囚徒困境（prisoner’sdilemma）參與者：甲、乙規(guī)則：甲、乙兩人分別決策，無法得知對方的選擇策略集：認(rèn)罪、沉默（純策略）局勢及對應(yīng)收益（年）甲認(rèn)罪：0 乙沉默：-10甲認(rèn)罪：-5 乙認(rèn)罪：-5甲沉默：-10 乙認(rèn)罪：0甲沉默：-0.5 乙沉默：-0.5在囚徒困境中，最優(yōu)解為兩人同時沉默，但是兩人實際傾向于選擇同時認(rèn)罪（均衡解）1950年，蘭德公司的梅里爾·弗勒德和梅爾文·德雷希爾擬定了相關(guān)困境理論，后來美國普林斯頓大學(xué)數(shù)學(xué)家阿爾伯特·塔克以“囚徒方式”闡述：

警方逮捕了共同犯罪的甲、乙兩人，由于警方?jīng)]有掌握充分的證據(jù)，所以將兩人分開審訊：若一人認(rèn)罪并指證對方，而另一方保持沉默，則此人會被當(dāng)即釋放，沉默者會被判監(jiān)禁10年若兩人都保持沉默，則根據(jù)已有的犯罪事實（無充分證據(jù)）兩人各判半年若兩人都認(rèn)罪并相互指證，則兩人各判5年乙沉默（合作）乙認(rèn)罪（背叛）甲沉默（合作）二人各服刑半年乙被釋放，甲服刑10年甲認(rèn)罪（背叛）甲被釋放，乙服刑10年二人各服刑5年博弈論的相關(guān)概念：囚徒困境（prisoner’sdilemma）1950年，蘭德公司的梅里爾·弗勒德和梅爾文·德雷希爾擬定了相關(guān)困境理論，后來美國普林斯頓大學(xué)數(shù)學(xué)家阿爾伯特·塔克以“囚徒方式”闡述：

警方逮捕了共同犯罪的甲、乙兩人，由于警方?jīng)]有掌握充分的證據(jù)，所以將兩人分開審訊：若一人認(rèn)罪并指證對方，而另一方保持沉默，則此人會被當(dāng)即釋放，沉默者會被判監(jiān)禁10年若兩人都保持沉默，則根據(jù)已有的犯罪事實（無充分證據(jù)）兩人各判半年若兩人都認(rèn)罪并相互指證，則兩人各判5年乙沉默（合作）乙認(rèn)罪（背叛）甲沉默（合作）二人各服刑半年乙被釋放，甲服刑10年甲認(rèn)罪（背叛）甲被釋放，乙服刑10年二人各服刑5年參與者：甲、乙規(guī)則：甲、乙兩人分別決策，無法得知對方的選擇策略集：認(rèn)罪、沉默（純策略）局勢及對應(yīng)收益（年）甲認(rèn)罪：0 乙沉默：-10甲認(rèn)罪：-5 乙認(rèn)罪：-5甲沉默：-10 乙認(rèn)罪：0甲沉默：-0.5 乙沉默：-0.5在囚徒困境中，最優(yōu)解為兩人同時沉默，但是兩人實際傾向于選擇同時認(rèn)罪（均衡解）合作博弈與非合作博弈合作博弈（cooperativegame）：部分參與者可以組成聯(lián)盟以獲得更大的收益非合作博弈（non-cooperativegame）：參與者在決策中都彼此獨立，不事先達(dá)成合作意向靜態(tài)博弈與動態(tài)博弈靜態(tài)博弈（staticgame）：所有參與者同時決策，或參與者互相不知道對方的決策動態(tài)博弈（dynamicgame）：參與者所采取行為的先后順序由規(guī)則決定，且后行動者知道先行動者所采取的行為完全信息博弈與不完全信息博弈完全信息（completeinformation）：所有參與者均了解其他參與者的策略集、收益等信息不完全信息（incompleteinformation）：并非所有參與者均掌握了所有信息囚徒困境是一種非合作、不完全信息的靜態(tài)博弈博弈論的相關(guān)概念：博弈的分類博弈的穩(wěn)定局勢即為納什均衡（Nashequilibrium）：指的是參與者所作出的這樣一種策略組合，在該策略組合上，任何參與者單獨改變策略都不會得到好處。換句話說，如果在一個策略組合上，當(dāng)所有其他人都不改變策略時，沒有人會改變自己的策略，則該策略組合就是一個納什均衡。

Nash定理：若參與者有限，每位參與者的策略集有限，收益函數(shù)為實值函數(shù)，則博弈必存在混合策略意義下的納什均衡。囚徒困境中兩人同時認(rèn)罪就是這一問題的納什均衡。Nash,J,Non-CooperativeGames.

TheAnnalsofMathematics.54,2(1951),286.博弈論的相關(guān)概念：納什均衡納什均衡的本質(zhì)不后悔博弈論的相關(guān)概念：混合策略下納什均衡的例子參與者：雇員、雇主規(guī)則：雇員與雇主兩人分別決策，事先無法得知對方的選擇混合策略集：雇員：偷懶、不偷懶雇主：檢查、不檢查局勢及對應(yīng)收益雇主采取檢查策略時雇員工作與偷懶對應(yīng)的結(jié)果雇主采取不檢查策略時雇員工作與偷懶對應(yīng)的結(jié)果

表8.4雇主-雇員每次采取對應(yīng)行動后的收益

博弈論的相關(guān)概念：混合策略下納什均衡的例子表8.5雇主-雇員之間博弈的期望收益表8.4雇主-雇員每次采取對應(yīng)行動后的收益

混合策略納什均衡：博弈過程中，博弈方通過概率形式隨機從可選策略中選擇一個策略而達(dá)到的納什均衡被稱為混合策略納什均衡。博弈論的相關(guān)概念：混合策略下納什均衡的例子表8.5雇主-雇員之間博弈的期望收益博弈論的相關(guān)概念：策梅洛定理策梅洛定理（Zermelo'stheorem）：對于任意一個有限步的雙人完全信息零和動態(tài)博弈，一定存在先手必勝策略或后手必勝策略或雙方保平策略

提綱二、博弈策略求解一、博弈論的相關(guān)概念三、博弈規(guī)則設(shè)計四、非完全信息博弈的實際應(yīng)用博弈策略求解動機博弈論提供了許多問題的數(shù)學(xué)模型納什定理確定了博弈過程問題存在解人工智能的方法可用來求解均衡局面或者最優(yōu)策略主要問題如何高效求解博弈參與者的策略以及博弈的均衡局勢？應(yīng)用領(lǐng)域大規(guī)模搜索空間的問題求解：圍棋非完全信息博弈問題求解：德州撲克網(wǎng)絡(luò)對戰(zhàn)游戲智能：Dota、星球大戰(zhàn)動態(tài)博弈的均衡解：廠家競爭、信息安全虛擬遺憾最小化算法（RegretMinimization）：若干定義

虛擬遺憾最小化算法：最優(yōu)反應(yīng)策略

虛擬遺憾最小化算法：納什均衡

遺憾最小化算法遺憾最小化算法是一種根據(jù)以往博弈過程中所得遺憾程度來選擇未來行為的方法。

遺憾最小化算法：有效遺憾值遺憾最小化算法：有效遺憾值

遺憾最小化算法：石頭-剪刀-布的例子

遺憾最小化算法：石頭-剪刀-布的例子

表8.7玩家A在兩輪后所得到的遺憾值遺憾最小化算法：計算理論

遺憾最小化算法：計算理論

遺憾最小化算法：計算理論

28

遺憾最小化算法：計算理論29

遺憾最小化算法：計算理論遺憾最小化算法在虛擬最小化算法的求解過程中，同樣需要反復(fù)模擬多輪博弈來擬合最佳反應(yīng)策略，算法步驟如下：初始化遺憾值和累加策略表為0采用隨機選擇的方法來決定策略利用當(dāng)前策略與對手進行博弈計算每個玩家采取每次行為后的遺憾值根據(jù)博弈結(jié)果計算每個行動的累加遺憾值大小來更新策略重復(fù)3)到5)步若干次，不斷的優(yōu)化策略根據(jù)重復(fù)博弈最終的策略，完成最終的動作選擇遺憾最小化算法表8.8雙人庫恩撲克游戲規(guī)則庫恩撲克[Kuhn1950]是一種簡單的有限注撲克游戲，由兩名玩家進行游戲博弈，游戲中僅提供牌值為1、2和3的三張紙牌。每輪中每位玩家各持一張紙牌，每位玩家根據(jù)各自判斷來決定是否追加定額賭注。攤牌階段時來比較未棄牌玩家的底牌大小，底牌值最大的玩家即為勝者。遺憾最小化算法

圖8.1先手玩家A對應(yīng)的庫恩撲克博弈樹

遺憾最小化算法圖8.1先手玩家A對應(yīng)的庫恩撲克博弈樹

遺憾最小化算法

35

遺憾最小化算法

遺憾最小化算法于是，根據(jù)遺憾值匹配算法計算結(jié)果，在下一輪的策略中會選擇“過牌”策略。遺憾最小化算法圖8.2先手玩家手牌為1的庫恩撲克博弈樹遺憾最小化算法圖8.3三人庫恩撲克的部分博弈樹安全子博弈從當(dāng)前已經(jīng)完成的部分博弈出發(fā)，將接下來博弈過程視為是一個單獨子博弈，然后找到子博弈的最優(yōu)反應(yīng)策略，這樣可以減小計算量，以便在接近葉節(jié)點的情況下得到更加精確的結(jié)果

圖8.4完全與非完全信息博弈的子博弈安全子博弈圖8.5拋硬幣游戲博弈樹玩家A隨機拋一個硬幣，然后根據(jù)硬幣的正反面可以決定將硬幣賣掉或者讓玩家B來猜測硬幣的正反面。如果硬幣拋擲結(jié)果是正面，玩家A賣掉這一硬幣可以獲得0.5元收益，如果硬幣拋擲結(jié)果是負(fù)面，則玩家A賣掉這一硬幣會虧損0.5元（收益為-0.5）。如果玩家A不采取售賣硬幣的行動，而是讓玩家B猜硬幣的正反，則玩家B猜錯正反前提下玩家A可以獲得1元或者玩家B猜對正反前提下玩家A會虧損1元。安全子博弈

安全子博弈

提綱二、博弈策略求解一、博弈論的相關(guān)概念三、博弈規(guī)則設(shè)計四、非完全信息博弈的實際應(yīng)用博弈規(guī)則設(shè)計：研究問題在現(xiàn)實生活中，如果所有博弈者都追求自己利益最大化，很可能會導(dǎo)致兩敗俱傷的下場，那么應(yīng)該如何設(shè)計博弈的規(guī)則使得博弈的最終局勢能盡可能達(dá)到整體利益的最大化呢？例如許多城市為了避免機動車過快增長造成城市擁堵，因此限制了車牌的發(fā)放量。這樣，車牌的發(fā)放方式就是需要決策者經(jīng)過周密的考慮后決定的。通常而言，車牌的發(fā)放既要能滿足有緊迫需求的人，又要滿足普通家庭的日常需求，所以很多城市都采取了車牌競價和隨機搖號兩種方式發(fā)放車牌。博弈規(guī)則設(shè)計：雙邊匹配算法在生活中，人們常常會碰到與資源匹配相關(guān)的決策問題(如求職就業(yè)、報考錄取等)，這些需要雙向選擇的情況被稱為是雙邊匹配問題。在雙邊匹配問題中，需要雙方互相滿足對方的需求才會達(dá)成匹配。

穩(wěn)定婚姻問題（stablemarriageproblem）博弈規(guī)則設(shè)計：雙邊匹配算法

表8.9穩(wěn)定婚姻匹配偏好序列博弈規(guī)則設(shè)計：雙邊匹配算法按照“修補”策略，匹配和修補過程如下表8.10修補策略下的穩(wěn)定婚姻匹配過程1962年，美國數(shù)學(xué)家大衛(wèi)·蓋爾和博弈論學(xué)家沙普利提出了針對雙邊穩(wěn)定匹配問題的解決算法（也被稱為Gale-Shapely算法或G-S算法），并將其應(yīng)用于穩(wěn)定婚姻問題的求解[Gale1962]，算法過程如下：單身男性向最喜歡的女性表白所有收到表白的女性從向其表白男性中選擇最喜歡的男性，暫時匹配未匹配的男性繼續(xù)向沒有拒絕過他的女性表白。收到表白的女性如果沒有完成匹配，則從這一批表白者中選擇最喜歡男性。即使收到表白的女性已經(jīng)完成匹配，但是如果她認(rèn)為有她更喜歡的男性，則可以拒絕之前的匹配者，重新匹配如此循環(huán)迭代，直到所有人都成功匹配為止博弈規(guī)則設(shè)計：雙邊匹配算法博弈規(guī)則設(shè)計：雙邊匹配算法表8.11G-S算法下的穩(wěn)定婚姻匹配過程

博弈規(guī)則設(shè)計：單邊匹配算法在匹配問題中，除了需要雙向選擇的雙邊匹配問題，還有一種類似于以物易物方式的交換匹配問題，被稱為單邊匹配問題，例如室友的匹配或者是座位的分配。這些問題中分配的對象都是不可分的標(biāo)的物，他們只能屬于一個所有者，且可以屬于任何一個所有者。博弈規(guī)則設(shè)計：單邊匹配算法對于單邊匹配問題，1974年，沙普利和斯卡夫提出了針對單邊匹配問題的穩(wěn)定匹配算法“最大交易圈算法（Top-tradingcycle，TTC）”[Shapley1974]，算法過程如下：首先記錄每個標(biāo)的物的初始占有者，或者對物品進行隨機分配。每個交易者連接一條指向他最喜歡的標(biāo)的物的邊，并從每一個標(biāo)的物連接到其占有者或是具有高優(yōu)先權(quán)的交易者。此時形成一張有向圖，且必存在環(huán)，這種環(huán)被稱為“交易圈”，對于交易圈中的交易者，將每人指向節(jié)點所代表的標(biāo)的物賦予交易者，同時交易者放棄原先占有的標(biāo)的物，占有者和匹配成功的標(biāo)的物離開匹配市場。接著從剩余的交易者和標(biāo)的物之間重復(fù)進行交易圈匹配，直到無法形成交易圈，算法停止。博弈規(guī)則設(shè)計：單邊匹配算法穩(wěn)定室友匹配問題就是一個典型的單邊匹配問題。假設(shè)某寢室有A、B、C、D四位同學(xué)和1、2、3、4四個床位，當(dāng)前給A、B、C、D四位同學(xué)隨機分配4、3、2、1四個床位。表8.12床位偏好順序博弈規(guī)則設(shè)計：單邊匹配算法圖8.6第一輪單邊匹配圖8.7第二輪單邊匹配在圖8.6可以看出:，A和D之間構(gòu)成一個交易圈，可達(dá)成交易，所以A得到床位1，D得到床位4，之后將A和D以及1和4從匹配圖中移除。從圖8.7可以看出，B和C都希望得到床位2，無法再構(gòu)成交易圈，但是由于C是床位的本身擁有者，所以C仍然得到床位2，B只能選擇床位3。博弈規(guī)則設(shè)計：單邊匹配算法圖8.6第一輪單邊匹配

圖8.7第二輪單邊匹配在圖8.6可以看出:，A和D之間構(gòu)成一個交易圈，可達(dá)成交易，所以A得到床位1，D得到床位4，之后將A和D以及1和4從匹配圖中移除。從圖8.7可以看出，B和C都希望得到床位2，無法再構(gòu)成交易圈，但是由于C是床位的本身擁有者，所以C仍然得到床位2，B只能選擇床位3。最后交易結(jié)果A→1，B→3，C→2，D→4提綱二、博弈策略求解一、博弈論的相關(guān)概念三、博弈規(guī)則設(shè)計四、非完全信息博弈的實際應(yīng)用非完全信息博弈的實際應(yīng)用圖8.8博弈論研究內(nèi)容非完全信息博弈的實際應(yīng)用圖8.9求解非完全信息博弈納什均衡的一般方法非完全信息博弈的實際應(yīng)用深度強化學(xué)習(xí)越來越多的被應(yīng)用于博弈的策略求解。強化學(xué)習(xí)的主要思想是通過試錯和搜索來優(yōu)化自身的行動[Sutton2018]，這一過程可以直接被應(yīng)用于博弈的決策中。在連續(xù)動態(tài)的環(huán)境中，通過強化學(xué)習(xí)的訓(xùn)練，可以讓參與博弈的AI智能體在不同情況下能夠找到可獲得最大收益的最佳策略[Racanière2017