計(jì)算機(jī)博弈-講義

1、計(jì)算機(jī)博弈游戲設(shè)計(jì)課程簡(jiǎn)介計(jì)算機(jī)博弈游戲設(shè)計(jì)與開(kāi)發(fā)課程是科技素質(zhì)教育公共選修課程。計(jì)算機(jī)博弈游戲設(shè)計(jì)與開(kāi)發(fā)是以博弈算法研究工作為邏輯起點(diǎn)，以全校各專(zhuān)業(yè)二年級(jí)以上本科學(xué)生為講授對(duì)象，是集理論性與應(yīng)用性為一體的學(xué)科。課程簡(jiǎn)介設(shè)置本課程的目的是：1.普及計(jì)算機(jī)博弈的基礎(chǔ)知識(shí)2.掌握計(jì)算機(jī)博弈算法的理論、方法、技術(shù)3.具備編程實(shí)現(xiàn)計(jì)算機(jī)博弈算法的實(shí)際技能4.通過(guò)比賽選拔出優(yōu)秀學(xué)生參加國(guó)內(nèi)及國(guó)際大賽課程簡(jiǎn)介學(xué)習(xí)本課程的要求是學(xué)習(xí)者應(yīng)在熟練掌握一門(mén)編程語(yǔ)言的基礎(chǔ)上，掌握計(jì)算機(jī)博弈（機(jī)器博弈）的相關(guān)概念，了解計(jì)算機(jī)博弈的歷程及已經(jīng)取得的成果，掌握計(jì)算機(jī)博弈的技術(shù)構(gòu)成與內(nèi)涵，熟悉博弈平臺(tái)的接口設(shè)計(jì)，并能按照軟

2、件工程的要求編寫(xiě)程序?qū)崿F(xiàn)一個(gè)五子棋博弈策略算法最終在博弈平臺(tái)上進(jìn)行比賽決出勝負(fù)。課程簡(jiǎn)介先修課程要求必須系統(tǒng)學(xué)習(xí)過(guò)至少一門(mén)程序設(shè)計(jì)語(yǔ)言課程，最好學(xué)習(xí)過(guò)數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)原理、算法分析與設(shè)計(jì)等相關(guān)課程。 教材與參考資料教材PC游戲編程（人機(jī)博弈） 王小春 編著 重慶大學(xué)出版社 2002參考書(shū)人工智能及其應(yīng)用（第4版） ，蔡自興，清華大學(xué)出版社，2010網(wǎng)絡(luò)資源東北大學(xué)機(jī)器博弈研究室，中國(guó)人工智能網(wǎng)，象棋百科全書(shū)，五子棋資料，考核方法學(xué)生成績(jī)由平時(shí)成績(jī)和博弈算法程序成績(jī)兩部分組成。其中平時(shí)成績(jī)占30%，教師將從上課、上機(jī)、參與討論等方面進(jìn)行考察；博弈算法程序成績(jī)占70%，教師則根據(jù)學(xué)生形成的算法程序

3、在博弈平臺(tái)上參與比賽的情況判定等級(jí)，并給出最終成績(jī)。目錄計(jì)算機(jī)博弈概述棋盤(pán)表示走法產(chǎn)生基本搜索技術(shù)博弈評(píng)估五子棋博弈實(shí)例高級(jí)搜索技術(shù)實(shí)訓(xùn)平臺(tái)：計(jì)算機(jī)博弈競(jìng)賽平臺(tái)1、計(jì)算機(jī)博弈概述1.1 機(jī)器博弈簡(jiǎn)介1.2 機(jī)器博弈的歷史1.3 中國(guó)象棋人機(jī)大戰(zhàn)1、計(jì)算機(jī)博弈概述 博弈的特征： 智力競(jìng)技博弈是智力競(jìng)技。機(jī)器博弈，意味著機(jī)器參與博弈，參與智力競(jìng)技。機(jī)器博弈可以是機(jī)器與機(jī)器之間的博弈，也可以是機(jī)器與人類(lèi)之間的博弈。我們這里的博弈只涉及雙方博弈，即雙方對(duì)壘的智力游戲，常見(jiàn)的是棋類(lèi)游戲，如：中國(guó)象棋，軍旗，圍棋，以及國(guó)際象棋等。1、計(jì)算機(jī)博弈概述博弈的目標(biāo)： 擊敗對(duì)手博弈的目標(biāo)是取勝，取勝的棋局如同狀態(tài)

4、空間法中的目標(biāo)狀態(tài)。與華容道游戲一樣，游戲者需要對(duì)棋局進(jìn)行操作，以改變棋局，使其向目標(biāo)棋局轉(zhuǎn)移。然而，華容道游戲只涉及一個(gè)主體，不是博弈。博弈涉及多個(gè)主體，他們按規(guī)則，依次對(duì)棋局進(jìn)行操作，并且，他們的目標(biāo)是擊敗對(duì)手。1、計(jì)算機(jī)博弈概述 雙方博弈實(shí)例 圍棋以圍棋為例，競(jìng)技的雙方分為黑方和白方，由黑方開(kāi)棋，雙方輪流行棋，最終，誰(shuí)占據(jù)的地盤(pán)大，誰(shuí)就成為獲勝方。01 計(jì)算機(jī)博弈概述計(jì)算機(jī)博弈（Computer Games，亦稱(chēng)：機(jī)器博弈）就是讓計(jì)算機(jī)能夠像人類(lèi)一樣思維，能夠下棋。下棋是超越各種專(zhuān)業(yè)領(lǐng)域知識(shí)局限的智力游戲，并且成為一種智力體育項(xiàng)目，深受廣大青少年的喜愛(ài)。計(jì)算機(jī)博弈競(jìng)賽是將計(jì)算機(jī)技術(shù)、人工

5、智能技術(shù)與體育比賽相結(jié)合，以計(jì)算機(jī)為研究平臺(tái)，以青年學(xué)生耳聞樂(lè)見(jiàn)的、娛樂(lè)性強(qiáng)的、高對(duì)抗性的棋牌為研究載體，借此調(diào)動(dòng)廣大青年學(xué)生的學(xué)習(xí)熱情與研究興趣。目前，它已發(fā)展成為國(guó)內(nèi)外流行的標(biāo)準(zhǔn)競(jìng)賽平臺(tái)。顯然開(kāi)展計(jì)算機(jī)博弈競(jìng)賽活動(dòng)，便能充分發(fā)揮其推動(dòng)教學(xué)與研究進(jìn)展的能動(dòng)作用。01 關(guān)于計(jì)算機(jī)博弈早在上世紀(jì)50年代，計(jì)算機(jī)和信息論的先驅(qū)者阿蘭圖靈（Alan Turing）、克勞德香濃（Claude Shannon）等老前輩就都非常重視計(jì)算機(jī)博弈的研究，指出計(jì)算機(jī)博弈具有理論的重要性，它的圓滿(mǎn)解決，可以幫助解決類(lèi)似并且重要的其它問(wèn)題；而且有著很好的應(yīng)用前景。半個(gè)多世紀(jì)的實(shí)踐也證實(shí)了他們的預(yù)言。01 關(guān)于計(jì)算機(jī)

6、博弈下棋本來(lái)是孩童就會(huì)玩的事情，但是讓計(jì)算機(jī)實(shí)現(xiàn)這種思維過(guò)程，便成為計(jì)算機(jī)與人工智能領(lǐng)域的頗具挑戰(zhàn)性的研究課題。因?yàn)樵谟?jì)算機(jī)博弈程序的設(shè)計(jì)與開(kāi)發(fā)當(dāng)中，不僅涉及到程序語(yǔ)言、程序設(shè)計(jì)方法學(xué)、圖形人機(jī)界面、數(shù)據(jù)結(jié)構(gòu)、軟件工程、數(shù)據(jù)庫(kù)、知識(shí)庫(kù)、優(yōu)化與學(xué)習(xí)算法等等，而且必然面對(duì)規(guī)模龐大（天文數(shù)字）的博弈樹(shù)的各種搜索算法，如：極大極小、-剪枝、迭代深化、蒙特卡洛、基于威脅、證據(jù)計(jì)數(shù)算法等等，內(nèi)容豐富，變化無(wú)窮，可以讓年輕人的聰明才智得到充分的發(fā)揮。01 關(guān)于計(jì)算機(jī)博弈計(jì)算機(jī)博弈進(jìn)入門(mén)檻并不高，其中的項(xiàng)目特別適合于團(tuán)隊(duì)協(xié)作，團(tuán)隊(duì)成員通過(guò)分工合作，完成項(xiàng)目的分析、策略、算法、建模、編程、測(cè)試等各項(xiàng)任務(wù)，因此，

7、只要會(huì)計(jì)算機(jī)、懂計(jì)算機(jī)的青年學(xué)生都能進(jìn)入計(jì)算機(jī)博弈項(xiàng)目小組，都能發(fā)現(xiàn)適合自己特點(diǎn)和能力的工作任務(wù)。 1.2 機(jī)器博弈的歷史17中國(guó)象棋人機(jī)大戰(zhàn)-2006中國(guó)象棋人機(jī)大戰(zhàn)-2006中國(guó)象棋人機(jī)大戰(zhàn)-2006中國(guó)象棋人機(jī)大戰(zhàn)-20061.3、人機(jī)博弈系統(tǒng)1.3.1 人機(jī)博弈系統(tǒng)的構(gòu)成1.3.2 棋盤(pán)表示1.3.3 走法產(chǎn)生1.3.4 搜索技術(shù)1.3.5 估值1.3.1 人機(jī)博弈系統(tǒng)的構(gòu)成人機(jī)對(duì)弈的程序，至少能具備如下幾個(gè)部分：某種在機(jī)器中表示棋局的方法，能夠讓程序知道博弈的狀態(tài)。產(chǎn)生合法走法的規(guī)則，以使博弈公正的進(jìn)行，并可判斷人類(lèi)對(duì)手是否亂走。從所有合法的走法中選擇最佳的走法的技術(shù)。一種評(píng)估局面優(yōu)

8、劣的方法，用以同上面的技術(shù)配合做出智能的選擇。一個(gè)界面，有了它，這個(gè)程序才能用。1.3.2 棋盤(pán)表示棋盤(pán)表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)描述棋盤(pán)及棋盤(pán)上的棋子，通常是使用一個(gè)二維數(shù)組。一個(gè)典型的中國(guó)象棋棋盤(pán)是使用9X10的二維數(shù)組表示。每一個(gè)元素代表棋盤(pán)上的一個(gè)交點(diǎn)。一個(gè)沒(méi)有棋子的交點(diǎn)所對(duì)應(yīng)的元素是0，一個(gè)黑帥對(duì)應(yīng)的元素是1，黑士則用2表示等等，依此類(lèi)推。棋盤(pán)的數(shù)據(jù)表示直接影響到程序的時(shí)間及空間復(fù)雜度。為了追求更高效率，研究人員針對(duì)不同棋類(lèi)提出了多種不同的表示方法。1.3.3 走法產(chǎn)生博弈的規(guī)則決定了哪些走法是合法的。對(duì)有的游戲來(lái)說(shuō)，這很簡(jiǎn)單，比如五子棋，任何空白的位置都是合法的落子點(diǎn)。但對(duì)于象棋來(lái)

9、說(shuō)，就有馬走日、象走田等一系列復(fù)雜的規(guī)則。走法產(chǎn)生是博弈程序中一個(gè)相當(dāng)復(fù)雜而且耗費(fèi)運(yùn)算時(shí)間的方面。不過(guò)，通過(guò)良好的數(shù)據(jù)結(jié)構(gòu)，可以顯著地提高生成的速度。1.3.4 搜索技術(shù)對(duì)于計(jì)算機(jī)來(lái)說(shuō)，直接通過(guò)棋盤(pán)信息判別走法的好壞并不精確。除了輸贏這樣的局面可以可靠地判別外，其他的判斷都只能做到大致估計(jì)。判別兩種走法孰優(yōu)孰劣的一個(gè)好方法就是察看棋局走下去的結(jié)果，也就是向下搜索若干步，然后比較發(fā)展下去的結(jié)果，為了避免差錯(cuò)，我們假定對(duì)手的思考也和我們一樣，也就是，我們想到的內(nèi)容，對(duì)手也想到了，這就是極大極小搜索算法的基本原則。極大極小搜索算法是本書(shū)中所有搜索算法的基礎(chǔ)。極大極小搜索算法的時(shí)間復(fù)雜度是O(bn)。

10、這里b是分枝因子(branching factor），指棋局在各種情況下的合法走步的平均值：n是搜索的最大深度，也就是向下搜索的博弈雙方的走步。1.3.5 估值然而，現(xiàn)有的計(jì)算機(jī)的運(yùn)算能力仍然十分有限。不可能一直搜索到分出輸贏的那一步，在有限搜索深度的末端，我們用一些靜態(tài)的方法，來(lái)估計(jì)局面的優(yōu)勢(shì)。這些方法在很大程度上依賴(lài)于具體的游戲規(guī)則和我們對(duì)于該游戲的經(jīng)驗(yàn)知識(shí)，其中相當(dāng)一部分不完全可靠。例如：中國(guó)象棋的程序通常將一個(gè)炮賦予遠(yuǎn)高于一個(gè)兵的價(jià)值，但一個(gè)兵在高手的運(yùn)用之下往往可以產(chǎn)生不次于炮的作用。寫(xiě)出一個(gè)好的估值函數(shù)并不是一件輕松的事，它需要你對(duì)所評(píng)估的棋類(lèi)相當(dāng)了解，最好是一個(gè)經(jīng)驗(yàn)豐富的高手。然

11、后還要進(jìn)行無(wú)數(shù)次的試驗(yàn)，經(jīng)歷幾番失敗后才可能得到一個(gè)令人滿(mǎn)意的估值函數(shù)。2、棋盤(pán)表示2.1 一般表示法2.2 比特棋盤(pán)2.1 一般表示法棋盤(pán)表示主要探討的是使用什么數(shù)據(jù)結(jié)構(gòu)來(lái)表示棋盤(pán)上的信息。一般說(shuō)來(lái)，這與具體的棋類(lèi)知識(shí)密切相關(guān)。通常，用來(lái)描述棋盤(pán)及其上棋子信息的是一個(gè)二維數(shù)組。例如，可以用一個(gè)9X10個(gè)字節(jié)的二維數(shù)組來(lái)表示中國(guó)象棋的棋盤(pán)，數(shù)組中每一個(gè)字節(jié)代表棋盤(pán)上的一個(gè)交點(diǎn)，其值表明這個(gè)交點(diǎn)上放置的是一個(gè)什么棋子或是沒(méi)有棋子，如圖2.1所示：也可以用19X19個(gè)字節(jié)的二維數(shù)組來(lái)表示圍棋的棋盤(pán)，在其上用值為0的字節(jié)表示該點(diǎn)空白，1表示該點(diǎn)有一個(gè)黑棋，2表示該點(diǎn)有一個(gè)白棋。2.1 一般表示法2.

12、1 一般表示法設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)來(lái)表示一種棋類(lèi)游戲的狀態(tài)往往要考慮3個(gè)方面的問(wèn)題：占用的空間數(shù)量操作速度使用方便與否2.1 一般表示法在早期的博弈編程中，由于內(nèi)存極其有限，一些程序采用了極為緊湊的數(shù)據(jù)結(jié)構(gòu)來(lái)表示棋盤(pán)上的信息。例如：中國(guó)象棋共有14種不同的棋子，紅黑各7種，所以棋盤(pán)上1個(gè)交點(diǎn)的狀態(tài)最多只能有15種，停放某種棋子或者空白?；谶@種思想，顯然可以用4位來(lái)表示一個(gè)交點(diǎn)。也就是說(shuō)，可以用一個(gè)字節(jié)來(lái)表示兩個(gè)交點(diǎn)。這樣表示整個(gè)棋盤(pán)的信息就只需要一個(gè)9X5個(gè)字節(jié)的二維數(shù)組了。可以讓每個(gè)字節(jié)的高4位代表奇數(shù)行的交點(diǎn)，讓低4位代表偶數(shù)行的交點(diǎn)。一個(gè)棋盤(pán)狀態(tài)總共需要45個(gè)字節(jié)來(lái)表示。如果從棋子的觀點(diǎn)出

13、發(fā)，將棋盤(pán)看作是一個(gè)平面坐標(biāo)系，可以看出每一個(gè)棋子的位置信息，包含一個(gè)小于10的橫坐標(biāo)和一個(gè)小于11的縱坐標(biāo)。顯然，我們使用一個(gè)有32個(gè)字節(jié)的一維數(shù)組就可以表示所有32個(gè)棋子的位置，每個(gè)字節(jié)的高4位表示該棋子的橫坐標(biāo)，低4位表示該棋子的縱坐標(biāo)。已被吃掉的棋子用一個(gè)坐標(biāo)范圍以外的數(shù)表示。這樣整個(gè)棋盤(pán)上的信息就被裝進(jìn)了這32個(gè)字節(jié)當(dāng)中。2.1 一般表示法緊湊的數(shù)據(jù)表示會(huì)贏得空間上的優(yōu)勢(shì)，這往往也伴隨著時(shí)間上的優(yōu)勢(shì)。復(fù)制32個(gè)字節(jié)的棋盤(pán)信息無(wú)疑會(huì)快于90個(gè)字節(jié)的棋盤(pán)，但并不意味著所有的運(yùn)算和操作都會(huì)更快。使用32個(gè)字節(jié)的數(shù)據(jù)表示，程序員在確定一個(gè)棋子的位置時(shí)往往需要增加額外的移位操作以取出一個(gè)字節(jié)中

14、含有的兩個(gè)坐標(biāo)信息。2.2 比特棋盤(pán)隨著計(jì)算機(jī)存儲(chǔ)能力的大幅度提高，棋盤(pán)表示的空間需求往往已不是設(shè)計(jì)人員最為關(guān)注的問(wèn)題。而考慮更多的問(wèn)題是性能。不太直觀的緊湊結(jié)構(gòu)往往不那么容易被理解和使用，這意味這更多的潛在錯(cuò)誤和更長(zhǎng)的調(diào)試時(shí)間。當(dāng)然如果能夠使內(nèi)存需求量降低并且無(wú)損性能，設(shè)計(jì)人員（尤其是為硬件能力較低的掌上電腦或手機(jī)編程的人員）仍會(huì)傾向于使用緊湊的結(jié)構(gòu)。2.2 比特棋盤(pán)在高性能的博弈程序里，往往有一些特別的數(shù)據(jù)表示。例如在國(guó)際象棋的棋盤(pán)表示中，很多情況下會(huì)采用8X8的數(shù)組來(lái)表示棋盤(pán)。但是有一種更精巧的結(jié)構(gòu)，比特棋盤(pán)（Bit Boards），也獲得了廣泛使用。20世紀(jì)60年代末，前蘇聯(lián)的KAIS

15、SA項(xiàng)目組提出了比特棋盤(pán)的技術(shù)。此技術(shù)后來(lái)應(yīng)用于64位主機(jī)，用一個(gè)64位數(shù)表示一種棋子的位置。這樣一個(gè)國(guó)際象棋棋盤(pán)上的全部信息就可用12個(gè)比特棋盤(pán)表示，也就是12個(gè)64位數(shù)。使用比特棋盤(pán)可以極大程度地提高某些運(yùn)算的速度。例如在一個(gè)國(guó)際象棋的局面里，你要檢查黑王是否被白后將軍了。如果采用8*8的數(shù)組表示，你需要完成如下步驟：2.2 比特棋盤(pán)先掃描數(shù)組找到白后的位置。往往要多次載入比較操作。找出白后可到達(dá)的位置，檢查黑王是否在其中一個(gè)位置上；如果是，就可以斷定將軍了。這往往也要多次比較操作。而使用比特棋盤(pán)表示，你只需執(zhí)行如下操作：載入代表白后的比特棋盤(pán)，一個(gè)64位數(shù)。利用這個(gè)比特棋盤(pán)，在預(yù)先建立的

16、數(shù)據(jù)庫(kù)中索引到代表白后可攻擊到的位置的比特棋盤(pán)。將這個(gè)比特棋盤(pán)和代表黑王的比特棋盤(pán)執(zhí)行按位與操作，如果結(jié)果是0，則沒(méi)有將軍；否則，黑王就被白后將軍了。2.2 比特棋盤(pán)兩種方法在運(yùn)算量上的差異是巨大的。當(dāng)然，中國(guó)象棋的棋盤(pán)不是8X8的，其他很多種棋類(lèi)游戲也不是，而大多數(shù)人使用的PC是32位的處理器。但比特棋盤(pán)的方法對(duì)于設(shè)計(jì)高效的數(shù)據(jù)表示仍有積極意義。實(shí)際上不少PC平臺(tái)上的頂級(jí)國(guó)際象棋程序都使用了比特棋盤(pán)，同64位主機(jī)相比，32位的PC處理器處理64位數(shù)可能多花一倍或更多的時(shí)鐘周期，但仍比8X8的數(shù)據(jù)表示快得多。讀者可以將類(lèi)似的方法運(yùn)用到自己的博弈程序當(dāng)中。本書(shū)的范例將采用最便于理解的表示方法，也

17、就是9X10的二維數(shù)組來(lái)表示中國(guó)象棋的棋盤(pán)信息。目的在于讓讀者清晰地把握棋盤(pán)表示的本質(zhì)，并能夠?qū)⒆⒁饬械奖緯?shū)所介紹的方法上，以免對(duì)讀者的理解構(gòu)成不必要的障礙。3、走法產(chǎn)生3.1 產(chǎn)生方法3.2 產(chǎn)生效率3.3 逐個(gè)與全部3.4 內(nèi)存分析3.1 產(chǎn)生方法走法產(chǎn)生是指將一個(gè)局面的所有可能的走法全部羅列出來(lái)。五子棋象棋3.2 產(chǎn)生效率走法產(chǎn)生需要搜索為了提高產(chǎn)生的速度，需要進(jìn)行優(yōu)化，優(yōu)化和具體棋類(lèi)規(guī)則有關(guān)象棋中，每個(gè)棋子的移動(dòng)需要復(fù)雜的判斷構(gòu)建數(shù)據(jù)庫(kù)可以減少判斷的計(jì)算量，就可以計(jì)算出合法的走法以象棋中的象為例3.3 逐個(gè)與全部逐個(gè)產(chǎn)生對(duì)于一個(gè)局面的所有直接后繼，一次產(chǎn)生一種走法，然后搜索之全部產(chǎn)

18、生一次產(chǎn)生所有走法，然后搜索之絕大部分情況是一次產(chǎn)生一個(gè)局面的全部走法，然后調(diào)整順序3.4 內(nèi)存分析產(chǎn)生走法時(shí)，通常將走法隊(duì)列置于預(yù)先的內(nèi)存中，以避免頻繁申請(qǐng)以中國(guó)象棋為例4、基本搜索技術(shù)什么是搜索盲目搜索一個(gè)一個(gè)的檢查對(duì)抗性搜索4、基本搜索技術(shù)4.1 博弈樹(shù)4.2 極大極小值算法4.3 深度優(yōu)先搜索4.4 負(fù)極大值算法4.1 博弈樹(shù)博弈樹(shù)把所有的走法都列出來(lái)樹(shù)根是棋局的初始局面根的若干子節(jié)點(diǎn)是甲的每種可能走法所生成的局面，而這些節(jié)點(diǎn)的子節(jié)點(diǎn)又是對(duì)方每種可能走法產(chǎn)生的局面樹(shù)的末梢是結(jié)束局面：一方獲勝、平局4.1 博弈樹(shù)博弈樹(shù)從根部向下遞歸產(chǎn)生的一顆包含所有可能的對(duì)弈過(guò)程的搜索樹(shù)，是完全搜索樹(shù)搜索過(guò)程分析不可能建立完全搜索樹(shù)很多情形根本到達(dá)不了葉節(jié)點(diǎn)節(jié)點(diǎn)數(shù)量太多，超過(guò)計(jì)算機(jī)的處理能力4.2 極大極小值算法棋局優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)假設(shè)甲勝的局面為1，乙勝的局面為-1，和局的值為0如何搜索？最有利于甲，最