五子棋ai如何判斷棋型
五子棋ai如何判斷棋型
五子棋ai如何判斷棋型?下面學(xué)習(xí)啦小編給你介紹五子棋ai判斷棋型的方法，歡迎閱讀。
五子棋ai如何判斷棋型
任何一種棋類游戲其關(guān)鍵是對(duì)當(dāng)前棋局是否有正確的評(píng)分,評(píng)分越準(zhǔn)確則電腦的AI越高。五子棋游戲也是如此，但在打分之前，我們先掃描
整個(gè)棋盤，把每個(gè)空位從八個(gè)方向上的棋型填入數(shù)組gStyle(2, 15, 15, 8, 2)，其中第一個(gè)下標(biāo)為1時(shí)表示黑棋，為2時(shí)表示白棋，第二和第三
個(gè)下標(biāo)表示(x,y)，第四個(gè)下標(biāo)表示8個(gè)方向，最后一個(gè)下標(biāo)為1時(shí)表示棋子數(shù)，為2時(shí)表示空格數(shù)，如：
gStyle(1,2,2,1,1)=3表示與坐標(biāo)(2,2)在第1個(gè)方向上相鄰的黑棋棋子數(shù)為3
gstyle(1,2,2,1,2)=4表示與坐標(biāo)(2,2)在第1個(gè)方向上的最近的空格數(shù)為4
在定義方向時(shí)，也應(yīng)該注意一定的技巧，表示兩個(gè)相反的方向的數(shù)應(yīng)該差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
這樣我們前四個(gè)方向可以通過(guò)加四得到另一個(gè)方向的值。如果你還是不太明白，請(qǐng)看下面的圖：
---------
---------
---oo----
-ox*xx---
---------
---------
圖中的*點(diǎn)從標(biāo)為(4,4),(打*的位置是空位),則:
gStyle(2,4,4,1,1)=1在(4,4)點(diǎn)相鄰的上方白棋數(shù)為1
gStyle(2,4,4,1,2)=2在(4,4)點(diǎn)的上方距上方白棋最近的空格數(shù)為2
gStyle(1,4,4,3,1)=2在(4,4)點(diǎn)相鄰的右方黑棋數(shù)為2
gStyle(1,4,4,3,2)=1在(4,4)點(diǎn)的右方距右方黑棋最近的空格數(shù)為3
一旦把所有空點(diǎn)的棋型值填完，我們很容易地得出黑棋水平方向上點(diǎn)(4,4)的價(jià)值，由一個(gè)沖1(我把有界的棋稱為沖)和活2(兩邊無(wú)界的
棋稱為活)組成的。對(duì)于而白棋在垂直方向上點(diǎn)(4,4)的價(jià)值是一個(gè)活1，而在/方向也是活1所以，只要我們把該點(diǎn)的對(duì)于黑棋和白棋的價(jià)值算出
來(lái)，然后我們就取棋盤上各個(gè)空點(diǎn)的這兩個(gè)值的和的最大一點(diǎn)作為下棋的點(diǎn)。然而，對(duì)各種棋型應(yīng)該取什么值呢?我們可以先作如下假設(shè)：
Fn 表示先手n個(gè)棋子的活棋型，如：F4表示先手活四
Fn'表示先手n個(gè)棋子的沖棋型，如：F4'表示先手沖四
Ln 表示后手n個(gè)棋子的活棋型，如：L3表示后手活三
Ln'表示后手n個(gè)棋子的沖棋型，如：L3'表示后手沖三
根據(jù)在一行中的棋型分析，得到如下關(guān)系：
L1'<=F1'
從這個(gè)關(guān)系包含了進(jìn)攻和防守的關(guān)系(當(dāng)然，這個(gè)關(guān)系是由我定的，你可以自己定義這些關(guān)系)。對(duì)這些關(guān)系再進(jìn)一步細(xì)化，如在一個(gè)可下
棋的點(diǎn)，其四個(gè)方向上都有活三，也比不上一個(gè)沖四，所以我們可以又得到4*F3
到了下面各種棋型的分值，由C語(yǔ)言表示為：
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數(shù)組表示先手，第一個(gè)下標(biāo)為0時(shí)表示沖型，第二個(gè)下標(biāo)表示棋子數(shù)，則F2'對(duì)應(yīng)F[0][2]L數(shù)組表示后手，第一個(gè)下標(biāo)為0時(shí)表示沖型，第二
個(gè)下標(biāo)表示棋子數(shù)，則L2對(duì)應(yīng)F[1][2]Ok，棋型的分值關(guān)系確定好了以后，我們把每一個(gè)可下點(diǎn)的四個(gè)方向的棋型值相加(包括先手和后手的分
值)，最后選擇一個(gè)最大值，并把這一點(diǎn)作為計(jì)算機(jī)要下的點(diǎn)就OK了:)。
后話：
1、得到最大值也許不止一個(gè)點(diǎn)，但在我的程序中只選擇第一個(gè)最大點(diǎn)，當(dāng)然你可以用于個(gè)隨機(jī)數(shù)來(lái)決定
選擇那一個(gè)最大值點(diǎn)，也可以對(duì)這些最大值點(diǎn)再作進(jìn)一步的分析。
2、在這個(gè)算法中我只考慮了周圍有棋子的點(diǎn)，而其它點(diǎn)我沒(méi)有考慮。
3、可以再更進(jìn)一步，用這個(gè)算法來(lái)預(yù)測(cè)以后的幾步棋，再選擇預(yù)測(cè)值最好的一步，這樣電腦的AI就更高了
4、這個(gè)算法沒(méi)有考慮黑棋的禁手(雙3、雙四和多于五子的連棋)。因?yàn)樵谄綍r(shí)我下的五子棋是沒(méi)有這些
禁手的。
五子棋算法探討
近來(lái)隨著計(jì)算機(jī)的快速發(fā)展，各種棋類游戲被紛紛請(qǐng)進(jìn)了電腦，使得那些喜愛(ài)下棋，又常常苦于沒(méi)有對(duì)手的棋迷們能隨時(shí)過(guò)足棋癮。而且這類軟件個(gè)個(gè)水平頗高，大有與人腦分庭抗禮之勢(shì)。其中戰(zhàn)勝過(guò)國(guó)際象棋世界冠軍-卡斯帕羅夫的“深藍(lán)”便是最具說(shuō)服力的代表;其它像圍棋的“手淡”、象棋的“將族”等也以其優(yōu)秀的人工智能深受棋迷喜愛(ài);而我們今天將向大家介紹的是五子棋的算法。
當(dāng)我們與電腦對(duì)戰(zhàn)時(shí)，您知道這些軟件是怎樣象人腦一樣進(jìn)行思考的嗎?前不久我曾編寫過(guò)一個(gè)五子棋的游戲，在這里就以此為例和大家一起探討探討。
總的來(lái)說(shuō)(我們假定您熟悉五子棋的基本規(guī)則)，要讓電腦知道該在哪一點(diǎn)下子，就要根據(jù)盤面的形勢(shì)，為每一可能落子的點(diǎn)計(jì)算其重要程度，也就是當(dāng)這子落下后會(huì)形成什么棋型(如：“沖四”、“活三”等)，然后通覽全盤選出最重要的一點(diǎn)，這便是最基本的算法。當(dāng)然，僅靠當(dāng)前盤面進(jìn)行判斷是遠(yuǎn)遠(yuǎn)不夠的，這樣下棋很容易掉進(jìn)玩家設(shè)下的陷阱，因?yàn)樗鼪](méi)有考慮以后的變化。所以在此基礎(chǔ)上我們加入遞歸調(diào)用，即：在電腦中預(yù)測(cè)出今后幾步的各種走法，以便作出最佳選擇，這也是我們下棋時(shí)常說(shuō)的“想了幾步”。如此一來(lái)您的程序便具有一定的水平了。什么?不信!過(guò)來(lái)試試吧!
總體思路弄清之后，下面進(jìn)行具體討論：
一：數(shù)據(jù)結(jié)構(gòu)
先來(lái)看看數(shù)據(jù)結(jié)構(gòu)，我們需要哪些變量?
首先得為整個(gè)棋盤建立一張表格用以記錄棋子信息，我們使用一個(gè)15*15的二維數(shù)組 Table[15][15] (15*15是五子棋棋盤的大小)，數(shù)組的每一個(gè)元素對(duì)應(yīng)棋盤上的一個(gè)交叉點(diǎn)，用‘0’表示空位、‘1’代表己方的子、‘2’代表對(duì)方的子;這張表也是今后分析的基礎(chǔ)。
在此之后還要為電腦和玩家雙方各建立一張棋型表Computer[15][15][4]和Player[15][15][4]，用來(lái)存放棋型數(shù)據(jù)，就是剛才所說(shuō)的重要程度，比如用‘20’代表“沖四”的點(diǎn)，用‘15’代表“活三”的點(diǎn)，那么在計(jì)算重要性時(shí)，就可以根據(jù)20>15得出前者比后者重要，下子時(shí)電腦便會(huì)自動(dòng)選擇“沖四”的點(diǎn)。那為什么棋型表要使用三維數(shù)組呢?因?yàn)槠灞P上的每一個(gè)點(diǎn)都可以與橫、豎、左斜、右斜四個(gè)方向的棋子構(gòu)成不同的棋型，所以一個(gè)點(diǎn)總共有4個(gè)記錄;這樣做的另一個(gè)好處是可以輕易判斷出復(fù)合棋型，例如：如果同一點(diǎn)上有2個(gè)‘15’就是雙三、有一個(gè)‘15’和一個(gè)‘20’就是四三。
怎么樣!3個(gè)數(shù)組構(gòu)成了程序的基本數(shù)據(jù)骨架，今后只要再加入一些輔助變量便可以應(yīng)付自如了。應(yīng)該不會(huì)太難吧?OK!有了這么多有用的數(shù)據(jù)，我們就可以深入到程序的流程中去了。
二：程序流程
我們主要討論五子棋的核心算法，即：人工智能部分，而其他像圖形顯示、鍵盤鼠標(biāo)控制等，因較為簡(jiǎn)單，所以就不作過(guò)多介紹了。
程序由六個(gè)基本功能模塊構(gòu)成，各模塊的詳細(xì)分析如下：
(1)初始化：首先，建立盤面數(shù)組Table[15][15]、對(duì)戰(zhàn)雙方的棋型表Computer[15][15][4]和Player[15][15][4]并將它們清零以備使用;然后初始化顯示器、鍵盤、鼠等輸入輸出設(shè)備并在屏幕上畫出棋盤。
(2)主循環(huán)控制模塊：控制下棋順序，當(dāng)輪到某方下子時(shí)，負(fù)責(zé)將程序轉(zhuǎn)到相應(yīng)的模塊中去，主要擔(dān)當(dāng)一個(gè)調(diào)度者的角色。
(3)玩家下子：當(dāng)輪到玩家下時(shí)，您通過(guò)鍵盤或鼠標(biāo)在棋盤上落子，程序會(huì)根據(jù)該點(diǎn)的位置，在Table[15][15]數(shù)組的相應(yīng)地方記錄‘2’，以表明該子是玩家下的。
(4)盤面分析填寫棋型表：本程序核心模塊之一，人工智能算法的根本依據(jù)!其具體實(shí)現(xiàn)方法如下：您在下五子棋時(shí)，一定會(huì)先根據(jù)棋盤上的情況，找出當(dāng)前最重要的一些點(diǎn)位，如“活三”、“沖四”等;然后再在其中選擇落子點(diǎn)。但是，電腦不會(huì)像人一樣分析問(wèn)題，要讓它知道哪是“活三”、哪是“沖四”，就得在棋盤上逐點(diǎn)計(jì)算，一步一步的教它。
先來(lái)分析己方的棋型，我們從棋盤左上角出發(fā)，向右逐行搜索，當(dāng)遇到一個(gè)空白點(diǎn)時(shí)，以它為中心向左挨個(gè)查找，如果遇到己方的子則記錄然后繼續(xù)，如果遇到對(duì)方的子、空白點(diǎn)或邊界就停止查找。左邊完成后再向右進(jìn)行同樣的操作;最后把左右兩邊的記錄合并起來(lái)，得到的數(shù)據(jù)就是該點(diǎn)橫向上的棋型，然后把棋型的編號(hào)填入到Computer[x][y][n]中就行了(x、y代表坐標(biāo)，n=0、1、2、3分別代表橫、豎、左斜、右斜四個(gè)方向)。而其他三個(gè)方向的棋型也可用同樣的方法得到，當(dāng)搜索完整張棋盤后，己方棋型表也就填寫完畢了。然后再用同樣的方法填寫對(duì)方棋型表。
注意：所有棋型的編號(hào)都要事先定義好，越重要的號(hào)數(shù)越大!
OK! 怎么樣?有點(diǎn)累了吧?不過(guò)千萬(wàn)別泄氣!因?yàn)楹脩蜻€在后頭。
Let's go!
(5)電腦下子：有了上面填寫的兩張棋型表，現(xiàn)在要作的就是讓電腦知道在哪一點(diǎn)下子了。其中最簡(jiǎn)單的計(jì)算方法，就是遍歷棋型表Computer[15][15][4]和Player[15][15][4]找出其中數(shù)值最大的一點(diǎn)，在該點(diǎn)下子即可。但這種算法的弱點(diǎn)非常明顯，只顧眼前利益，不能顧全大局，這就和許多五子棋初學(xué)者一樣犯了“目光短淺”的毛病。
要解決這個(gè)問(wèn)題，我們引入‘今后幾步預(yù)測(cè)法’，具體方法是這樣的： 首先， 讓電腦分析一個(gè)可能的點(diǎn)，如果在這兒下子將會(huì)形成對(duì)手不得不防守的棋型(例如：‘沖四’、‘活三’);那么下一步對(duì)手就會(huì)照您的思路下子來(lái)防守您，如此一來(lái)便完成了第一步的預(yù)測(cè)。這時(shí)再調(diào)用模塊4對(duì)預(yù)測(cè)后的棋進(jìn)行盤面分析，如果出現(xiàn)了‘四三’、‘雙三’或‘雙四’等制勝點(diǎn)，那么己方就可以獲勝了(當(dāng)然對(duì)黑棋而言‘雙三’、‘雙四’是禁手，另當(dāng)別論);否則照同樣的方法向下分析，就可預(yù)測(cè)出第二步、第三步……
等一等，要是盤面上沒(méi)有對(duì)手必須防的棋型，哪該怎么辦呢?進(jìn)攻不成的話就得考慮防守了，將自己和對(duì)手調(diào)換一下位置，然后用上面的方法來(lái)預(yù)測(cè)對(duì)手的棋，這樣既可以防住對(duì)手巧妙的攻擊，又能侍機(jī)發(fā)動(dòng)反擊，何樂(lè)而不為呢!
但是必須告訴大家的是：預(yù)測(cè)法的運(yùn)算量相當(dāng)之大，據(jù)我的經(jīng)驗(yàn)，用Pentium-100預(yù)測(cè)3步的走法平均需要15秒以上時(shí)間，所以建議預(yù)測(cè)量在5步以內(nèi)。可別小瞧了這5步，有時(shí)它甚至?xí)叱鲎屇氖纸薪^的妙著呢!
(6)勝負(fù)判斷：務(wù)須多言，某方形成五子連即獲勝;若黑棋走出‘雙三’、‘雙四’或長(zhǎng)連即以禁手判負(fù)。
到現(xiàn)在為止，整個(gè)五子棋軟件就基本完成了，其水平大約在中級(jí)上下。當(dāng)然，這種算法并不是最好的，但我相信它的基本思路是正確的。如果您有什么問(wèn)題或好的想法，歡迎給我發(fā)E-mail: softboy@sina.com，我期待著您的見(jiàn)解。
五子棋禁手判定算法
禁手的判定較為復(fù)雜，設(shè)計(jì)一個(gè)判斷禁手的算法既要分析構(gòu)成它的棋型又要找到合適的搜索方法。
首先分析棋型。
先考慮構(gòu)成長(zhǎng)連禁手的棋型，構(gòu)成長(zhǎng)連的棋型較簡(jiǎn)單，可歸納為一種，即相連后形成六子或更多相連。一旦發(fā)現(xiàn)產(chǎn)生此棋型，即判為長(zhǎng)連禁手。
再考慮構(gòu)成四四禁手、三三禁手的棋型。要判斷下某一子是否構(gòu)成四四禁手(或三三禁手)，只需判斷下這一子后是否產(chǎn)生兩個(gè)或兩個(gè)以上的沖四或活四(或活三)即可。所以歸結(jié)起來(lái)，要正確判斷四四禁手、三三禁手就是要正確判斷沖四、活四和活三。
考慮沖四、活四和活三的定義。沖四是只有一個(gè)點(diǎn)可以成五的四，這里我們將那個(gè)點(diǎn)稱為關(guān)鍵點(diǎn)。同樣，構(gòu)成活四的有兩個(gè)關(guān)鍵點(diǎn)，構(gòu)成活三的有一個(gè)關(guān)鍵點(diǎn)。如圖11，a,b兩點(diǎn)是其構(gòu)成活四的關(guān)鍵點(diǎn)，又如圖12，a點(diǎn)是其構(gòu)成活三的關(guān)鍵點(diǎn)。
 圖12 |
以下是對(duì)各棋型和關(guān)鍵點(diǎn)的分析。
1、活四：
歸結(jié)起來(lái)構(gòu)成活四的只有一種棋型,如圖13
 圖13 |
這種棋型真正構(gòu)成活四的條件是左右兩空位(即a,b點(diǎn))必須是黑棋可下的點(diǎn)，也就是在a,b點(diǎn)下黑子后都不會(huì)構(gòu)成禁手。
2、沖四：
形成沖四有兩種棋型，如圖14和圖15
 圖14 |  圖15 |
這兩種棋型真正構(gòu)成沖四的條件是中間的空位(即a點(diǎn))必須是黑棋可下的點(diǎn)，也就是在a點(diǎn)下子后不會(huì)構(gòu)成禁手。
3、活三：
形成活三有兩種棋型，如圖16和圖17
 圖16 |  圖17 |
其中，a點(diǎn)是關(guān)鍵點(diǎn)，b,c點(diǎn)可以是邊界、無(wú)子或白色棋子，但不能是黑色棋子。
這兩種棋型真正構(gòu)成活三的條件是a點(diǎn)必須是黑棋可下的點(diǎn)，也就是在a點(diǎn)下子后不會(huì)構(gòu)成禁手，m,n兩點(diǎn)不用管是否構(gòu)成禁手，因?yàn)楫?dāng)a點(diǎn)放入黑子后，不管在m點(diǎn)還是n點(diǎn)放黑子，就會(huì)形成五連，即獲勝，不構(gòu)成禁手。
所以我們要判斷一種棋型是否構(gòu)成沖四、活四或活三，需要在已判斷它是可能的沖四、活四或活三的棋型的基礎(chǔ)上判斷它的關(guān)鍵點(diǎn)是否可落黑色棋子，也就是判斷關(guān)鍵點(diǎn)是否不會(huì)構(gòu)成新的禁手點(diǎn)，這一步在程序中可以用遞歸實(shí)現(xiàn)。
棋型分析完成，我們就要據(jù)此考慮選擇合適的算法。
基于禁手分析所需的精確度，我們?cè)谄灞P盤面搜索時(shí)，需要記錄與待判斷點(diǎn)相鄰的連續(xù)黑色棋子數(shù)，并記錄之后的連續(xù)空子數(shù)，并記錄再之后的連續(xù)黑子數(shù)，和再之后的連續(xù)空子數(shù)，以及再之后的連續(xù)黑子數(shù)。所以可以說(shuō)搜索的深度要達(dá)到5層。
在判斷關(guān)鍵點(diǎn)的可下性時(shí)，選用遞歸的方法來(lái)判斷其是否不是禁手點(diǎn)。
于是最后我們可以得出禁手判定算法的思路。
第一步：將待判斷點(diǎn)放入黑棋子;
第二步：搜索待判斷點(diǎn)周邊棋盤;
第三步：還原棋盤;
第四步：利用搜索結(jié)果依次對(duì)各方向進(jìn)行分析，判斷黑棋放入后所產(chǎn)生的棋型是否形成長(zhǎng)連或形成可能構(gòu)成活四、沖四、活三的棋型。若形成長(zhǎng)連，判定為禁手，返回長(zhǎng)連禁手標(biāo)識(shí)。若形成可能是活四、沖四、活三的棋型，判斷關(guān)鍵點(diǎn)是否可下，若不可下，該棋型統(tǒng)計(jì)數(shù)加1，反之，則對(duì)下一個(gè)方向進(jìn)行判斷，直到各個(gè)方向分析結(jié)束。
第五步：若活四、沖四棋型的統(tǒng)計(jì)數(shù)大于1，返回四四禁手標(biāo)識(shí)，若活三棋型的統(tǒng)計(jì)數(shù)大于1，返回三三禁手標(biāo)識(shí)。其余情況返回非禁手標(biāo)識(shí)。
源代碼:
