郑培铭+何丽

摘要：介绍计算机博弈基础算法及部分优化算法，根据五子棋的规则，提出了针对五子棋的数据结构和算法设计，尝试将计算机博弈算法应用于五子棋，设计并实现了一个五子棋AI，并在国际赛事中取得良好成绩；实验证实使用置换表与PVS（Principal Variation Search）算法后搜索效率显著提高。

关键词：五子棋；人工智能；博弈树算法

中图分类号：TP181 文献标识码：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 概述

人工智能是一门正在迅速发展的新兴的综合性很强的学科。它与生物工程、空间技术一起被并列为当今三大尖端技术。人工智能的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。人工智能有诸多领域，博弈就是其中一种。

博弈的参加者可以是个人、集体、一类生物或机器。他们都力图用自己的智力去击败对手， 博弈为人工智能提供了一个很好的试验场所。人工智能中许多概念和方法都是从博弈程序中提炼出来，并在新的技术中获得应用。许多研究成果已用于军事指挥和经济决策系统之中。

博弈问题中，最经典的就是棋类博弈。

在此以五子棋为研究样例，基于针对五子棋设计的数据结构与算法，实现了经典的计算机博弈算法。旨在证实计算机博弈算法的普适性，证明针对五子棋设计数据结构与算法的高效。

2 关键技术分析

2.1博弈树搜索算法

任何棋类游戏都要定义一棵由博弈状态为节点的树（即“博弈树”），一个结点就代表棋类的一个局面，子结点就是这个局面进行一次状态转移可以到达的局面。……