人工智能五子棋論文(2)
人工智能五子棋論文篇二
五子棋人工智能算法實現(xiàn)研究
五子棋是一種兩人對弈的純策略型棋類游戲，是起源于中國古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”(Five in a Row的縮寫)，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”等多種稱謂[1]。因其規(guī)則簡單，變化多端，容易上手，而廣受大眾喜愛。五子棋游戲不僅能增強思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋游戲規(guī)則比較簡單，棋盤通常采用類似圍棋盤的15路或19路的棋盤，兩人分別執(zhí)黑白兩色棋子，輪流在棋盤上選擇一個無子的交叉點落子，無子的交叉點又被稱為空點或合法點，當(dāng)黑白一方有五個棋子在橫、豎或斜方向上連接成一線即為該方贏。
人工智能(Artificial Intelligence，AI)，是計算機科學(xué)的一個分支，是研究、開發(fā)用于模擬、延伸和擴展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的綜合性的技術(shù)科學(xué)。該領(lǐng)域的研究包括機器人、語言識別、圖像識別、自然語言處理和專家系統(tǒng)等，而博弈是人工智能研究的一個重要分支。它不僅存在于游戲、下棋之中，也存在于政治、經(jīng)濟(jì)、軍事和生物競爭中。與其他棋類游戲相比，五子棋游戲每一層棋局搜索節(jié)點數(shù)量龐大，規(guī)則簡單，更便于深入研究博弈算法。本文以五子棋游戲為研究對象，采用Alpha-Beta剪枝和最大最小樹原理，優(yōu)化了博弈樹搜索過程，通過控制搜索深度，實現(xiàn)了初級和高級的人機對弈。此外，本文還對優(yōu)化五子棋智能算法的思路做出了初步探討。
一、 五子棋傳統(tǒng)算法
1.人機博弈傳統(tǒng)算法。
解決博弈問題的傳統(tǒng)算法是搜索樹法，也叫博弈樹法。以甲乙兩人對弈五子棋為例，假定現(xiàn)在該甲走棋且甲有若干種走法，而對甲的任一走法，乙也可以有與之對應(yīng)的不同的多種走法，然后又輪到甲走棋，而對乙的走法甲又有若干種方法應(yīng)對，如此反復(fù)。顯然，可以從當(dāng)前棋局狀態(tài)(根節(jié)點)出發(fā)，找出所有可能的乙的走法(子節(jié)點)，再從每個子節(jié)點出發(fā)找出甲對應(yīng)于每個乙的走法的所有應(yīng)對(子子節(jié)點)，直到出現(xiàn)一方贏局。由此構(gòu)成的樹，就稱為博弈樹。對于19*19的棋盤而言，顯然這是一個典型的指數(shù)復(fù)雜度問題，其計算量之大是目前所有的計算機都無法承受的。因此，用搜索樹法來解決人機博弈時，通常只能搜索到一個非常有限的深度，并根據(jù)此有限深度的形勢來判斷每種走法的優(yōu)劣，從而選擇較優(yōu)位置下子。
2. 極小極大值算法(MinMax 算法)。
極小極大算法[3]是考慮雙方對弈若干步之后， 從可能的走法中選一步相對好的來走。若最大(MAX)節(jié)點為己方下的棋，此時選擇估值最大的點走。最小(MIN)節(jié)點為對方下的棋，此時選擇估值最小的點行走。因此MIN節(jié)點的父節(jié)點(MAX節(jié)點)所賦的倒推值等于端節(jié)點估值中的最大值。另一方面，MAX節(jié)點的父節(jié)點(MIN節(jié)點)所賦的倒推值等于端節(jié)點估值中的最小值。這樣一級一級地計算倒推值，直至起始節(jié)點的后繼節(jié)點也被賦以倒推值為止，即從下往上逐層交替使用極小極大的選值方法。但當(dāng)搜索深度增加時，搜索節(jié)點快速大幅增加，時間和內(nèi)存空間消耗太大，且利用先前信息的效率較低。于是人們在極小極大的基礎(chǔ)上提出了α-β剪枝技術(shù)。
3. α-β剪枝算法。
α-β剪枝算法[2]是在極大極小算法的基礎(chǔ)上，當(dāng)甲向下搜索節(jié)點時發(fā)現(xiàn)走第一個子節(jié)點就可以贏了，則剩下的節(jié)點就不需要再搜索，甲的值就是第一個子節(jié)點的值。即可以將甲的其余后繼節(jié)點拋棄，此過程稱為剪枝。如果甲所在的層是MAX 節(jié)點的層，則稱此剪枝為α剪枝，否則成為β剪枝。如圖1左半部所示的一棵極大極小樹的片斷。其中節(jié)點下方數(shù)字為該節(jié)點的值，方形框節(jié)點代表計算機走，圓形框節(jié)點代表人走。A節(jié)點表示計算機走，由于A是極大值點，根據(jù)極小極大搜索原理它要從B和C當(dāng)中選最大的值。假設(shè)目前已經(jīng)通過估值得出B為18，當(dāng)搜索C節(jié)點時，因為C是該人走，所以根據(jù)極小極大搜索原理要從D、E、F中選取最小的值。此時如果估出D為16，那么C的值必小于或等于16。又因為已經(jīng)得出B的值為18，說明節(jié)點A的值為Max(B，C)=18，也就是說無須求出節(jié)點C的其他子節(jié)點如E、F的值就可以得出父節(jié)點A的值。這種將節(jié)點D 的后繼兄弟節(jié)點剪去的方法稱為Alpha剪枝。
同理，在圖1右半部一棵極大極小樹的片段中，將節(jié)點D 的后繼兄弟節(jié)點剪去稱為Beta 剪枝。與極小極大算法相比，α-β剪枝需要遍歷的節(jié)點遠(yuǎn)遠(yuǎn)減少，它能在較短的時間內(nèi)找到最佳的走法節(jié)點。
二、 五子棋智能算法實現(xiàn)及優(yōu)化
1. 估值函數(shù)。
為使用極大極小算法，需要對一個估值函數(shù)Eval (p)對當(dāng)前棋局進(jìn)行估值，p是當(dāng)前局面。即由這個估值函數(shù)確定哪個局面更好，如果Eval(p1)<eval(p2)，我們就有理由相信，p2比p1更好。對于五子棋而言，由其勝負(fù)判定規(guī)則可以很容易設(shè)定不同的棋型的優(yōu)先級，從而得到比較合理的估值函數(shù)。例如，四個棋子連成一線且還能繼續(xù)落子的棋型(活四)顯然要比只有三個棋子連成一線(活三或死三)好。另外，為了盡可能地加快搜索速度，估值函數(shù)應(yīng)設(shè)計的越仔細(xì)越好。估值時，需要從四個方向上來考慮所下棋子對當(dāng)前盤面的影響。這四個方向分別是以該棋子為出發(fā)點，水平、豎直和兩條為45度角和135度角的線。算法中關(guān)于棋子死活的規(guī)定如下：一方落子后，它的落子連成的一條線有兩條不損傷的出路，則稱該棋型是活的。否則稱該棋型是死的。比如關(guān)于活三的定義：不論對手如何落子，仍然至少有一種方法可以沖四。因此，b?aaa? B中的三個A，不能算是活三;B?AAAB中的三個A，也不是活三，盡管它有可能成為活四。這樣，棋型的估值設(shè)計才能比較細(xì)致。本文算法對特定棋型的估值如表1所示。="" <br=""> 2. 算法實現(xiàn)及優(yōu)化
使用以上定義的估值函數(shù)和描述的算法，可以實現(xiàn)基本的人機對弈。但是在實現(xiàn)中，由于搜索深度增加后運算量呈指數(shù)級數(shù)增加，運算效率急劇下降。為提高搜索效率，增進(jìn)用戶體驗，提出以下優(yōu)化改進(jìn)方法：
減少搜索范圍。對于19*19的五子棋棋盤而言，傳統(tǒng)算法中計算機每走一步都要遍歷整個棋盤，對棋面上所有空位都進(jìn)行試探性下子并估值，大大影響了算法的效率。本文采用在某個時只要考慮距以棋子為中心邊長為4的正方形區(qū)域即可，這樣便縮小了搜索空間，提高搜索效率。
減少計算量。為進(jìn)一步減少計算量，提高計算機反應(yīng)速度，通過以空間換時間的方法，在游戲過程中維持一個棋盤所有位置的估值信息的數(shù)組。每次對棋盤上的每個位置的當(dāng)前估值進(jìn)行計算后，存儲在當(dāng)前棋局信息中。當(dāng)新的棋局產(chǎn)生時，只需更新計算新下子位置和相關(guān)位置的估值，而對其他可下子位置的估值只需查詢上步棋局信息即可。這樣保持的估值表雖然增大了空間需求，但可以大大減少搜索算法的估值計算時間，提高了算法執(zhí)行效率。
三、 結(jié)論及后續(xù)工作
本文主要論述了五子棋游戲的基本游戲規(guī)則，傳統(tǒng)五子棋人機對弈游戲的基本算法，描述了算法實現(xiàn)的MinMax算法和Alpha-Beta剪枝算法，并描述了算法實現(xiàn)的估值函數(shù)定義、數(shù)據(jù)結(jié)構(gòu)等，并通過減少搜索范圍、減少計算量和設(shè)置對弈等級的方法，對算法進(jìn)行初步優(yōu)化，提高了算法性能，增進(jìn)了人機對弈的用戶體驗。下步工作主要是通過改進(jìn)算法和增加搜索輔助手段的方式，探索分析優(yōu)化搜索性能的方法。比如[2]，結(jié)合使用啟發(fā)式搜索，利用五子棋游戲開局階段現(xiàn)成的棋譜，進(jìn)行啟發(fā)式搜索，或者加入自學(xué)習(xí)功能等。
人工智能五子棋論文相關(guān)文章：
1.人工智能資料介紹