任何一種棋類遊戲其關鍵是對目前棋局是否有正确的評分,評分越準确則電腦的AI越高。五子棋遊戲也是如此，但在打分之前，我們先掃描
整個棋盤，把每個空位從八個方向上的棋型填入數組gStyle(2, 15, 15, 8, 2)，其中第一個下标為1時表示黑棋，為2時表示白棋，第二和第三
個下标表示(x,y)，第四個下标表示8個方向，最後一個下标為1時表示棋子數，為2時表示空格數，如：
gStyle(1,2,2,1,1)=3表示與坐标(2,2)在第1個方向上相鄰的黑棋棋子數為3
gstyle(1,2,2,1,2)=4表示與坐标(2,2)在第1個方向上的最近的空格數為4
在定義方向時，也應該注意一定的技巧，表示兩個相反的方向的數應該差4，在程式中我是這樣定義的：
Const DIR_UP = 1
Const DIR_UPRIGHT = 2
Const DIR_RIGHT = 3
Const DIR_RIGHTDOWN = 4
Const DIR_DOWN = 5
Const DIR_DOWNLEFT = 6
Const DIR_LEFT = 7
Const DIR_LEFTUP = 8
這樣我們前四個方向可以通過加四得到另一個方向的值。如果你還是不太明白，請看下面的圖：
---------
---------
---oo----
-ox*xx---
---------
---------
圖中的*點從标為(4,4),（打*的位置是空位）,則:
gStyle(2,4,4,1,1)=1在(4,4)點相鄰的上方白棋數為1
gStyle(2,4,4,1,2)=2在(4,4)點的上方距上方白棋最近的空格數為2
gStyle(1,4,4,3,1)=2在(4,4)點相鄰的右方黑棋數為2
gStyle(1,4,4,3,2)=1在(4,4)點的右方距右方黑棋最近的空格數為3
一旦把所有空點的棋型值填完，我們很容易地得出黑棋水準方向上點(4,4)的價值，由一個沖1（我把有界的棋稱為沖）和活2（兩邊無界的
棋稱為活）組成的。對于而白棋在垂直方向上點(4,4)的價值是一個活1，而在/方向也是活1是以，隻要我們把該點的對于黑棋和白棋的價值算出
來，然後我們就取棋盤上各個空點的這兩個值的和的最大一點作為下棋的點。然而，對各種棋型應該取什麼值呢？我們可以先作如下假設：
Fn 表示先手n個棋子的活棋型，如：F4表示先手活四
Fn'表示先手n個棋子的沖棋型，如：F4'表示先手沖四
Ln 表示後手n個棋子的活棋型，如：L3表示後手活三
Ln'表示後手n個棋子的沖棋型，如：L3'表示後手沖三
.
.
.
根據在一行中的棋型分析，得到如下關系：
L1'<=F1'<L2'<=F2'<=L1<F1<L2<F2<L3'<=F3'<L4'<F4'=F4
從這個關系包含了進攻和防守的關系（當然，這個關系是由我定的，你可以自己定義這些關系）。對這些關系再進一步細化，如在一個可下
棋的點，其四個方向上都有活三，也比不上一個沖四，是以我們可以又得到4*F3<L4'這個關系，同樣，我們還可以得到其它的關系，如：4*F2<L3、4*L3<F3...，這些的關系由于你的定法和我的定法制可能不一樣，這樣計算機的AI也就不一樣，最後我們把分值最小的L1'值定為1，則我們就得
到了下面各種棋型的分值，由C語言表示為：
F[2][5]={{0,2,5,50,16000},{0,10,30,750,16000}};
L[2][5]={{0,1,5,50,3750},{0,10,30,150,4000}};
F數組表示先手，第一個下标為0時表示沖型，第二個下标表示棋子數，則F2'對應F[0][2]L數組表示後手，第一個下标為0時表示沖型，第二
個下标表示棋子數，則L2對應F[1][2]Ok，棋型的分值關系确定好了以後，我們把每一個可下點的四個方向的棋型值相加（包括先手和後手的分
值），最後選擇一個最大值，并把這一點作為計算機要下的點就OK了:)。
後話：
1、得到最大值也許不止一個點，但在我的程式中隻選擇第一個最大點，當然你可以用于個随機數來決定
選擇那一個最大值點，也可以對這些最大值點再作進一步的分析。
2、在這個算法中我隻考慮了周圍有棋子的點，而其它點我沒有考慮。
3、可以再更進一步，用這個算法來預測以後的幾步棋，再選擇預測值最好的一步，這樣電腦的AI就更高了
4、這個算法沒有考慮黑棋的禁手（雙3、雙四和多于五子的連棋）。因為在平時我下的五子棋是沒有這些
禁手的。
五子棋算法探讨
近來随着計算機的快速發展，各種棋類遊戲被紛紛請進了電腦，使得那些喜愛下棋，又常常苦于沒有對手的棋迷們能随時過足棋瘾。而且這類軟體個個水準頗高，大有與人腦分庭抗禮之勢。其中戰勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍”便是最具說服力的代表；其它像圍棋的“手淡”、象棋的“将族”等也以其優秀的人工智能深受棋迷喜愛；而我們今天将向大家介紹的是五子棋的算法。
當我們與電腦對戰時，您知道這些軟體是怎樣象人腦一樣進行思考的嗎？前不久我曾編寫過一個五子棋的遊戲，在這裡就以此為例和大家一起探讨探讨。
總的來說（我們假定您熟悉五子棋的基本規則），要讓電腦知道該在哪一點下子，就要根據盤面的形勢，為每一可能落子的點計算其重要程度，也就是當這子落下後會形成什麼棋型（如：“沖四”、“活三”等），然後通覽全盤選出最重要的一點，這便是最基本的算法。當然，僅靠目前盤面進行判斷是遠遠不夠的，這樣下棋很容易掉進玩家設下的陷阱，因為它沒有考慮以後的變化。是以在此基礎上我們加入遞歸調用，即：在電腦中預測出今後幾步的各種走法，以便作出最佳選擇，這也是我們下棋時常說的“想了幾步”。如此一來您的程式便具有一定的水準了。什麼？不信！過來試試吧！
總體思路弄清之後，下面進行具體讨論：
一：資料結構
先來看看資料結構，我們需要哪些變量？
首先得為整個棋盤建立一張表格用以記錄棋子資訊，我們使用一個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）勝負判斷：務須多言，某方形成五子連即獲勝；若黑棋走出‘雙三’、‘雙四’或長連即以禁手判負。
到現在為止，整個五子棋軟體就基本完成了，其水準大約在中級上下。當然，這種算法并不是最好的，但我相信它的基本思路是正确的。如果您有什麼問題或好的想法，歡迎給我發E-mail: [email protected]，我期待着您的見解。
汪疆
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=3284
<script type="text/javascript">function StorePage(){d=document;t=d.selection?(d.selection.type!='None'?d.selection.createRange().text:''):(d.getSelection?d.getSelection():'');void(keyit=window.open('http://www.365key.com/storeit.aspx?t='+escape(d.title)+'&u='+escape(d.location.href)+'&c='+escape(t),'keyit','scrollbars=no,width=475,height=575,left=75,top=20,status=no,resizable=yes'));keyit.focus();}</script>
五子棋禁手判定算法 禁手的判定較為複雜，設計一個判斷禁手的算法既要分析構成它的棋型又要找到合适的搜尋方法。 首先分析棋型。 先考慮構成長連禁手的棋型，構成長連的棋型較簡單，可歸納為一種，即相連後形成六子或更多相連。一旦發現産生此棋型，即判為長連禁手。 再考慮構成四四禁手、三三禁手的棋型。要判斷下某一子是否構成四四禁手（或三三禁手），隻需判斷下這一子後是否産生兩個或兩個以上的沖四或活四（或活三）即可。是以歸結起來，要正确判斷四四禁手、三三禁手就是要正确判斷沖四、活四和活三。 考慮沖四、活四和活三的定義。沖四是隻有一個點可以成五的四，這裡我們将那個點稱為關鍵點。同樣，構成活四的有兩個關鍵點，構成活三的有一個關鍵點。如圖 11 ， a,b 兩點是其構成活四的關鍵點，又如圖 12 ， a 點是其構成活三的關鍵點。
| | |
以下是對各棋型和關鍵點的分析。 1 、活四： 歸結起來構成活四的隻有一種棋型 , 如圖 13
| |
這種棋型真正構成活四的條件是左右兩空位（即 a,b 點）必須是黑棋可下的點，也就是在 a,b 點下黑子後都不會構成禁手。 2 、沖四： 形成沖四有兩種棋型，如圖 14 和圖 15
| | |
這兩種棋型真正構成沖四的條件是中間的空位（即 a 點）必須是黑棋可下的點，也就是在 a 點下子後不會構成禁手。 3 、活三： 形成活三有兩種棋型，如圖 16 和圖 17
| | |
其中， a 點是關鍵點， b,c 點可以是邊界、無子或白色棋子，但不能是黑色棋子。 這兩種棋型真正構成活三的條件是 a 點必須是黑棋可下的點，也就是在 a 點下子後不會構成禁手， m,n 兩點不用管是否構成禁手，因為當 a 點放入黑子後，不管在 m 點還是 n 點放黑子，就會形成五連，即獲勝，不構成禁手。 是以我們要判斷一種棋型是否構成沖四、活四或活三，需要在已判斷它是可能的沖四、活四或活三的棋型的基礎上判斷它的關鍵點是否可落黑色棋子，也就是判斷關鍵點是否不會構成新的禁手點，這一步在程式中可以用遞歸實作。 棋型分析完成，我們就要據此考慮選擇合适的算法。 基于禁手分析所需的精确度，我們在棋盤盤面搜尋時，需要記錄與待判斷點相鄰的連續黑色棋子數，并記錄之後的連續空子數，并記錄再之後的連續黑子數，和再之後的連續空子數，以及再之後的連續黑子數。是以可以說搜尋的深度要達到 5 層。 在判斷關鍵點的可下性時，選用遞歸的方法來判斷其是否不是禁手點。 于是最後我們可以得出禁手判定算法的思路。 第一步：将待判斷點放入黑棋子； 第二步：搜尋待判斷點周邊棋盤； 第三步：還原棋盤； 第四步：利用搜尋結果依次對各方向進行分析，判斷黑棋放入後所産生的棋型是否形成長連或形成可能構成活四、沖四、活三的棋型。若形成長連，判定為禁手，傳回長連禁手辨別。若形成可能是活四、沖四、活三的棋型，判斷關鍵點是否可下，若不可下，該棋型統計數加1，反之，則對下一個方向進行判斷，直到各個方向分析結束。 第五步：若活四、沖四棋型的統計數大于１，傳回四四禁手辨別，若活三棋型的統計數大于１，傳回三三禁手辨別。其餘情況傳回非禁手辨別。 源代碼:
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=822873