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