五子棋的一種價值的估算

徐建

摘要：人工智能是一門正在迅速發(fā)展的新興綜合學(xué)科，博弈是其主要研究領(lǐng)域之一。五子棋游戲，其規(guī)則簡單，但變化多端，適宜于研究分析人機(jī)博弈算法。本文設(shè)計實(shí)現(xiàn)了五子棋人工智能功能，主要采用α-β修剪法算法，優(yōu)化博弈樹搜索過程，通過控制搜索深度和寬度，實(shí)現(xiàn)人機(jī)對弈。五子棋博弈的關(guān)鍵部分是價值估算，本文介紹一種簡單有效的估值方法。

關(guān)鍵字：五子棋；價值估值；博弈

A method of value estimation for Gobang game

XU Jian

（School of Education Intelligent Technology（School of Computer Science and Technology）， Jiangsu Normal University， Xuzhou Jiangsu 221116， China）

Abstract： The rapidly developing artificial intelligence is a new comprehensive discipline， and game is one of its main research fields. The rules of Gobang game are simple， but in which there are many changes， so it is suitable for research and analysis of man-machine game algorithm. The paper designs and implements Gobang artificial intelligence function. In the process， mainly apply α-βpruning algorithm， optimize search process of the game tree， and by controlling the search depth and width， to achieve human-computer chess. Especially， the key part of Gobang game is the value estimation. This paper proposes a simple and effective method of valuation.

Keywords： Gobang； valuation； game

0 引言

博弈是人工智能的一個重要領(lǐng)域。在國際象棋、圍棋等方面已經(jīng)作出了很多研究，五子棋的博弈研究則更是獲得了重點(diǎn)突出的關(guān)注與矚目。五子棋的博弈系統(tǒng)，由于搜索空間比較小（和國際象棋、圍棋等比較），一般情況下均是采用α-β修剪法來展開搜索。但對棋盤面的價值估算卻仍是一個演進(jìn)難點(diǎn)。本文將提出一種簡單、且有效的價值估算方法。

1 五子棋博弈系統(tǒng)簡介

本文論述的五子棋博弈系統(tǒng)軟件采用VB編寫，核心搜索部分則選用C語言編寫。其中，VB可調(diào)用C編寫的DLL庫來進(jìn)行功能實(shí)現(xiàn)。并采用α-β修剪法來解析搜索。當(dāng)然，不可能完全搜索，而是選擇適當(dāng)?shù)乃阉鲗挾群蜕疃取８鶕?jù)價值估算的獲取內(nèi)容，對下一步點(diǎn)的價值估算來構(gòu)建排序，同時選擇一個適當(dāng)?shù)臄?shù)作為搜索寬度，只搜索寬度內(nèi)的點(diǎn)。對于深度也給出一個適當(dāng)?shù)臄?shù)作為搜索深度。在給定的搜索寬度和深度的范圍內(nèi)搜索下一步的最優(yōu)點(diǎn)。本博弈系統(tǒng)的下一步搜索時間，在可忍受的等待時間內(nèi)（在普通PC機(jī)上，一般等待在30秒內(nèi)，有時長考最長等待5分鐘）可以搜索224的搜索空間。一般可以取（2，24）（其中2為搜索寬度，24為搜索深度，以下同），（3，15）、（4，12）、（5，10）、（6，9）、（7，8）和（8，8）。經(jīng)試驗(yàn)（5，10）的效果比較好。

2 價值估算方法

下面介紹價值估算的設(shè)計方法。棋盤采用二維數(shù)組表示，估值采用與棋盤對應(yīng)的二維數(shù)組記錄，黑白子各用一個二維數(shù)組。對棋盤上每個點(diǎn)依次逐一掃描，無論有子/無子都對其4個方向進(jìn)行搜索計算。每個方向的搜索方法是：假設(shè)當(dāng)前方向的當(dāng)前點(diǎn)的坐標(biāo)為0，搜索-4到4范圍內(nèi)的空間，每5個點(diǎn)作為一個算分單位，即：-4到0，-3到1，-2到2，-1到3，0到4。此時，當(dāng)前點(diǎn)若為有子的情況，就依據(jù)當(dāng)前點(diǎn)的子的（黑白）計算對應(yīng)的分值；如果當(dāng)前點(diǎn)沒有子，就假定其有黑子和白子，對應(yīng)將計算2次結(jié)果分值。在此基礎(chǔ)上，還需繼續(xù)搜索每個算分單位，找出和當(dāng)前點(diǎn)一樣的子有多少個（中間不能有不同的子），然后，根據(jù)子數(shù)和當(dāng)中空位數(shù)得到最終分值，分值如表1所示。這樣就分別計算出當(dāng)前點(diǎn)的黑白的分值，再將所有的算分單位和所有的方向的分值根據(jù)黑白分別求和就是當(dāng)前點(diǎn)的總分值（每點(diǎn)有（黑白）2個總分值）。

2.3 估值算分算法C語言代碼

計算分值的C語言程序代碼如下：

3 結(jié)束語

綜上可知，無論在估值數(shù)據(jù)的精確度，以及估值算法和搜索算法上均有待進(jìn)一步發(fā)展與優(yōu)化。今后的研究方向和重點(diǎn)將設(shè)定在搜索深度和寬度自適應(yīng)變化等方面，以有效拓寬論文算法的實(shí)用范圍與價值。

參考文獻(xiàn)：

[1] RUSSELL S J，Norvig P著.人工智能：一種現(xiàn)代的方法[M].3版. 殷建平，祝恩，劉越，等譯. 北京：清華大學(xué)出版社，2013.