計(jì)算機(jī)博弈算法與編程 課件全套 王靜文 1概述、2計(jì)算機(jī)博弈基礎(chǔ)-7 Q學(xué)習(xí)算法

1概述1.1計(jì)算機(jī)博弈概述人工智能(ArtificialIntelligence)在當(dāng)前計(jì)算機(jī)博弈游戲中被廣泛地應(yīng)用，計(jì)算機(jī)博弈逐漸成為人工智能中的一個(gè)重要的分支。美國(guó)麻省理工學(xué)院著名教授ClaudeShannon早在1948年就撰寫(xiě)了ProgrammingaComputerPlayingChess一文。1966年麻省理工學(xué)院的MacHack6開(kāi)發(fā)小組就開(kāi)發(fā)了第一個(gè)能與人進(jìn)行對(duì)弈的計(jì)算機(jī)棋類游戲，開(kāi)始了計(jì)算博弈成長(zhǎng)之路。1997年5月11日，國(guó)際象棋世界冠軍卡斯帕羅夫與ＩＢＭ公司的國(guó)際象棋電腦“深藍(lán)II”(更深的藍(lán))的六局對(duì)抗賽降下帷幕?！吧钏{(lán)II”以3.5:2.5的比分戰(zhàn)勝了世界冠軍卡斯帕羅夫，在第6局，僅下到19步卡斯帕羅夫就向“深藍(lán)”拱手稱臣，草草簽下城下之盟，這一天也成為計(jì)算機(jī)人工智能的一個(gè)重要的里程碑，計(jì)算機(jī)博弈也得到越來(lái)越多的學(xué)者的重視。1概述2016年3月15日,谷歌圍棋人工智能AlphaGo與韓國(guó)棋手李世石進(jìn)行較量,AlphaGo獲得比賽勝利。2017年5月27日谷歌圍棋人工智能AlphaZero與中國(guó)棋手柯潔進(jìn)行較量,AlphaZero獲得比賽勝利。1概述1.2國(guó)際電腦奧林匹克大賽電腦奧林匹克(ComputerOlympiad)大賽是目前世界上規(guī)模最大的計(jì)算機(jī)博弈大賽，自1989年在英國(guó)倫敦舉辦第一屆電腦奧林匹克以來(lái)，目前已經(jīng)進(jìn)行了十五屆電腦奧林匹克，吸引了全世界眾多計(jì)算機(jī)博弈愛(ài)好者的參加，我國(guó)于2008年在北京成功舉辦了第13屆電腦奧林匹克。1概述比賽的項(xiàng)目包括較為普及的項(xiàng)目，如圍棋(含九路圍棋、國(guó)際跳棋、五子棋、六子棋、中國(guó)象棋、日本將棋、西洋雙陸棋、幻影圍棋等之外，還有許多外國(guó)的民間棋類，如：?？怂梗℉ex）、亞馬遜（Amazons）、克拉巴（Clobber）、蘇拉卡爾塔（Surakarta）、點(diǎn)格棋（DotsandBoxes）等近40種比賽項(xiàng)目。1概述1.3中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽起源于中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽，自2006年以來(lái)，至今已經(jīng)成功舉辦了十四屆中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽，比賽的項(xiàng)目由最早的中國(guó)象棋、圍棋、九路圍棋和六子棋等四個(gè)項(xiàng)目，發(fā)展到目前已經(jīng)達(dá)到中國(guó)象棋、圍棋、九路圍棋、幻影圍棋、亞馬遜棋、蘇拉卡爾塔棋、六子棋、點(diǎn)格棋等10多個(gè)項(xiàng)目，參賽的代表隊(duì)也由初始階段的十個(gè)左右的代表隊(duì)發(fā)展到目前的由100多個(gè)院校參加、1600多個(gè)代表隊(duì)近2000名選手參與的規(guī)模。1概述從2011年開(kāi)始，由中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽發(fā)展成全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽暨計(jì)算機(jī)博弈錦標(biāo)賽，并由教育部主辦，人工智能協(xié)會(huì)承辦，在北京科技大學(xué)成功舉辦了第一屆全國(guó)大學(xué)生計(jì)算博弈大賽，在2012年?yáng)|北大學(xué)舉辦的第二屆全國(guó)大學(xué)生計(jì)算博弈錦標(biāo)賽中參賽的隊(duì)伍已經(jīng)達(dá)到170多個(gè)代表隊(duì)，同時(shí)增加國(guó)際跳棋、愛(ài)恩斯坦棋和軍棋等項(xiàng)目的比賽，為新參與該項(xiàng)活動(dòng)的學(xué)校提供了一個(gè)更好的交流學(xué)習(xí)的機(jī)會(huì)，亞馬遜棋、蘇拉卡爾塔棋、六子棋、點(diǎn)格棋等參賽隊(duì)伍均超過(guò)了20個(gè)，計(jì)算機(jī)博弈吸引了越來(lái)越多的大學(xué)生博弈愛(ài)好者參加。2.1計(jì)算機(jī)博弈的基本原理2.1.1基本原理計(jì)算機(jī)博弈的基本思想并不復(fù)雜，將計(jì)算機(jī)博弈的過(guò)程用“樹(shù)”的方式表達(dá)出來(lái)稱為博弈樹(shù)，而計(jì)算機(jī)博弈實(shí)際上就是對(duì)博弈樹(shù)上的節(jié)點(diǎn)進(jìn)行估值和對(duì)博弈樹(shù)進(jìn)行搜索的過(guò)程。2計(jì)算機(jī)博弈基礎(chǔ)2.1計(jì)算機(jī)博弈的基本原理2.1.1基本原理在博弈過(guò)程中站在其中的一方的立場(chǎng)上來(lái)構(gòu)建一個(gè)博弈樹(shù)，博弈樹(shù)的根節(jié)點(diǎn)就是當(dāng)前的棋局，而博弈樹(shù)的子節(jié)點(diǎn)就是假設(shè)再行棋一步以后產(chǎn)生的棋局。再構(gòu)建更下一步的棋局，直至某一深度或結(jié)束為止，由此構(gòu)建出的博弈樹(shù)通常是非常巨大的，往往無(wú)法直接通過(guò)構(gòu)造博弈樹(shù)而分出勝負(fù)，博弈程序的任務(wù)則是根據(jù)博弈樹(shù)搜索出一種當(dāng)前棋局的最佳走法。2計(jì)算機(jī)博弈基礎(chǔ)通常計(jì)算機(jī)博弈需要滿足以下條件：1)雙方對(duì)弈，對(duì)弈的雙方輪流走步。2)信息完備，對(duì)弈的雙方所得到的信息是一樣的，不存在一方能看到而另一方看不到的情況，每一方不僅知道對(duì)方走過(guò)的每一步棋，而且還能估計(jì)出對(duì)方未來(lái)可能走的棋。3)零和，即對(duì)一方有利的局面對(duì)另一方肯定不利，不存在對(duì)雙方均有利或均不利的情況，對(duì)弈的結(jié)果是一方贏而另一方輸，或者是和棋。2計(jì)算機(jī)博弈基礎(chǔ)下面從一個(gè)較為簡(jiǎn)單的游戲來(lái)介紹計(jì)算機(jī)是如何進(jìn)行下棋的，井字游戲(Tic-Tac-Toe)是計(jì)算機(jī)博弈游戲中最為簡(jiǎn)單的例子之一。在如圖2-1的棋盤(pán)中，雙方輪流下棋，若其中一方在水平、垂直或斜線方向形成三個(gè)棋子連線，則獲勝，下棋過(guò)程大致如圖2-1所示：2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)圖2-1中，白棋在右側(cè)形成三連，故白棋獲勝。針對(duì)井字游戲，在設(shè)計(jì)游戲智能過(guò)程中可按照以下基本原則進(jìn)行：1)如果下在該位置可以贏棋，那就下在該位置。2)如果對(duì)手下在該位置可以贏棋，那就下在該位置。3)如果中心位置空閑，那么下在中心位置要優(yōu)于邊上和角上的位置。4)如果角上位置空閑，那么下在角上位置要優(yōu)于邊上位置。5)如果只有邊上位置有空閑，那只有下在邊上位置。2

計(jì)算機(jī)博弈基礎(chǔ)圖2-1中所示的過(guò)程只是下棋中一種，如果計(jì)算機(jī)能夠搜索出所有可能的下棋過(guò)程那是最好的了，只要從中選擇出能贏棋的走法在走棋過(guò)程中使用就可以了，那么，這種方法是否可行呢？至少有兩個(gè)理由說(shuō)明這種方法是不可行的。2

計(jì)算機(jī)博弈基礎(chǔ)1)如果一種棋，在棋盤(pán)上有x個(gè)可以下棋的位置，共有y步才能下完，那么下棋過(guò)程中最多可能的步子共有xy種，對(duì)于上述井字游戲，如果不考慮對(duì)稱的因素，那么在第一步下棋時(shí)，如果模擬到整個(gè)棋局結(jié)束，需要模擬的總的步數(shù)為9！，共362,880種可能步數(shù)，考慮排除相應(yīng)的對(duì)稱因素外。2

計(jì)算機(jī)博弈基礎(chǔ)1)如，在第一步下棋中只需要考慮中間點(diǎn)、四個(gè)角點(diǎn)中的一個(gè)和中間水平與中間垂直中的一個(gè)點(diǎn)即可，即：第一步棋只需要考慮三個(gè)可下棋的位置，以此類推來(lái)考慮第二步、第三步……下棋的位置，這樣可以得到大約有255,168多種下法。而對(duì)于國(guó)際象棋來(lái)說(shuō)，可能的下法有3640種可能的下法，顯然，以目前計(jì)算機(jī)的計(jì)算速度來(lái)計(jì)算，這種搜索方法是不可行的。2

計(jì)算機(jī)博弈基礎(chǔ)2)“這就叫人工智能？這就是機(jī)器博弈？”，如果上述方法可行的話，這可能是你最可能說(shuō)出的那句話，對(duì)于硬件崇拜者，這也許是個(gè)方法，而大多數(shù)設(shè)計(jì)者用一個(gè)優(yōu)秀的搜索算法來(lái)解決這個(gè)問(wèn)題會(huì)帶來(lái)更大的快樂(lè)。在實(shí)際應(yīng)用中并不搜索所有的節(jié)點(diǎn)，僅僅搜索有價(jià)值的節(jié)點(diǎn)，并對(duì)它們進(jìn)行估值，如何對(duì)節(jié)點(diǎn)進(jìn)行合理的估值并設(shè)計(jì)相應(yīng)的估值函數(shù)是計(jì)算機(jī)博弈中的一個(gè)重要環(huán)節(jié)，在后續(xù)章節(jié)中會(huì)專門對(duì)估值函數(shù)的設(shè)計(jì)方法進(jìn)行討論。2

計(jì)算機(jī)博弈基礎(chǔ)為方便表達(dá)游戲的狀態(tài)，通常使用樹(shù)或圖來(lái)表達(dá)，圖2-2表示了一種博弈樹(shù)，樹(shù)的根部為起始狀態(tài)，moveA、moveB等表示可以選擇的下棋位置，Player1、Player2表示在樹(shù)的該層走棋的一方，W代表贏棋，L表示輸棋，進(jìn)行初始化之后，Player1可選擇A、B、C和D位置下棋，然后輪到Player2下棋，以此類推，向下進(jìn)行的深度稱為層次，在計(jì)算機(jī)博弈中通常使用ply來(lái)表示。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)圖中，L表示Lost，W表示W(wǎng)in，不同游戲者所處的層次分別用圓圈和矩形表示。那么，我們現(xiàn)在所要做的工作就是要找到獲勝的節(jié)點(diǎn)，為更好理解搜索的過(guò)程，先介紹一下博弈樹(shù)中的一些常用的概念：分支因子(BranchingFactor，b)：從游戲起始出發(fā)游戲者可以移動(dòng)到的位置，例如，井字游戲的分支因子為9(當(dāng)游戲開(kāi)始時(shí)，下棋方公有9個(gè)位置可以選擇)。2

計(jì)算機(jī)博弈基礎(chǔ)層次(Ply)：博弈樹(shù)的層次，游戲者通過(guò)下棋而進(jìn)入博弈樹(shù)的下一層次。深度(Depth，d)：在博弈樹(shù)中向下搜索的層次稱為深度(或搜索深度)，井字游戲的搜索深度一般為6~7，而國(guó)際象棋通常要達(dá)到40。2

計(jì)算機(jī)博弈基礎(chǔ)在實(shí)際搜索過(guò)程中通過(guò)窮舉法搜索得到制勝的下法在大多數(shù)游戲中是不現(xiàn)實(shí)的，通過(guò)選擇合適的算法實(shí)現(xiàn)最優(yōu)搜索則是計(jì)算機(jī)博弈游戲中的一個(gè)重要的環(huán)節(jié)。計(jì)算機(jī)博弈或人機(jī)對(duì)弈一般來(lái)說(shuō)需要滿足以下條件：1)某種棋局可以在博弈程序中以一定的方式表示出來(lái)，并能使程序獲得當(dāng)前棋局的狀態(tài)。2

計(jì)算機(jī)博弈基礎(chǔ)以上述的井字棋為例，我們可以使用一個(gè)二維的數(shù)組來(lái)表示棋盤(pán)，假設(shè)我們采用整型的board[3][3]來(lái)表示棋盤(pán)，也可以使用一維數(shù)組來(lái)表示棋盤(pán)，如采用整型的board[9]，9個(gè)變量分別表示棋盤(pán)中的9個(gè)位置，當(dāng)其值為0時(shí)可以表示當(dāng)前位置沒(méi)有棋子，當(dāng)其值為1時(shí)可以表示當(dāng)前位置為“X”方，而當(dāng)其值為-1時(shí)可以表示當(dāng)前位置為“O”方。這樣，我們就可以將棋盤(pán)的當(dāng)前狀態(tài)完整的表示出來(lái)，在不同的棋種中棋局的表示方法略有不同，主要是根據(jù)相關(guān)棋局的特征來(lái)確定棋局的具體表示方法。2

計(jì)算機(jī)博弈基礎(chǔ)2)博弈過(guò)程在計(jì)算機(jī)可判別的規(guī)則中進(jìn)行。在第一條的狀態(tài)表示中，如果當(dāng)前位置的值為0，表示當(dāng)前位置為空，則下棋方可以在該位置下棋，如果水平、垂直或斜線方向有三個(gè)同值的數(shù)據(jù)，則表示該方已經(jīng)贏棋，這些規(guī)則都是計(jì)算機(jī)可以識(shí)別的規(guī)則。2

計(jì)算機(jī)博弈基礎(chǔ)3)博弈程序具有從所有可行的走法中選擇最佳走法的技術(shù)。例如在圖2-1的井字棋的游戲過(guò)程中，下圖的白棋有兩個(gè)位置可以直接贏棋，那么，這兩個(gè)位置就可以作為最佳位置進(jìn)行選擇，計(jì)算機(jī)可以通過(guò)判斷這兩個(gè)位置下棋后能贏棋來(lái)確定在該位置可以直接下棋，在沒(méi)有直接可以獲勝的情況下需要評(píng)估所下位置的價(jià)值來(lái)確定具體下載那個(gè)位置。2

計(jì)算機(jī)博弈基礎(chǔ)4)博弈程序應(yīng)具有適當(dāng)?shù)墓乐捣椒ǎ糜谠u(píng)估當(dāng)前局面的優(yōu)劣。例如在上述的井字棋中，我們可以通過(guò)我方可能勝利的線路總數(shù)減去對(duì)方可能勝利的線路總數(shù)來(lái)確定當(dāng)前位置的價(jià)值，通過(guò)具體價(jià)值類評(píng)估當(dāng)前的局面。2

計(jì)算機(jī)博弈基礎(chǔ)5)具有適合的運(yùn)行界面以準(zhǔn)確地表達(dá)當(dāng)前局面。在目前的大多數(shù)計(jì)算機(jī)博弈比賽中都要求比賽軟件以可視化形式來(lái)表示當(dāng)前局面，可以根據(jù)不同的語(yǔ)言采用不同的界面制作工具。例如使用C++作為編程語(yǔ)言時(shí)，通?？梢允褂肰isualC++的MFC(微軟基礎(chǔ)類)來(lái)制作界面，如果使用Java語(yǔ)言則可以使用AWT(AbstractWindowingToolkit，抽象窗口工具包)或SWING來(lái)制作界面，運(yùn)行界面必須符合比賽的基本要求。2

計(jì)算機(jī)博弈基礎(chǔ)2.1.2計(jì)算機(jī)博弈的搜索方法在計(jì)算機(jī)博弈中，博弈過(guò)程可能產(chǎn)生驚人龐大的搜索空間，通常這個(gè)搜索空間是無(wú)法使用窮舉搜索(遍歷整個(gè)空間，找到獲勝的走法就可以了)來(lái)完成。要搜索這些龐大而復(fù)雜的空間需要使用相應(yīng)的技術(shù)來(lái)判斷備選狀態(tài)，探索問(wèn)題空間，人類解決問(wèn)題是以一些判斷性規(guī)則為基礎(chǔ)的，這些規(guī)則使我們的搜索僅尋找在狀態(tài)空間中最“有效”的一部分。這些技術(shù)和規(guī)則被稱為啟發(fā)(heuristic)，啟發(fā)式算法依賴于評(píng)估邏輯表達(dá)式，從而降低了搜索空間的復(fù)雜度。2

計(jì)算機(jī)博弈基礎(chǔ)啟發(fā)就是有所選擇地搜索問(wèn)題空間的策略，它引導(dǎo)搜索沿高成功概率的路線前進(jìn)，避免做多余的或明顯愚蠢的行為，啟發(fā)也是人工智能研究的中心問(wèn)題之一，也是計(jì)算機(jī)博弈的基礎(chǔ)。啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。在計(jì)算機(jī)博弈程序設(shè)計(jì)過(guò)程中，通常需要從博弈樹(shù)中搜索出最佳位置，搜索的方法通常有兩種，一種是深度優(yōu)先的搜索方法，一種是寬度優(yōu)先的搜索方法。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)在深度優(yōu)先搜索中，搜索過(guò)程是盡可能地向搜索空間的更深層次進(jìn)行，只有在找不到狀態(tài)(或最佳位置)時(shí)，才會(huì)搜索它的兄弟節(jié)點(diǎn)。對(duì)于圖2-3來(lái)說(shuō)，深度優(yōu)先的搜索順序是A、B、E、K、S、L、T、F、M、C、G、N、H、O、P、U、D、I、Q、J、R。2

計(jì)算機(jī)博弈基礎(chǔ)寬度優(yōu)先的搜索方法與深度優(yōu)先的搜索方法正好相反，寬度優(yōu)先的搜索方法是一層一層地搜索空間，只有在給定的層上不再存在要搜索的狀態(tài)時(shí)，算法才轉(zhuǎn)移到下一個(gè)更深的層次。對(duì)圖2-3而言寬度優(yōu)先的搜索順序是A、B、C、D、E、F、G、H、I、J、K、L、M、N、O、P、Q、R、S、T、U。2

計(jì)算機(jī)博弈基礎(chǔ)寬度優(yōu)先搜索在搜索分析第n+1層之前必然先分析第n層的所有節(jié)點(diǎn)，因此，寬度優(yōu)先搜索找到的目標(biāo)節(jié)點(diǎn)的路徑總是最短的，對(duì)于一個(gè)有簡(jiǎn)單解的問(wèn)題，寬度優(yōu)先的搜索方案能夠保證發(fā)現(xiàn)這個(gè)解。但是，如果存在一個(gè)不利的分支因子，也就是各個(gè)狀態(tài)都有相對(duì)很多個(gè)后代，那么組合爆炸可能使算法無(wú)法在現(xiàn)有可用內(nèi)存的條件下找到解。2

計(jì)算機(jī)博弈基礎(chǔ)深度優(yōu)先的搜索方法可以迅速地深入搜索的空間，如果已知解路徑很長(zhǎng)，那么深度優(yōu)先搜索不會(huì)浪費(fèi)時(shí)間來(lái)搜索大量“淺層”狀態(tài)。當(dāng)深度優(yōu)先搜索可能在深入空間，失去了達(dá)到目標(biāo)的更短路徑，或者陷入不能達(dá)到目標(biāo)的無(wú)限長(zhǎng)路徑，通常對(duì)于具有很多分支的空間，那么深度優(yōu)先搜索方法具有更高的效率。2

計(jì)算機(jī)博弈基礎(chǔ)平衡深度優(yōu)先搜索和寬度優(yōu)先搜索的一個(gè)很好的折中的方法是對(duì)深度優(yōu)先搜索使用一個(gè)界限，一旦搜索在某個(gè)層次以下，深度界限就強(qiáng)制停止對(duì)這條路徑的搜索，形成了一種對(duì)某個(gè)搜索空間的“橫掃”，這種思想產(chǎn)生的算法彌補(bǔ)了深度優(yōu)先搜尋和寬度優(yōu)先搜索算法的不足。2

計(jì)算機(jī)博弈基礎(chǔ)在1987年，Korf提出了迭代加深的深度優(yōu)先搜索算法，即對(duì)空間進(jìn)行深度界限為1的深度優(yōu)先搜索，如果找不到目標(biāo)，再進(jìn)行深度界限為2的深度優(yōu)先搜索，這樣繼續(xù)下去，每次將深度界限加1。在每一次迭代中，算法執(zhí)行一次當(dāng)前深度范圍內(nèi)的完全深度優(yōu)先搜索，在兩次迭代之間不保存任何狀態(tài)空間信息。這種算法雖然彌補(bǔ)了深度優(yōu)先搜索和寬度優(yōu)先搜索算法的各自缺點(diǎn)，但由上面的過(guò)程可以看出，其搜索過(guò)程所需要搜索的量也會(huì)在一定程度上增加。2

計(jì)算機(jī)博弈基礎(chǔ)2.1.3遞歸遞歸(recursive)是數(shù)學(xué)和計(jì)算機(jī)科學(xué)中的一個(gè)基本概念，廣義遞歸的定義是一種直接或間接引用自身的定義方法，在編程語(yǔ)言中，遞歸可以簡(jiǎn)單定義為自我調(diào)用的程序，遞歸程序不能總是自我調(diào)用，否則程序永遠(yuǎn)不會(huì)終止。因此，一個(gè)合法的遞歸應(yīng)包含兩部分：基礎(chǔ)情況和遞歸部分，基礎(chǔ)情況是指遞歸對(duì)象的表現(xiàn)形式，而遞歸部分是指遞歸的條件和方法，在遞歸的條件中必須有一個(gè)終止條件以避免遞歸進(jìn)入無(wú)限循環(huán)。2

計(jì)算機(jī)博弈基礎(chǔ)遞歸算法就是通過(guò)解決同一個(gè)問(wèn)題的一個(gè)或多個(gè)更小的實(shí)例最終解決一個(gè)大問(wèn)題的算法，即直接或間接調(diào)用自身的算法。遞歸與博弈樹(shù)的以遞歸方式定義的結(jié)構(gòu)的研究是互相重合的，研究遞歸有助于幫助解決博弈樹(shù)的搜索的研究。以遞歸定義的一個(gè)典型例子是斐波那契(Fibonacci)數(shù)列，它的定義可遞歸表示為：

2

計(jì)算機(jī)博弈基礎(chǔ)根據(jù)這一定義，我們可以得到一個(gè)無(wú)窮數(shù)列0,1,1,2,3,5,8,13,21,34,55…,這個(gè)數(shù)列就稱為斐波那契數(shù)列，斐波那契數(shù)列產(chǎn)生于12世紀(jì)，一直到18世紀(jì)才由A.De.Moivre提出了它的非遞歸形式，從12世紀(jì)到18世紀(jì)之間，人們只能以遞歸的形式來(lái)計(jì)算斐波那契數(shù)列。斐波那契數(shù)列的非遞歸形式可以用如下公式來(lái)計(jì)算：2

計(jì)算機(jī)博弈基礎(chǔ)根據(jù)斐波那契數(shù)列的遞歸定義，可以很自然地寫(xiě)出寫(xiě)出計(jì)算Fn的遞歸算法，將該過(guò)程設(shè)計(jì)成一個(gè)函數(shù)可以用偽碼描述如下：1 functionlongFib(longn)2 {3 if(n<=1)4 returnn5 else6 returnFib(n-2)+Fib(n-1)7 }2

計(jì)算機(jī)博弈基礎(chǔ)函數(shù)Fib(n)中又調(diào)用了Fib(n-2)和Fib(n-1)，這種在函數(shù)體內(nèi)調(diào)用自己的做法稱為遞歸調(diào)用，包含遞歸調(diào)用的函數(shù)又稱為遞歸函數(shù)，編譯器是利用系統(tǒng)棧來(lái)實(shí)現(xiàn)函數(shù)的遞歸調(diào)用，系統(tǒng)棧是實(shí)現(xiàn)遞歸調(diào)用的基礎(chǔ)。我們可以用遞歸樹(shù)的方法來(lái)描述上述函數(shù)Fib執(zhí)行是的調(diào)用關(guān)系，假設(shè)我們調(diào)用Fib(5)，F(xiàn)ib(5)的執(zhí)行過(guò)程可以用下面的遞歸樹(shù)來(lái)表示：2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)由圖2-4可見(jiàn)，F(xiàn)ib(5)計(jì)算的執(zhí)行過(guò)程為：Fib(5)需要分別調(diào)用Fib(4)和Fib(3)，F(xiàn)ib(4)需要分別調(diào)用Fib(3)和Fib(2)，F(xiàn)ib(3)又需要分別調(diào)用Fib(2)和Fib(1)……，其中Fib(0)被調(diào)用了三次，F(xiàn)ib(1)被調(diào)用了五次，可見(jiàn)使用遞歸在許多工作上是重復(fù)的，當(dāng)然這也是費(fèi)時(shí)的。在上面的遞歸中，我們也可以看到上述的遞歸過(guò)程符合遞歸的兩個(gè)基本條件：每一次遞歸調(diào)用必須包含更小的參數(shù)值，同時(shí)當(dāng)n<=1時(shí)終止了遞歸調(diào)用，即滿足了遞歸調(diào)用必須有一個(gè)終止條件。2

計(jì)算機(jī)博弈基礎(chǔ)2.1.4回溯回溯(backtracking)是一種系統(tǒng)搜索問(wèn)題解的方法，在搜索過(guò)程中先列出所有候選解，然后依次檢查每一個(gè)候選解，在檢查完所有或部分候選解之后，即可找到所有或部分候選解，回溯法是常用的搜索候選解的方法。為了實(shí)現(xiàn)回溯，首先要定義一個(gè)解的空間，在這個(gè)空間中至少包含問(wèn)題的一個(gè)解，一旦定義了解的空間，在這個(gè)空間就可以按照深度優(yōu)先的方法從開(kāi)始節(jié)點(diǎn)進(jìn)行搜索，回溯算法的實(shí)現(xiàn)步驟如下：2

計(jì)算機(jī)博弈基礎(chǔ)(1)定義一個(gè)解空間，它包含問(wèn)題的解。(2)用適合搜索的方法組織該空間。(3)用深度優(yōu)先的方法搜索該空間，利用界定函數(shù)避免移動(dòng)不可能產(chǎn)生解的子空間。2

計(jì)算機(jī)博弈基礎(chǔ)回溯算法的特點(diǎn)是在搜索過(guò)程中就可能產(chǎn)生解空間，在搜索期間的任何時(shí)刻只保留從開(kāi)始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑，回溯算法求解過(guò)程的本質(zhì)就是遍歷一顆“狀態(tài)樹(shù)”的過(guò)程。這顆狀態(tài)樹(shù)隱含在遍歷過(guò)程中，回溯法的基本思想是從一條路往前走(沿著一個(gè)方向前進(jìn))，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試，直到找到符合條件的位置就可以了，下面用迷宮問(wèn)題來(lái)說(shuō)明回溯算法。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)迷宮是一個(gè)矩形區(qū)域，它有一個(gè)入口和一個(gè)出口，，迷宮的入口位置為左上角，迷宮的出口位置為右上角，迷宮內(nèi)部不能穿越障礙物或墻，障礙物沿著行和列放置，它們與迷宮的邊界平行，圖2-5(a)是10×10的迷宮，圖2-5(b)是迷宮的矩陣表示。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)為了能夠更加簡(jiǎn)單描述回溯過(guò)程，用圖2-6的3×3的迷宮來(lái)說(shuō)明搜索的過(guò)程，其中位置數(shù)據(jù)用maze(n,m)表示。圖2-6(a)是要搜索的迷宮，搜索過(guò)程從節(jié)點(diǎn)maze(1,1)開(kāi)始，它是一個(gè)活節(jié)點(diǎn)或E-節(jié)點(diǎn)(ExpansionNode)，為了避免再次走到該節(jié)點(diǎn)，將maze(1,1)置為1，從這個(gè)位置可以移動(dòng)到maze(1,2)或maze(2,1)兩個(gè)位置，因?yàn)榇藭r(shí)兩個(gè)位置的值都為0，假定我們選擇移動(dòng)到maze(1,2)，maze(1,2)被置為1以避免再次經(jīng)過(guò)該點(diǎn)，此時(shí)迷宮的狀態(tài)變?yōu)閳D2-6(b)，maze(1,2)也變?yōu)镋-節(jié)點(diǎn)，從maze(1,2)出發(fā)有三個(gè)可能移動(dòng)的方向，其中兩個(gè)節(jié)點(diǎn)的值為1，是不可以往該方向移動(dòng)的，因此只剩下maze(1,3)一個(gè)節(jié)點(diǎn)可以移動(dòng)，移動(dòng)到該位置，。2

計(jì)算機(jī)博弈基礎(chǔ)同樣將該位置的值設(shè)為1，但是從這個(gè)位置出發(fā)沒(méi)有可以移動(dòng)的方向，所以這個(gè)E節(jié)點(diǎn)maze(1,3)死亡了，回溯到最近被檢查的或節(jié)點(diǎn)maze(1,2)，這個(gè)位置也沒(méi)有可能的移動(dòng)，故這個(gè)節(jié)點(diǎn)也死亡了，唯一留下的活節(jié)點(diǎn)是maze(1,1)，這個(gè)節(jié)點(diǎn)再次變?yōu)镋-節(jié)點(diǎn)，它可以移動(dòng)到maze(2,1)?，F(xiàn)在活節(jié)點(diǎn)為maze(1,1)、maze(2,1)。繼續(xù)下去，能夠到達(dá)maze(3,3)，此時(shí)的活節(jié)點(diǎn)表為maze(1,1)maze(2,1)maze(3,1)maze(3,2)maze(3,3)，這就是走出迷宮的路徑2

計(jì)算機(jī)博弈基礎(chǔ)由上面過(guò)程可以看出，回溯算法實(shí)際上采用的是深度優(yōu)先的搜索策略，從根節(jié)點(diǎn)出發(fā)搜索解的空間樹(shù)算法搜索至解空間樹(shù)的任意一個(gè)節(jié)點(diǎn)時(shí)，總是先判斷這個(gè)節(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)該節(jié)點(diǎn)，逐步向祖先節(jié)點(diǎn)回溯，否則就進(jìn)入該子樹(shù)繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮菟惴ǖ慕K止條件是已經(jīng)找到了答案或回溯盡了所有的活結(jié)點(diǎn)時(shí)，搜索過(guò)程就結(jié)束了。2

計(jì)算機(jī)博弈基礎(chǔ)2.2常用搜索算法與示例

搜索算法是計(jì)算機(jī)博弈中的一個(gè)重要的組成部分，常用的搜索算法包括極大極小算法、α-β剪枝算法、歷史回溯算法等等，在本節(jié)中主要介紹一些常用的搜索算法，在后續(xù)的示例中會(huì)結(jié)合目前一些較為先進(jìn)的搜索算法進(jìn)行講解。2

計(jì)算機(jī)博弈基礎(chǔ)2.2.1極大極小算法

極大極小算法是計(jì)算機(jī)博弈游戲設(shè)計(jì)中最為容易理解的算法，它的基本策略是：考慮雙方對(duì)弈若干步之后，從可能的步子中選擇一步相對(duì)好的走法來(lái)走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。

定義一個(gè)靜態(tài)估值函數(shù)f，以便對(duì)棋局的形勢(shì)做出優(yōu)劣評(píng)估，規(guī)定： MAX和MIN代表對(duì)弈雙方。 P代表一個(gè)棋局(即一個(gè)狀態(tài))。

有利于MAX的態(tài)勢(shì)，f(p)取正值，有利于MIN的態(tài)勢(shì)f(p)取負(fù)值，態(tài)勢(shì)均衡f(p)取零值。2

計(jì)算機(jī)博弈基礎(chǔ)MINIMAX的基本思路為：當(dāng)輪到MIN走步時(shí)，MAX應(yīng)考慮最壞的情況(即f(p)取極小值)，當(dāng)輪到MAX走步時(shí)，MAX應(yīng)考慮最好的情況(即f(p)取極大值)，評(píng)價(jià)往回倒推時(shí)，相應(yīng)于兩位棋手的對(duì)抗策略，交替使用取值方法來(lái)傳遞倒推值。向上值的傳播原則是：若父狀態(tài)在MIN層，那么孩子層的最小值傳遞上去，若父狀態(tài)在MAX層，那么孩子層中的最大值被傳遞上去。目前許多搜索算法都是從極大極小算法發(fā)展而來(lái)，下面從一個(gè)示例中解釋極大極小算法的概念。2

計(jì)算機(jī)博弈基礎(chǔ)假設(shè)甲和乙在玩一個(gè)游戲，我們并不知道游戲具體的規(guī)則，但是我們知道游戲的狀態(tài)，甲方在游戲過(guò)程中希望盡可能獲得盡可能多的“分值”。即：使自己的“分值”量最大化，而乙方則在游戲過(guò)程中則希望在游戲過(guò)程中使甲方的“分值”最少，即：最小化，游戲是如何進(jìn)行的呢？甲方要選擇下法是使游戲過(guò)程中“分值”最大，而乙方則相反，這就是游戲過(guò)程中的極大極小問(wèn)題，也就是“極大極小”算法(MiniMax)。2

計(jì)算機(jī)博弈基礎(chǔ)極大極小算法可以在一個(gè)函數(shù)中完成，也可以在兩個(gè)函數(shù)中完成，即：一個(gè)為計(jì)算極大值函數(shù)，一個(gè)為計(jì)算極小值函數(shù)，用回溯的方法遞歸調(diào)用來(lái)完成。2

計(jì)算機(jī)博弈基礎(chǔ)采用兩個(gè)函數(shù)的極大極小算法的偽碼分別如下：

計(jì)算極大值函數(shù)偽碼：1 functionmax-value(state,depth)2 {3 if(depth==0):4 returnvalue(state)5 endif6 v=-infinite7 foreachsinSUCCESSORS(state):8 v=MAX(v,min-value(s,depth-1))9 returnv10 }2

計(jì)算機(jī)博弈基礎(chǔ)計(jì)算極小值函數(shù)偽碼：1 functionmin-value(state,depth):2 {3 if(depth==0):4 returnvalue(state)5 endif6 v=infinite7 foreachsinSUCCESSORS(state):8 v=MIN(v,max-value(s, depth-1))9 returnv10 }2

計(jì)算機(jī)博弈基礎(chǔ)其中，state表示狀態(tài)，depth表示深度，infinite表示極大值。上述算法的過(guò)程通過(guò)depth(深度)來(lái)控制搜索的深度，從而達(dá)到控制計(jì)算時(shí)間的效果，上述算法是典型的深度優(yōu)先搜索算法，在目前的計(jì)算機(jī)博弈領(lǐng)域應(yīng)用相當(dāng)廣泛。

通過(guò)博弈樹(shù)可以描繪上述游戲的極大極小搜索的過(guò)程，圖2-7是一個(gè)簡(jiǎn)單的搜索過(guò)程示意圖。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)節(jié)點(diǎn)的價(jià)值表示與所經(jīng)過(guò)的路徑產(chǎn)生的價(jià)值，甲方先走棋時(shí)要選擇可以到達(dá)價(jià)值最大的路徑，但他也知道下一步為乙方走棋，而乙方會(huì)盡力下出使他達(dá)到最小節(jié)點(diǎn)的路徑，因此，我們需從底部遞歸填充節(jié)點(diǎn)的價(jià)值，如圖2-8至圖2-10所示。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)由以上示意圖可以看出如果甲方先走棋則應(yīng)選擇C。

博弈樹(shù)假設(shè)游戲者都是合理選擇相應(yīng)節(jié)點(diǎn)，或者說(shuō)游戲者會(huì)選擇最優(yōu)節(jié)點(diǎn)，若果乙方在走棋的時(shí)候不按照常理進(jìn)行，那沒(méi)有什么關(guān)系，對(duì)于甲方來(lái)說(shuō)只會(huì)獲得更佳的結(jié)果。

考慮如下的情況：如果甲方選擇了C，而乙方為了能使甲方的“分值”最小，則會(huì)選擇A作為選擇的路徑，而甲方則會(huì)選擇B，與最大值15相比10是可以獲得的最佳的結(jié)果，同樣對(duì)乙方來(lái)說(shuō)他也已經(jīng)做了最好的選擇。2

計(jì)算機(jī)博弈基礎(chǔ)因此，對(duì)于類似于上述過(guò)程的游戲可以博弈樹(shù)(博弈樹(shù)中有許多節(jié)點(diǎn))的方法來(lái)解決，而節(jié)點(diǎn)則通過(guò)相應(yīng)的估值函數(shù)進(jìn)行賦值，而游戲者則可以通過(guò)極大極小策略來(lái)找到最優(yōu)化的策略。2

計(jì)算機(jī)博弈基礎(chǔ)

為了能更好地理解極大極小搜索算法，我們以井字游戲來(lái)說(shuō)明整個(gè)應(yīng)用過(guò)程。對(duì)井字游戲節(jié)點(diǎn)的評(píng)估我們可以用以下公式表述： E(n)=M(n)-O(n)(2-2)其中：E(n)為狀態(tài)n的總評(píng)價(jià)值，M(n)為我方勝利的路線總數(shù)，O(n)為敵方勝利的路線總數(shù)，假設(shè)若我方達(dá)到勝利局面則E(n)=100，若敵方達(dá)到勝利局面則E(n)=-100，圖2-11所示為在其中的一個(gè)搜索層次兩種不同狀態(tài)的估值方法。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)第三次搜索之后，MAX方只有節(jié)點(diǎn)A可選，其它節(jié)點(diǎn)都會(huì)導(dǎo)致MIN方直接獲勝，在MAX方選擇A節(jié)點(diǎn)后，MIN方無(wú)論選擇A節(jié)點(diǎn)下的任意一個(gè)節(jié)點(diǎn)都會(huì)導(dǎo)致MAX方獲勝，至此，搜索結(jié)束。

極大極小搜索算法由于搜索的深度有限，容易受到“特別好”的狀態(tài)引誘，從而受到沉重的打擊，這就是“地平線”效應(yīng)，在有限的深度或固定的深度進(jìn)行搜索時(shí)所做出的評(píng)估完全可能是誤導(dǎo)性的，因此，當(dāng)把一個(gè)啟發(fā)用于有限深度的預(yù)判時(shí)，在這個(gè)預(yù)判深度內(nèi)無(wú)法探測(cè)出一個(gè)有希望的路徑是否會(huì)在以后的博弈中產(chǎn)生壞的結(jié)果。而對(duì)進(jìn)一步深度的預(yù)判則通常會(huì)受到計(jì)算機(jī)資源的約束。2

計(jì)算機(jī)博弈基礎(chǔ)極大極小搜索算法對(duì)一些“無(wú)價(jià)值”節(jié)點(diǎn)的數(shù)據(jù)也未進(jìn)行處理，致使數(shù)據(jù)存在大量冗余，使計(jì)算機(jī)的資源得不到有效利用，并成為提高搜索深度的障礙，在后續(xù)介紹的算法中對(duì)極大極小算法進(jìn)行了相應(yīng)的改進(jìn)。2

計(jì)算機(jī)博弈基礎(chǔ)2.2.2極大極小法實(shí)現(xiàn)Tic-Tac-Toe游戲

對(duì)上一節(jié)的極大極小算法與Tic-Tac-Toe(井字游戲)，本節(jié)介紹該游戲的完整實(shí)現(xiàn)過(guò)程，為后續(xù)的游戲?qū)崿F(xiàn)做準(zhǔn)備，后續(xù)游戲的基本實(shí)現(xiàn)方法可以在此基礎(chǔ)上進(jìn)行相應(yīng)的改造來(lái)完成，同時(shí)也可以根據(jù)游戲的基本原理進(jìn)行圖形化設(shè)計(jì)，方便游戲參與者進(jìn)行游戲。2

計(jì)算機(jī)博弈基礎(chǔ)下棋過(guò)程可用偽碼描述如下： 1 CreateanemptyTic-Tac-Toeboard 2 Displaythegameinstructions 3 Determinewhogoesfirst 4 Displaytheboard 5 Whilenobody’swonandit’snotstie 6 Ifit’sthehuman’sturn 7 Getthehuman’smove 8 Updatetheboardwithhuman’smove 9 Otherwise 10 Calculatethecomputer’smove 11 Updatetheboardwiththecomputer’smove 12 Displaytheboard 13 Switchturns 14 Congratulatethewinnerordeclareattie2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)Tic-Tac-Toe程序中各個(gè)主要函數(shù)的偽碼如下：初始化棋盤(pán)函數(shù)的偽碼如下：1 functioninitGame()2 {3 fori:0to94 board[i]=BOARD[i]5 }注：BOARD為常量棋盤(pán)，用于初始化棋盤(pán)用，通常可以將所有BOARD[i]值設(shè)為0或null來(lái)表示當(dāng)前棋盤(pán)位置為空。在本例程序中，棋盤(pán)采用了一維數(shù)組來(lái)表示，即board[9]。2

計(jì)算機(jī)博弈基礎(chǔ)設(shè)置棋盤(pán)的函數(shù)主要將棋盤(pán)位置的值改變?yōu)橄缕宸降闹?，同時(shí)將棋盤(pán)更新，設(shè)置函數(shù)的偽碼如下：1 functionsetBoard(inti,intplayer)2 {3 ifboard[i]==null4 thenboard[i]=player5 return0; //棋盤(pán)設(shè)置成功6 elseifboard[i]!=null7 thenreturn-18 endif9 }2

計(jì)算機(jī)博弈基礎(chǔ)判斷棋盤(pán)是否已滿的函數(shù)的作用是判斷棋盤(pán)是否還有可以下棋的位置，采用的方法是掃描整個(gè)棋盤(pán)，檢查是否還有可以下棋的位置，如果有返回false，如果沒(méi)有返回true，函數(shù)的偽碼如下：1 functionisFull()2 {3 fori:0to84 ifboard[i]==null5 thenreturnfalse6 endif7 returntrue8 }2

計(jì)算機(jī)博弈基礎(chǔ)判斷棋盤(pán)是否為空的函數(shù)的作用是檢查棋盤(pán)上的所有位置都為空，如果棋盤(pán)上有位置不是空的則返回false，否則返回true，函數(shù)的偽碼如下：1 functionisEmpty()2 {3 fori:0to84 ifboard[i]!=null5 thenreturnfalse6 endif7 returntrue8 }2

計(jì)算機(jī)博弈基礎(chǔ)判斷贏棋與否的函數(shù)是通過(guò)估值函數(shù)返回的值來(lái)確定是否有一方贏棋，如果棋盤(pán)已經(jīng)下滿且沒(méi)有一方贏棋時(shí)返回平局，函數(shù)的偽碼如下：1 functionisWin()2 {3 ifeval()==+INFINITY4 thenreturnmanwin5 elseifeval()==-INFINITY6 thenreturncomputerwin7 elseifisFull()8 thenreturnDRAW //平局9 elsereturn10 endif11 }2

計(jì)算機(jī)博弈基礎(chǔ)偽碼中的INFINITY表示是一個(gè)足夠大的值，當(dāng)前棋盤(pán)若有對(duì)手直接贏棋的局面則返回+INFINITY，若計(jì)算機(jī)方能夠直接贏棋則返回-INFINITY，該值具體大小可根據(jù)局面價(jià)值的評(píng)估體系來(lái)確定，例如：下棋過(guò)程中一般的估值大小以十位數(shù)計(jì)算，那么該值可以定為1000，即要與基本的估值大小有明顯的區(qū)別，易于計(jì)算機(jī)判別。2

計(jì)算機(jī)博弈基礎(chǔ)估值函數(shù)是通過(guò)掃描棋盤(pán)的狀態(tài)給出當(dāng)前局面的價(jià)值，具體的內(nèi)容根據(jù)估值方法來(lái)確定，下屬偽碼的估值采用的是根據(jù)前述井字棋的估值方法來(lái)實(shí)現(xiàn)的，估值函數(shù)的偽碼如下：1 functioneval()2 {3 inttemp[9]={0}4 fori:0to85 temp[i]=board[i]6 intwin=07 intlose=08 fori:0to89 intsum=010 forj:0to211 sum+=temp[line[i][j]]12 if(sum==3)13 thenreturnMAX=+INFINITY14 elseif(sum==-3)15 thenreturnMIN=-INFINITY16 elseif(-3<sum<0)17 thenlose++18 elseif(0<sum<3)19 thenwin++20 endif21 returnwin-lose22 }2

計(jì)算機(jī)博弈基礎(chǔ)該估值函數(shù)使用的估值方法是：E(n)=M(n)-O(n)，這個(gè)估值函數(shù)僅僅是個(gè)示例，實(shí)際上還有比這種方法更為有效的評(píng)估方法，在棋力上要強(qiáng)于上述的估值函數(shù)。

極大極小搜索算法偽碼如下：1 functionminimaxSearch(intdepth)2 {3 intbestMoves[9]={0}4 index=05 intbestValue=-INFINITY6 if(depth==0andisFull())7 thenreturneval()8 else9 forpos:0to810 if(board[pos]==NULL)11 thenboard[pos]=MAX //生成下棋局面2

計(jì)算機(jī)博弈基礎(chǔ)12 intvalue=minSearch(depth-1)13 if(value>bestValue)14 thenbestValue=value15 intindex=016 bestMoves[index]=pos17 elseif(value==bestValue)18 thenbestMoves[++index]=pos19 endif20 board[pos]=NULL //恢復(fù)棋盤(pán)21 endif22 endif23 returnbestMoves[index]24 }注：minimaxSearch遞歸調(diào)用minSearch和maxSearch，將函數(shù)分解成兩部分更有助于對(duì)搜索過(guò)程的理解。2

計(jì)算機(jī)博弈基礎(chǔ)搜索極大值算法的偽碼如下：1 functionmaxSearch(intdepth)2 {3 intbestValue=-INFINITY4 if(depth==0andisFull())5 thenreturneval()6 else7 intvalue8 forpos:0to89 if(board[pos]==NULL)10 thenboard[pos]=MAX11 value=minSearch(depth-1)12 if(value>bestValue)13 thenbestValue=value14 endif15 board[pos]=NULL16 endif17 endif18 returnbestValue19 }2

計(jì)算機(jī)博弈基礎(chǔ)搜索極小值算法的偽碼如下：1 functionminSearch(intdepth)2 {3 intbestValue=+INFINITY4 if(depth==0andisFull())5 thenreturneval()6 else7 intvalue8 forpos:0to89 if(board[pos]==NULL)10 thenboard[pos]=MIN11 value=maxSearch(depth-1)12 if(value<bestValue)13 then bestValue=value14 endif15 board[pos]=NULL16 endif17 endif18 returnbestValue19 }2

計(jì)算機(jī)博弈基礎(chǔ)在極大極小搜索、極大搜索和極小搜索的過(guò)程中都使用了下面的代碼：board[pos]=NULL這行代碼的作用是在回溯過(guò)程中將當(dāng)前棋局還原，這個(gè)還原過(guò)程實(shí)際上是沿著可能的最佳下法向上還原棋盤(pán)，最終得到當(dāng)前棋局的最佳位置的棋盤(pán)表示。

打印棋盤(pán)的偽碼如下：1 functionprint()2 {3 fori:0to84 if(i%3==0)5 thenprint‘\n’6 endif7 if(board[i]==NULL)8 thenprint‘-’9 endif10 if(board[i]==MAX)11 thenprint‘x’12 endif13 if(board[i]==MIN)14 thenprint‘o’15 endif16 print‘\n’17 }2

計(jì)算機(jī)博弈基礎(chǔ)由于在本示例中采用了一維數(shù)組來(lái)表示棋盤(pán)，因此在打印棋盤(pán)的過(guò)程中采用了每打印三個(gè)數(shù)據(jù)后就換行，這樣就保證了棋盤(pán)的正常顯示，根據(jù)實(shí)際需要也可以采用二維數(shù)組，將數(shù)據(jù)定義成board[3][3]，將上述過(guò)程稍加修改即可。上述Tic-Tac-Toe的偽碼可以根據(jù)實(shí)際編程語(yǔ)言轉(zhuǎn)換成具體的程序，各個(gè)函數(shù)的實(shí)現(xiàn)也可以根據(jù)設(shè)計(jì)來(lái)實(shí)現(xiàn)，并且可以根據(jù)實(shí)際情況附加其它相關(guān)的功能來(lái)豐富Tic-Tac-Toe的功能，本例偽碼是以控制臺(tái)下實(shí)現(xiàn)進(jìn)行設(shè)計(jì)，讀者可以根據(jù)實(shí)際情況轉(zhuǎn)化成可視界面來(lái)完成。2

計(jì)算機(jī)博弈基礎(chǔ)2.2.3α-β剪枝算法α-β剪枝算法(Alpha-BetaPruning)來(lái)源于極大極小算法。形成原因：1、大規(guī)模搜索數(shù)據(jù)采用極大極小搜索算法顯然在搜索深度上受到極大的限制，對(duì)游戲局面很難進(jìn)行深層次的評(píng)估，有很多節(jié)點(diǎn)再進(jìn)行更深層次的搜索是沒(méi)有太大的意義的。2、有些節(jié)點(diǎn)的分支并不需要進(jìn)一步考慮。2

計(jì)算機(jī)博弈基礎(chǔ)下圖注意灰色部分2

計(jì)算機(jī)博弈基礎(chǔ)部分剪枝的說(shuō)明示意圖：2

計(jì)算機(jī)博弈基礎(chǔ)α-β剪枝算法偽碼如下：01 functionalphabeta(node,depth,α,β,Player)02 {03 ifdepth=0ornodeisaterminalnode04 returntheheuristicvalueofnode05 endif06 ifPlayer=MaxPlayer07 foreachchildofnode08 α:=max(α,alphabeta(child,depth-1,α,β,not(Player)))09 ifβ≤α10 break(*Beta剪枝*)11 endif12 returnα13 else2

計(jì)算機(jī)博弈基礎(chǔ)foreachchildofnode15 β:=min(β,alphabeta(child,depth-1,α,β,not(Player)))16 ifβ≤α17 break(*Alpha剪枝*)18 endif19 returnβ20 endif21 (*Initialcall*)22 alphabeta(origin,depth,-infinity,+infinity,MaxPlayer)23 }2

計(jì)算機(jī)博弈基礎(chǔ)2.2.4期望搜索算法期望搜索算法主要針對(duì)不完備信息博弈，不完備信息博弈是指在博弈過(guò)程中對(duì)手的信息不能完全了解或了解得不夠準(zhǔn)確，例如軍棋和軍棋就屬于不完備信息類的博弈游戲。例如：愛(ài)恩斯坦棋則是在下棋過(guò)程中并不能確定下一步棋對(duì)方應(yīng)該下在哪一個(gè)位置，具體下在那個(gè)位置需要根據(jù)擲骰子得到的數(shù)字來(lái)確定下棋棋子的編號(hào)，這類游戲不能采用上述的搜索算法來(lái)進(jìn)行搜索，需要采用適合于這類游戲的方法，目前比較適合的方法是期望極大極小法(ExpectMinimax)。2

計(jì)算機(jī)博弈基礎(chǔ)期望極大極小算法是極大極小算法的變種，在搜索過(guò)程中引入了概率，克服了不完備信息博弈中的概率問(wèn)題。期望極大極小算法的示意圖：圖2-222

計(jì)算機(jī)博弈基礎(chǔ)期望搜索算法有以下幾個(gè)特點(diǎn)： 1、極大節(jié)點(diǎn)是期望極大極小的下一層返回的最大值。 2、極小節(jié)點(diǎn)是期望極大極小的下一層返回的最小值。 3、概率節(jié)點(diǎn)是期望極大極小的下一層返回的期望平均值?？梢杂萌缦路绞接?jì)算式中：n表示概率節(jié)點(diǎn)，s表示節(jié)點(diǎn)n的所有下一層節(jié)點(diǎn)。2

計(jì)算機(jī)博弈基礎(chǔ)愛(ài)恩斯坦棋是使用期望極大極小搜索算法的比較典型的例子，下面用愛(ài)恩斯坦棋來(lái)說(shuō)明CHANCE節(jié)點(diǎn)的問(wèn)題：2

計(jì)算機(jī)博弈基礎(chǔ)愛(ài)恩斯坦棋的布局是由下棋方自己確定，具體下那個(gè)棋子是通過(guò)擲骰子來(lái)確定的。對(duì)手無(wú)法準(zhǔn)確猜測(cè)具體下那個(gè)棋子，在愛(ài)恩斯坦棋中占領(lǐng)對(duì)方角點(diǎn)是一種取勝的手段，而對(duì)局面的估值的一種常用的方法是計(jì)算到對(duì)方角點(diǎn)的距離，即需要多少步才能到達(dá)對(duì)方的角點(diǎn)。此時(shí)是無(wú)法直接計(jì)算的，就需要考慮CHANCE問(wèn)題來(lái)解決，以計(jì)算黑方為例，圖2-22中的距離和出現(xiàn)的概率如表2-1所示：2

計(jì)算機(jī)博弈基礎(chǔ)計(jì)算value=∑r(si)×p(si)=28/6，得到黑棋占領(lǐng)對(duì)方角點(diǎn)的期望距離。2

計(jì)算機(jī)博弈基礎(chǔ)上面計(jì)算的CHANCE節(jié)點(diǎn)問(wèn)題是每個(gè)棋子都有可能下棋的情況，在某些棋子被吃掉的情況下還需進(jìn)一步考慮其它因素。2

計(jì)算機(jī)博弈基礎(chǔ)在左圖中很顯然無(wú)論擲骰子得到什么數(shù)都只能移動(dòng)4號(hào)黑棋，因此很容易計(jì)算得到它的價(jià)值為4。而對(duì)右圖棋局殘留2個(gè)棋子，棋子1和棋子6，當(dāng)骰子擲出1和6時(shí)，則必須移動(dòng)對(duì)應(yīng)的棋子，當(dāng)骰子擲出2、3、4、5時(shí)，由于棋子1離角點(diǎn)的距離為1，而棋子6離角點(diǎn)的距離為2，因此，移動(dòng)棋子1，計(jì)算得到：value=5/6×1+1/6×2=7/6。2

計(jì)算機(jī)博弈基礎(chǔ)2.2.5迭代加深假如在游戲開(kāi)始時(shí)，搜索層次只設(shè)置為一層，如果還有時(shí)間則再進(jìn)行下一層搜索，以此類推來(lái)控制游戲的進(jìn)行。采用這種方法就能有效利用時(shí)間來(lái)控制搜索的層次。這種搜索方法就稱為迭代加深。2

計(jì)算機(jī)博弈基礎(chǔ)迭代加深的偽碼如下：01 for(depth=1;;depth++)02 {03 val=AlphaBeta(depth,-INFINITY, INFINITY);04

if(TimedOut())05 {06

break;07

}08 }2

計(jì)算機(jī)博弈基礎(chǔ)2.2.6PVS算法PVS算法(PrincipalVariationSearch，簡(jiǎn)稱PVS)也是對(duì)α-β剪枝算法的一種改進(jìn)，它的主要思想是在第一層搜索時(shí)找到最佳位置，那么α-β剪枝算法具有最高搜索效率。采用PVS搜索算法需要在進(jìn)行第一層搜索時(shí)對(duì)所有可行下法進(jìn)行估值并獲得其中估值最高的位置，并將該位置置于所有可下位置的第一位，然后以該位置為基礎(chǔ)進(jìn)行搜索。2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)PVS算法的偽碼如下：01 intalphabeta(intdepth,intalpha,intbeta)02 {03 movebestMove,current;04 if(gameOver()||depth==0)05 {06 returneval();07 }08 movem=firstMove;09 makeMovem;10 current=-alphabeta(depth-1,-beta,- alpha);11 unMakeMovem;12 ……2

計(jì)算機(jī)博弈基礎(chǔ)PVS算法的核心是獲得第一層的最佳位置，獲得最佳位置的方法可以是排序，也可以是查找獲得最佳位置，并將該位置放置可下位置的首位。也可以采用置換表的方法，將每次搜索中獲得的最佳位置存放到置換表，在需要的時(shí)候直接使用。2

計(jì)算機(jī)博弈基礎(chǔ)2.3估值函數(shù)的設(shè)計(jì)估值函數(shù)在博弈軟件設(shè)計(jì)中的作用是為尋找最佳位置提供數(shù)值計(jì)算的依據(jù)，在計(jì)算機(jī)博弈軟件的設(shè)計(jì)中，一個(gè)好的估值方法往往是博弈取勝的關(guān)鍵，它為搜索過(guò)程的具體實(shí)現(xiàn)提供計(jì)算的基礎(chǔ)。在下面的小節(jié)中將介紹估值函數(shù)設(shè)計(jì)的基本原理和方法，并簡(jiǎn)單介紹估值函數(shù)參數(shù)和權(quán)重的調(diào)整方法。2

計(jì)算機(jī)博弈基礎(chǔ)2.3.1估值函數(shù)設(shè)計(jì)概述估值函數(shù)又可以稱為啟發(fā)式估值函數(shù)或靜態(tài)估值函數(shù)，是在極大極小算法、α-β剪枝算法及其它相關(guān)算法中用到的對(duì)游戲程序中當(dāng)前位置的價(jià)值進(jìn)行評(píng)估的一種比較好的方法。估值函數(shù)的作用是評(píng)估當(dāng)前的局面。通常估值函數(shù)有兩個(gè)基本的要求：估值的準(zhǔn)確性和估值的速度，準(zhǔn)確性依賴于對(duì)游戲規(guī)則與下法的理解程度，估值的速度取決于估值計(jì)算方法的合理性。2

計(jì)算機(jī)博弈基礎(chǔ)估值函數(shù)設(shè)計(jì)得好壞主要依賴于游戲規(guī)則和對(duì)游戲的經(jīng)驗(yàn)知識(shí)。并且其中的某一部分并不一定完全可靠，而僅依賴于你或他人的相關(guān)經(jīng)驗(yàn)，同時(shí)還需要進(jìn)行大量的試驗(yàn)來(lái)確定相應(yīng)的估值函數(shù)參數(shù)。2

計(jì)算機(jī)博弈基礎(chǔ)估值函數(shù)的設(shè)計(jì)一般是基于兩個(gè)基本的假設(shè)：其一是我們可以把局面量化成一個(gè)數(shù)字，這個(gè)數(shù)字可以對(duì)取勝的概率作出一個(gè)估計(jì)，當(dāng)大多數(shù)程序并不給這個(gè)數(shù)字以如此確切的含義，因此這僅僅是一個(gè)數(shù)字。其二是衡量的這個(gè)性質(zhì)和對(duì)手衡量的性質(zhì)是一樣的(如果我們認(rèn)為我們處于優(yōu)勢(shì)，那么反過(guò)來(lái)對(duì)手認(rèn)為它處于劣勢(shì))，但在實(shí)際上的情況可能有一定的出入，但這種假設(shè)使得搜索算法能夠正常地進(jìn)行，并且在實(shí)戰(zhàn)中和實(shí)際情況非常接近。2

計(jì)算機(jī)博弈基礎(chǔ)典型的估值函數(shù)大致需要包含以下幾方面的內(nèi)容：(1)子力——子力是評(píng)估棋盤(pán)上棋子的總價(jià)值(2)空間——空間評(píng)價(jià)就是將各個(gè)區(qū)域加在一起。例如：圍棋、亞馬遜棋等(3)靈活性——例如：亞馬遜棋(4)下法——例如在點(diǎn)格棋中采用控制先后手的方法來(lái)保證在最后獲得長(zhǎng)鏈，而當(dāng)不能獲得最后下棋權(quán)利時(shí)采用讓格手段。(5)威脅——對(duì)手是否有更兇狠的手段？你有哪些更好的下法？例如在國(guó)際象棋、中國(guó)象棋中有哪些棋子可能會(huì)被吃掉？在六子棋中是否有四連或五連？(6)形狀——例如中國(guó)象棋的連環(huán)馬2

計(jì)算機(jī)博弈基礎(chǔ)將以上的過(guò)程綜合就可以得到：2

計(jì)算機(jī)博弈基礎(chǔ)式中n表示所需估值種類的數(shù)量，具體需根據(jù)不同的博弈游戲來(lái)確定，F(xiàn)表示估值的內(nèi)容，K表示相應(yīng)估值所占的權(quán)重。2.3.2估值函數(shù)設(shè)計(jì)示例愛(ài)恩斯坦棋贏棋方法有兩種，其一是占領(lǐng)對(duì)方角部位置其二是吃掉對(duì)方所有棋子。從占領(lǐng)對(duì)方角部位置分析，這種贏棋方式在估值函數(shù)設(shè)計(jì)時(shí)需考慮棋子給對(duì)方造成的威脅2

計(jì)算機(jī)博弈基礎(chǔ)其一是占領(lǐng)對(duì)方角部位置，可以通過(guò)下面公式計(jì)算：2

計(jì)算機(jī)博弈基礎(chǔ)式中：R表示占領(lǐng)對(duì)方角部的期望距離，p(i)表示移動(dòng)某個(gè)棋子的概率，r(i)表示某個(gè)棋子距離角部的距離。其二是吃掉對(duì)方所有的棋子，可以通過(guò)下面公式計(jì)算：式中：T表示棋子受對(duì)方威脅的估值，p(i)表示對(duì)方擲骰子得到某個(gè)數(shù)的概率，此處都是1/6，v(i)表示棋子的價(jià)值(棋子處于不同位置的價(jià)值不同，越接近于對(duì)方角部位置的棋子價(jià)值越大)，擲骰子得到數(shù)目從1到6都可能，因此需計(jì)算1~6所有的數(shù)。有上述過(guò)程可以得到量化的愛(ài)恩斯坦棋的估值方法，將兩者結(jié)合就可以得到：(2-7)式中K1和K2分別是權(quán)重因子，F(xiàn)(r)是占領(lǐng)對(duì)方角部的期望距離，F(xiàn)(t)是受對(duì)方威脅的估值。權(quán)重因子K1和K2到底為多大需根據(jù)具體情況確定，或采用一定的優(yōu)化方法調(diào)整，在下一節(jié)中將簡(jiǎn)單介紹估值函數(shù)參數(shù)和權(quán)重因子的調(diào)整方法。2

計(jì)算機(jī)博弈基礎(chǔ)2.3.3布局與估值在計(jì)算機(jī)博弈游戲中包含了很多不完備信息類的博弈游戲，其中的一些游戲的布局是由博弈雙方各自確定，雙方可以根據(jù)自己對(duì)開(kāi)局布局的理解來(lái)確定各自的布局，目前全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽中的軍棋、愛(ài)恩斯坦棋等就屬于這類游戲。下圖是愛(ài)恩斯坦棋布局的勝率2

計(jì)算機(jī)博弈基礎(chǔ)2

計(jì)算機(jī)博弈基礎(chǔ)3.博弈比賽典型游戲簡(jiǎn)介本部分主要介紹博弈比賽常見(jiàn)游戲的下法與規(guī)則。亞馬遜棋規(guī)則：棋盤(pán)：由黑白相間的10*10的方格組成，雙方右下角為白色格子

棋子：每方有4個(gè)棋子（4個(gè)Amazons）。

棋規(guī)：

1．每個(gè)棋子都相當(dāng)于國(guó)際象棋中的皇后，它們的行棋方法與皇后相同，可以在8個(gè)方向（上、下、左、右、左上、左下、右上、右下）上任意行走，但不能穿過(guò)阻礙；

2．當(dāng)輪到一方行棋時(shí)，此方只能而且必須移動(dòng)4個(gè)Amazons中的一個(gè)，并在移動(dòng)完成后，由當(dāng)前移動(dòng)的棋子釋放一個(gè)障礙，障礙的釋放方法與棋子的移動(dòng)方法相同（8個(gè)方向，但不能穿過(guò)障礙），同樣障礙的放置也是必須的；

3．當(dāng)某方完成某次移動(dòng)后，對(duì)方4個(gè)棋子均不能再移動(dòng)時(shí)，對(duì)方將輸?shù)舯荣悾?/p>

4．每次開(kāi)局位于棋盤(pán)下方的玩家先手；

5．整個(gè)比賽中雙方均不能吃掉對(duì)方或己方的棋子或障礙。六子棋規(guī)則：與傳統(tǒng)的五子棋（這里指的是沒(méi)有禁著的五子棋）非常相似，規(guī)則非常簡(jiǎn)單僅有以下三條：

玩家：如五子棋及圍棋，有黑白兩方，各持黑子與白子，黑先。

玩法：除了第一次黑方下一顆子外，之后黑白雙方輪流每次各下兩子，直的、橫的、斜的連成6子（或以上）者獲勝。若全部棋盤(pán)填滿仍未分出勝負(fù)，則為和局。沒(méi)有禁手；例如長(zhǎng)連仍算贏。

棋盤(pán)：因?yàn)楣叫圆皇菃?wèn)題，棋盤(pán)是可以任意地大，甚至是無(wú)限大亦可。然而為了讓游戲可實(shí)質(zhì)地來(lái)玩，目前棋盤(pán)采用圍棋的十九路棋盤(pán)。

注：六子棋詳細(xì)規(guī)則見(jiàn)：.tw/~icwu/connect6/chinese/蘇拉卡爾塔棋蘇拉卡塔棋是一種兩人玩的吃子類游戲，源自印尼爪哇島的蘇拉卡爾塔(Surakarta)。

棋盤(pán)：

由6×6正方形網(wǎng)絡(luò)與角落上的8個(gè)圓弧所組成，如圖1所示。

棋子：在游戲開(kāi)始時(shí)，黑白方各12個(gè)棋子排成兩行(圖1)。

棋規(guī)：

1．參賽者擲硬幣決定由誰(shuí)先開(kāi)始，每次只能移動(dòng)一個(gè)棋子，兩人輪流走棋；

2．每個(gè)棋子可以向8個(gè)方向（上、下、左、右、左上、左下、右上、右下）移動(dòng)一格（當(dāng)所去的方向方向無(wú)棋子時(shí)）；

3．若要吃掉對(duì)方棋子，必須經(jīng)過(guò)至少一個(gè)完整的弧線，并且移動(dòng)路徑中不可以有本方棋子阻擋；

4．黑子可以吃掉白子，同樣白子沿同一路徑的相反方向也可以吃掉黑子；

5．當(dāng)一方棋子全部被吃掉時(shí)棋局結(jié)束，有剩余棋子方獲勝；

6．當(dāng)雙方都不能再吃掉對(duì)方棋子時(shí)，剩余棋子多的一方獲勝。?？怂蛊搴？怂蛊澹℉ex）?？怂蛊澹℉ex）屬于一種雙人的落子類游戲。棋盤(pán)（國(guó)際奧林匹克比賽采用的棋盤(pán)）：

典型的棋盤(pán)由11×11個(gè)六邊形單元格組成，上下兩個(gè)邊界線為紅色、左右兩個(gè)邊界線為藍(lán)色，紅色（橫向）坐標(biāo)表示范圍A-K,藍(lán)色（縱向）坐標(biāo)表示范圍1-11，如圖1所示。棋子：兩種顏色的圓形棋子（略小于棋盤(pán)上的六邊形單元格），紅與藍(lán)。對(duì)弈雙方各執(zhí)一種顏色的棋子。

棋規(guī)：比賽開(kāi)始后，雙方交替落子，每次只能落一個(gè)棋子，每個(gè)棋子占據(jù)一個(gè)六邊形單元格；兩個(gè)相鄰的同色棋子被認(rèn)為相互連通；最先將同色的兩個(gè)邊界用同色棋子連通的一方獲勝（如圖2中的藍(lán)方勝）；

不存在和棋。

雙方輪流先手，各賽一局，每局比賽紅方先。對(duì)戰(zhàn)溝通落棋位置時(shí)嚴(yán)格按照坐標(biāo)（先縱再橫的順序）描述。五子棋棋盤(pán)：15×15圍棋的棋盤(pán)。

棋子：黑白兩種圍棋棋子。

棋規(guī)：

1.先后手的確定：可由大賽組委會(huì)抽簽或?qū)智安孪取?/p>

2.開(kāi)局：包括指定開(kāi)局、自由開(kāi)局兩種，全國(guó)博弈大賽擬采用指定開(kāi)局模式。

3.對(duì)局雙方各執(zhí)一色棋子，黑先、白后交替下在棋盤(pán)的交叉點(diǎn)上，棋子下定后，不得向其它點(diǎn)移動(dòng)，不得從棋盤(pán)上拿起另落別處。每次只能下一子（指定開(kāi)局、三手交換和五手N打、行使PASS權(quán)除外）。

在采用指定開(kāi)局時(shí)黑方的第一枚棋子應(yīng)下在天元上。同時(shí)在下面的對(duì)局中應(yīng)執(zhí)行三手交換和五手N打及禁手規(guī)則。

4.指定開(kāi)局：指黑方?jīng)Q定了前三個(gè)棋子落于何處，其中包括兩個(gè)黑子和一個(gè)白子，一般由黑方完成。黑方應(yīng)同時(shí)給出第五手需要的打點(diǎn)數(shù)量。采用指定開(kāi)局辦法的比賽均采用斜指或直指開(kāi)局（26種），黑方第一子應(yīng)落在天元處（黑1）。黑方還決定了白方的第一子的落點(diǎn)（白2）。黑方的第二子（黑3），應(yīng)落在圍繞天元點(diǎn)5線×5線而形成的以天元為正中的由交叉點(diǎn)組成的區(qū)域內(nèi)。

5.自由開(kāi)局：由雙方輪流行棋共同決定開(kāi)局前3個(gè)棋子落于何處。即黑方落第一子（黑1）、白方落第二子（白2），黑方落第三子（黑3）。采用此種開(kāi)局時(shí)一般雙方的對(duì)局?jǐn)?shù)為偶數(shù)，或采用其他附加條款對(duì)黑方的先行優(yōu)勢(shì)進(jìn)行限制。而不采用指定開(kāi)局中使用的三手交換和五手N打，也可不執(zhí)行禁手規(guī)則。

6.三手交換

在采用指定開(kāi)局的對(duì)局中，在黑3之后，白方在應(yīng)白4之前，可選擇黑棋或白棋，每盤(pán)棋只有一次選擇機(jī)會(huì)，如提出交換黑、白方，則黑方必須同意交換。

五子棋

7.五手N打

黑方在指定開(kāi)局的同時(shí)要給出本局盤(pán)面黑5時(shí)所需的打點(diǎn)數(shù)量，此后無(wú)論對(duì)局者誰(shuí)執(zhí)黑棋，都需要在落第五手時(shí)按照要求的打點(diǎn)數(shù)量，在盤(pán)面上的空白交叉點(diǎn)上放置相應(yīng)數(shù)量且位置不同形的黑子，白方只能在這些黑子中留下一個(gè)黑子作為黑5。

8.禁手

對(duì)局中如果使用三三禁手、四四禁手、長(zhǎng)連禁手，將被判負(fù)。

9.終局勝負(fù)判定：

（1）最先在棋盤(pán)上形成五連的一方為勝。白棋長(zhǎng)連視同五連。

（2）黑方出現(xiàn)禁手，則判白方勝。如白方在黑方出現(xiàn)禁手后，未立即指出而又落下一白子，則黑方禁手不再成立。

若黑方走出長(zhǎng)連禁手，白方只要是在終局前指出此禁手，判白方勝。

黑方五連與禁手同時(shí)形成，禁手失效，黑方勝。

（3）對(duì)局中，一方出現(xiàn)下列情況之一判負(fù)：比賽對(duì)局中移子或棋局散亂、超過(guò)規(guī)定時(shí)限、人為輔助計(jì)算、主動(dòng)停止計(jì)時(shí)。

（4）對(duì)局中出現(xiàn)下列情況之一，判和棋：對(duì)局雙方同一回合均放棄行棋權(quán)、全盤(pán)下滿，且無(wú)勝局出現(xiàn)、雙方比賽同時(shí)超時(shí)。五子棋26種開(kāi)局愛(ài)恩斯坦棋

棋盤(pán)為5×5的方格形棋盤(pán)，方格為棋位，左上角為紅方出發(fā)區(qū)；右下角為藍(lán)方出發(fā)區(qū)，如圖1所示；

1．紅藍(lán)方各有6枚方塊形棋子，分別標(biāo)有數(shù)字1—6。開(kāi)局時(shí)雙方棋子在出發(fā)區(qū)的棋位可以隨意擺放；

2．雙方輪流擲骰子，然后走動(dòng)與骰子顯示數(shù)字相對(duì)應(yīng)的棋子。如果相對(duì)應(yīng)的棋子已從棋盤(pán)上移出，便可走動(dòng)大于或者小于此數(shù)字的并與此數(shù)字最接近的棋子，例如：假設(shè)編號(hào)為4和5的棋子已移出，如果骰子顯示為4，則可以走動(dòng)編號(hào)為3或6的棋子；

3．紅方棋子走動(dòng)方向?yàn)橄蛴摇⑾蛳?、向右下，每次走?dòng)一格；藍(lán)方棋子走動(dòng)方向?yàn)橄蜃?、向上、向左上，每次走?dòng)一格；

4．如果在棋子走動(dòng)的目標(biāo)棋位上有棋子，則要將該棋子從棋盤(pán)上移出（吃掉）。有時(shí)吃掉本方棋子也是一種策略，因?yàn)榭梢栽黾悠渌遄幼邉?dòng)的機(jī)會(huì)與靈活性；

5．率先到達(dá)對(duì)方出發(fā)區(qū)角點(diǎn)或?qū)?duì)方棋子全部吃掉的一方獲勝；

6．對(duì)弈結(jié)果只有勝負(fù)，沒(méi)有和棋。

7．每盤(pán)每方用時(shí)4分鐘，超時(shí)判負(fù)；每輪雙方對(duì)陣最多7盤(pán)，輪流先手（甲方一四五盤(pán)先手，乙方二三六七盤(pán)先手），兩盤(pán)中間不休息，先勝4盤(pán)為勝方。點(diǎn)格棋

點(diǎn)格棋又稱之為點(diǎn)點(diǎn)連格棋，也是國(guó)外的一種添子類游戲。

棋盤(pán)：N×N的點(diǎn)格棋盤(pán)由N×N個(gè)等距點(diǎn)陣構(gòu)成。全國(guó)大賽采用6×6點(diǎn)格棋盤(pán)。

棋子：

1)連接橫豎相鄰兩點(diǎn)的短桿（火柴棍），雙方公用。對(duì)于6×6點(diǎn)格棋需要60個(gè)短桿；

2)標(biāo)示棋子各25個(gè)，用以標(biāo)示格的占有。

棋規(guī)：

1)雙方輪流用短桿（棋子）將橫向或豎向鄰近的兩點(diǎn)連成一邊——占邊，不可越點(diǎn)，不可重邊；

2)當(dāng)一個(gè)格子的四條邊均被占滿，則最后一個(gè)占邊者獲取這個(gè)格子。在格子中間放入一個(gè)標(biāo)示棋子；

3)當(dāng)一方在占邊時(shí)捕獲了格子，則該方繼續(xù)占邊。該輪添子結(jié)束的標(biāo)志是占邊后未獲取格子；

4)游戲結(jié)束的標(biāo)志：所有的鄰近點(diǎn)均被連成邊，也就是說(shuō)所有的格子被俘獲；

5)占領(lǐng)格子較多的一方為獲勝方。終局如圖2所示，E、D分別為雙方的標(biāo)示棋子。4Zobrist鍵值——比較局面的方法

博弈游戲局面包含了棋盤(pán)上的棋子、哪一方走棋、可以下棋位置等信息。

在寫(xiě)博弈的程序時(shí)，需要比較兩個(gè)局面看它們是否相同。如果你比較每個(gè)棋子的位置，或許不需要花很多時(shí)間，但是實(shí)戰(zhàn)中你每秒種需要做成千上萬(wàn)次比較，因此這樣會(huì)使比較操作變成瓶頸的。

另外，需要比較的局面數(shù)量多得驚人，要存儲(chǔ)每個(gè)棋子的位置，需要占用非常大的空間。一個(gè)解決方案是建立一個(gè)標(biāo)簽，通常是64位。由于64位不足以區(qū)別每個(gè)局面，所以仍然存在沖突的標(biāo)簽。但是實(shí)戰(zhàn)中這種情況非常罕見(jiàn)，你可以有充分的把握不會(huì)發(fā)生沖突。

用32位是否足夠，目前爭(zhēng)論很多，而用64位通常是明智的。Zobrist鍵值是一個(gè)常用的建立標(biāo)簽的方法。Zobrist鍵值——實(shí)現(xiàn)

從64位數(shù)組開(kāi)始，每個(gè)數(shù)組含有一個(gè)隨機(jī)數(shù)。在C語(yǔ)言中，“rand()”函數(shù)返回一個(gè)15位的值(0~32767)，所以要得到64位的隨機(jī)數(shù)還需要再加工一下。這個(gè)64位隨機(jī)數(shù)的函數(shù)是：U64rand64(void){

returnrand()^((U64)rand()<<15)^((U64)rand()<<30)^((U64)rand()<<45)^((U64)rand()<<60);} Zobrist鍵值——實(shí)現(xiàn)

這個(gè)函數(shù)用來(lái)填滿一個(gè)“U64”的元素(你需要自己來(lái)定義這個(gè)類型，這取決于你的編譯器，試一下“l(fā)onglong”或者“__int64”)，它是通過(guò)調(diào)用一系列“rand()”來(lái)實(shí)現(xiàn)的。

無(wú)論如何你的數(shù)組要有三維：棋子的類型、棋子的顏色和棋子的位置：U64zobrist[pcMAX][coMAX][sqMAX]; Zobrist鍵值——為什么Zobrist鍵值特別有用

用Zobrist技術(shù)產(chǎn)生的鍵值，表面上跟局面沒(méi)什么關(guān)系。如果一個(gè)棋子動(dòng)過(guò)了，你會(huì)得到完全不同的鍵值，所以這兩個(gè)鍵值不會(huì)擠在一塊兒或者沖突。當(dāng)你把它們用作散列表鍵值的時(shí)候會(huì)非常有效。

另一個(gè)優(yōu)點(diǎn)在于，鍵值的產(chǎn)生是可以逐步進(jìn)行的。

如果你要改變著子的一方，只要異或一個(gè)“改變著子方”的鍵值就可以了。

Zobrist鍵值——鍵值的用途

Zobrist鍵值通常用在散列鍵值當(dāng)中，而散列鍵值在博弈程序里有以下幾個(gè)作用：(1)

用Zobrist鍵值來(lái)實(shí)現(xiàn)置換表。置換表是一個(gè)巨大的散列表，來(lái)保存以前搜索過(guò)的局面，讓你節(jié)省很多搜索的時(shí)間。如果你需要對(duì)某個(gè)局面搜索9層，你可以從置換表中查找該局面，如果它已經(jīng)搜索過(guò)9層，那么你不必去重復(fù)搜索。置換表的一個(gè)并不起眼的作用是，它可以幫助你改善著法的順序。Zobrist鍵值——鍵值的用途

(2)

用Zobrist鍵值來(lái)實(shí)現(xiàn)兵型的散列表。你可以用一個(gè)鍵值只記錄棋盤(pán)上的兵，對(duì)兵型做了很復(fù)雜的分析后，在散列表中記錄分析的結(jié)果。在實(shí)戰(zhàn)中兵型是很少發(fā)生變化的，所以這個(gè)散列表的命中率會(huì)非常高，它可以為你評(píng)估兵型節(jié)省很多時(shí)間。

Zobrist鍵值——鍵值的用途

(3)

可以用Zobrist鍵值制造一個(gè)很小的散列表，來(lái)檢測(cè)當(dāng)前著法路線中有沒(méi)有重復(fù)局面，以便發(fā)現(xiàn)長(zhǎng)將或其他導(dǎo)致和局的著法。

(4)

可以用Zobrist鍵值創(chuàng)建支持置換的開(kāi)局庫(kù)。

5MonteCarlo算法蒙特·卡羅方法（MonteCarlomethod），也稱統(tǒng)計(jì)模擬方法，是二十世紀(jì)四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明，而被提出的一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類非常重要的數(shù)值計(jì)算方法。是指使用隨機(jī)數(shù)（或更常見(jiàn)的偽隨機(jī)數(shù)）來(lái)解決很多計(jì)算問(wèn)題的方法。與它對(duì)應(yīng)的是確定性算法。MonteCarlo算法提出：蒙特卡羅方法于20世紀(jì)40年代美國(guó)在第二次世界大戰(zhàn)中研制原子彈的“曼哈頓計(jì)劃”計(jì)劃的成員S.M.烏拉姆和J.馮·諾伊曼首先提出。數(shù)學(xué)家馮·諾伊曼用馳名世界的賭城—摩納哥