基于計(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)了一個(gè)五子棋AI，并在國際賽事中取得良好成績；實(shí)驗(yàn)證實(shí)使用置換表與PVS（Principal Variation Search）算法后搜索效率顯著提高。

關(guān)鍵詞：五子棋；人工智能；博弈樹算法

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）33-0080-02

Abstract： This paper introduces the basic algorithm 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 experiment 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 algorithm

1 概述

人工智能是一門正在迅速發(fā)展的新興的綜合性很強(qiáng)的學(xué)科。它與生物工程、空間技術(shù)一起被并列為當(dāng)今三大尖端技術(shù)。人工智能的中心任務(wù)是研究如何使計(jì)算機(jī)去做那些過去只能靠人的智力才能做的工作。人工智能有諸多領(lǐng)域，博弈就是其中一種。

博弈的參加者可以是個(gè)人、集體、一類生物或機(jī)器。他們都力圖用自己的智力去擊敗對手， 博弈為人工智能提供了一個(gè)很好的試驗(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)的樹（即“博弈樹”），一個(gè)結(jié)點(diǎn)就代表棋類的一個(gè)局面，子結(jié)點(diǎn)就是這個(gè)局面進(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）。

一個(gè)問題空間（problem space）是一個(gè)狀態(tài)（state）和實(shí)現(xiàn)狀態(tài)之間映射的操作（state）的集合。在博弈問題中，博弈樹上的一個(gè)內(nèi)部結(jié)點(diǎn)或葉結(jié)點(diǎn)就是一個(gè)狀態(tài)，一般稱為位置（position）。狀態(tài)轉(zhuǎn)移（move）是將一個(gè)位置轉(zhuǎn)化為其子位置（successor position）的操作。如果一個(gè)位置是博弈樹的葉結(jié)點(diǎn)，可以用估值函數(shù)（evaluator）來對其優(yōu)劣進(jìn)行評分（evaluate）。根據(jù)估值函數(shù)，博弈樹中的每個(gè)葉結(jié)點(diǎn)都有一對應(yīng)值（value）。博弈樹搜索的目的就是找出博弈樹的值（game tree value）。博弈樹的值（下面簡稱博弈值）指的是博弈樹中一個(gè)子結(jié)點(diǎn)的值，該值對于博弈雙方都是最優(yōu)的。博弈樹的子樹在該子樹搜索完成之后也會返回一個(gè)博弈值，該值是子樹的局部最優(yōu)值。

計(jì)算一棵博弈樹的博弈值，可以使用基本的極大極小樹搜索（Min-Max Tree Search）。為了減少搜索的節(jié)點(diǎn)數(shù)，可以使用Alpha-Beta算法進(jìn)行剪枝。在Alpha-Beta算法的基礎(chǔ)上，各種改進(jìn)方法被先后提出來，例如置換表，PVS算法以及并行Alpha-Beta算法。在博弈樹搜索算法方面，前人做了許多豐富而充滿意義的研究工作。

2.1針對Alpha-Beta算法的改進(jìn)

在Alpha-Beta算法被廣泛運(yùn)用后，對該算法的很多改進(jìn)算法也相繼被提出.這些改進(jìn)算法主要在以下幾個(gè)方面對Alpha-Beta算法進(jìn)行改進(jìn)：

1）擇序。在搜索博弈樹時(shí)，內(nèi)部結(jié)點(diǎn)有多個(gè)可能的狀態(tài)轉(zhuǎn)移。擇序指的是搜索這些分支的順序。

在Alpha-Beta算法中，提高擇序的好壞就意味著提高剪枝發(fā)生的概率。所以一個(gè)好的狀態(tài)轉(zhuǎn)移可以定義為：

①導(dǎo)致剪枝的移動(dòng)。

②或者如果沒有導(dǎo)致剪枝，但是產(chǎn)生了最小最大值。

一個(gè)好的狀態(tài)轉(zhuǎn)移并不一定是最優(yōu)的狀態(tài)轉(zhuǎn)移（best move），因?yàn)橐粋€(gè)導(dǎo)致剪枝的狀態(tài)轉(zhuǎn)移可能引起了該子結(jié)點(diǎn)上的搜索停止，但是并不意味著其后的子結(jié)點(diǎn)的搜索不會產(chǎn)生一個(gè)更好的值。

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有更高的效率。使得搜索效率大幅提高。

3 五子棋數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)

3.1 棋盤數(shù)據(jù)結(jié)構(gòu)

由于在PC上棋盤的訪問不是性能瓶頸，所以我們用可讀性較強(qiáng)的方法來定義顯式的棋盤，通過調(diào)用指定接口落子，我們還能維護(hù)一個(gè)編碼后的棋盤。

1）顯式的棋盤

定義一個(gè)Board[SIZE][SIZE]數(shù)組。其中，SIZE是指可落子的棋盤范圍+8。因?yàn)樵谂袛嗥逍偷倪^程中，需要訪問相鄰4格內(nèi)的點(diǎn)（9格棋型：4 + 1 + 4 = 9），為了便于操作與編碼，在棋盤圍增加4格的預(yù)留空間。

2）編碼后的棋盤

首先我們分別定義二進(jìn)制數(shù)[00]2，[01]2，[10]2為空、黑、白狀態(tài)，[11]2為預(yù)留空間。再定義四個(gè)數(shù)組L[POS]，R[POS]，R[POS]，W[POS]，其中保存著在四個(gè)方向（橫豎撇捺）上棋盤的二進(jìn)制編碼。例如111111110000011111111就是5*5的空棋盤在第一行上的編碼。也就是說，在二進(jìn)制棋盤中，每一個(gè)格子占兩個(gè)比特。

3.2著法生成

著法生成是指，一個(gè)局面（狀態(tài)）下有幾個(gè)可能的走法（狀態(tài)轉(zhuǎn)移）。最簡單的著法生成是將所有空點(diǎn)納入著法序列。但實(shí)際上，有價(jià)值的走法一般在已落子的點(diǎn)相鄰3格內(nèi)。所以只需維護(hù)一個(gè)表C[SIZE][SIZE]，其中C[i][j]保存著點(diǎn)[i， j]三個(gè)內(nèi)的棋子數(shù)。這些信息同樣可以用于擇序。

3.3 著法擇序

使用估值函數(shù)Evaluate（）得到值v。

3.4棋型與棋型表

各種棋型的定義。一個(gè)棋型只能有一個(gè)類型。優(yōu)先級從高到低。

1.成五：連續(xù)的五個(gè)及以上的同色棋子的棋型。

2.活四：有兩個(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.無效：雙方都不可能成五的棋型。

根據(jù)這些規(guī)則，可以遞歸的生成可查詢的棋型表Pattern。

顯然，棋型表的大小只與棋型長度有關(guān)，一個(gè)長9格的棋型對應(yīng)18位的編碼?？汕蟪銎逍捅淼拇笮?18 byte。即使棋型拓展到11格，222 byte 也是可以接受的大小。

3.5 估值設(shè)計(jì)

定義向量V （v1， v2， v3 ... ， v10） 分別對應(yīng)十種棋型的分值（value）。

定義向量C （c1， c2， c3 ... ， c10） 分別對應(yīng)棋盤上十種棋型的數(shù)量。

通過手動(dòng)設(shè)置或者調(diào)參算法給定V以后，在搜索過程中維護(hù)C。到達(dá)葉節(jié)點(diǎn)時(shí)調(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)了一個(gè)五子棋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)對特定數(shù)據(jù)結(jié)構(gòu)有較強(qiáng)的依賴性。

參考文獻(xiàn)：

[1] 劉雅靖.計(jì)算機(jī)博弈之六子棋的主要技術(shù)分析[J].電腦知識與技術(shù)，2011（10）.

[2] 徐心和，王驕.中國象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2006（6）.

[3] 瞿錫泉，白振興，包建平.棋類博弈算法的改進(jìn)[J].現(xiàn)代電子技術(shù)，2005（1）.

[4] 周新林，李淑琴，張晨光.六子棋博弈系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn).軟件導(dǎo)刊，2015（3）.