基于蒙特卡洛树搜索的计算机围棋博弈研究

摘要

近年来，计算机软硬件和互联网迅猛发展，相关学科也在不断进步。人工智能是长期以来的热点话题，而计算机博弈是它的一个受到广泛关注的研究方向。作为最复杂的博弈项目之一，具有挑战性的围棋能够充分检验人工智能的发展水平，因此计算机围棋博弈的研究在计算机博弈、人工智能乃至计算机科学领域占有重要的地位。
　　由于围棋知识规则不便归纳，搜索空间过于巨大，传统计算机博弈的理论和方法目前均难以适用。近些年，在计算机性能大幅度提高的基础上，计算机围棋博弈采用蒙特卡洛方法进行动态评估，并引入了上限信心界应用树算法，搜索的效率和评估的性能均得到了很大提升，计算机围棋博弈程序的水平不断提高。同时，这种聚类智能的计算方法不仅适用于围棋，还适用于规划决策类问题等其他许多问题，因此计算机围棋博弈方面的研究成果有着重要的现实意义，可以有更广阔的用武之地。
　　由蒙特卡洛方法和上限信心界应用树算法构成的蒙特卡洛树搜索是当今高水平计算机围棋程序普遍采用的较优方法，但其仍有可完善之处。本文立足于蒙特卡洛树搜索的思想和特点，针对蒙特卡洛方法和上限信心界应用树算法存在的不足，提出了绝对剪枝策略和渐进展开策略两大改进措施，并从理论上证明了改进的必要性和正确性。而后，本文选用了采用蒙特卡洛树搜索的棋力很强的开源围棋程序Fuego作为改进试验程序，通过GoGui平台使其改进前和改进后分别与另一高水平程序Pachi对弈，根据对局的用时和胜负进行验证和分析。实验结果表明，Fuego在用时略有下降的情况下胜率有所提高，这说明改进方案切实有效，具备一定的实用价值。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究意义

1．3 研究现状

1．4 论文内容

1．5 论文结构

1．6 本章小结

第2章 计算机博弈的基本理论与方法

2．1 计算机博弈的主要特征

2．2 博弈树

2．3 博弈的复杂度与可解性

2．3．1 博弈的复杂度

2．3．2 博弈的可解性

2．4 博弈的盘面评估

2．5 博弈树常用搜索算法

2．5．1 极大极小搜索算法

2．5．2 Alpha-Beta搜索算法

2．6 本章小结

第3章 计算机围棋博弈的特点与难点

3．1 围棋简介

3．2 围棋的复杂度

3．2．1 围棋的状态空间复杂度

3．2．2 围棋的博弈树复杂度

3．2．3 围棋与其他主要博弈项目复杂度的比较

3．3 计算机围棋博弈的主要特点

3．3．1 目标的总体效应

3．3．2 庞大的搜索空间

3．3．3 复杂的盘面评估

3．3．4 密切相关的盘面评估与博弈树搜索

3．4 计算机围棋博弈的主要难点

3．4．1 难以终结搜索

3．4．2 难以验证选点

3．5 本章小结

第4章 计算机围棋博弈的盘面评估

4．1 静态盘面评估

4．1．1 评估函数

4．1．2 影响函数

4．2 蒙特卡洛盘面评估

4．2．1 蒙特卡洛方法的发展历史

4．2．2 蒙特卡洛方法的基本思想

4．2．3 蒙特卡洛对弈

4．3 静态评估与动态评估的分析与比较

4．4 本章小结

第5章 蒙特卡洛树搜索

5．1 在线机器学习

5．2 多臂匪徒模型与上限信心界策略

5．2．1 多臂匪徒问题

5．2．2 多臂匪徒问题的数学模型

5．2．3 上限信心界策略

5．3 上限信心界应用树算法与蒙特卡洛树搜索

5．4 本章小结

第6章 蒙特卡洛树搜索的尝试改进与验证分析

6．1 采用绝对剪枝策略进行改进

6．2 采用渐进展开策略进行改进

6．3 改进效果验证与分析

6．3．1 协议、平台与程序

6．3．2 效果验证与结果分析

6．4 本章小结

结论

参考文献

致谢