五子棋人工智能算法實(shí)現(xiàn)研究五子棋是一種兩人對(duì)弈的純策略型棋類游戲，是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”等多種稱謂［1］。因其規(guī)則簡(jiǎn)單，變化多端，容易上手，而廣受大眾喜愛。五子棋游戲不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋游戲規(guī)則比較簡(jiǎn)單，棋盤通常采用類似圍棋盤的15路或19路的棋盤，兩人分別執(zhí)黑白兩色棋子，輪流在棋盤上選擇一個(gè)無子的交叉點(diǎn)落子，無子的交叉點(diǎn)又被稱為空點(diǎn)或合法點(diǎn)，當(dāng)黑白一方有五個(gè)棋子在橫、豎或斜方向上連接成一線即為該方贏。人工智能，是計(jì)算機(jī)科學(xué)的一個(gè)分支，是研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的綜合性的技術(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剪枝和最大最小樹原理，優(yōu)化了博弈樹搜索過程，通過控制搜索深度，實(shí)現(xiàn)了初級(jí)和高級(jí)的人機(jī)對(duì)弈。此外，本文還對(duì)優(yōu)化五子棋智能算法的思路做出了初步探討。一、五子棋傳統(tǒng)算法.人機(jī)博弈傳統(tǒng)算法。解決博弈問題的傳統(tǒng)算法是搜索樹法，也叫博弈樹法。以甲乙兩人對(duì)弈五子棋為例，假定現(xiàn)在該甲走棋且甲有若干種走法，而對(duì)甲的任一走法，乙也可以有與之對(duì)應(yīng)的不同的多種走法，然后又輪到甲走棋，而對(duì)乙的走法甲又有若干種方法應(yīng)對(duì)，如此反復(fù)。顯然，可以從當(dāng)前棋局狀態(tài)出發(fā)，找出所有可能的乙的走法，再?gòu)拿總€(gè)子節(jié)點(diǎn)出發(fā)找出甲對(duì)應(yīng)于每個(gè)乙的走法的所有應(yīng)對(duì)，直到出現(xiàn)一方贏局。由此構(gòu)成的樹，就稱為博弈樹。對(duì)于19*19的棋盤而言，顯然這是一個(gè)典型的指數(shù)復(fù)雜度問題，其計(jì)算量之大是目前所有的計(jì)算機(jī)都無法承受的。因此，用搜索樹法來解決人機(jī)博弈時(shí)，通常只能搜索到一個(gè)非常有限的深度，并根據(jù)此有限深度的形勢(shì)來判斷每種走法的優(yōu)劣，從而選擇較優(yōu)位置下子。.極小極大值算法。極小極大算法［3］是考慮雙方對(duì)弈聯(lián)盟若干步之后，從可能的走法中選一步相對(duì)好的來走。若最大節(jié)點(diǎn)為己方下的棋，此時(shí)選擇估值最大的點(diǎn)走。最小節(jié)點(diǎn)為對(duì)方下的棋，此時(shí)選擇估值最小的點(diǎn)行走。因此MIN節(jié)點(diǎn)的父節(jié)點(diǎn)所賦的倒推值等于端節(jié)點(diǎn)估值中的最大值。另一方面，MAX節(jié)點(diǎn)的父節(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ǔ)上提出了a-p剪枝技術(shù)。.a-p剪枝算法。a-p剪枝算法［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)拋棄，此過程稱為剪枝。如果甲所在的層是MAX節(jié)點(diǎn)的層，則稱此剪枝為a剪枝，否則成為p剪枝。如圖1左半部所示的一棵極大極小樹的片斷。其中節(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)通過估值得出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,說明節(jié)點(diǎn)A的值為Max=18,也就是說無須求出節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F的值就可以得出父節(jié)點(diǎn)A的值。這種將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)剪去的方法稱為Alpha剪枝。同理，在圖1右半部一棵極大極小樹的片段中，將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)剪去稱為Beta剪枝。與極小極大算法相比，a-p剪枝需要遍歷的節(jié)點(diǎn)遠(yuǎn)遠(yuǎn)減少，它能在較短的時(shí)間內(nèi)找到最佳的走法節(jié)點(diǎn)。二、五子棋智能算法實(shí)現(xiàn)及優(yōu)化1.估值函數(shù)。為使用極大極小算法，需要對(duì)一個(gè)估值函數(shù)Eval對(duì)當(dāng)前棋局進(jìn)行估值，p是當(dāng)前局面。即由這個(gè)估值函數(shù)確定哪個(gè)局面更好，如果Eval2.算法實(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的五子棋棋盤而言，傳統(tǒng)算法中計(jì)算機(jī)每走一步都要遍歷整個(gè)棋盤，對(duì)棋面上所有空位都進(jìn)行試探性下子并估值，大大影響了算法的效率。本文采用在某個(gè)時(shí)只要考慮距以棋子為中心邊長(zhǎng)為4的正方形區(qū)域即可，這樣便縮小了搜索空間，提高搜索效率。減少計(jì)算量。為進(jìn)一步減少計(jì)算量，提高計(jì)算機(jī)反應(yīng)速度，通過以空間換時(shí)間的方法，在游戲過程中維持一個(gè)棋盤所有位置的估值信息的數(shù)組。每次對(duì)棋盤上的每個(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)等，并通過減少搜索范圍、減少計(jì)算量和設(shè)置對(duì)弈等級(jí)的方法