论文部分内容阅读
人工智能的发展促进了棋牌类游戏计算机程序的飞速进步。目前的棋类计算机程序已经达到了专家的水平,完全可以战胜人类棋手。同样作为人工智能的研究热门方向,牌类游戏的进展却比较缓慢。这主要是因为牌类游戏基本上都是多人游戏,并且牌手相互间的信息具有隐蔽性。牌类游戏属于不完全信息决策问题,相关的研究没有棋类这种完全信息游戏的深入和成熟。另外,多人参加游戏使得打牌决策的搜索空间不断膨胀,甚至达到了无法表示的地步。
本文主要讨论了桥牌计算机程序的相关问题。在给定了打牌系统整体框架后,围绕框架的前几部分,集中研究了以下几个方面的问题:
(1)对传统桥牌游戏搜索空间进行了研究,并利用牌型概念计算合理的打牌顺序,通过紧凑边界缩小了桥牌游戏的搜索空间。
(2)为了能够合理的解决问题,将桥牌打牌分解为单花色打牌,降低了问题的难度。本文从单花色打牌的策略开始讨论,确定了单花色中如何利用策略进行合理的打牌,并给出了具体的算法以及简单的算法分析。
(3)在不完全信息的搜索过程中,传统的搜索方法存在着一些问题,从而不能找到最优的打牌序列。因此,文中提出了策略最小化的算法,通过此算法可以克服传统的搜索方法所面临的问题,其缺点是比较浪费资源。
(4)使用单花色打牌序列打牌时,可能不能生成最好的全局策略,所以需要对他们进行合并。但是单花色序列之问可能存在的相互依赖,使得合并比较困难,因此有关合并的问题需要更深入研究。本文没有解决这个问题,只是提出了一些合并中可能遇到的困难。