搜索
本科毕业设计（论文）外文翻译译文学生姓名：强旺院（系）：计算机学院专业班级：计0702指导教师：强新建完成日期：2011年3月15日数学行为中的人工智能游戏BehavioralMathematicsforGameAI作者：DAVEMARK起止页码：55—68页出版日期：March5,2009出版单位：CourseTechnologyPTR外文翻译译文：博弈论当从大量各式的学科研究解决了决策理论的巨兽，或许一个最成功的(合宜的与我们相关)突袭到这个领域里是在博奕论区域做的努力的汇集。博奕论从来都不是主流话题。对博弈论的最初的提及可回溯至18世纪的早期。然而，伟大的数学天才冯·诺依曼则是广泛熟知的博弈论之父。在1928年他发表了在这一主题的一系列的论文。对博弈论更加明确的概念的论点由冯·诺依曼和经济学家奥斯卡·摩根斯坦合著的出版书籍《博奕论与经济行为》在1944年发行。不久之后，在1951年约翰·福布斯·纳什对博弈论的均衡点的分析使其更多在之后达到了另一个水平。然而总体上，博奕论经历过衰退和效益的浮动。主要限制在军事战略或者科学竞技场上。它在其他领域应用于政治学、社会学、生物学、计算机科学等，甚而逻辑学和哲学。在20世纪80年代，冯·诺依曼的原文最终使世界经济复苏以后的50年超过在冯·诺依曼和奥斯卡·摩根斯坦出版了他们在博弈论这个话题的伟大的学术论文之后的35年间。尽管博奕论这个名称只是简单地被联系到比赛的概念上。但实际上，名称“博弈论”是（一些也许致使了在科学界严重被考虑的延迟)一个有点不合时宜的错误的名称。其核心概念更加趋向于一般分析报告的结果——游戏程序的一些适用性。在人工智能的领域中，其中一项最重要的任务是灌输对决策能力的承担——游戏程序的一些适用性。可以知道的是地方性的对博奕论的想法是研究一个自然开始的地方关于怎样决定在比赛中的人为代理的创新。博弈论的定义当你读到博弈论时，你可以适宜地参考下以下说明：俩人对局：俩个人打的比赛。或者说，这也适用于俩个团队的人一起往同样的目标努力(例如：桥牌)。零和博弈：有一个平衡的终端条件，例如只有一个优胜者或一个失败者的比赛(例如：国际象棋、验查员、一字棋)，或者是一个选手的赢是另一个选手的输的比赛。(例如：在桌前一定量支出地玩扑克)。非零和博弈：比赛有一定程度的赢取和丢失的地方(例如：扑克，一种需要运气的游戏，像桥牌一样需要获得一定分数的比赛)。完全信息博弈：一种需要参与者有完善的信息才能进行下去的比赛(例如：国际象棋、验查员、一字棋)。不完全信息博弈：参与者难以发现确切答案的比赛(例如:主力舰,扑克,类似于战争中的模糊不清)。合作社：比赛球员能形成约束承诺的地方。对称：比赛双方有着同一信息和玩法通过同一规则。不对称：比赛中一方的规则或者是信息与另外一方的规则或者是信息不同。初级起步十四世纪英国逻辑学家和方济会天主教修士威廉·奥克姆提出了在所有科学理论中最有用的一个概念。奥克姆叙述说。对于那些无法叙述拉丁语的(我承认我必须包括这里)，这可以大致翻译为“不能够在需要之外倍增个体。”在这必须再大量声明使这个公告更加清晰明朗。两者或更多的是“所有其他的事情必须是平等的，简单的来说是最好的。”和“最简单的解释可以掩盖住所有的事实以达到最经常使用的最好的效果。”冯·诺依曼的兄弟奥克姆常常会以他高兴。尽管他是一位精采地天才的数学家(认识他的著名是在他的拒绝使用，实际上是为了帮助他而发明的巨型计算机，因为他可以非常快速地做演算在他的头脑中)。当冯·诺依曼先生知道闪光和样式不适当时，其中他的一个博奕论的介绍的有用的方面是它对足够小的零件的辩明概念在比赛中是容易的的结果的深入。在博奕论上的例子的描绘经常只是简单规则和平等地透明地决定的可能。事实上证明冯·诺依曼和奥斯卡·摩根斯坦对博弈论的主张紧密相结合着，重点来说博弈论和经济效益行为在很大程度上是很难完全理解的。冯·诺依曼对俩人对局，零和博弈和完全信息博弈开始有了初步的想法。通过对奥克姆的尊敬，我们可以从小型积木中学会并且通过自身去建立。通过这些例子，我们可以建立关于怎么进行决定的基础，不仅仅从逻辑的立场上建立，更是从数学的观点来建立。这是对数学的理论成果的实际应用，它允许我们建立的模型有些微妙的不同，在第一章中我们已经提及。匹配便士在第四章中游戏及经济行为的理论，冯·诺依曼和奥斯卡·摩根斯坦开始了话题为“几个基本的游戏”，它有一个小节，有一节是“最简单的游戏。”他们不是在开玩笑。他们推出的第一个是并不常提及的,我们称之为匹配便士。它类似于石头，剪刀,布，但有两个选择，而不是三个。（我告诉你们他们不是在开玩笑！）这是一个零和博弈，一方比赛者输则另一方就会获益。游戏中涉及到两名比赛者和两个便士。（我尽量使用有趣的选择，尽管缺乏长期的游戏...但是这只是我的两分钱。）每个比赛者盖住他的一分钱，打开它要么元首或尾巴。然后，他们同时显示对方的硬币，以及随之而来的得分，是一轮非常复杂严峻的考验。正如你可以看到在图5.1，如果便士匹配要么两国元首或两个尾巴，那么比赛者A是赢家。相反，如果硬币不匹配，那么比赛者B是赢家。（我不知道它是如何确定谁是比赛者A，但我认为他们可以抛硬币。）比赛者A元首尾巴比赛者B元首A:+1（赢）B:-1（输）A:-1（输）B:+1（赢）尾巴A:-1（输）B:+1（赢）A:+1（赢）B:-1（输）图5.1匹配便士矩阵图·如果便士有相同两面，那么比赛者A获胜。·如果便士有相反两面，那么比赛者B获胜。在这里要吸取的教训严格来说是术语之一。选配几个便士是一种游戏，其中有没有“纯策略。”也就是说，不存在“最好的回应。”一个单纯的战略是一个什么样的参赛者应该在任何时间做完整的决定。也就是说，如果你选择这个方式，你会赢得（这样做至少将获得最大限度地的机会）。例如，正如我们讨论过，一字棋有一个纯策略。如果你想成功，你必须做出一定的动作。如果你选择这些举措，您将获得最大的机会，其中，在一字棋的情况下，通常会导致一场平局。在最坏的情况下，它并不会导致亏损。在最好的情况下，如果你的对手犯错（未选择纯策略），你会获胜。当你玩游戏时纯策略就像是一个金矿，但是他们就是一个丧钟，对于游戏开发者来说。如果玩家发现了对您的人工智能玩纯策略，他们将能够用很少的思想或工作时间赢得所有。另一方面，如果人工智能代理可以决定一个纯粹的战略，使它们每一次以同样的方式发挥，他们变得非常明确，因此，很无聊。在匹配便士中，因为是不需要知识的游戏环境，没有感知，并没有计算到制造，甚至规范性决策理论不能前来救援并且告诉我们答案，我们应该对任何给定自由发挥。因此，不存在玩纯策略。在任何一个时间没有“最好“的事情。有趣的是，尽管由于没有“最好”的策略，随着时间的推移有一个最坏的战略...总是选择你的硬币相同的脸。如果你这样做，它不会需要很长时间和其他人来决定你的模式，并作出相应的反应。同样，一个并行的策略是最糟糕的头和尾之间始终交替。你的对手应该能够拿起你的方法，发挥这样一种方式，你可预见的话则重复自己的优势。请注意，在这一点上，我们还没有推出了一些知识来意识到它的发挥格局。如果人工智能代理人能辨别，并据此计算（即扩展模式），那么它可能作出什么决定，应该发挥的规范性理论为每一个相当不错的尝试。除非，只希望我们大约懂得一些应用心理学以确定你的伙伴的行为模范，因此得出，他的下一步行动。如果你的对手更是合理的善于混淆视听，但是，任何短暂的机会没有要比技巧产生出更好的效果。把它混合这与纯策略相反的做法被称为混合策略。在这种方法中，您选择的战略之间是提供给您多种。通常，您可以分配这些概率决定选择哪一个，你可以做。这是值得我们深入讨论以后。我只想说，在任何一个时间里选择匹配便士，你只有两种选择。虽然这么说，最好的办法是由所有不同的一个点随机的方式播放。当然，如果你这样做，你不是比翻转，如果你有你的硬币了。两者更进一步，为什么翻转两枚硬币，看着他们比赛的时候，你和你的对手可能只是一个硬币翻转和它做什么？但现在与我兴高采烈地争论简单的游戏的整个前提是，奥卡姆不会批准。正如我所提到的，游戏大致类似于石头，剪刀，布。所不同的是，有三种可能的石头，剪刀，布，而不是简单地扮演两个。这就像是制作获得3×3矩阵一样。无论如何，像是匹配便士，对石头，剪刀，布来说这没有“纯策略”，你可以按照此获取得更多的成功。在游戏中匹配穿孔首先，它像匹配便士那样简单，与计算机和视频游戏世界没有真正的比较。不过，过去几年大量的游戏中使用了某种形式或另一种这样的机制。事实上，人们对一些游戏那样声称。如果我们想象一个最简单的排序格斗游戏，我们可以先画一个平行线。假设参赛者A有两个攻击高，低冲头。参赛者B，另一方面，有两个防御高和低块。游戏的目标是让一个参赛者A过去参赛者B的块那里并且得分命中。如果B的地块为A的攻击（即高对比高）同一地区，则一个没有一分。如果B的块是在错误的区域（即高对比低），则A的分数一击。鉴于这种游戏的参数，我们一样可以完全分析，同样的方式选配几个便士。没有“最好”的战略，其他的发挥不重复的相同的序列一遍又一遍。你唯一能做的就是观察其他参赛者的潜在线索，他是打哑和重复模式。如果两个参赛者的选择适当的混合，最好你可以尝试完成下面按钮的随机的混合。写入代码虽然这可能看起来很明显，但我还是把它写在这。如果你把整体的人工智能配对便士或者是假定格斗游戏中的代码，这就是它的大致模样。typedefenum{MV_HEADS=0,MV_TAILS=1}PENNIES_MOVE;PENNIES_MOVEMyGame::SelectPenniesMove(){PENNIES_MOVEThisMove=PENNIES_MOVE(rand()%2);returnThisMove;}这似乎看起来很没意义，不是吗？我们有一个单一的功能，它返回0或1，在这种情况下，代表正面或反面。顺便说一句，如果你在函数返回三个而不是两个选择，你有人工智能的石头，剪子，布。typedefenum{MV_ROCK=0,MV_PAPER=1,MV_SCISSORS=2}RPS_MOVE;RPS_MOVEMyGame::SelectRPSMove(){RPS_MOVEThisMove=RPS_MOVE(rand()%3);returnThisMove;}正如我在第一章中建议，如这些游戏不仅有对另一个人玩的外观。如果你最好的选择是随机播放，唯一的选择是，这样做或没有。如果你选择随机播放，且你的对手也这样做，那么我们就没有一个游戏满足了条件“有趣的选择。”这也相当快地使人变得很累。（我不相信这是一个巧合。）囚徒困境较常被引用的一个例子是博弈论的囚徒困境。它最初是由弗罗德·梅里尔和德雷舍·梅尔文在著名的兰德研究所工作时所认为的1950年的坦克。阿尔贝瓦·特塔克正式定义收益与游戏并且给它命名为囚徒的困境。在冯·诺依曼的精神下，这是两个人的，完善的知识游戏。然而，与匹配便士相比，这不是一个零和游戏，与两个人可以“双赢”的程度不同。同样地，双方参赛者有可以“输”的可能。而这，我们将看到的，就是在这次比赛成为一个重要的但却是欺骗的因素。在其最经常被引用的形式，囚犯的困境使用了两名嫌疑人假设的情况，被警方逮捕。警方已为上的一个重大罪行进行了10年徒刑定罪但证据不足。警方同时与囚犯分开，并参与他们每个人提供同样的协议。如果证明（即“缺陷”）就对其他与其他检控保持沉默，背叛者失去自由和沉默的帮凶收到完整的10年定期徒刑。如果双方保持沉默，无论是在监狱中的囚犯被判刑仅半年，而且对未成年人的负责来说。如果每个背叛对方，每收到一个五年刑期。每个囚犯必须选择背叛对方，或保持沉默。每个人是有保证的，其他就不会知道在调查结束前背叛。提出的问题是，由于这些参数，包括具体的长度准则，囚犯的行为应如何做选择？从数学的角度看，看似是解决简单的问题。但是，并不是每个人都注意到了解决方法。乍看之下（图5.2），作出的选择似乎是：如果我保持沉默我可能去坐牢10年牢。如果我告诉了我的伙伴，我可能失去自由。上面