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

1、    基于計(jì)算機(jī)博弈的五子棋ai設(shè)計(jì)    鄭培銘+何麗摘要：介紹計(jì)算機(jī)博弈基礎(chǔ)算法及部分優(yōu)化算法，根據(jù)五子棋的規(guī)則，提出了針對(duì)五子棋的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)，嘗試將計(jì)算機(jī)博弈算法應(yīng)用于五子棋，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)五子棋ai，并在國(guó)際賽事中取得良好成績(jī)；實(shí)驗(yàn)證實(shí)使用置換表與pvs（principal variation search）算法后搜索效率顯著提高。關(guān)鍵詞：五子棋；人工智能；博弈樹(shù)算法：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 概述人工智能是一門(mén)正在迅速發(fā)展的新興的綜合性很強(qiáng)的學(xué)科。它與生物工程、空間技術(shù)一起被并列為當(dāng)今三大尖端技術(shù)。人工智能的中心任務(wù)是研究如何使計(jì)算機(jī)去做那些過(guò)去只能靠人的智力才

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

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

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

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

8、best move），因?yàn)橐粋€(gè)導(dǎo)致剪枝的狀態(tài)轉(zhuǎn)移可能引起了該子結(jié)點(diǎn)上的搜索停止，但是并不意味著其后的子結(jié)點(diǎn)的搜索不會(huì)產(chǎn)生一個(gè)更好的值。2）搜索窗口的大小。搜索窗口的大小指的是和之差.搜索窗口越小，發(fā)生剪枝的概率越大。3）信息的重用。保存子樹(shù)的搜索結(jié)果，并審查這棵子樹(shù)是否在隨后的搜索中再次出現(xiàn)。如果該子樹(shù)再次出現(xiàn)，那么關(guān)于子樹(shù)的搜索結(jié)果的信息就可重復(fù)使用。常見(jiàn)的改進(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 棋盤(pán)數(shù)據(jù)結(jié)構(gòu)由于在pc上棋盤(pán)的訪問(wèn)不是性能瓶頸，所以我們用可讀性較強(qiáng)的方法來(lái)定義顯式的棋盤(pán)，通過(guò)調(diào)用指定接口落子，我們還能維護(hù)一個(gè)編碼后的棋盤(pán)。1）顯式的棋盤(pán)定義一個(gè)boardsizesize數(shù)組。其中，size是指可落子的棋盤(pán)范圍+8。因?yàn)樵谂袛嗥逍偷倪^(guò)程中，需要訪問(wèn)相鄰4格內(nèi)的點(diǎn)（9格棋型：4 + 1 + 4 = 9），為了便于操作與編碼，在棋盤(pán)圍增加4格的預(yù)留空間。2）編碼后的棋盤(pán)首先我們分別定義二進(jìn)制數(shù)002，012，102為空、黑、白狀態(tài)，112為預(yù)留空間。再定義四個(gè)數(shù)組lpos，rpos，rpos，wpos，其中保存著在四個(gè)方向（橫豎撇捺）上棋

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

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

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