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