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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、就是9X10的二維數組來表示中國象棋的棋盤信息。目的在于讓讀者清晰地把握棋盤表示的本質，并能夠將注意力集中到本書所介紹的方法上，以免對讀者的理解構成不必要的障礙。3、走法產生3.1 產生方法3.2 產生效率3.3 逐個與全部3.4 內存分析3.1 產生方法走法產生是指將一個局面的所有可能的走法全部羅列出來。五子棋象棋3.2 產生效率走法產生需要搜索為了提高產生的速度，需要進行優化，優化和具體棋類規則有關象棋中，每個棋子的移動需要復雜的判斷構建數據庫可以減少判斷的計算量，就可以計算出合法的走法以象棋中的象為例3.3 逐個與全部逐個產生對于一個局面的所有直接后繼，一次產生一種走法，然后搜索之全部產

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