讲义组合游戏论_第1页
讲义组合游戏论_第2页
讲义组合游戏论_第3页
讲义组合游戏论_第4页
讲义组合游戏论_第5页
已阅读5页，还剩13页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、论（2）Zhou Yuan组合by Zhou YuanOutlineCh.3 图的Ch.4 组合的和by Zhou YuanCh.3 图的有向图上的有向图G上的双人有确定的结果（win-lose game）有向边ab：b是a的后继将棋子放在一个选择的点x0，作为起点双方轮流将棋子移动到一个后继结点不能移动者失败一般来说，图没有环by Zhou Yuan示例，每次取1, 2, 3粒石子取石子by Zhou YuanSprague-Grundy函数定义在有向无环图G上为每一结点x定义其 SG函数值（非负整数）或 mex: minimal excludingg(x) = 0：先手必败(P)；否则先手

2、必胜(N)by Zhou Yuan示例右图SG函数的计算最初的取石子by Zhou Yuan练习(8)中，每次只能取1, 3, 4粒石子取石子求每一个状态的SG函数值by Zhou Yuan练习(9)在一堆石子中取石子每次能取走不超过一半的石子最少取一粒石子求每一个状态的SG函数值by Zhou Yuan0)练在一个二维棋盘上有一个棋子双人轮流移动这个棋子 将它移动至靠左边的方格或者同列靠下面的方格（有左边界和下边界）求每一个位置上的SG函数值by Zhou YuanCh.4 组合的和）给定了几个组合（子可以组成一个新的 新的状态为原有组合状态的联合 双方移动规则：选择一个子进行移动新称为这些

3、子的和G = G1 + G2 + + Gnby Zhou Yuan定理2：Sprague-Grundy Theorem设gi是Gi的SG函数值g是G的SG函数值则证明思路：设b = g(x1, x2, , xn)对于0 = a b, 有一个后继的SG值为a不存在一个后继的SG值为bby Zhou Yuan证明对于0 = a b, 有一个后继的SG值为a，选择k使得 令则二进制中d的第k位是一个1由于a b，则a的第k位是0，b的第k位是1 由于，定存在一个子：设为G1，g1(x1)的第k位是1:存在后继x1使得 于是从(x1, x2, , xn)移动到(x1, x2, , xn)by Zhou

4、 Yuan证明(contd)不存在一个后继的SG值为b反设存在一步移动 从(x1, x2, , xn)移动到(x1, x2, , xn)若有 则g1(x1) = g1(x1) 与SG函数的定义：x1 = x1by Zhou Yuan理解将任何组合等价为适当大小的一堆石子by Zhou Yuan1)练0)接练如右棋盘判断先手必胜还是必败若必胜提供必胜策略by Zhou Yuan2)练一列n个站立的保龄球两个人轮流 选择击倒某一个，或者是连续的两个保龄球击倒最后一个球的玩家胜利的SG函数求这个by Zhou Yuan3)练在平面上有很多点双方轮流画封闭的圆圈至少经过一个点不能碰到已有的圆圈不能画圆圈分析这

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论