点格棋机器博弈系统的研究与实现

摘要

机器博弈素有人工智能领域的“果蝇”之称，是该领域公认的最具挑战性的研究课题之一。对于它的研究，学者们提出了很多重要的理论和技术方法，应用于人工智能领域，在社会和学术界产生了深远的影响。国际上对机器博弈的研究可以追溯到上个世纪五十年代，过去的六十多年里，机器博弈的研究已经取得了令世人瞩目的成就。无论是IBM的“深蓝”还是浪潮的“天梭”，都让世人看到了机器的力量，机器在博弈上的智能正在逐渐超过人类，达到让人类望尘莫及的地步。近几年，随着国内计算机博弈大赛的开展，众多博弈爱好者被吸引到计算机博弈的研究中来，极大地促进了计算机博弈理论和技术在国内的发展。　　传统的机器博弈模型多是连珠式棋类模型，它的落子点是棋盘上的交叉点，此种棋类的数据结构设计与棋盘状态描述相对简单，国内多数关于机器博弈的研究大多以连珠式棋类为研究载体。本文以点格棋为研究对象，研究关于点格棋机器博弈的相关技术，因为点格棋对弈着法关注的是邻近两点之间的边，所以下棋规则和行棋方式的与传统博弈模型相比有一定的特殊性，从而更具有研究意义。　　本文以点格棋博弈平台为研究载体，研究了机器博弈领域的关键技术，包括一些基本概念、研究对象的属性分析和系统构成要素；设计了点格棋机器博弈系统，包括棋盘数据结构设计，棋盘棋型记录，基于棋型模拟落子的估值函数设计；设计实现了删除了等价边和冗余边的着法生成函数，与对所有可行棋位全搜索相比保证了博弈水平的同时提高了搜索效率；设计了基于Alpha-Beta剪枝搜索的博弈树搜索算法，并采用置换表、历史启发以及迭代深化等技术优化了搜索效率，提高博弈水平。　　从搜索效率和博弈水平两个角度进行实验验证得出如下结论：相比于对所有可行棋位进行深度搜索，删除了等价边和冗余边的部分着法深度搜索没有降低程序的博弈水平，但是明显提高了搜索效率。在Alpha-Beta剪枝搜索算法的基础上，分别加入置换表、历史启发以及迭代深化等多种优化技术，实验表明历史启发技术提升博弈树搜索效率最高，迭代深化最差，同时加入三种优化技术的策略表现和仅加入历史启发的策略表现相当，三种优化技术在点格棋博弈程序中同样适用。　　本文实现的基于棋型的模拟落子估值方法表现出一定的智力水平，该方法在残局阶段估值精准，但是在前期开局棋盘划分不明确的情况会由于安全边的落边顺序不同导致估值不准确。关于如何设计出一套在任何阶段都准确刻画棋局优劣势的估值函数有待于以后进一步研究。　　本文有如下创新点：　　1．根据点格棋的特点，提出点格棋博弈树宽度裁剪的着法生成方法，删除等价边和冗余边，采用Alpha-Beta剪枝算法实现对博弈树的搜索，实验对比其可以提高博弈树的搜索效率同时不降低博弈水平。　　2．在Alpha-Beta剪枝搜索算法的基础上，引入置换表、历史启发和迭代深化等一系列优化算法，降低了博弈树的搜索节点数，提高了搜索算法的效率。　　3．设计实现了基于点格棋棋型的模拟落子估值方法，并将该方法应用于点格棋博弈程序中，表现出一定的“智力”水平。　　上述方法均在点格棋博弈系统“格子杀手”程序中成功应用，该程序在2014年“成理杯”全国大学生计算机博弈大赛中荣获一等奖（点格棋项目），实践上证明了本文提出方法具有可操作性和实际应用价值。

目录

第一个书签之前