五子棋演算法探討

06-01

五子棋演算法探討ofengofeng | 更新時間:2008-09-25 18:46:58 | 點擊數:89

標籤：
五子棋
演算法

五子棋演算法探討

近來隨著計算機的快速發展，各種棋類遊戲被紛紛請進了電腦，使得那些喜愛下棋，又常常苦於沒有對手的棋迷們能隨時過足棋癮。而且這類軟體個個水平頗高，大有與人腦分庭抗禮之勢。其中戰勝過國際象棋世界冠軍-卡斯帕羅夫的「深藍」便是最具說服力的代表；其它像圍棋的「手淡」、象棋的「將族」等也以其優秀的人工智慧深受棋迷喜愛；而我們今天將向大家介紹的是五子棋的演算法。

當我們與電腦對戰時，您知道這些軟體是怎樣象人腦一樣進行思考的嗎？前不久我曾編寫過一個五子棋的遊戲，在這裡就以此為例和大家一起探討探討。

總的來說（我們假定您熟悉五子棋的基本規則），要讓電腦知道該在哪一點下子，就要根據盤面的形勢，為每一可能落子的點計算其重要程度，也就是當這子落下後會形成什麼棋型（如：「沖四」、「活三」等），然後通覽全盤選出最重要的一點，這便是最基本的演算法。當然，僅靠當前盤面進行判斷是遠遠不夠的，這樣下棋很容易掉進玩家設下的陷阱，因為它沒有考慮以後的變化。所以在此基礎上我們加入遞歸調用，即：在電腦中預測出今後幾步的各種走法，以便作出最佳選擇，這也是我們下棋時常說的「想了幾步」。如此一來您的程序便具有一定的水平了。什麼？不信！過來試試吧！

總體思路弄清之後，下面進行具體討論：

一：數據結構

先來看看數據結構，我們需要哪些變數？

首先得為整個棋盤建立一張表格用以記錄棋子信息，我們使用一個15×15的二維數組 Table[15][15] (15×15是五子棋棋盤的大小)，數組的每一個元素對應棋盤上的一個交叉點，用『0』表示空位、『1』代表己方的子、『2』代表對方的子；這張表也是今後分析的基礎。

在此之後還要為電腦和玩家雙方各建立一張棋型表Computer[15][15][4]和Player[15][15][4]，用來存放棋型數據，就是剛才所說的重要程度，比如用『20』代表「沖四」的點，用『15』代表「活三」的點，那麼在計算重要性時，就可以根據20>15得出前者比後者重要，下子時電腦便會自動選擇「沖四」的點。那為什麼棋型表要使用三維數組呢？因為棋盤上的每一個點都可以與橫、豎、左斜、右斜四個方向的棋子構成不同的棋型，所以一個點總共有4個記錄；這樣做的另一個好處是可以輕易判斷出複合棋型，例如：如果同一點上有2個『15』就是雙三、有一個『15』和一個『20』就是四三。

怎麼樣！3個數組構成了程序的基本數據骨架，今後只要再加入一些輔助變數便可以應付自如了。應該不會太難吧？OK！有了這麼多有用的數據，我們就可以深入到程序的流程中去了。

二：程序流程

我們主要討論五子棋的核心演算法，即：人工智慧部分，而其他像圖形顯示、鍵盤滑鼠控制等，因較為簡單，所以就不作過多介紹了。

首先，請仔細閱讀圖1：

我們看到本程序由六個基本功能模塊構成，各模塊的詳細分析如下：

（1）初始化：首先，建立盤面數組Table[15][15]、對戰雙方的棋型表Computer[15][15][4]和Player[15][15][4]並將它們清零以備使用；然後初始化顯示器、鍵盤、鼠等輸入輸出設備並在屏幕上畫出棋盤。

（2）主循環控制模塊：控制下棋順序，當輪到某方下子時，負責將程序轉到相應的模塊中去，主要擔當一個調度者的角色。

（3）玩家下子：當輪到玩家下時，您通過鍵盤或滑鼠在棋盤上落子，程序會根據該點的位置，在Table[15][15]數組的相應地方記錄『2』，以表明該子是玩家下的。

（4）盤面分析填寫棋型表：本程序核心模塊之一，人工智慧演算法的根本依據！其具體實現方法如下：您在下五子棋時，一定會先根據棋盤上的情況，找出當前最重要的一些點位，如「活三」、「沖四」等；然後再在其中選擇落子點。但是，電腦不會像人一樣分析問題，要讓它知道哪是「活三」、哪是「沖四」，就得在棋盤上逐點計算，一步一步的教它。

先來分析己方的棋型，我們從棋盤左上角出發，向右逐行搜索，當遇到一個空白點時，以它為中心向左挨個查找，如果遇到己方的子則記錄然後繼續，如果遇到對方的子、空白點或邊界就停止查找。左邊完成後再向右進行同樣的操作；最後把左右兩邊的記錄合併起來，得到的數據就是該點橫向上的棋型，然後把棋型的編號填入到Computer[x][y][n]中就行了（x、y代表坐標，n=0、1、2、3分別代表橫、豎、左斜、右斜四個方向）。而其他三個方向的棋型也可用同樣的方法得到，當搜索完整張棋盤後，己方棋型表也就填寫完畢了。然後再用同樣的方法填寫對方棋型表。

注意：所有棋型的編號都要事先定義好，越重要的號數越大！

OK! 怎麼樣？有點累了吧？不過千萬別泄氣！因為好戲還在後頭。

Let"s go！

（5）電腦下子：有了上面填寫的兩張棋型表，現在要作的就是讓電腦知道在哪一點下子了。其中最簡單的計算方法，就是遍歷棋型表 Computer[15][15][4]和Player[15][15][4]找出其中數值最大的一點，在該點下子即可。但這種演算法的弱點非常明顯，只顧眼前利益，不能顧全大局，這就和許多五子棋初學者一樣犯了「目光短淺」的毛病。

要解決這個問題，我們引入『今後幾步預測法』，具體方法是這樣的：首先，讓電腦分析一個可能的點，如果在這兒下子將會形成對手不得不防守的棋型（例如：『沖四』、『活三』）；那麼下一步對手就會照您的思路下子來防守您，如此一來便完成了第一步的預測。這時再調用模塊4對預測後的棋進行盤面分析，如果出現了『四三』、『雙三』或『雙四』等制勝點，那麼己方就可以獲勝了（當然對黑棋而言『雙三』、『雙四』是禁手，另當別論）；否則照同樣的方法向下分析，就可預測出第二步、第三步……

等一等，要是盤面上沒有對手必須防的棋型，哪該怎麼辦呢？進攻不成的話就得考慮防守了，將自己和對手調換一下位置，然後用上面的方法來預測對手的棋，這樣既可以防住對手巧妙的攻擊，又能侍機發動反擊，何樂而不為呢！

但是必須告訴大家的是：預測法的運算量相當之大，據我的經驗，用Pentium-100預測3步的走法平均需要15秒以上時間，所以建議預測量在5步以內。可別小瞧了這5步，有時它甚至會走出讓您拍手叫絕的妙著呢！

（6）勝負判斷：務須多言，某方形成五子連即獲勝；若黑棋走出『雙三』、『雙四』或長連即以禁手判負。

到現在為止，整個五子棋軟體就基本完成了，其水平大約在中級上下。當然，這種演算法並不是最好的，但我相信它的基本思路是正確的。

本文屬網路搜集而來緊供參考~~~~~~~~~~