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