基于贝叶斯均衡和搜索算法的博弈模型研究

摘要

博弈论从诞生至今，对经济学乃至整个社会科学产生了极其重要的影响。目前，博弈论已经成为主流经济学的重要组成部分，同时，博弈论作为现代经济学的前沿领域，已成为占据主流的基本决策分析工具之一。而下棋是人类智慧的典型表现，机器博弈是运筹学与控制论和人工智能学科的重要研究对象。随着计算机软件和硬件技术的快速发展。计算机已经可以在象棋领域与人类天才较量。苏拉卡尔塔棋机器博弈系统开发属于离散事件动态过程，它为机器智能的开发与研究提供了新的方向与工具，它也是人工智能学科极富挑战性的研究课题。
　　本文以高校学生贷款还贷问题博弈模型和苏拉卡尔塔棋机器博弈系统作为研究课题，在阅读了大量的相关文献基础上，首先根据实际现象建立了模型，然后按照人工智能和计算机博弈的一般原理设计了苏拉卡尔塔棋计算机博弈的模型，所做的工作包括以下几部分:
　　首先，以高校学生贷款还贷问题为引例，研究了不完全信息动态模型，通过海萨尼转换转化为完全信息博弈模型，应用贝叶斯动态博弈理论，分析了学生贷款不还的问题。
　　其次，研究了博弈树的搜索算法。在负极大值和alpha-beta搜索算法的基础上，采用极小窗口、历史启发等算法，有效的提高了搜索的效率。
　　然后，以苏拉卡尔塔棋机器博弈系统开发设计为研究载体，通过对计算机博弈技术的研究，结合一般棋类软件的开发思路，阐述了一个可以达到人类高手水平的计算机博弈程序的设计和实现原理。通过利用离散事件对策的七元组模型，设计了苏拉卡塔尔棋计算机博弈软件的数据结构，包括棋盘、棋子编码。将苏拉卡塔尔棋的着法生成分为吃子着法生成和非吃子着法生成。
　　最后，利用VC++语言编程，对以上各种算法编程实现，展示了苏拉卡尔塔棋的计算机博弈系统的开发实现过程。实践结果表明了算法的可行性，并表现出了很好的性能。

目录

声明

摘要

第1章 绪论

1．1 博弈论的起源与发展历程

1．2 博弈论的研究意义和目的

1．3 机器博弈的发展

1．4 机器博弈的研究意义

1．5 本文的内容安排

第2章 预备知识

2．1 博弈论的基础知识

2．1．1 博弈论的基本概念

2．1．2 博弈问题的分类

2．1．3 几种纳什均衡的概念

2．2 机器博弈的基础知识

2．2．1 机器博弈的分类

2．2．2 棋类游戏的基本特点

2．2．3 评估函数

2．3 小结

第3章 一个贝叶斯纳什均衡的博弈模型分析

3．1 博弈模型的分析与建立

3．1．1 博弈的简单分析

3．1．2 博弈中的基本假设

3．1．3 博弈的行动顺序

3．2 博弈模型的完美贝叶斯均衡分析

3．3 基于模型给出的解决问题方案

3．4 小结

第4章 博弈搜索算法研究

4．1 博弈树

4．2 基本搜索算法

4．2．1 极大极小算法

4．2．2 负极大值算法

4．2．3 Alpha-Beta剪枝搜索算法

4．3 改进的Alpha-Beta算法

4．3．1 Fail-soft alpha-beta搜索

4．3．2 迭代深化算法

4．3．3 渴望窗口搜索

4．3．4 PVS搜索算法

4．4 历史启发搜索算法

4．5 算法实现

4．6 小结

第5章 苏拉卡尔塔棋的研究与系统实现

5．1 苏拉卡尔塔棋的描述和建模

5．1．1 苏拉卡尔塔棋的描述

5．1．2 基本概念

5．1．3 苏拉卡尔塔棋的棋局分析

5．1．4 博弈建模过程

5．2 苏拉卡尔塔棋的关键技术分析

5．2．1 棋子和棋盘的数字表示

5．2．2 着法生成

5．2．3 棋局评估

5．3 苏拉卡尔塔棋的系统实现

5．3．1 程序流程图

5．3．2 数据结构定义

5．3．3 程序设计中的主要函数

5．4 人机界面

5．5 小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

攻读硕士学位期间的研究成果