五子棋人工智能算法實(shí)現(xiàn)研究

段曉麗

摘 要：人工智能是一門(mén)正在迅速發(fā)展的新興綜合學(xué)科，博弈是其主要研究領(lǐng)域之一。五子棋游戲，其規(guī)則簡(jiǎn)單，但變化多端，適宜于研究分析人機(jī)博弈算法。本文設(shè)計(jì)實(shí)現(xiàn)了五子棋人工智能功能，主要采用Alpha-Beta剪枝和MinMax算法，優(yōu)化博弈樹(shù)搜索過(guò)程，通過(guò)控制搜索深度，實(shí)現(xiàn)初級(jí)和高級(jí)的人機(jī)對(duì)弈。本文還提出了優(yōu)化五子棋智能算法的思路，并做出了初步探討。

關(guān)鍵詞：人工智能；五子棋；Alpha-Beta搜索

五子棋是一種兩人對(duì)弈的純策略型棋類游戲，是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一?，F(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)走。最?。∕IN）節(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）

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í)功能等。

參考文獻(xiàn)：

[1] 百度百科：五子棋[EB/OL]。http：//baike.baidu.com/view

/2697.htm。

[2] 王長(zhǎng)飛，蔡強(qiáng)，李海生。智能五子棋算法的設(shè)計(jì)實(shí)現(xiàn)[J]?！断到y(tǒng)仿真學(xué)報(bào)》，2009.

摘 要：人工智能是一門(mén)正在迅速發(fā)展的新興綜合學(xué)科，博弈是其主要研究領(lǐng)域之一。五子棋游戲，其規(guī)則簡(jiǎn)單，但變化多端，適宜于研究分析人機(jī)博弈算法。本文設(shè)計(jì)實(shí)現(xiàn)了五子棋人工智能功能，主要采用Alpha-Beta剪枝和MinMax算法，優(yōu)化博弈樹(shù)搜索過(guò)程，通過(guò)控制搜索深度，實(shí)現(xiàn)初級(jí)和高級(jí)的人機(jī)對(duì)弈。本文還提出了優(yōu)化五子棋智能算法的思路，并做出了初步探討。

關(guān)鍵詞：人工智能；五子棋；Alpha-Beta搜索

五子棋是一種兩人對(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)走。最?。∕IN）節(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）

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í)功能等。

參考文獻(xiàn)：

[1] 百度百科：五子棋[EB/OL]。http：//baike.baidu.com/view

/2697.htm。

[2] 王長(zhǎng)飛，蔡強(qiáng)，李海生。智能五子棋算法的設(shè)計(jì)實(shí)現(xiàn)[J]?！断到y(tǒng)仿真學(xué)報(bào)》，2009.

摘 要：人工智能是一門(mén)正在迅速發(fā)展的新興綜合學(xué)科，博弈是其主要研究領(lǐng)域之一。五子棋游戲，其規(guī)則簡(jiǎn)單，但變化多端，適宜于研究分析人機(jī)博弈算法。本文設(shè)計(jì)實(shí)現(xiàn)了五子棋人工智能功能，主要采用Alpha-Beta剪枝和MinMax算法，優(yōu)化博弈樹(shù)搜索過(guò)程，通過(guò)控制搜索深度，實(shí)現(xiàn)初級(jí)和高級(jí)的人機(jī)對(duì)弈。本文還提出了優(yōu)化五子棋智能算法的思路，并做出了初步探討。

關(guān)鍵詞：人工智能；五子棋；Alpha-Beta搜索

五子棋是一種兩人對(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)走。最?。∕IN）節(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）

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í)功能等。

參考文獻(xiàn)：

[1] 百度百科：五子棋[EB/OL]。http：//baike.baidu.com/view

/2697.htm。

[2] 王長(zhǎng)飛，蔡強(qiáng)，李海生。智能五子棋算法的設(shè)計(jì)實(shí)現(xiàn)[J]?！断到y(tǒng)仿真學(xué)報(bào)》，2009.