人工智能五子棋論文
本文將這些技術(shù)用于五子棋中。設(shè)計(jì)了一個(gè)智能五子棋系統(tǒng)，實(shí)現(xiàn)人和計(jì)算機(jī)兩方進(jìn)行博弈。以下是學(xué)習(xí)啦小編整理分享的關(guān)于人工智能五子棋論文的相關(guān)文章，歡迎閱讀!
人工智能五子棋論文篇一
智能五子棋博弈算法研究
摘要：人工智能是一門(mén)正在迅速發(fā)展的新興的綜合性很強(qiáng)的邊緣科學(xué)。博弈是人工智能的主要研究領(lǐng)域之一，他涉及人工智能中的推理技術(shù)、搜索方法和決策規(guī)劃。本文將這些技術(shù)用于五子棋中。設(shè)計(jì)了一個(gè)智能五子棋系統(tǒng)，實(shí)現(xiàn)人和計(jì)算機(jī)兩方進(jìn)行博弈。
關(guān)鍵詞：五子棋 人工智能 搜索
人工智能是一門(mén)綜合性很強(qiáng)的邊緣科學(xué)，它研究如何使計(jì)算機(jī)去做那些過(guò)去只能靠人的智力才能做的工作。而博弈是人工智能研究的一個(gè)重要分支，它不僅存在于游戲、下棋之中，也存在于政治、經(jīng)濟(jì)、軍事和生物競(jìng)爭(zhēng)中。
五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一。現(xiàn)代五子棋日文稱(chēng)之為“連珠”，英譯為“Ren-ju”，英文稱(chēng)之為“Gobang”或“FIR”(Five in a Row的縮寫(xiě))，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱(chēng)謂。與其他棋類(lèi)相比，五子棋每一層搜索節(jié)點(diǎn)數(shù)量龐大，因此盤(pán)面預(yù)測(cè)的計(jì)算量是非常大的，比如對(duì)于五子棋的中盤(pán)走法中，如果要預(yù)測(cè)四步的局面數(shù)的話可以達(dá)到一百萬(wàn)。
本文是對(duì)五子棋算法的設(shè)計(jì)原理和實(shí)現(xiàn)方法進(jìn)行探討和研究，主要包括數(shù)據(jù)結(jié)構(gòu)、搜索算法和優(yōu)劣評(píng)價(jià)函數(shù)組成，主要的特點(diǎn)包括快速的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)實(shí)現(xiàn)、以及高效率的搜索算法和盡可能的模擬人類(lèi)的智能。
1、棋局的數(shù)據(jù)結(jié)構(gòu)表示
我們知道五子棋的走法中有優(yōu)先和禁手，如連四肯定是沒(méi)有三四優(yōu)先，而如果是黑方出現(xiàn)三三(包括“四、三、三”)、四四(包括“四、四、三”)，而黑方只能以四三取勝，如果黑方走出禁手則是輸;五連與禁手同時(shí)形成，先五為勝，等等的規(guī)矩。但是電腦畢竟不是人類(lèi)，可以類(lèi)人但是卻不可以自己思考，那么就需要給電腦一個(gè)它可以明白的評(píng)判標(biāo)準(zhǔn)。
下面，我列出基本的棋型優(yōu)先順序：
造一個(gè)二<……<造四個(gè)二<沖三<……<沖兩個(gè)二和一個(gè)三<沖雙三<沖四<沖四三。
之所以這么設(shè)置是由于五子棋的下法所致，只要構(gòu)成5顆一線就贏了，所以說(shuō)一條線上構(gòu)成的越多那么就有優(yōu)勢(shì)，當(dāng)然就是棋數(shù)越多，分越多。
那么為了讓電腦明確的知道是不是應(yīng)該落子，就給它一個(gè)標(biāo)準(zhǔn)：分值。用程序語(yǔ)言表示：
enum Value {FAILED=-99999，SKIP=20，LENG=10，TWO =100，THREE =1000， IF0UR =10000，F(xiàn)OUR =50000，SF0UR=70000，WIN=100000};
如果某一點(diǎn)導(dǎo)致失敗，則分值為FAILED，由于它足夠小，所以無(wú)論任何棋型與它的組合都小于0，SKIP之所以給它20分，是為了避免電腦出現(xiàn)無(wú)棋可下的情況，LENG是有可能發(fā)生長(zhǎng)連的點(diǎn)，這有可能導(dǎo)致禁手，TWO、THREE、FOUR、WIN 觀名知意，TFOUR 和SFOUR分別是弱四和強(qiáng)四。強(qiáng)四的點(diǎn)比普通的沖四重要的多，比如一個(gè)活四，意味著即將判出勝負(fù)。弱四是為了提供更大的靈活。也許有某種沖四并不一定比沖三重要，我在這里并沒(méi)有使用，以后可以擴(kuò)充。
2、五子棋算法介紹及初步實(shí)現(xiàn)
2.1 五子棋博弈樹(shù)中的極大極小搜索和α-β剪枝
為了使談?wù)摳袟l理性[5]，將博弈的雙方分別命名為MAX和MIN。而搜索的任務(wù)是為MAX找最佳的移動(dòng)。假設(shè)MAX先移動(dòng)(此時(shí)暫時(shí)不考慮五子棋的禁手等規(guī)則)，然后2個(gè)博弈者輪流移動(dòng)。因此，深度為偶數(shù)的節(jié)點(diǎn)，對(duì)應(yīng)于MAX下一步移動(dòng)的位置，稱(chēng)為MAX節(jié)點(diǎn);深度為奇數(shù)的節(jié)點(diǎn)對(duì)應(yīng)于MIN下一步移動(dòng)的位置，稱(chēng)為MIN節(jié)點(diǎn)(博弈樹(shù)的頂節(jié)點(diǎn)深度為0)。k層包括深度為2k和2k+1的節(jié)點(diǎn)。通常用層數(shù)表示博弈樹(shù)的搜索深度。他可以表示出向前預(yù)測(cè)的MAX和MIN交替運(yùn)動(dòng)的回合數(shù)。
用整個(gè)棋盤(pán)估值的函數(shù)h(n)為靜態(tài)估值函數(shù)。設(shè)想當(dāng)前棋局S為輪到計(jì)算機(jī)方下棋(用方框表示)，任選一空點(diǎn)作為計(jì)算機(jī)方的下棋位置(可有若干種選擇)，接著考慮在此情況下游戲者一方下棋的棋局(用圓圈表示);從某一個(gè)圓圈棋局出發(fā)，任選一空點(diǎn)作為游戲者一方的落子處(又有若干種選擇)。再次形成計(jì)算機(jī)方下棋的方框棋局;依此類(lèi)推，這樣可形成一棵以S為根結(jié)點(diǎn)的博弈樹(shù)，該樹(shù)以圓圈棋局為第2層子結(jié)點(diǎn)，以方框棋局為第3層子結(jié)點(diǎn)等等。如果繼續(xù)向前搜索，可形成多層子結(jié)點(diǎn)，現(xiàn)在以向前搜索3層子結(jié)點(diǎn)為例來(lái)說(shuō)明極大極小值的過(guò)程。對(duì)第3層子結(jié)點(diǎn)的某一棋局n，求出其估計(jì)值h(n)，假設(shè)有一博弈樹(shù)已形成，如圖1所示[2]，h(n)的值由各結(jié)點(diǎn)旁的數(shù)值給出。
根據(jù)極小極大化分析法，先計(jì)算第3層子結(jié)點(diǎn)h(n)值，然后第2層子結(jié)點(diǎn)的估計(jì)值取他的各后繼子結(jié)點(diǎn)的極小值，根結(jié)點(diǎn)的估計(jì)值取他的各子結(jié)點(diǎn)的極大值。這個(gè)取得最大估計(jì)值的子結(jié)點(diǎn)即為從S出發(fā)的計(jì)算機(jī)方的最佳落子方案。棋盤(pán)上某一行、某一列或某一對(duì)角線為一路，這里使用的棋盤(pán)為19行19列，因此，行和列方向上共有19+19=38路;從左下到右上方向的對(duì)角線有37路，同樣，從左上到右下方向的對(duì)角線也有37路。但對(duì)于五子棋來(lái)說(shuō)必須在一條直線上有連續(xù)五個(gè)棋子才能贏。因此，在對(duì)角線上就可以減少8路。所以，整個(gè)棋盤(pán)路的總數(shù)為：38+(37-8)+(37-8)=96路。對(duì)某一棋局n[14-15]，第i路得分：
h(i)=h(i)t-hm(i)[1]。
我們不用把每個(gè)節(jié)點(diǎn)都搜索一遍也可獲得和極大極小搜索同樣結(jié)果的走步，不搜索分支節(jié)點(diǎn)而舍棄該分支的過(guò)程叫剪枝。常用的剪枝方法是α-β剪枝算法。
在極大極小搜索的過(guò)程中，存在著一定程度的數(shù)據(jù)冗余。如下圖2所示左半部的一棵極大極小樹(shù)的片斷，節(jié)點(diǎn)下面為該節(jié)點(diǎn)的值，設(shè)A 為極大值節(jié)點(diǎn)，節(jié)點(diǎn)B的值為18，節(jié)點(diǎn)D 的值為16，由此可以判斷節(jié)點(diǎn)C的值將小于等于16(取極小值);而節(jié)點(diǎn)A的值為節(jié)點(diǎn)Max(B，C)，是18，也就是說(shuō)不再需要估節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F的值就可以得出父節(jié)點(diǎn)A 的值了。這樣將節(jié)點(diǎn)D 的后繼兄弟節(jié)點(diǎn)減去稱(chēng)為Alpha剪枝(α剪枝)。如圖2：
同樣道理在圖3右半部一棵極大極小樹(shù)的片段中，設(shè)A為極小值節(jié)點(diǎn)，節(jié)點(diǎn)B的估值為8，節(jié)點(diǎn)D的估值為l8，由此可以判斷節(jié)點(diǎn)C的值將大于等于18(取極大值);而節(jié)點(diǎn)A 的值為Min(B，c)，是8。也就是說(shuō)不再需要求節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F值就可以得出父節(jié)點(diǎn)A 的值了。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)剪去稱(chēng)為Beta剪枝(β剪枝)。如圖3： 將Alpha剪枝和Beta剪枝加入極大極小搜索，就得到α-β搜索算法。
現(xiàn)在假設(shè)五子棋問(wèn)題深度為3的搜索樹(shù)給出α-β剪枝算法，用類(lèi)C語(yǔ)言對(duì)其進(jìn)行描述：
設(shè)電腦為Max，人為Min，初始時(shí)α為-∞，β為+∞;函數(shù)Evalue( )返回對(duì)當(dāng)前局面的估值
在p處下黑子;
if(已到達(dá)搜索的最后一層) return Evalue( );
如果Max(point p，α，β)函數(shù)，則返回對(duì)Max結(jié)點(diǎn)最有利的走步的局勢(shì)靜態(tài)估值函數(shù)值。反之Min (point p， α， β)函數(shù)，則返回對(duì)Min結(jié)點(diǎn)最有利的局勢(shì)靜態(tài)估值函數(shù)值。兩種互為遞歸調(diào)用，可以動(dòng)態(tài)改變搜索深度。
2.2 優(yōu)化估值函數(shù)
通過(guò)以上的研究可以看出，在博弈的程序中電腦的行為都是以估值函數(shù)為依據(jù)的，所以說(shuō)估值函數(shù)在很大的程度上是決定了電腦的棋力高低。我們可以采用遺傳算法來(lái)改進(jìn)靜態(tài)估值。
遺傳算法的優(yōu)點(diǎn)：
(1)由于搜索算法是從問(wèn)題的解開(kāi)始的，而不是一組參數(shù)。所以被局部震蕩干擾導(dǎo)致求最優(yōu)解失敗的可能性大大減小。
(2)此算法能將搜索重點(diǎn)集中于性能高的部分，能較快地求出最佳的參數(shù)。
遺傳算法的優(yōu)化估值參數(shù)的過(guò)程：首先是①隨機(jī)產(chǎn)生幾組參數(shù)作為初始種群;接著②對(duì)種群的參數(shù)進(jìn)行收斂判斷，收斂則③輸出優(yōu)化結(jié)果并且評(píng)估過(guò)程結(jié)束，否則就④執(zhí)行復(fù)制操作產(chǎn)生一組新參數(shù);然后⑤取0、1之間的隨機(jī)數(shù)，讓隨機(jī)數(shù)和交叉概率進(jìn)行比較;若大于⑥則執(zhí)行交叉操作改變新參數(shù)，若小于就不用執(zhí)行這一步;⑦接著取0、1之間的隨機(jī)數(shù)，隨機(jī)數(shù)和變異概率進(jìn)行比較，若⑧大于就執(zhí)行變異操作改變新參數(shù)，小于就不執(zhí)行這一步;接著是⑨把較差的一組參數(shù)從種群中去除;接著跳回第二步判斷是否已經(jīng)收斂，如此循環(huán)就能將搜索重點(diǎn)集中于性能高的部分，能較快地求出最佳的參數(shù)。畫(huà)圖4表示如下：
2.3 禁手特征計(jì)算
五子棋中還有項(xiàng)規(guī)則就是是禁手的判斷，在上邊已經(jīng)給出了3顆棋子的時(shí)候的分值為1000。如果是雙三則需要乘以2，即2000。電腦在分值表中將會(huì)判斷雙三點(diǎn)比一個(gè)三的點(diǎn)更為重要。這在電腦進(jìn)行全局判斷的時(shí)候也是正確的，可是如果電腦執(zhí)黑子，這一點(diǎn)是不能落子的，否則將導(dǎo)致失敗。但是電腦不能真的會(huì)自己去判斷，只有認(rèn)為的給他一個(gè)判斷的標(biāo)準(zhǔn)，處理的方法是：在累加分值的時(shí)候增加一個(gè)判斷語(yǔ)句，如果正好形成雙三，那么這一點(diǎn)不加入分值表同時(shí)判斷此點(diǎn)落棋將判為負(fù)，其他禁手按同樣的方法處理。
3、結(jié)論及展望未來(lái)
3.1總結(jié)
本文介紹了應(yīng)用人工智能設(shè)計(jì)五子棋的總體方法。用極大極小值的過(guò)程以及啟發(fā)式搜索的方法，采用靜態(tài)估值函數(shù)對(duì)各節(jié)點(diǎn)的代價(jià)進(jìn)行估計(jì)，應(yīng)用遺傳算法對(duì)估計(jì)的值進(jìn)行了優(yōu)化，克服了人為主觀因素的片面性。對(duì)博弈的研究具有一定的借鑒意義。在實(shí)際五子棋系統(tǒng)的設(shè)計(jì)中。應(yīng)用本方法只向前搜索了三步，就可以取得很好的效果。也可以增加搜索的深度來(lái)提高系統(tǒng)的判斷能力，但是是以犧牲電腦的運(yùn)算速度為前提的，畢竟加深搜索的話就需要更大的運(yùn)算量。此外，也可以通過(guò)增加機(jī)器學(xué)習(xí)，比如電腦對(duì)棋局進(jìn)行記憶，在對(duì)手落子之前對(duì)棋局和之前記憶的棋局進(jìn)行比較，先判斷出更優(yōu)的走法，就可以進(jìn)一步提高系統(tǒng)的智能。
3.2 未來(lái)展望
隨著Intel HP(超線程技術(shù))的實(shí)現(xiàn)和將來(lái)多處理器PC機(jī)的普及.對(duì)于數(shù)據(jù)計(jì)算量大的人機(jī)對(duì)弈問(wèn)題必然要求應(yīng)用并行的思想去處理。超快搜索速度和必要的復(fù)盤(pán)“反思”必然帶給下棋電腦更多智慧。
參考文獻(xiàn)：
[1]蔡自興.人工智能及其應(yīng)用[M].北京：清華大學(xué)出版社，1999
[2]閻平凡.人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算[M].北京：清華大學(xué)出版社，2002
[3]王小春.游戲編程(人機(jī)博弈)[M].重慶：重慶大學(xué)出版社，2002
[4]Nils J Nilsson，鄭扣根，莊越挺譯.Artificial Intelligence A New Synthesis[M].北京：機(jī)械工業(yè)出版社，2000
[5]陳爾紹.傳感器實(shí)用裝置制作集錦[M].北京：人民郵電出版社，1999
[6]鄧天炎，李?lèi)?ài)華，尹正主編.離散數(shù)學(xué)教程[M].徐州：中國(guó)礦業(yè)大學(xué)出版社，2002
[7]潘金貴，顧鐵成，曾儉等編譯.現(xiàn)代計(jì)算機(jī)常用數(shù)據(jù)結(jié)構(gòu)和算法[M].南京：南京大學(xué)出版社，1994
[8]王小平.遺傳算法-理論應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，1998
[9]王永慶.人工智能原理與方法[M].西安：西安交通大學(xué)出版社，1998
[10]林堯瑞，馬少平.人工智能導(dǎo)論[M].北京：清華出版社，1989
[11]田盛豐，黃厚寬.人工智能與知識(shí)工程[M].北京：中國(guó)鐵道出版社，1999
[12]陸汝鈐.人工智能[M].北京：科學(xué)出版社，1995
[13]王鐫.博弈樹(shù)搜索的算法改進(jìn)[J].福建電腦.2004，(2)
[14]蔣加伏，陳藹樣，唐賢英.基于知識(shí)推理的博弈樹(shù)搜索算法[J].計(jì)算機(jī)工程與應(yīng)用，2004，(1)
[15]Nilsson NJ.人工智能[M].北京：機(jī)械工業(yè)出版社，2000
下一頁(yè)分享更優(yōu)秀的<<<人工智能五子棋論文