版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、ACM程序设计杭州电子科技大学 刘春英 2022/9/192今天,你 了吗?AC2022/9/193每周一星(10):Lin2144 2022/9/194第十一讲组合博弈入门(Simple Game Theory)2022/9/195导引游戏(1) 玩家:2人;(2) 道具:23张扑克牌;(3) 规则:游戏双方轮流取牌;每人每次仅限于取1张、2张或3张牌;扑克牌取光,则游戏结束;最后取牌的一方为胜者。2022/9/196基本思路?请陈述自己的观点2022/9/197第一部分简单取子游戏(组合游戏的一种)2022/9/198什么是组合游戏有两个玩家;游戏的操作状态是一个有限的集合(比如:限定大小
2、的棋盘);游戏双方轮流操作;双方的每次操作必须符合游戏规定;当一方不能将游戏继续进行的时候,游戏结束,同时,对方为获胜方;无论如何操作,游戏总能在有限次操作后结束;2022/9/199概念:必败点和必胜点(P点 & N点)必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。 2022/9/1910必败(必胜)点属性(1) 所有终结点是必败点(P点);(2) 从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点);(3)无论如何操作, 从必败点(P点)都只能进入必胜点(N点)
3、.2022/9/1911取子游戏算法实现 步骤1:将所有终结位置标记为必败点(P点);步骤2: 将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;步骤4: 如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。2022/9/1912课内练习:Subtraction Games:subtraction set S = 1, 3, 4x : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14Pos: P N P N N N N P N P N N N N P
4、2022/9/1913实战练习kikis game 2022/9/1914第二部分Nim游戏2022/9/1915Nim游戏简介有两个玩家;有三堆扑克牌(比如:可以分别是 5,7,9张);游戏双方轮流操作;玩家的每次操作是选择其中某一堆牌,然后从中取走任意张;最后一次取牌的一方为获胜方;2022/9/19162022/9/1917初步分析(0, 0, 0) (0, 0, x) (0, 1, 1) (0, k, k) P-position P-position P-position N-position (14, 35, 46) ? 2022/9/1918引入概念:Nim-Sum定义: 假设 (
5、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=0m).2022/9/1919定理一: 对于nim游戏的某个位置(x1,x2,x3),当且仅当它各部分的nim-sum等于0时(即x1x2x3=0),则当前位于必败点。定理一也适用于更多堆的情况2022/9/1920定理一的证明 2022/9/1921思考(1):有了定理一,如果判断某个游戏的先手是输还是赢?2022/9/1922思考(2):对于必胜点,如何判断有几种可行的操作方案?2022/9/1
6、923实例分析(HDOJ_1850)Being a Good Boy in Spring Festival 2022/9/1924第三部分Graph Games &Sprague-Grundy Function2022/9/1925What 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 pl
7、ayer who is confronted with a terminal position at his turn, and thus cannot move, loses.2022/9/1926Example about graph game:0,0,01,0,00,0,10,1,05,7,92,0,02022/9/1927The Sprague-Grundy Function.Definition: The Sprague-Grundy function of a graph, (X,F), is a function, g, defined on X and taking non-n
8、egative integer values, such thatg(x) =minn 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) =mexg(y) : y F(x). (2)2022/9/1928Use of the Sprague-Grundy Function:P-positions: Positions x for which g(x) = 0 N
9、-positions: Positions x for which g(x) 0 2022/9/1929Exercise:What is the SG-value of the subtraction game with subtraction set S = 1, 2, 3?x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14. . .g(x) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2. . .2022/9/1930Question:What can the S-G value describe?2022/9/1931Part 4:Sums of Com
10、binatorial Games2022/9/1932What is so-called “Sums of Combinatorial Games”?2022/9/1933Theorem 2.If gi is the Sprague-Grundy function of Gi , i = 1, . . . , n, then G = G1 + + Gn has Sprague-Grundy function g(x1, . . . , xn) = g1(x1) gn(xn).2022/9/1934Applications:Sums of three Subtraction Games.In t
11、he first game: m = 3 and the pile has 9 chips. In the second: m = 5 and the pile has 10 chips. In the third:m = 7 and the pile has 14c hips.g(9, 10, 14) =?2022/9/1935附:参考源码(HDOJ-1536)#include#include#includeusing namespace std;int k,a100,f10001;int mex(int p) int i,t; bool g101=0; for(i=0;ik;i+) t=p
12、-ai; if(t0) break; if(ft=-1) ft=mex(t); gft=1; for(i=0;i+) if(!gi) return i; int main() int n,i,m,t,s; while(scanf(%d,&k),k) for(i=0;ik;i+) scanf(%d,&ai); sort(a,a+k); memset(f,-1,sizeof(f); f0=0; scanf(%d,&n); while(n-) scanf(%d,&m); s=0; while(m-) scanf(%d,&t); if(ft=-1) ft=mex(t); s=sft; if(s=0) printf(L); else printf(W); printf(n); 2022/9/1936课后练习2008ACM ProgrammingExercise(12)_博弈入门 1517 A Multiplication Game 1079 Calendar Game 2147 ki
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高中语文古诗词诵读无衣课件新人教版必修上册
- 高中语文第2课千言万语总关“音”第4节声情并茂-押韵和平仄课件新人教版选修语言文字应用
- 高三诗歌复习-山水田园诗公开课
- 2024至2030年中国带嘴茶壶数据监测研究报告
- 2024年重庆市初中学业水平暨高中招生考试语文试题(B卷)含答案
- 2024至2030年中国三轮车用前挡泥皮数据监测研究报告
- 2024年甘肃省白银市、武威市、嘉峪关市、临夏州中考语文试题含解析
- 2024年中国紫砂红泥茶壶市场调查研究报告
- 2024年中国桂皮油市场调查研究报告
- 制定市场营销的行动纲要计划
- 《声音的产生与传播》说课课件
- 小学高年级学生数学自主学习能力培养现状的调查问卷(学生卷)
- 社工创业计划书
- 黑龙江省哈尔滨市第九中学2023-2024学年高三年级上册期中考试语文试题(解析版)
- 《工装夹具设计》课程标准
- 医院药房岗前培训
- 湘菜餐厅品牌策划方案
- 国内外质量认证标准对比与分析
- 2023年7月黑龙江高中学业水平合格性考试历史试卷真题(含答案详解)
- 郑州热力总公司招聘笔试题
- 姨妈巾新媒体运营方案
评论
0/150
提交评论