[理学]lecture_11组合博弈入门.ppt

  1. 1、本文档共38页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[理学]lecture_11组合博弈入门

ACM程序设计 杭州电子科技大学 刘春英 acm@hdu.edu.cn 今天, 你 了吗? 每周一星(10): 第十一讲 组合博弈入门 (Simple Game Theory) 导引游戏 (1) 玩家:2人; (2) 道具:23张扑克牌; (3) 规则: 游戏双方轮流取牌; 每人每次仅限于取1张、2张或3张牌; 扑克牌取光,则游戏结束; 最后取牌的一方为胜者。 基本思路? 请陈述自己的观点 第一部分 简单取子游戏 什么是组合游戏—— 有两个玩家; 游戏的操作状态是一个有限的集合(比如:限定大小的棋盘); 游戏双方轮流操作; 双方的每次操作必须符合游戏规定; 当一方不能将游戏继续进行的时候,游戏结束,同时,对方为获胜方; 无论如何操作,游戏总能在有限次操作后结束; 概念:必败点和必胜点(P点 N点) 必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。 必败(必胜)点属性 (1) 所有终结点是必败点(P点); (2) 从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点); (3)无论如何操作, 从必败点(P点)都只能进入必胜点(N点). 取子游戏算法实现—— 步骤1:将所有终结位置标记为必败点(P点); 步骤2: 将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点) 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ; 步骤4: 如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。 课内练习: Subtraction Games: subtraction set S = {1, 3, 4} 实战练习… 第二部分 Nim游戏 Nim游戏简介 有两个玩家; 有三堆扑克牌(比如:可以分别是 5,7,9张); 游戏双方轮流操作; 玩家的每次操作是选择其中某一堆牌,然后从中取走任意张; 最后一次取牌的一方为获胜方; 初步分析 (0, 0, 0) 引入概念:Nim-Sum 定义: 假设 (xm · · · x0)2 和(ym · · · y0)2 的nim-sum是(zm · · · z0)2,则我们表示成 (xm · · · x0)2 ⊕ (ym · · · y0)2 = (zm · · · z0)2, 这里,zk = xk + yk (mod 2)(k=0…m). 定理一: 对于nim游戏的某个位置(x1,x2,x3),当且仅当它各部分的nim-sum等于0时(即x1⊕x2⊕x3=0),则当前位于必败点。 定理一的证明…… 思考(1): 有了定理一,如果判断某个游戏的先手是输还是赢? 思考(2): 对于必胜点,如何判断有几种可行的操作方案? 实例分析(HDOJ_1850) Being a Good Boy in Spring Festival 第三部分 Graph Games Sprague-Grundy Function What is the graph game ? (1) Player I moves first, starting at x0. (2) Players alternate moves. (3) At position x, the player whose turn it is to move chooses a position y ∈ F(x). (4) The player who is confronted with a terminal position at his turn, and thus cannot move, loses. Example about graph game: The Sprague-Grundy Function. Definition: The Sprague-Grundy function of a graph, (X,F), is a function, g, defined on X and taking non-negative integer values, such that g(x) =min{n ≥ 0 : ng(y) for y ∈ F(x)}. (1) In words, g(x) the smallest non-negative integer not found among the Sprague-Grundy values of the followers of x. g(x) =mex{g(y) : y ∈ F(x)}. (2) Use of the Sprague-Grund

文档评论(0)

hhuiws1482 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:5024214302000003

1亿VIP精品文档

相关文档