游戲策略講義-資料下載頁(yè)
2025-01-16 05:53本頁(yè)面
【正文】 ionsoffieldsbelongingtoAnn,andthen,ofonesbelongingtoBilly.The(i+1)stline,for1=i=a+b,beginswithintegersz,kmeaningrespectivelythecolourofthefieldi(0meanswhite,1green)andthenumberofsuccessorsofthisfield.Thenkintegers(1=ka+b)arewritten(stillinthesameline).Theyarethenumbersdenotingthesuccessorsoftheithfield.Theintegersineachlineareseparatedbysinglespaces.Thenumberofgreenfieldsontheboardisnotgreaterthan100.Thetotalnumberofsuccessorsofallthefieldsontheboardisnotgraterthan30000.l Outputl Thefirstlineofthetextfileshouldcontainexactlyoneintegerl,whichindicatesthenumberoffieldsforwhichAnnhasawinningstrategy.Thefollowingllinesshouldcontainnumbersofthesefieldswritteninascendingordereachintegershouldbewritteninaseparateline.分析l 在整個(gè)的游戲過(guò)程當(dāng)中， Ann和 Billy都會(huì)設(shè)法讓自己贏得游戲。首先我們必須明確一點(diǎn)：從某一區(qū)域出發(fā)，如果 Ann沒(méi)有必勝策略，那么 Billy顯然存在著必勝策略，反之亦然。根據(jù)這一特點(diǎn)，設(shè)置一個(gè)布爾函數(shù) y=f(i)，當(dāng) f(i)=true時(shí)表示從編號(hào)為的區(qū)域開(kāi)始游戲 Ann存在著贏得游戲的必勝策略，當(dāng) f(i)=false時(shí)則表示 Billy存在著贏得游戲的必勝策略。l 當(dāng)士兵處于屬于 Ann的區(qū)域的時(shí)候，如果這個(gè)區(qū)域的某一個(gè)后繼區(qū)域能夠是 Ann必勝的話(huà)， Ann肯定會(huì)讓士兵走向那一個(gè)區(qū)域，同樣當(dāng)士兵處于屬于 Billy的區(qū)域的時(shí)候 Billy也會(huì)采用相同的策略。那么，可以得到這樣一個(gè)遞推公式：構(gòu)圖l 為了便于思考，將問(wèn)題簡(jiǎn)化一下：把 a+b個(gè)區(qū)域看成 a+b個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)與區(qū)域編號(hào)對(duì)應(yīng)，如果編號(hào)為 i的區(qū)域是編號(hào)為 j的區(qū)域的后繼區(qū)域，就從編號(hào)為 i的節(jié)點(diǎn)向編號(hào)為 j的節(jié)點(diǎn)連一條有相弧 i?j，這樣便構(gòu)成了一個(gè)由 a+b個(gè)節(jié)點(diǎn)構(gòu)成的有向圖。l 然而在這個(gè)有向圖中存在著許許多多的環(huán)，上面的這一遞推式顯然存在后效性，是不能夠求解的。但是如果某一些區(qū)域的 f值能夠直接求得的話(huà)，其它區(qū)域的 f值就有可能求出來(lái)。求 f值l 定義 B集合是一個(gè)點(diǎn)集，該集合當(dāng)中不存在綠色節(jié)點(diǎn)，所有的節(jié)點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量，若編號(hào)為 i的節(jié)點(diǎn)屬于該集合，當(dāng)時(shí)，該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)都屬于該集合，當(dāng)時(shí)，該節(jié)點(diǎn)至少有一個(gè)后繼節(jié)點(diǎn)屬于該集合。l B集合有一個(gè)非常重要的性質(zhì)：一旦士兵走入了某一個(gè) B集合， Billy總能夠使士兵始終處于該集合當(dāng)中，而 Ann無(wú)法使士兵走出該集合。由于B集合當(dāng)中節(jié)點(diǎn)個(gè)數(shù)是有限的，所以士兵經(jīng)過(guò)的路線(xiàn)上必定會(huì)出現(xiàn)一個(gè)沒(méi)有綠色節(jié)點(diǎn)的環(huán)。因此只要士兵走進(jìn)某一個(gè) B集合當(dāng)中，那么 Billy必然會(huì)贏得比賽的勝利，故所有 B集合當(dāng)中的節(jié)點(diǎn)的 f值都為 False。l 接下來(lái)，根據(jù)上面的遞推式能夠確定另外一些節(jié)點(diǎn)（當(dāng)且僅當(dāng)該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)的 f值已經(jīng)確定了）的 f值，這些節(jié)點(diǎn)的 f值都只可能為False。例如上圖那一個(gè)例子，圖中標(biāo)有星號(hào)的那些節(jié)點(diǎn)可以在確定 B集合之后確定它們的 f值。進(jìn)一步分析l 實(shí)際上從上圖涂有紅色的那些節(jié)點(diǎn)出發(fā)仍然是 Billy獲得比賽的勝利，因此這些節(jié)點(diǎn)的 f值也應(yīng)當(dāng)為 False。可按照上面的步驟 f值是不能夠確定的，怎樣處理這種情況呢？l 確定 B集合的目的是為了使士兵走入這個(gè)點(diǎn)集后 Ann不能讓他走不出來(lái)，從而使 Billy獲得游戲的勝利，如果 Ann可以使士兵走出來(lái)，但不過(guò)是使士兵走到了一個(gè)使 Billy必勝的節(jié)點(diǎn)，這樣在本質(zhì)上與士兵仍處于 B集合是一樣的。l 因此可以把所有已經(jīng)確定了 f值的節(jié)點(diǎn)刪除，那么被涂成紅色的節(jié)點(diǎn)就成為了一個(gè)新的 B集合。算法框架while能夠從圖中找到 B集合 do{ 尋找所有的 B集合并將所有 B集合當(dāng)中的節(jié)點(diǎn)的 f值置為 False； 尋找所有可以確定 f值的節(jié)點(diǎn)，并將它們的置值為 False； 將已確定 f值的節(jié)點(diǎn)從圖中刪除；}將剩余的節(jié)點(diǎn)的 f置值為 True.l 下面簡(jiǎn)單的論證一下該算法的正確性。l 因?yàn)槭Ｓ喙?jié)點(diǎn)當(dāng)中已經(jīng)不存在 B集合，那么 Billy完全無(wú)法控制士兵能夠到達(dá)的節(jié)點(diǎn)的范圍，那么 Ann是一定能夠在游戲結(jié)束之前使士兵到達(dá)一個(gè)特定的強(qiáng)連通分量中的某一節(jié)點(diǎn)，這個(gè)連通分量中任何一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)都處于該連通分量中，因?yàn)椴淮嬖?B集合，那么這一連通分量中必然存在綠色節(jié)點(diǎn)，因此 Ann可以使士兵在這一個(gè)連通分量中走出一個(gè)含有綠色節(jié)點(diǎn)的環(huán)。性能分析l 時(shí)間復(fù)雜度：該算法中尋找 B集合和尋找可以確定 f值的節(jié)點(diǎn)的過(guò)程的時(shí)間復(fù)雜度為， m表示圖中有向弧的條數(shù)。因此算法的時(shí)間復(fù)雜度為， k相當(dāng)于算法框架當(dāng)中 while循環(huán)的次數(shù)， k的取值與有向圖的構(gòu)型有關(guān)， k的上限為 (a+b)/2。l 空間需求 ：參考資料《博弈論》 中國(guó)人民大學(xué)出版社 朱 弗登博格 （法）讓梯若爾 《博弈與信息：博弈論概論（第二版）》 GamesandInformation:AnIntroductiontoGameTheory北京大學(xué)出版社[美 ]艾里克 .拉斯繆森王暉 白金輝 吳任昊《人工智能導(dǎo)論 》清華大學(xué)出版社 林堯瑞 馬少平
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1