基于蒙特卡罗树搜索的计算机扑克程序

作     者：曹一鸣 

作者单位：北京邮电大学 

学位级别：硕士

导师姓名：刘知青

授予年度：2014年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：计算机博弈 德州扑克 蒙特卡罗树搜索 对手模型 

摘      要：计算机博弈是测试人工智能所达到水平的一个重要平台。早期的研究主要集中在确定性完全信息博弈之上。然而由于与现实之中的问题更加贴近,非确定性非完全信息博弈逐渐引起学术界的重视。 德州扑克是一种非确定性非完全信息博弈。因为它的规则简单同时富于变化,所以其作为这种博弈的一个典型,正在成为计算机博弈研究领域的又一个热点。机器学习中的蒙特卡罗树搜索算法,是一种集成了蒙特卡罗方法作为评估的博弈树搜索算法,毋需引入过多的领域知识,同时具有巨大的可扩展性。多臂匪徒问题是一种从多重决策选择问题之中抽象出来的一种机器学习模型。UCB策略是求解多臂匪徒问题的一种方法。集成UCB策略的基于UCT的蒙特卡罗树搜索算法被证明可以极大地提升计算机博弈引擎水平。 本文结合德州扑克的相关特性改进并设计了德州扑克的蒙特卡罗博弈树,同时对博弈树中的相关节点设计了对应的模拟、选择、回溯更新策略。本文使用C++编程序语言、面向对象技术以及设计模式思想实现了一个德州扑克的博弈引擎。 本文为基于蒙特卡罗树搜索算法的博弈引擎引入了与德州扑克的相关的领域知识,其包括Bucketing的底牌提取,以及在此基础上的基于统计的对手模型用于模拟对手以及估计对手的底牌的概率分布。最后我们提出了一个保守度的概念用于将引擎的下注行为改造成一个比较“松的策略。 本文设计四个实验来验证纯粹的蒙特卡罗树搜索引擎的性能,并通过分析输出日志,发现了过“紧的下注策略对于博弈的负面影响。我们测试了在引入保守度后执行一个比较“松的下注策略时对博弈结果的影响,同时验证集成了对手模型后对于程序博弈水平的提升。 最终,通过实验结果的分析,可以确认,蒙特卡罗树搜索算法可以应用于求解非确定性非完全信息博弈问题。同时在求解德州扑克博弈的问题中,集成领域知识以及对手模型可以提高蒙特卡罗树搜索引擎的性能。