五子棋的一種價值的估算

徐建

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

關鍵字：五子棋；價值估值；博弈

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 引言

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

1 五子棋博弈系統簡介

本文論述的五子棋博弈系統軟件采用VB編寫，核心搜索部分則選用C語言編寫。其中，VB可調用C編寫的DLL庫來進行功能實現。并采用α-β修剪法來解析搜索。當然，不可能完全搜索，而是選擇適當的搜索寬度和深度。根據價值估算的獲取內容，對下一步點的價值估算來構建排序，同時選擇一個適當的數作為搜索寬度，只搜索寬度內的點。對于深度也給出一個適當的數作為搜索深度。在給定的搜索寬度和深度的范圍內搜索下一步的最優點。本博弈系統的下一步搜索時間，在可忍受的等待時間內（在普通PC機上，一般等待在30秒內，有時長考最長等待5分鐘）可以搜索224的搜索空間。一般可以取（2，24）（其中2為搜索寬度，24為搜索深度，以下同），（3，15）、（4，12）、（5，10）、（6，9）、（7，8）和（8，8）。經試驗（5，10）的效果比較好。

2 價值估算方法

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

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

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

3 結束語

綜上可知，無論在估值數據的精確度，以及估值算法和搜索算法上均有待進一步發展與優化。今后的研究方向和重點將設定在搜索深度和寬度自適應變化等方面，以有效拓寬論文算法的實用范圍與價值。

參考文獻：

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