五子棋算法探討

1、近來隨著計算機的快速發(fā)展，各種棋類游戲被紛紛請進(jìn)了電腦，使得那些喜愛下棋，又常常苦于沒有對手的棋迷們能隨時過足棋癮。而且這類軟件個個水平頗高，大有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍(lán)”便是最具說服力的代表；其它像圍棋的“手淡”、象棋的“將族”等也以其優(yōu)秀的人工智能深受棋迷喜愛；而我們今天將向大家介紹的是五子棋的算法。當(dāng)我們與電腦對戰(zhàn)時，您知道這些軟件是怎樣象人腦一樣進(jìn)行思考的嗎？前不久我曾編寫過一個五子棋的游戲，在這里就以此為例和大家一起探討探討?？偟膩碚f（我們假定您熟悉五子棋的基本規(guī)則），要讓電腦知道該在哪一點下子，就要根據(jù)盤面的形勢，為每一可能落子的點計算其重

2、要程度，也就是當(dāng)這子落下后會形成什么棋型（如：“沖四”、“活三”等），然后通覽全盤選出最重要的一點，這便是最基本的算法。當(dāng)然，僅靠當(dāng)前盤面進(jìn)行判斷是遠(yuǎn)遠(yuǎn)不夠的，這樣下棋很容易掉進(jìn)玩家設(shè)下的陷阱，因為它沒有考慮以后的變化。所以在此基礎(chǔ)上我們加入遞歸調(diào)用，即：在電腦中預(yù)測出今后幾步的各種走法，以便作出最佳選擇，這也是我們下棋時常說的“想了幾步”。如此一來您的程序便具有一定的水平了。什么？不信！過來試試吧！ 總體思路弄清之后，下面進(jìn)行具體討論：一：數(shù)據(jù)結(jié)構(gòu)先來看看數(shù)據(jù)結(jié)構(gòu)，我們需要哪些變量？首先得為整個棋盤建立一張表格用以記錄棋子信息，我們使用一個15*15的二維數(shù)組 Table1515 (15*1

3、5是五子棋棋盤的大小)，數(shù)組的每一個元素對應(yīng)棋盤上的一個交叉點，用0表示空位、1代表己方的子、2代表對方的子；這張表也是今后分析的基礎(chǔ)。在此之后還要為電腦和玩家雙方各建立一張棋型表Computer15154和Player15154，用來存放棋型數(shù)據(jù)，就是剛才所說的重要程度，比如用20代表“沖四”的點，用15代表“活三”的點，那么在計算重要性時，就可以根據(jù)20>15得出前者比后者重要，下子時電腦便會自動選擇“沖四”的點。那為什么棋型表要使用三維數(shù)組呢？因為棋盤上的每一個點都可以與橫、豎、左斜、右斜四個方向的棋子構(gòu)成不同的棋型，所以一個點總共有4個記錄；這樣做的另一個好處是可以輕易判斷出復(fù)合

4、棋型，例如：如果同一點上有2個15就是雙三、有一個15和一個20就是四三。怎么樣！3個數(shù)組構(gòu)成了程序的基本數(shù)據(jù)骨架，今后只要再加入一些輔助變量便可以應(yīng)付自如了。應(yīng)該不會太難吧？OK！有了這么多有用的數(shù)據(jù)，我們就可以深入到程序的流程中去了。二：程序流程我們主要討論五子棋的核心算法，即：人工智能部分，而其他像圖形顯示、鍵盤鼠標(biāo)控制等，因較為簡單，所以就不作過多介紹了。我們看到本程序由六個基本功能模塊構(gòu)成，各模塊的詳細(xì)分析如下：（1）初始化：首先，建立盤面數(shù)組Table1515、對戰(zhàn)雙方的棋型表Computer15154和Player15154并將它們清零以備使用；然后初始化顯示器、鍵盤、鼠等輸入輸

5、出設(shè)備并在屏幕上畫出棋盤。（2）主循環(huán)控制模塊：控制下棋順序，當(dāng)輪到某方下子時，負(fù)責(zé)將程序轉(zhuǎn)到相應(yīng)的模塊中去，主要擔(dān)當(dāng)一個調(diào)度者的角色。（3）玩家下子：當(dāng)輪到玩家下時，您通過鍵盤或鼠標(biāo)在棋盤上落子，程序會根據(jù)該點的位置，在Table1515數(shù)組的相應(yīng)地方記錄2，以表明該子是玩家下的。（4）盤面分析填寫棋型表：本程序核心模塊之一，人工智能算法的根本依據(jù)！其具體實現(xiàn)方法如下：您在下五子棋時，一定會先根據(jù)棋盤上的情況，找出當(dāng)前最重要的一些點位，如“活三”、“沖四”等；然后再在其中選擇落子點。但是，電腦不會像人一樣分析問題，要讓它知道哪是“活三”、哪是“沖四”，就得在棋盤上逐點計算，一步一步的教它。先

6、來分析己方的棋型，我們從棋盤左上角出發(fā)，向右逐行搜索，當(dāng)遇到一個空白點時，以它為中心向左挨個查找，如果遇到己方的子則記錄然后繼續(xù)，如果遇到對方的子、空白點或邊界就停止查找。左邊完成后再向右進(jìn)行同樣的操作；最后把左右兩邊的記錄合并起來，得到的數(shù)據(jù)就是該點橫向上的棋型，然后把棋型的編號填入到Computerxyn中就行了（x、y代表坐標(biāo)，n=0、1、2、3分別代表橫、豎、左斜、右斜四個方向）。而其他三個方向的棋型也可用同樣的方法得到，當(dāng)搜索完整張棋盤后，己方棋型表也就填寫完畢了。然后再用同樣的方法填寫對方棋型表。注意：所有棋型的編號都要事先定義好，越重要的號數(shù)越大！OK! 怎么樣？有點累了吧？不過

7、千萬別泄氣！因為好戲還在后頭。Let's go?。?）電腦下子：有了上面填寫的兩張棋型表，現(xiàn)在要作的就是讓電腦知道在哪一點下子了。其中最簡單的計算方法，就是遍歷棋型表Computer15154和Player15154找出其中數(shù)值最大的一點，在該點下子即可。但這種算法的弱點非常明顯，只顧眼前利益，不能顧全大局，這就和許多五子棋初學(xué)者一樣犯了“目光短淺”的毛病。要解決這個問題，我們引入今后幾步預(yù)測法，具體方法是這樣的： 首先， 讓電腦分析一個可能的點，如果在這兒下子將會形成對手不得不防守的棋型（例如：沖四、活三）；那么下一步對手就會照您的思路下子來防守您，如此一來便完成了第一步的預(yù)測。這時再調(diào)用模塊4對預(yù)測后的棋進(jìn)行盤面分析，如果出現(xiàn)了四三、雙三或雙四等制勝點，那么己方就可以獲勝了（當(dāng)然對黑棋而言雙三、雙四是禁手，另當(dāng)別論）；否則照同樣的方法向下分析，就可預(yù)測出第二步、第三步等一等，要是盤面上沒有對手必須防的棋型，哪該怎么辦呢？進(jìn)攻不成的話就得考慮防守了，將自己和對手調(diào)換一下位置，然后用上面的方法來預(yù)測對手的棋，這樣既可以防住對手巧妙的攻擊，又能侍機發(fā)動反擊，何樂而不為呢！但是必須告訴大家的是：預(yù)測法的運算量相當(dāng)之大，據(jù)我的經(jīng)驗，用Pentium-100預(yù)測3步的走法平均需要15秒以上時間，所以建議預(yù)測量在5步以內(nèi)?？蓜e小瞧了這5步，有時它甚至