论文部分内容阅读
人类生活中有利益冲突的地方就会有博弈,而现实生活中大多数博弈问题都属于非完备信息博弈,例如金融交易、军事博弈、政治谈判、棋牌游戏等,因此对相关问题的研究具有极大的经济价值和现实意义。非完备信息博弈由于信息不对称的特点,复杂的博弈背景导致决策节点数目呈指数级增长,传统的人工智能方法难以直接应用到非完备信息博弈中。针对以上问题,本文提出了使用对手建模和改进树搜索算法来解决非完备信息博弈问题,并将其应用到四人竞技麻将博弈中。本文的主要工作和创新点如下:1.结合知识和蒙特卡洛模拟方法构建对手模型来预测隐藏信息,并将其转化为相对概率。非完备信息博弈中存在巨大的隐藏信息,只依赖于可见信息可能导致较大的偏差,本文通过蒙特卡洛方法对每位对手的手牌进行模拟,结合时序信息、历史信息和相关领域知识设计了手牌的分配度计算方法,使模拟结果更加符合现实场景,最后将模拟结果转化为每张牌的获取概率和危险度表,为后续相关权重的计算提供重要帮助。2.根据麻将博弈的规则特点,设计了改进的树搜索算法用于探索获胜路径。首先,在分析博弈机理的基础上,简化了博弈模式,将搜索对象转化为手牌的更新过程。然后,使用了启发式信息设计了手牌拆分算法生成组合信息,基于组合信息设计了快速获胜、高分探索和改良探索三种策略从不同角度来提升搜索效率。最后结合胜率、得分和风险值评估,设计了攻守兼备的评估函数来计算最优解,通过对比实验验证了本文博弈决策方法具备了胜率高、得分高和风险低的优点。3.设计了基于知识的非完备信息博弈智能决策系统和测试平台。将设计好的决策模型部署到云服务器构建智能决策系统,通过云服务的方式提供决策服务,并将其应用到人机对战、辅助决策和博弈行为分析等功能中。搭建了测试平台来测试和评估系统的决策能力,建立了评估体系用于分析决策系统可能存在的缺陷,从而加快模型的迭代更新速度。基于以上方法开发的麻将AI程式“ZONST-KF-TREE”参加了由ICGA(International Computer Game Association)举办的 Computer Olympiad 2019 锦标赛,并最终取得了银牌的成绩,从实践上证明了本文方法具备相当高的决策水平和可操作性。