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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

遺憾最小化算法：計(jì)算理論

遺憾最小化算法：計(jì)算理論

28

遺憾最小化算法：計(jì)算理論29

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

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

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

遺憾最小化算法

35

遺憾最小化算法

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

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

安全子博弈

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

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

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

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

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