人工智慧之实作研究应用於五子棋游戏

1、人工智慧之實作研究應用於五子棋遊戲一、摘要人工智慧的研究，一直都是計算機科學方面的重點項目人工智慧(AI)是電腦科學中涉及設計智慧電腦系統的一個分支，這些系統呈現出與人類的智慧行為如理解語言、學習、推理和解決問題等有關的特性。許多人相信，透過對有關程式操作的研究，能夠深人地了解人腦機理的本質。自從五十年代中期開始對人工智慧進行研究以來，一些人工智慧研究工作者已經創造出許多保障這些智慧行為的程式設計技術、程式撰寫技術以及用於描述它們的計算上的概念。因此在這次的專題研究，就選定人工智慧的這個主題來進行。而人工智慧的研究課題包羅萬象，涵蓋成面十分廣泛，而這次選定的是最常為人所接觸的五子棋遊戲，希望藉

2、此較簡易的主題來對人工智慧的理論加以論證，並發展出一個實際可運作的遊戲程式。二、序言相信不少人玩過井字遊戲，可是您知道井字遊戲的排列組合有多少組嗎，也就遊戲的複雜度，答案是組，計算方式為：此遊戲共有九格，每格有、及無三種狀態，故，不到兩萬種，所以以電腦來加以計算，很快就可以得到答案，因此井字遊戲的難度不高，一般人玩一兩次就會厭煩了。但是五其他遊戲呢？就不相同了以西洋棋為例他的遊戲複雜度，是以兆為單位計算的，所以使用電腦來加以計算會消耗非常多的時間，但一個遊戲不能讓對手等太久，否則遊戲將失去趣味性，因此電腦在計算棋步時，必須在時間與最佳解中取得平衡，換句話說就是讓電腦在最短的時間內考慮最多的步數

3、，取得相對性的最佳解，是一個成功的人工智慧遊戲最大的挑戰。這次的研究內容，在於討論如何使電腦具有與人類下五子棋的能力，其中包含了五子棋程式的基本架構，-資料搜尋法，以及審局函數，和如何增進程式的智慧。三、五子棋論我想大多數的中國人都玩過五子棋吧！規則簡單我把它將其大致說明如下：在棋盤上將五子連成一線的一方為得勝方。雖然日本人定出新的規則，如三三禁負著、四四禁負著等，但此次並不採用，而以大多數人習慣的方式（無禁負著的玩法），並且依照這個玩法來發展程式。五子棋的一般規則很簡單。兩個人玩，可以使用和圍棋一樣的棋子，一個人下黑子，另一個人下白子。在日本規則和國際規則中，對於誰黑誰白各有一套複雜的決定方

4、法，不過在這個程式中則是由使用者自行決定。棋盤則是採用十五路棋盤，和圍棋不同。黑白雙方輪流下子，一直到其中一方有五個棋子在橫、直或斜的方向連成一線，就算是贏了，棋局也到此結束。雖然五子棋簡單，但還是存在不少的技巧和特殊走法，以下就來說明五子棋中比較常使用到的特殊名稱。同時簡單說明日規（日本的規則）和普規（一般的規則）的不同天元：第一步習慣上由黑子下在棋盤的正中央。正中央這一點，就稱為天元。如果第一步下在棋盤邊緣的話，那麼可以攻擊的方向就會受到限制，對自已是不利的。在日規中，就硬性規定黑方的第一步一定要下在天元。星位：棋盤上距離邊緣各四格的地方，也就是（4,4）、（4,D）、（D,4）、（D,D

5、）四個點。在天元和星位上都會有一個小黑點方便辦認。連五或長連：在橫線、直線或是斜線上，有五子連成一線了。不管其他的棋子如何，都是由下出連五的一方獲勝，棋局也到此結束。如果連成一線的棋子超過五個，就稱為長連。在日規中黑子的長連是禁負著，黑方下出長連算輸。活四、活三：有幾個棋子連成一線了，但是還沒有連成五子。如果這幾個棋子兩端都沒有受到阻擋，就稱為活棋，因為它們可以輕易地再多連一子。通常下出活四就可以算是贏了，因為無論後來怎麼阻擋，只要在另一端再下一子就會變成連五了。所以當對手下出活三的時候就要加以阻擋，以免發展成活四。然而有的時候活三不一定能發展成活四，這個時候就不用急著阻擋。死四、死三：有幾個

6、棋子連成一線了，還沒連成五子，但是在連線的一端被對手的棋子擋住。當對手下出死四的時候，只要馬上阻擋連線的另一邊，對手就無法下出連五了。跳四、跳三：有幾個棋子連成一線，但是中間隔了一個棋子的位置。把連五以後中間的棋子拿掉一個，剩下的兩段合起來就叫做跳四。同樣的，把活四或死四中間的棋子拿掉一個，剩下的就是跳三。很明顯地，跳四再下一子就可以連五了，所以唯一的方法就只有下在中間的隔子來防守。而跳三就要看它會形成活四還是死四，來決定要不要馬上防守，而且也不一定要下在隔子。如果跳子的數目大於四個，就稱為長跳。由於在日規中黑方是不能下出長連的，所以黑子的長跳就變得沒有攻擊力，不過在普規中還是要加以防守。三三

7、：下一子後同時造成兩個方向的活三。這個時候無論對手如何阻擋，另一個活三都可以發展成活四而贏棋。除非對手已經下出死四或活四，可以先下成連五。在日規中黑方三三是禁負著，如果黑方下出三三就算輸。四四：類似三三，同時造成兩個死四或是活四。這個時候死四或是活四已經不重要，因為其中一個一定可以發展成連五了。在日規中黑方四四也是禁負著。四三：下一子同時造成活四和活三，或是死四和活三。跟三三和四四一樣，下出這種棋形就贏定了。在日規中黑方只有四三不是禁負著，可以說黑方只能利用下出四三而贏棋。禁負著：在日規中，黑方下出長連、三三、四四是不被允許的，要直接算輸。普規沒有禁負著，愛怎麼下就怎麼下。因為根據統計的結果，

8、五子棋先下的一方勝率大約是0.6，也就是十局中大約會贏六局，這違反了比賽的公平精神。於是日本人定出了一些規則限制先下的黑方，不能下出這些特殊的棋形。所以只有黑方有禁負著的限制，而白方沒有。不過即使有這些禁負著，先下的一方勝率還是略高於後下的一方，於是又規定在下完一局以後交換黑白方，也就是交換先後下的順序。四、研究理論人工智慧，就是研究如何製造出智慧機器或智慧系統，來模擬人類智慧活動的能力，以實現人造智慧的一門科學。人類的智慧在解決問題的時候表現出來，因此人工智慧也就是在模擬人類解決問題的能力。而最常見的方法之一，就是驗証所有可能答案的正確性。如果使用這種方法，那麼第一步就是先要找出所有可能的答

9、案，再來一個一個地檢查它們的正確性，於是有了搜尋的觀念。（一）基本搜尋依照搜尋的目的不同，發展出不同的搜尋方法。常見的搜尋目的有三種：尋找路徑，尋找最佳路徑，和競局。在這裡所要研究的就是競局。由競局所發展出來的搜尋方法很多，包括了極大極小搜尋法（mini-max Search）、修剪搜尋法（alpha-beta pruning）、漸深搜尋法（tic pruning），和經驗式修剪搜尋法（heuristic pruning）等等。這一類的搜尋法在棋戲中相當普遍，尤其是西洋跳棋和西洋象棋。（二）對局樹何為對局樹？舉格例子來說，假設輪到我方著手，我們會考慮走哪一步會比較有利，而我們走了這一步之後，對

10、方有幾種走法，當對方走了某一步之後我方又該如何對應等，如將這一連串的對一過程繪制成圖表，則我們可稱此圖表為對局樹，而對局樹是十分重要的，由於在棋戲中是不可能將所有的變化都搜尋一遍的，因為假設一步棋有10種走法，而雙方各要走10步棋才能分出勝負的話，那麼就一共有10的20次方種狀態需要搜尋。這樣的天文數字根本就不可能完成。於是在競局的搜尋法中，如何修剪所要搜尋的樹，來減少搜尋的量，成為最重要的問題。一般的方法，就是只考慮下幾步棋，再加上大略的棋盤評估公式，使局面保持優勢來繼續。由於人類棋手在下棋時大多也是採取這種思考模式，所以搜尋的深度和棋盤評估公式的好壞，便直接影響到程式在與人類對奕時的棋力。

11、（三）極大極小搜尋下棋時是一人走一步的，雙方都想要使自已的局面保持優勢，同時使對方處於劣勢。於是我們往往要考慮對手的應對走法，來決定下一步要怎麼走。同樣地，對手也會預測我們的走法，不讓你稱心如意。極大極小法就是假設敵我雙方都選擇最佳走法的一種有限深度、深度優先的搜尋方法。它從根節點出發，呼叫走法產生函式產生可能走法，向下巡行到給定深度後，在葉節點處使用評估函數判斷局勢好壞。自已的走法選擇得到最大分數的走法，反之對手的目標則是選取使評估函數得到最小值的走法。因此程式在不同層中，交互使用取極大值和極小值的走法。這也就是這個名稱的由來。在上圖只搜尋一層的時候，應該選取對自已最有利的走法，也就是中間的

12、節點，可以得到9分。但是在搜尋兩層的時候，發現中間的節點竟然給敵人可趁之機，使我們反而只得到-3分。於是我們應該選擇左邊的節點，既使在最差的情況下，還是可以得到1分。使用極大極小搜尋法，在某一個深度內的所有變化都要一個一個地去檢查。然而真的有這個必要嗎？如果說有一串走法，無論如何都不能再好了，我們可以利用分支限制（branch-and-bound）的技巧，來增加極大極小搜尋的效率。也就是說，在搜尋的過程中，一旦發現目前所看的這個走法，已經比已知的走法還差的時候，就可以提早放棄它。輸了就是輸了，沒有必要去找出有幾種輸法。這是因為敵我雙方輪流下子，雙方的立場不同，自已盡力使評估值拉高，而敵方則是拼

13、命使評估值降低。當發現無論如何都不能改變對方目前的最佳值時，當然就可以提早放棄。於是出現了-搜尋法。（三）-搜尋法如果我們使用兩個參數和，分別記錄在取極大值節點和取極小值節點的數值，使越來越大而越來越小。當我們在取極小值節點發現了一個比還小的值，就不用往下搜尋了。同理在取極大值節點，如果發現了一個比還大的值，也一樣不用再往下搜尋。拿上面那個例子，先搜尋完左邊節點所有子節點（取極小）後，得到=1。再搜尋中間節點的子節點，第一個就發現-3，比=1小，發生截斷，於是剩下的兩個子節點就不用搜尋了。因為中間節點無論如何都不會比-3大了，但是我們已經知道有一個1的節點，那麼再搜尋比-3還小的數值就變得沒有

14、意義。趕快換右邊的節點，發現它的第一個節點-5更小，所以也跳過其他的子節點。結果我們只評估了5種局面，就找出了這個遊戲樹中的最佳走法，節省了將近一半的時間。利用到底可以截斷多少個節點呢？1975年，Knuth和Moore針對某些較容易分析的樹得到了一些分析結果。就高度為d，每個節點都有b個子節點的均勻樹來說，最佳情形只需搜尋個節點。如果在一棵隨意均勻樹上，當d 趨近時，預期要檢驗的葉節點數目上限則為。很明顯地，-搜尋法的執行效率和走法的排列順序有很大的關係。把好的走法排在前面，就可以儘早發生截斷，省掉對壞走法的無謂搜尋。於是我們可以漸漸地增加搜尋深度，先將上一次搜尋的結果排序了以後，再做下一個

15、深度的搜尋。所以搜尋深度就從1、2、3、一直進行到設定的深度，或是設定的時間為止。這就是漸深法，或是疊代-搜尋法。乍看之下，這個方法似乎浪費大部分時間在較淺層分析上。真的是這樣嗎？假設分析時間大都使用在靜態評估上，對一個高度d ，分支數為b的均勻樹來說，一共有b的d次方個節點需要做靜態評估。而前d-1層全部所需的評估次數為：所以第d 層的節點數和其餘各層的節點總和的比為：也就是說如果b=21，那麼d 層以前各層所需的評估數不過是第d 層本身所需的評估數的二十分之一。多花二十分之一的時間，就可以提早發生截斷，可能節省更多時間，這種交易何樂而不為？而且漸深法在搜尋完一個深度後可以先檢查所花費的時間

16、，以免超過時間而輸棋。這對有時間限制的棋局是一件很重要的事。另外，從上面的推導，我們也可以知道多搜尋一個深度是很費力的。由於-搜尋法的搜尋深度有限，在深度以下的變化情形都被我們忽略了。如果這個時候的局勢對輸贏很重要，程式就會出現錯誤判斷。例如敵方再兩步就可以下出四三，而自已卻去下活三想攻擊，以為對方會來防守我，那麼就非輸不可了。然而多搜尋一個深度並不是一個很好的辦法，於是這時候就需要判斷局勢是不是已經穩定了。如果局勢不穩定，雙方都在交互攻擊的時候，就有必要從這個局勢下去多看幾步，直到局勢穩定為止。如果局勢是穩定的，就可以確定不會遭受太大的反擊，可以放心地停止往下搜尋了。然而即使電腦搜尋的深度遠

17、遠超過人類，雖然可以輕易地打敗絕大多數的我們，但還是不能打敗人類的冠軍。這是為什麼呢？我們在下棋的時候，顯然不是只有靠“往前看幾步“而已。下棋的高手們，似乎把重點放在擬定中長期的作戰策略，只對幾種重要走法加以分析，再修正之前的計畫。相對於電腦以走法為重點，人類的思考方法則是以策略為主。Wilkins在1980年提出的Paradise系統，就是先詳細分析目前局勢，然後產生可能的計畫。如果在計畫進行的時候會受到阻礙，就修正計畫試著去掉阻礙。如果無法去掉阻礙，就嚐試另一種計畫。於是程式就在計畫的產生、修改之間搜尋。再加上高階概念的運用，使得計畫可以更周詳，而且也可以很容易地維護和增修資料庫。結果Pa

18、radise2的棋力竟然可以勝過西洋棋的A級棋手。那麼為什麼向前搜尋法依然是主流吧？因為這種作法最大的缺點，就是在於知識庫太難建立了。要把抽象的知識清楚地完全表達出來，使程式依據這些規則來分析棋局和搜尋棋步，非得擁有豐富的經驗不可。另外要如何決定知識的抽象程度，和如何表達知識，都是難題。所以在這次的專題中，將使用-修剪搜尋法，並且配合漸深搜尋來控制搜尋時間。五、實作首先利用BCB製作出程式外觀和功能表。使用者可以利用【選項】中的【黑棋】、【白棋】來設定由人類或電腦來玩某一方，預設值都是由人類來玩。【檔案】【重新開始】會用目前設定的黑白方來重新開始一局。如果已經有一局正在進行中了，會出現一個對話

19、框詢問是不是要放棄這一局。再來就是設計一個五子棋的物件。這個物件又可以分成演算法物件、節點物件和棋盤物件。演算法物件的內容主要就是搜尋法和評估函式，並且提供和主程式連接的介面。搜尋的過程會用到的節點結構用節點物件來處理。而棋盤物件的主要功能是在評估目前的局面，並且用來記錄棋局的過程。審局函式每次從棋盤物件取得連續的7個棋子，並且依照這7個棋子的排列組合，來判斷它們所代表的棋型。同時判斷整個局面的情勢，來計算目前局面的分數，估為搜尋時的依據。各個棋型的分數是實驗得來的。先定下基本的強弱和攻擊力、防守力，再用這個分數和人類對局，看電腦的表現來調整對應的分數，直到電腦可以做出正確的反應為止。不過這種

20、做法和對局人類的棋力有很大的關係，可以依照每次執行的結果統計起來慢慢調整程式中分數的設定。本來程式在搜尋時無法處理Message，結果看起來就像是當掉了一樣。於是又使用了一個Thread物件，使用Windows提供的MultiThread功能來在另一個執行緒進行搜尋。這樣程式在搜尋的時候就可以同時處理其他的訊息，不會看起來像是當掉了。六、討論及應用本專題之五子棋的程式受限於搜尋的深度，這個程式的棋力大約只有中等的程度。C+是物件導向的語言，於是這個程式使用了大量的物件。使用物件的好處是程式變得更結構化了，而且在除錯和修改的時候很方便。只要維持介面不變，物件的內部結構無論怎麼更改，都不會影響到程式的其他部分。然而大量使用物件的結果，就是使程式的效率降低。在一般的情形下，搜尋一步大約需要1秒，搜尋兩步大約需要5秒，搜尋三步時就需要1分鐘以上才能完成了，這實在是令人無法忍受。除了-修剪和漸深法之外，在程式中也使用了許多其他的技巧來加速搜尋和評估，例如評估函數利用查表法得到棋型的分數，以及簡化棋盤的存取等等。但是速度還是沒有得到太大的改進。於是只好限制使用者可以設定的搜尋深度，這是最大的缺點。向前搜尋法對棋力改進似乎有一定的極限，或許利用概念式的做法會讓程式變得更聰明。到於知識庫，應該有辦法讓電腦在自行對局的