基于計(jì)算機(jī)博弈的五子棋AI設(shè)計(jì)

1、    基于計(jì)算機(jī)博弈的五子棋ai設(shè)計(jì)    鄭培銘+何麗摘要：介紹計(jì)算機(jī)博弈基礎(chǔ)算法及部分優(yōu)化算法，根據(jù)五子棋的規(guī)則，提出了針對五子棋的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)，嘗試將計(jì)算機(jī)博弈算法應(yīng)用于五子棋，設(shè)計(jì)并實(shí)現(xiàn)了一個五子棋ai，并在國際賽事中取得良好成績；實(shí)驗(yàn)證實(shí)使用置換表與pvs（principal variation search）算法后搜索效率顯著提高。關(guān)鍵詞：五子棋；人工智能；博弈樹算法：tp181 ：a ：1009-3044（2016）33-0080-02abstract： this paper introduces the basic algorit

2、hm of machine game and some optimization algorithms. according to the rules of gomoku， the paper presents the data structure and algorithm for gomoku. it tries to apply game tree algorithm to gomoku， designs and implements a gomoku ai， and achieves good results in international competitions. ； the e

3、xperiment proves that the search efficiency is significantly improved by using the substitution table and pvs （principal variation search） algorithm.key words： gomoku； artificial intelligence； game tree algorithm1 概述人工智能是一門正在迅速發(fā)展的新興的綜合性很強(qiáng)的學(xué)科。它與生物工程、空間技術(shù)一起被并列為當(dāng)今三大尖端技術(shù)。人工智能的中心任務(wù)是研究如何使計(jì)算機(jī)去做那些過去只能靠人的智力才

4、能做的工作。人工智能有諸多領(lǐng)域，博弈就是其中一種。博弈的參加者可以是個人、集體、一類生物或機(jī)器。他們都力圖用自己的智力去擊敗對手， 博弈為人工智能提供了一個很好的試驗(yàn)場所。人工智能中許多概念和方法都是從博弈程序中提煉出來，并在新的技術(shù)中獲得應(yīng)用。許多研究成果已用于軍事指揮和經(jīng)濟(jì)決策系統(tǒng)之中。博弈問題中，最經(jīng)典的就是棋類博弈。在此以五子棋為研究樣例，基于針對五子棋設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)與算法，實(shí)現(xiàn)了經(jīng)典的計(jì)算機(jī)博弈算法。旨在證實(shí)計(jì)算機(jī)博弈算法的普適性，證明針對五子棋設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法的高效。2 關(guān)鍵技術(shù)分析2.1博弈樹搜索算法任何棋類游戲都要定義一棵由博弈狀態(tài)為節(jié)點(diǎn)的樹（即“博弈樹”），一個結(jié)點(diǎn)就代表棋

5、類的一個局面，子結(jié)點(diǎn)就是這個局面進(jìn)行一次狀態(tài)轉(zhuǎn)移可以到達(dá)的局面。根節(jié)點(diǎn)由決策方開始進(jìn)行狀態(tài)轉(zhuǎn)移。博弈樹的葉子節(jié)點(diǎn)為終結(jié)狀態(tài)，即平局或者一方獲勝。許多博弈問題可以使用博弈樹搜索算法解決。處于樹底層的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)（leaf node），葉結(jié)點(diǎn)的祖先稱為內(nèi)部結(jié)點(diǎn)（interior node）。一個問題空間（problem space）是一個狀態(tài)（state）和實(shí)現(xiàn)狀態(tài)之間映射的操作（state）的集合。在博弈問題中，博弈樹上的一個內(nèi)部結(jié)點(diǎn)或葉結(jié)點(diǎn)就是一個狀態(tài)，一般稱為位置（position）。狀態(tài)轉(zhuǎn)移（move）是將一個位置轉(zhuǎn)化為其子位置（successor position）的操作。如果一個位置

6、是博弈樹的葉結(jié)點(diǎn)，可以用估值函數(shù)（evaluator）來對其優(yōu)劣進(jìn)行評分（evaluate）。根據(jù)估值函數(shù)，博弈樹中的每個葉結(jié)點(diǎn)都有一對應(yīng)值（value）。博弈樹搜索的目的就是找出博弈樹的值（game tree value）。博弈樹的值（下面簡稱博弈值）指的是博弈樹中一個子結(jié)點(diǎn)的值，該值對于博弈雙方都是最優(yōu)的。博弈樹的子樹在該子樹搜索完成之后也會返回一個博弈值，該值是子樹的局部最優(yōu)值。計(jì)算一棵博弈樹的博弈值，可以使用基本的極大極小樹搜索（min-max tree search）。為了減少搜索的節(jié)點(diǎn)數(shù)，可以使用alpha-beta算法進(jìn)行剪枝。在alpha-beta算法的基礎(chǔ)上，各種改進(jìn)方法被先

7、后提出來，例如置換表，pvs算法以及并行alpha-beta算法。在博弈樹搜索算法方面，前人做了許多豐富而充滿意義的研究工作。2.1針對alpha-beta算法的改進(jìn)在alpha-beta算法被廣泛運(yùn)用后，對該算法的很多改進(jìn)算法也相繼被提出.這些改進(jìn)算法主要在以下幾個方面對alpha-beta算法進(jìn)行改進(jìn)：1）擇序。在搜索博弈樹時，內(nèi)部結(jié)點(diǎn)有多個可能的狀態(tài)轉(zhuǎn)移。擇序指的是搜索這些分支的順序。在alpha-beta算法中，提高擇序的好壞就意味著提高剪枝發(fā)生的概率。所以一個好的狀態(tài)轉(zhuǎn)移可以定義為：導(dǎo)致剪枝的移動?；蛘呷绻麤]有導(dǎo)致剪枝，但是產(chǎn)生了最小最大值。一個好的狀態(tài)轉(zhuǎn)移并不一定是最優(yōu)的狀態(tài)轉(zhuǎn)移（

8、best move），因?yàn)橐粋€導(dǎo)致剪枝的狀態(tài)轉(zhuǎn)移可能引起了該子結(jié)點(diǎn)上的搜索停止，但是并不意味著其后的子結(jié)點(diǎn)的搜索不會產(chǎn)生一個更好的值。2）搜索窗口的大小。搜索窗口的大小指的是和之差.搜索窗口越小，發(fā)生剪枝的概率越大。3）信息的重用。保存子樹的搜索結(jié)果，并審查這棵子樹是否在隨后的搜索中再次出現(xiàn)。如果該子樹再次出現(xiàn)，那么關(guān)于子樹的搜索結(jié)果的信息就可重復(fù)使用。常見的改進(jìn)算法有迭代加深算法、pvs（principal variation search）算法與置換表等。實(shí)驗(yàn)證實(shí)，使用置換表與迭代加深算法提供啟發(fā)性的估值，并用于狀態(tài)轉(zhuǎn)移的排序后，良有序的狀態(tài)轉(zhuǎn)移使pvs有更高的效率。使得搜索效率大幅提高。

9、 3 五子棋數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)3.1 棋盤數(shù)據(jù)結(jié)構(gòu)由于在pc上棋盤的訪問不是性能瓶頸，所以我們用可讀性較強(qiáng)的方法來定義顯式的棋盤，通過調(diào)用指定接口落子，我們還能維護(hù)一個編碼后的棋盤。1）顯式的棋盤定義一個boardsizesize數(shù)組。其中，size是指可落子的棋盤范圍+8。因?yàn)樵谂袛嗥逍偷倪^程中，需要訪問相鄰4格內(nèi)的點(diǎn)（9格棋型：4 + 1 + 4 = 9），為了便于操作與編碼，在棋盤圍增加4格的預(yù)留空間。2）編碼后的棋盤首先我們分別定義二進(jìn)制數(shù)002，012，102為空、黑、白狀態(tài)，112為預(yù)留空間。再定義四個數(shù)組lpos，rpos，rpos，wpos，其中保存著在四個方向（橫豎撇捺）上棋

10、盤的二進(jìn)制編碼。例如111111110000011111111就是5*5的空棋盤在第一行上的編碼。也就是說，在二進(jìn)制棋盤中，每一個格子占兩個比特。3.2著法生成著法生成是指，一個局面（狀態(tài)）下有幾個可能的走法（狀態(tài)轉(zhuǎn)移）。最簡單的著法生成是將所有空點(diǎn)納入著法序列。但實(shí)際上，有價值的走法一般在已落子的點(diǎn)相鄰3格內(nèi)。所以只需維護(hù)一個表csizesize，其中cij保存著點(diǎn)i， j三個內(nèi)的棋子數(shù)。這些信息同樣可以用于擇序。3.3 著法擇序使用估值函數(shù)evaluate（）得到值v。3.4棋型與棋型表各種棋型的定義。一個棋型只能有一個類型。優(yōu)先級從高到低。1.成五：連續(xù)的五個及以上的同色棋子的棋型。2.

11、活四：有兩個落同樣顏色子后能成五的點(diǎn)的棋型。3.沖四：只有一個點(diǎn)落同樣顏色子后能成五的棋型。4.活三：有落子后能成活四的點(diǎn)的棋型。5.眠三：有落子后能成沖四的點(diǎn)的棋型。6.活二：有落子后能成活三的點(diǎn)的棋型。7.眠二：有落子后能成眠三的點(diǎn)的棋型。8.活一：有落子后能成活二的點(diǎn)的棋型。9.眠一：有落子后能成眠二的點(diǎn)的棋型。10.無效：雙方都不可能成五的棋型。根據(jù)這些規(guī)則，可以遞歸的生成可查詢的棋型表pattern。顯然，棋型表的大小只與棋型長度有關(guān)，一個長9格的棋型對應(yīng)18位的編碼?？汕蟪銎逍捅淼拇笮?18 byte。即使棋型拓展到11格，222 byte 也是可以接受的大小。3.5 估值設(shè)計(jì)定

12、義向量v （v1， v2， v3 . ， v10） 分別對應(yīng)十種棋型的分值（value）。定義向量c （c1， c2， c3 . ， c10） 分別對應(yīng)棋盤上十種棋型的數(shù)量。通過手動設(shè)置或者調(diào)參算法給定v以后，在搜索過程中維護(hù)c。到達(dá)葉節(jié)點(diǎn)時調(diào)用估值函數(shù)。估值函數(shù)執(zhí)行簡單的向量運(yùn)算。向量運(yùn)算可以使用simd進(jìn)行優(yōu)化，從而得到更高的效率。3.5 實(shí)驗(yàn)數(shù)據(jù)及結(jié)果利用本文設(shè)計(jì)的五子棋數(shù)據(jù)結(jié)構(gòu)和對博弈算法的改進(jìn)；實(shí)現(xiàn)了一個五子棋ai，在國際賽事中取得良好成績。結(jié)果如下所示。其中chis為本文實(shí)現(xiàn)的ai。 gomocup 1的結(jié)果為決賽，gomocup 2為半決賽。chis在freestyle中獲得第13名。4 結(jié)論經(jīng)過與世界排名靠前的ai進(jìn)行對比測試，本文設(shè)計(jì)并實(shí)現(xiàn)的ai取得了快棋（fastgame）第11名與自由規(guī)則（freestyle）第13名的良好成績。從而證實(shí)了經(jīng)典博弈算法對特定博弈問題具有普適性，五子棋博弈系統(tǒng)對特定