基于蒙特卡罗抽样的桥牌机器博弈的研究与实现

摘要

本论文属于人工智能范畴。人工智能是20世纪三大科技成就之一，机器博弈是人工智能研究的发源地和原动力。自1956年人工智能创立同年，塞缪尔研制成功了“跳棋机”电脑软件以来，研究者们已经发展了一系列的通用的卓有成效的完备信息搜索技术，使得在以国际象棋为代表的机器博弈比赛中，机器选手的水平已经达到或超越人类的顶尖选手。
　　桥牌作为一项高雅、文明、竞技性很强的体育运动风靡全球，并以它特有的魅力而称雄于各类牌戏。以计算机模拟进行的桥牌机器博弈是一种非完备信息博弈，它已被证明是一个NP难题，只能寻找近似的解决方法，其相关研究目前还不是十分成熟。
　　本文从讨论最简单的“二人零和、完备信息、非偶然”博弈入手，详细剖析了极大极小值算法，并以此为基础，引申探讨了其它完备信息的基本搜索算法。接着，通过蒙特卡罗抽样方法来消除游戏中的非完备信息问题，应用双明手算法来处理桥牌机器博弈。
　　我们借助成熟的商业软件Jack4.01随机产生一批牌局，并将其发牌、叫牌（使用简化的美国标准黄卡叫牌法）和打牌的全过程生成 html文件，再输入到本系统作为参照物。本系统以发牌和叫牌信息为已知信息，我们站在首攻人的角度去考虑出牌，出第一次牌之前，很显然他手上的13张牌中的任一张都是可供选择的，我们通过提取叫牌过程中产生的牌情约束条件，建立牌张概率分布表，应用蒙特卡罗方法产生一组牌，并对其进行双明手搜索，计算每一种走步的收益，在允许的时间内对上述流程进行多次重复，最终汇总计算出每一种走步的得分，然后与商业软件Jack4.01实际走步比对，以一个特定公式进行打分，验证蒙特卡罗方法的广泛适用性和桥牌机器博弈的可实现性。基于同样原理，每一轮由电脑按照读入信息完成其他三方的出牌，本系统站在原首攻人的角度来对局面进行一次分析，以完成桥牌全局机器博弈。
　　最后，以三个典型桥牌局面为例，分别记录其三组实验数据，验证了以蒙特卡罗抽样方法是可以用来解决桥牌机器博弈的。

目录

基于蒙特卡罗抽样的桥牌机器博弈的研究与实现

Research on bridge computer game with monte-carlo sampling and implementation

摘 要

Abstract

目 录

第１章 绪 论

1.1 课题背景与来源

1.2 研究目的和意义

1.3 国内外研究现状综述

1.4 主要研究内容及论文结构

第2章 完备信息机器博弈及其搜索算法

2.1最基本的博弈

2.2机器博弈的核心思想

2.3机器博弈的常见搜索算法

2.3.1搜索算法基本分类

2.3.2 极大极小值算法

2.3.3负极大值搜索

2.3.4 基本alpha-beta搜索

2.3.5对基本alpha-beta搜索算法的改进

2.3.6 置换表

2.3.7 A*算法

2.4 本章小结

第3章 蒙特卡罗方法

3.1 蒙特卡罗方法的起源

3.2 现代蒙特卡罗方法的出现

3.3 蒙特卡罗方法的适用性

3.4蒙特卡罗方法在桥牌机器博弈的应用

3.5 本章小结

解决完备信息博弈的算法取得了很多的成果，但是这些算法对非完备信息博弈却不再适用，此时寻找最佳走步已经被证明为是一个NP难题，人们只能通过寻找近似算法来逼近最佳走步的选择。本章从蒙特卡罗方法的基本思想入手，并寻根溯源描述了布丰在著作中提出了著名的投针问题，来阐述蒙特卡罗方法的基本思想，进而探讨其别具风味的特点和强大的适应性，并应用于解决桥牌机器博弈问题。

第4章 桥牌机器博弈系统的构造

4.1 桥牌规则

4.1.1 坐位

4.1.2 发牌

4.1.3 叫牌

4.1.4 打牌与计分

4.1.4.1 基本分

4.1.4.2 奖分

4.1.4.3 罚分

4.2 美国标准黄卡叫牌体系

4.2.1基本叫法

4.2.2 1NT开叫之后的应叫

4.2.3 对2NT和3NT开叫的应叫

4.2.4对一阶高花开叫的应叫

4.2.5对 1/1 开叫的应叫

4.2.6强2开叫

4.2.7满贯试探约定叫

4.3 Jack软件的应用

4.3.1 设置简化版美国标准黄卡约定卡

4.3.2 随机生成牌局

4.4系统框架

4.4.1数据结构

4.4.2 着法生成

4.4.3 双明手搜索

4.4.4 实验结果分析

4.5 本章小结

结 论

参考文献

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致 谢

个人简历