前言：

?? 剛學(xué)玩C一個(gè)月，院里有個(gè)程序設(shè)計(jì)的比賽，于是就動(dòng)手寫了這玩意兒。

正文：

??? 首先，對(duì)于每一盤棋都有很多種下法，當(dāng)黑方落下第一顆棋子的時(shí)候，白方有254種下法，白方在這254種下法中選擇其一后，黑方又有253中下法。如此，將所有的下法都考慮，全部列出來就構(gòu)成了一顆巨大的博弈樹，也稱搜索數(shù)。這顆博弈樹的根節(jié)點(diǎn)便是黑方下的第一顆棋子，緊接著的下一層便是白方下棋的所有情況，依次下去，直到結(jié)束。而電腦要做的是從下面的子節(jié)點(diǎn)中找出最有利于電腦方的節(jié)點(diǎn)，也就是最佳走法。誰想得深遠(yuǎn)，預(yù)測(cè)的步數(shù)越多，棋局了解到位，就越厲害。如果能將未來的所有情況都考慮到位，那必定處于不敗之地。

??? 在選擇最佳走法中，我們要用到極小極大搜索算法。我們先假設(shè)有個(gè)對(duì)棋局的評(píng)價(jià)函數(shù)，即可以對(duì)任何一個(gè)局面對(duì)電腦方打分，分越高越對(duì)電腦有利，分越低卻對(duì)玩家有利，也就是說這個(gè)評(píng)價(jià)函數(shù)是對(duì)電腦方而言的，計(jì)算機(jī)贏則為無窮大，輸則無窮小。其它所有情況都在這之間。

如上圖就是所謂的博弈樹，假如：甲對(duì)應(yīng)電腦方，乙對(duì)應(yīng)玩家。當(dāng)前該電腦方下棋，即甲0節(jié)點(diǎn)，下一層的子節(jié)點(diǎn)即該玩家下。雙方都希望在未來的局勢(shì)中，往最有利于己方的方向進(jìn)行。計(jì)算機(jī)當(dāng)然想自己的分高，所以會(huì)選子節(jié)點(diǎn)分值最大的乙1，分值為2，所以甲0分值為2。而乙1想分值低，于是，他會(huì)選甲3-4中分值最小的甲3，分值為2，乙1的值因此為2。所以，在極小極大搜索算法中，稱想要最大值的甲的節(jié)點(diǎn)為極大值點(diǎn)，想要最小值的乙的節(jié)點(diǎn)為極小值點(diǎn)。在這個(gè)極大值極小值的搜索過程為極小極大搜索算法。

??? 前面所說的，都是理論上可行的方法，因?yàn)樵谶@復(fù)雜度指數(shù)級(jí)增長(zhǎng)的過程中，想要搜索完這么龐大的博弈樹是不可能的。我們只能往后預(yù)測(cè)幾步，就用靜態(tài)估值函數(shù)算出分?jǐn)?shù)，然后一步步倒推上去，而到當(dāng)前最佳的走法。這時(shí)，我們就需要一個(gè)對(duì)任意局面評(píng)分的評(píng)價(jià)函數(shù)。如果給評(píng)估函數(shù)打分呢？我是把把棋面分成72路，橫15 + 豎15 + 左斜21 + 右斜21 = 72（因?yàn)樾敝墓灿?6路形成不了五子）。為72路是為了收集具有形成5子可能性的特征。一個(gè)棋局具有電腦方的這些特征越多，棋局分?jǐn)?shù)便越高，具有玩家方特征越多，分值便越低，因此玩家的特征是記負(fù)分的。當(dāng)然不同的特征分值也不同。我將電腦方棋子抽象為1，空格抽象為0。例如：遇到11111便賦值9999999，011110賦值300000，011100或001110賦值為3000等等。如果是玩家的棋就賦相應(yīng)的負(fù)分。最后把72路的分?jǐn)?shù)加起來，黑白雙方的總分相加就得到整個(gè)棋局的分?jǐn)?shù)。其實(shí)，我把每一路的情況分成一個(gè)個(gè)長(zhǎng)度為6的字符串，一一跟原來預(yù)定的16個(gè)特征做比較，留下每一路分值最大的特征。然而，在沒一次判斷下那一步的時(shí)候，要預(yù)測(cè)的情況數(shù)是巨大的，而沒一種情況都要調(diào)用靜態(tài)估值函數(shù)，進(jìn)行大概7000次特征的匹配。為了減少匹配的次數(shù)，我用了哈夫曼樹編碼的思想，把所有的特征編成了一個(gè)哈夫曼樹（如下圖，當(dāng)時(shí)的草稿），每個(gè)節(jié)點(diǎn)都由0、1組成，這也是我之前把棋子抽象為1，空格抽象為0的原因。具體就不在詳述，哈夫曼樹編碼的思想我是參考的《算法與數(shù)據(jù)結(jié)構(gòu)》151頁(yè)。如此，每一個(gè)長(zhǎng)度為6個(gè)字符就不必跟16個(gè)特征一一線性的比較，這樣就大大的減少了計(jì)算量。

??? 光憑上面的還遠(yuǎn)遠(yuǎn)不夠，我實(shí)驗(yàn)過，僅預(yù)測(cè)三步的時(shí)候，電腦下一步，需要等待近半個(gè)小時(shí)。因此，我在極小極大搜索算法中還加入了Alpha-Beta剪枝剪枝法，可以叫它為Alpha-Beta搜索算法。如下圖：

上述的極小極大值搜索過程中，遍歷了整棵的博弈樹，每一個(gè)節(jié)點(diǎn)都訪問了一次，這樣的搜索算法粗糙，效率低下，搜索量非常大。假如將葉節(jié)點(diǎn)的評(píng)估，計(jì)算倒推值與樹的產(chǎn)生同時(shí)進(jìn)行，就可能大量減少所需搜索的節(jié)點(diǎn)數(shù)目，而且保持搜索效果不變。具體思路如下：

Alpha剪枝：

如圖：極大值點(diǎn)甲3及下面所有節(jié)點(diǎn)

1.因?yàn)橐?為2，因此甲三大于或等于2；

2.甲19為1，則乙8小于或等于1；

3.既然甲2是取最大的，暫且等于2，就不用考慮小于或等于1的乙 8了。

? 因此，甲20不需要考慮，把它剪掉。

Beta剪枝：

同理，如圖：極小值點(diǎn)乙1及下面所有節(jié)點(diǎn)，一樣分析。

這樣，就減少了不少分支，剪掉的分部，既不用創(chuàng)建合法的走法，也不用在評(píng)估時(shí)大量的計(jì)算，在一定程度上優(yōu)化了許多。但是，Alpha-Beta剪枝剪枝法在減枝過程搜索效率與節(jié)點(diǎn)的排列順序有很大關(guān)系。因此，可以在產(chǎn)生走法的時(shí)候?qū)λM(jìn)行排序來達(dá)到進(jìn)一步的優(yōu)化。按理說，對(duì)極小節(jié)點(diǎn)按從小到大的順序排序，對(duì)極大節(jié)點(diǎn)按從大到小的順序排序是最理想的，但是在最后的節(jié)點(diǎn)沒產(chǎn)生之前，不可能得到評(píng)估值。所以，排序的時(shí)候可以根據(jù)威脅性大的點(diǎn)周圍進(jìn)行優(yōu)先搜索的辦法達(dá)到優(yōu)化的效果。

??? 最后便是我在最后兩天想出來的優(yōu)化辦法，在開頭的幾十步里，它的優(yōu)化效果比Alpha-Beta剪枝剪枝法好上幾十倍。這里我用到的是縮小搜索范圍算法，其實(shí)是我瞎起的一個(gè)名字。前面的Alpha-Beta剪枝剪枝法是在產(chǎn)生一定子節(jié)點(diǎn)后剪掉部分枝節(jié)而達(dá)到優(yōu)化效果，而縮小搜索范圍算法則是從根節(jié)點(diǎn)處直接砍掉分支，從頂端砍下來的話，完全舍棄了其下龐大的分支。具體思路如下：我們?cè)谙缕宓臅r(shí)候，基本都是在已有的棋子周圍下子，所以還有很多空位是完全不需要搜索的。就是基于這一點(diǎn)，我們就能可以確定搜索范圍，先判斷已下了的棋子最大對(duì)角線，在此對(duì)角線的基礎(chǔ)上畫矩形，然后在向外圍擴(kuò)大一兩格，這樣就在根節(jié)點(diǎn)上減少了分支，更不需要考慮在其范圍外的以后幾步的情況了。不過，在預(yù)測(cè)的過程中，我們要假設(shè)下了某子，這些預(yù)測(cè)的下子會(huì)很快的將范圍擴(kuò)大到邊界，而當(dāng)預(yù)測(cè)完一個(gè)父節(jié)點(diǎn)及以下子節(jié)點(diǎn)的所有情況后，與前面父節(jié)點(diǎn)同一深度的節(jié)點(diǎn)并不需要那么大的搜索范圍，因此理想的搜索范圍應(yīng)和預(yù)測(cè)前同樣的。這里，我們可以采用堆棧的結(jié)構(gòu)，用入棧操作就可將一方下的棋子存入棧中，得到新的搜索范圍，當(dāng)搜索過程的回溯發(fā)生時(shí)用出棧操作退出一子，即可恢復(fù)到前一搜索范圍。這樣就能步步為營(yíng)，有進(jìn)有退，盡可能的減少不必要的計(jì)算。

展望未來：

?? 前面講的改進(jìn)搜索算法的目標(biāo)在于將不必搜索的(冗余)分枝從搜索的過程中盡量剔除，以達(dá)到盡量搜索少的分枝束降低運(yùn)算量的目的。但是仍然在有限時(shí)間內(nèi)預(yù)測(cè)幾步而已，想要讓電腦達(dá)到世界級(jí)水平還是不夠的。開頭我提過中原大學(xué)的碩士學(xué)位論文《五子棋棋略的演化學(xué)習(xí)法》中核心講的“基因演算法”，也稱遺傳算法，是讓程序具有學(xué)習(xí)功能，在大量的實(shí)踐中，程序會(huì)不段的更改評(píng)估函數(shù)特征的權(quán)值，這樣便克服了人為主觀因素的片面性。而在啟發(fā)式搜索過程中，其實(shí)有很多局面是重復(fù)的，就增加了很多不必要的重復(fù)計(jì)算，為了解決這個(gè)問題，可以使用基于哈希表的置換表搜索算法，將搜索過的局面存如數(shù)據(jù)，不需要了就清除，遇到相同的局面只需調(diào)用前面計(jì)算得出的數(shù)據(jù)，就避免重算。另外，現(xiàn)在的超線程技術(shù)和多核技術(shù)也能達(dá)到進(jìn)一步的優(yōu)化。

感想：

??? 這此做人工智能五子棋，多少也有點(diǎn)收獲，相對(duì)以前更加懂得怎么在有限的時(shí)間內(nèi)完成自己看似不可能或很難完成的任務(wù)，此類任務(wù)最好的方法便是證比求易。當(dāng)中肯定有自己不曾具備的知識(shí)，當(dāng)處于當(dāng)今這個(gè)時(shí)代，我們需要的這點(diǎn)知識(shí)還是很輕易的找到。然而最關(guān)鍵的還是自己以最快的方法消化弄懂它，讓前人或大師研究過的寶貴成果迅速成為自己的技能。作為一名程序員，這次經(jīng)歷給我的感受是，完成一個(gè)程序，最重要的絕對(duì)是算法，這此做五子棋，人工智能模塊的算法我也弄了幾天才搞清楚，也許只有某一個(gè)點(diǎn)有疑惑，它也可以讓你一個(gè)下午也弄不明白。當(dāng)算法完成之后，就可以立即開始組織編碼，從數(shù)據(jù)結(jié)構(gòu)入手，理清程序流程，然后把各個(gè)子模塊一一攻破。算法花了幾天，而編碼一天內(nèi)便能完成，我們?nèi)蘸蟮闹攸c(diǎn)也因在構(gòu)思這塊。碼農(nóng)于軟件工程師的共同點(diǎn)是都會(huì)編程，而軟件工程師之所以不同是因?yàn)樗芤猿绦蚧枷虢鉀Q問題本身，而編碼是碼農(nóng)們的事了。

總結(jié)

以上是生活随笔為你收集整理的关于做人工智能—五子棋的总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。