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