計算機博弈-講義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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