徐建

摘要：人工智能是一门正在迅速发展的新兴综合学科，博弈是其主要研究领域之一。五子棋游戏，其规则简单，但变化多端，适宜于研究分析人机博弈算法。本文设计实现了五子棋人工智能功能，主要采用α-β修剪法算法，优化博弈树搜索过程，通过控制搜索深度和宽度，实现人机对弈。五子棋博弈的关键部分是价值估算，本文介绍一种简单有效的估值方法。

关键字：五子棋；价值估值；博弈

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的搜索空间。……