英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
黑桃的成功：
使用AI规划技术赢得世界计算机桥牌锦标赛
Stephen J. J. Smith Dana S. Nau Dana S. Nau
摘要：
最新的计算机桥牌项目的世界冠军赛是由美国定约桥牌联盟于1997年7月主办的“男爵巴克莱世界桥牌计算机挑战赛”。 据“纽约时报”和“华盛顿邮报”报道，本次比赛的冠军是一个出自叫做“伟大游戏产品”计划的新版本的计算机程序“桥牌男爵”。 目前这个新版本的“桥牌男爵 8”已经上市; 在1997年的最后三个月里，它已经被1000多个客户购买。“桥牌男爵”的成功也代表了科学家对于人工智能规划系统研究的一次具有重要意义的成功。“桥牌男爵8”采用了分层任务网络（HTN）规划技术来规划客户的牌局。 本文概述了这些技术及此程序的使用方法
1.问题描述：
要在桥牌比赛这样的商业比赛中取得成功，桥牌游戏的计算机程序必须在各个方面都表现出色。 客户希望尽可能感觉像是在挑战一个牌手。显而易见，要想赢得比赛，程序必须足够智能。尽管研究人员在开发诸如国际象棋等棋类游戏的高性能程序方面已经取得了巨大成功，可是他们在定约桥牌游戏中并没有如此收获。 即使是最好的桥牌程序也会被当地许多桥牌俱乐部的优秀牌手击败。
很难为桥牌游戏开发一个优秀的计算机程序重要原因是桥牌并不是一个信息公开的游戏。 桥牌选手不知道其他选手手中的牌是什么（除了开场前，猜测手中有什么牌）; 因此每个玩家对于比赛整体的状态，可能的进展以及出牌造成的影响只有部分的掌握。 如果我们天真地想要类比象棋和跳棋那样对计算机程序中使用的古典游戏树搜索技术进行改编，那么游戏树就需要包含所有玩家可能做出的所有动作，这棵树就会很庞大。其大小取决于特定的桥牌打法，但在最坏的情况下它将包括约5.6times;1044个叶节点（Smith 1997，p226），在平均情况下约2.3x1024叶节点（Lopatin 1992， p8）。 由于桥牌选手通常要在几分钟内打出牌，所以没有足够的时间让游戏树搜索算法完全地搜索这棵树来做出正确的决策。
目前为止，在桥牌游戏的计算机程序中最成功的方法是使用一种不依赖领域的模式匹配技术。 大多数商业桥牌程序都使用了这种方法，例如旧版本的“桥牌男爵”程序（Throop 1983，Great Game Products 1997）。“桥牌男爵”通常被认为是最好的定约桥牌游戏的商业程序。 在引入人工智能技术之前（本文稍后会介绍），它已经赢得了四次国际计算机桥牌锦标赛的冠军。 在美国定约桥牌联盟对七种商业上可用的桥牌程序（Manley 1993）的测评中，“桥牌男爵”被评为是七个中最好的，并且将“桥牌男爵”评定为没有“偷看”对手牌的五个技术中最好的一个。
2.应用说明：
图1.第一轮中各桥牌角色的一个例子。 在这里，南是庄家，北是明手，西和东是防守者
a.桥牌概述
桥牌是由四名选手参加的游戏，使用一副含52张扑克牌的标准牌，分为四种花色（黑桃，红桃，方块，梅花），每种包括13张牌。
选手（被分为北，南，东，西），作为两队对抗，南北方组成的队对抗东西方组成的队。桥牌游戏包括两个阶段：竞叫和比赛。
竞叫：这些牌在四名牌手之间平等分配。 牌手们通过竞叫决定哪种花色作为将牌以及定约的水平。通常，每次竞叫包括两部分：竞叫者承诺采取的一些打法（见下文），以及竞叫者竞叫的将牌花色。目前已经制定了很多种竞叫约定，其中一些也可向竞叫者的队友传达关于自己的手牌有多强的信息。竞叫进行到没有玩家提高叫牌为止。 此时，最高的叫牌成为定约。 在叫牌最高的一方中，先出牌的叫牌者成为庄家，庄家的搭档成为明手。 另外两名选手成为防守方。
打牌：第一次轮到明手打牌时（见下文），明手将她（他）的牌放在桌子上，正面朝上，以便每个人都能看到; 在打牌的过程中，庄家既可以打出庄家的牌也可以打出明手的卡牌。每位牌手将牌正面朝上放在牌桌上（如图1所示），第一张牌是初始牌; 只要能跟打，玩家必须跟打，即打出的牌是与初始牌相同的花色的牌。
桥牌游戏的基本单位是墩，每位牌手将牌面朝上放在牌桌上，除非某牌手打出一张将牌，否则任何打出最大牌的牌手都会赢一墩。打牌的过程中，一轮可以有一个选手赢一墩，直到所有牌手都打完手牌。 这时，桥牌的得分是根据每一方赢了多少墩，以及庄家所在一方是否赢得自己叫牌时约定的墩数来判定。
b.桥牌男爵
“桥牌男爵”由数以万计行的C代码行组成。程序的不同版本可分为Windows版，MS-DOS版和Macintosh版; Windows版占销售额的绝大多数。
在“桥牌男爵”中，有超过五万行代码专门作为桥牌引擎，它可以计算出如何竞叫和打什么牌。桥牌引擎基于功能可以大致分为三个部分，即庄家的出牌，防守方的出牌，以及叫牌。 桥牌引擎大体上是通过一些处理特定牌局的特定代码段来表示知识库。
还有其他的成千上万行代码用于处理用户界面。 用户界面用于客户与计算机进行比赛，根据桥牌规则产生合理的处理结果，同时展示了“桥牌男爵”是如何打牌以及叫牌等。
用户界面通过展示出程序的叫牌与出牌过程来同用户进行交互，这一过程还要调用c函数来根据当前的牌局情况做出决策。用户界面还会根据当前情况的一些细节更新桥牌引擎的数据结构。
通常，当一位客户与“桥牌男爵”坐下来玩几局桥牌时， 客户会扮演四个角色之一，而“桥牌男爵”会担任客户队友或对手的角色。 每个角色是信息隔离的：例如，一个对手不知道另一个对手拥有什么牌，也不知道该客户的队友拥有什么牌。（客户也可以选择允许“桥牌男爵”扮演的角色知道其他牌手的手牌并改变打牌思路。）
对于庄家来说，以前版本的“桥牌男爵”都使用了Ad-hoc模式匹配技术。 不同的是，“桥牌男爵 8”（最新版本）应用了本文后面介绍的新的AI规划技术。但是我们并没有从“桥牌男爵”中删除旧的技术，用户可以选择使用新的AI规划技术也可以选择旧的Ad-hoc技术。 我们还增加了一些选项，以使得新技术在特定牌局下的出牌时间限制在30秒，60秒或120秒内。这个新版本的“桥牌男爵”于1997年10月上市。
3.AI技术的使用
为了提升“桥牌男爵”的表现，我们在它的基于HTN（层级任务 网络规划技术）的庄家角色的例程中做了补充。通过我们的研究（Smith et al.1996a; Smith et al.1996c; Smith et al; 1996e; Smith 1997年）发现，其实桥牌是一种规划游戏。在打牌时，玩家利用许多不同的固定策略来赢得墩数。这些策略有固定名称（例如流血，交叉浮动，飞行，兑现和发现打法）。在一定程度上，桥牌选手的能力取决于该选手能否巧妙地规划和执行这些策略。对于同时负责打庄家和明手的牌的庄家尤其如此。在大多数桥牌角色中，庄家将在游戏开始时花费一些时间来制定一个粗略的计划，用于决定如何打出庄家和明手的牌。这个计划通常是各种策略的组合。由于庄家不确定对手手中的牌和对手打牌的策略，这个计划通常需要考虑对手出牌的各种可能性。
通过调整和扩展HTN规划的一些属性，我们就能够利用桥牌具有规划性这一特征。 我们使用规划技术来开发游戏树，使得其中每个节点的分支对应于玩家可能使用的不同策略，而不是玩家可能打出的不同的牌。 由于有效的策略的数量通常远少于可能的出牌的情况，这使得我们可以开发出足够小的游戏树来使其可以被完全搜索。下面我们给出HTN规划的概述，并描述我们如何调整它以用于“桥牌男爵”。
a.HTN计划概述
最初的HTN规划技术是在20多年前开发的（Sacerdoti 1974; Tate 1977），并且力求在现实世界的规划问题中体现出很好的应用性能（Currie和Tate 1985; Wilkins 1988）。但直到近来才出现研究人员为HTN规划技术制定了一个的连贯的理论基础。最近，利用数学对HTN规划技术进行的分析已经表明它比使用STRIPS风格的技术进行规划要严格得多（Erol et al.1994b）。除此之外，目前还定义了一些特性，如规划算法的完整性，稳定性（Erol et al.1994a），复杂性（Erol et al.1996），以及各种控制策略的相对效率。同时人们可以在lt;http://www.cs.umd.edu/projects/plus/umcp/manualgt;上找到一个实验用的与域无关的HTN规划器。目前，针对若干工业问题正在开发特定领域的HTN规划器（(Aarup et at. 1994; Hebbar et al. 1996; Smith et
al. 1996b; Smith et al. 1996d; Wilkins amp; Desimone 1994）。
为了制定规划，HTN规划系统使用了任务分解策略，规划系统将任务分解到越来越小的子任务直到找到可以直接执行的原子任务。 HTN规划系统的知识库是基于包含方法的， 每种方法包括：1.如何将一些任务分解成一组子任务的描述。2.使得任务适用于该方法的各种限制。3.子任务和子任务间关系的各种限制。 要完成给定的任务，规划器要选择一个适用的方法，并且实例化该方法来将任务分解为子任务。之后再选择并实例化其他的方法，将更多的任务分解成子任务。如果子任务本身的限制或它们之间的相互作用使得规划不可行，那么规划系统将回溯并尝试其他方法。
以下举出一个简单的例子：
看电影可分为：1.在剧院看电影。2.在家看录像带。首先，在剧院看要依次执行：去剧院，获得电影票，看电影，回家。 此外，在家看要依次执行：去商店，购买录像带，回家看电影。
现在，考虑看电影泰坦尼克号这样一个任务。使用HTN规划技术解决规划问题通常比这个简单的例子复杂得多。 例如，规划者可能需要识别和解决子任务之间的相互影响（例如在电影开始之前必须要到剧院）。 如果这种交互作用无法解决，那么规划者可能需要回溯并尝试使用另一种方法。
b.庄家打法的HTN规划
“桥牌男爵 8”的Tignum 2部分使用了改进版的HTN规划技术来规划定约桥牌中的庄家打法。 为了表示桥牌中打牌的各种策略，Tignum 2使用了类似于HTN方法的结构，但是需要通过一些修改来表示多机构和不确定性。 Tignum 2使用状态信息集来表示庄家确定的卡牌的位置，而用置信函数表示与庄家不确定的卡牌位置相关的概率。
还有些方法涉及到对手的行为。 比如在Tignum 2中，我们允许这些方法对对手手中的牌进行假设，并借此设计我们的方法，以便使得大多数可能存在的状态都被至少一种方法所覆盖。 在我们的所有方法中，子任务都是完全有序的; 也就是说，子任务在方法中的顺序必须是这些子任务完成的顺序。
例如，考虑我们的算法如何实例化特定的角色的某些方法。 假设南方牌手（庄家）正在尝试一种技巧，该技巧是一种玩家试图用大牌赢得一墩的策略：即在拥有更大的牌的对手后出牌。 如果西方牌手（防守者）拥有hearts;K，但是在领先的时候没有出牌，那么北方牌手（明手）将能够用hearts;Q赢得一墩，这是因为北方选手在西方选手之后出牌。 （如果她（他）有其他选择，西方牌手将不会打出hearts;K，因为这样的话北方牌手就会通过hearts;A赢得这一墩并用hearts;Q赢得下一墩。）但是，如果东方牌手（另一个防守者）拥有hearts;K，东方牌手将在北方牌手打出hearts;Q之后进行出牌，这样北方则不会获胜。 请注意，这些方法会考虑到游戏中的每个玩家的出牌情况。
对于以这种方式生成的游戏树，每个状态的分支数量不代表角色可以做出的动作的数量（如在传统的游戏树搜索过程中那样），而是代表不同的角色可以使用的规划。这种游戏树足够小，可以一直搜索到最后，从而预测玩家所有可能的出牌序列。
为了测试游戏树中轮到庄家出牌时候的情况，我们的算法对节点的孩子节点进行了加权平均，并基于置信函数产生的概率选择期望得分最高的打法。 例如，如果南方牌手选打出由“细分”方法产生的hearts;2，这导致预期得分为 210，而不是由“兑现”方法产生的spades;A， 这会使得分为-100。
4.应用程序使用和回报
我们推出“桥牌男爵 8”的预发布版本，用以参加最近举行的计算机桥牌世界冠军赛，也就是由美国人主办的“男爵巴克莱定约桥牌世界冠军赛（ACBL）”。 为期五天的比赛已经于1997年7月28日至1997年8月1日在新墨西哥州的阿尔伯克基举行。据“纽约时报”（Truscott 1997）和华盛顿邮报（Chandrasekaran 1997）报道，比赛获胜者是“桥牌男爵” ， 更具体地说，获奖者是包含Tignum 2代码的 “桥牌男爵 8”的预发布版本。 竞争者包括五个电脑程序.
“桥牌男爵 8”的正式发布并开始销售于1997年10月; 在1997年的最后三个月里，有1000多个客户购买了它。 吉姆·洛伊（Jim Loy，1997）在对桥牌程序的评论中提到“桥牌男爵”：“它打牌的表现明显更优秀，所以才会成为市场上最热销的程序。”
5.应用程序开发和部署
a.开发时间
一位研究生通过复用“桥牌男爵”的几百行代码完成了HTN规划技术的所有主要的编程。还有两个人也对此提供了一些帮助。此外还有几个人偶尔提供了一些协助，主要是讨论哪些知识需被纳入以及如何执行构件。开发过程中我们没有使用任何正式的开发方法。
我
全文共6286字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[10905]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
