五子棋人機(jī)對(duì)戰(zhàn)算法分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)總的來(lái)說(shuō)，要讓電腦知道該在哪一點(diǎn)下子，就要根據(jù)盤(pán)面的形勢(shì)，為每一可能落子的點(diǎn)計(jì)算其重要程度，也就是當(dāng)這子落下后會(huì)形成什么棋型（如：“沖四”、“活三”等），然后通覽全盤(pán)選出最重要的一點(diǎn)，這便是最基本的算法。當(dāng)然，僅靠當(dāng)前盤(pán)面進(jìn)行判定是遠(yuǎn)遠(yuǎn)不夠的，這樣下棋很輕易掉進(jìn)玩家設(shè)下的陷阱，因?yàn)樗鼪](méi)有考慮以后的變化。所以在此基礎(chǔ)上我們加入遞歸調(diào)用，即：在電腦中猜測(cè)出今后幾步的各種走法，以便作出最佳選擇，這也是我們下棋時(shí)常說(shuō)的“想了幾步”。如此一來(lái)您的程序便具有一定的水平了。什么？不信

2、！過(guò)來(lái)試試吧！ 總體思路弄清之后，下面進(jìn)行具體討論：一：數(shù)據(jù)結(jié)構(gòu) 先來(lái)看看數(shù)據(jù)結(jié)構(gòu)，我們需要哪些變量？ 首先得為整個(gè)棋盤(pán)建立一張表格用以記錄棋子信息，我們使用一個(gè)15*15的二維數(shù)組 Table1515 (15*15是五子棋棋盤(pán)的大小)，數(shù)組的每一個(gè)元素對(duì)應(yīng)棋盤(pán)上的一個(gè)交叉點(diǎn)，用0表示空位、1代表己方的子、2代表對(duì)方的子；這張表也是今后分析的基礎(chǔ)。 在此之后還要為電腦和玩家雙方各建立一張棋型表Computer15154和Player15154，用來(lái)存放棋型數(shù)據(jù)，就是剛才所說(shuō)的重要程度，比如用20代表“沖四”的點(diǎn)，用15代表“活三”的點(diǎn)，那么在計(jì)算重要性時(shí)，就可以根據(jù)2015得出前者比后者重要，

3、下子時(shí)電腦便會(huì)自動(dòng)選擇“沖四”的點(diǎn)。那為什么棋型表要使用三維數(shù)組呢？因?yàn)槠灞P(pán)上的每一個(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ù)，我們就可以深入到程序的流程中去了。二：程序流程 我們主要討論五子棋的核心算法，即：人工智能部分，而其他像圖形顯示、鍵盤(pán)鼠標(biāo)控制等，因較為簡(jiǎn)單，所以就不作過(guò)多介紹了。 我們看到本程序由六個(gè)

4、基本功能模塊構(gòu)成，各模塊的具體分析如下： （1）初始化：首先，建立盤(pán)面數(shù)組Table1515、對(duì)戰(zhàn)雙方的棋型表Computer15154和Player15154并將它們清零以備使用；然后初始化顯示器、鍵盤(pán)、鼠等輸入輸出設(shè)備并在屏幕上畫(huà)出棋盤(pán)。 （2）主循環(huán)控制模塊：控制下棋順序，當(dāng)輪到某方下子時(shí)，負(fù)責(zé)將程序轉(zhuǎn)到相應(yīng)的模塊中去，主要擔(dān)當(dāng)一個(gè)調(diào)度者的角色。 （3）玩家下子：當(dāng)輪到玩家下時(shí)，您通過(guò)鍵盤(pán)或鼠標(biāo)在棋盤(pán)上落子，程序會(huì)根據(jù)該點(diǎn)的位置，在Table1515數(shù)組的相應(yīng)地方記錄2，以表明該子是玩家下的。 （4）盤(pán)面分析填寫(xiě)棋型表：本程序核心模塊之一，人工智能算法的根本依據(jù)！其具體實(shí)現(xiàn)方法如下：您在

5、下五子棋時(shí)，一定會(huì)先根據(jù)棋盤(pán)上的情況，找出當(dāng)前最重要的一些點(diǎn)位，如“活三”、“沖四”等；然后再在其中選擇落子點(diǎn)。但是，電腦不會(huì)像人一樣分析問(wèn)題，要讓它知道哪是“活三”、哪是“沖四”，就得在棋盤(pán)上逐點(diǎn)計(jì)算，一步一步的教它。 先來(lái)分析己方的棋型，我們從棋盤(pán)左上角出發(fā)，向右逐行搜索，當(dāng)碰到一個(gè)空白點(diǎn)時(shí)，以它為中心向左挨個(gè)查找，假如碰到己方的子則記錄然后繼續(xù)，假如碰到對(duì)方的子、空白點(diǎn)或邊界就停止查找。左邊完成后再向右進(jìn)行同樣的操作；最后把左右兩邊的記錄合并起來(lái)，得到的數(shù)據(jù)就是該點(diǎn)橫向上的棋型，然后把棋型的編號(hào)填入到Computerxyn中就行了（x、y代表坐標(biāo)，n=0、1、2、3分別代表橫、豎、左斜、

6、右斜四個(gè)方向）。而其他三個(gè)方向的棋型也可用同樣的方法得到，當(dāng)搜索完整張棋盤(pán)后，己方棋型表也就填寫(xiě)完畢了。然后再用同樣的方法填寫(xiě)對(duì)方棋型表。 注重：所有棋型的編號(hào)都要事先定義好，越重要的號(hào)數(shù)越大！ OK! 怎么樣？有點(diǎn)累了吧？不過(guò)千萬(wàn)別泄氣！因?yàn)楹脩蜻€在后頭。 Lets go！ （5）電腦下子：有了上面填寫(xiě)的兩張棋型表，現(xiàn)在要作的就是讓電腦知道在哪一點(diǎn)下子了。其中最簡(jiǎn)單的計(jì)算方法，就是遍歷棋型表Computer15154和Player15154找出其中數(shù)值最大的一點(diǎn)，在該點(diǎn)下子即可。但這種算法的弱點(diǎn)非常明顯，只顧眼前利益，不能顧全大局，這就和許多五子棋初學(xué)者一樣犯了“目光短淺”的毛病。 要解決這

7、個(gè)問(wèn)題，我們引入今后幾步猜測(cè)法，具體方法是這樣的： 首先， 讓電腦分析一個(gè)可能的點(diǎn)，假如在這兒下子將會(huì)形成對(duì)手不得不防守的棋型（例如：沖四、活三）；那么下一步對(duì)手就會(huì)照您的思路下子來(lái)防守您，如此一來(lái)便完成了第一步的猜測(cè)。這時(shí)再調(diào)用模塊4對(duì)猜測(cè)后的棋進(jìn)行盤(pán)面分析，假如出現(xiàn)了四三、雙三或雙四等制勝點(diǎn)，那么己方就可以獲勝了（當(dāng)然對(duì)黑棋而言雙三、雙四是禁手，另當(dāng)別論）；否則照同樣的方法向下分析，就可猜測(cè)出第二步、第三步 等一等，要是盤(pán)面上沒(méi)有對(duì)手必須防的棋型，哪該怎么辦呢？進(jìn)攻不成的話(huà)就得考慮防守了，將自己和對(duì)手調(diào)換一下位置，然后用上面的方法來(lái)猜測(cè)對(duì)手的棋，這樣既可以防住對(duì)手巧妙的攻擊，又能侍機(jī)發(fā)動(dòng)反擊，何樂(lè)而不為呢！ 但是必須告訴大家的是：猜測(cè)法的運(yùn)算量相當(dāng)之大，據(jù)我的經(jīng)驗(yàn)，用Pentium-100猜測(cè)3步的走法平均需要15秒以上時(shí)間，所以建議猜測(cè)量在5步以?xún)?nèi)?？蓜e小瞧了這5步，有時(shí)它甚至?xí)叱鲎屇?/p>