




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
ACM程序设计杭州电子科技大学刘春英acm@8/16/20241今天,你
了吗?AC8/16/20242每周一星(9):Hugo8/16/20243第十讲组合博弈入门(SimpleGameTheory)8/16/20244导引游戏(1)玩家:2人;(2)道具:23张扑克牌;(3)规则:游戏双方轮流取牌;每人每次仅限于取1张、2张或3张牌;扑克牌取光,则游戏结束;最后取牌的一方为胜者。8/16/20245基本思路?请陈述自己的观点8/16/20246第一部分简单取子游戏(组合游戏的一种)8/16/20247什么是组合游戏——有两个玩家;游戏的操作状态是一个有限的集合(比如:限定大小的棋盘);游戏双方轮流操作;双方的每次操作必须符合游戏规定;当一方不能将游戏继续进行的时候,游戏结束,同时,对方为获胜方;无论如何操作,游戏总能在有限次操作后结束;8/16/20248概念:必败点和必胜点(P点&N点)必败点(P点):前一个选手(Previousplayer)将取胜的位置称为必败点。必胜点(N点):下一个选手(Nextplayer)将取胜的位置称为必胜点。
8/16/20249必败(必胜)点属性(1)所有终结点是必败点(P点);(2)从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点);(3)无论如何操作,从必败点(P点)都只能进入必胜点(N点).8/16/202410取子游戏算法实现——
步骤1:将所有终结位置标记为必败点(P点);步骤2:将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点),则将该点标记为必败点(P点);步骤4:如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。8/16/202411课内练习:SubtractionGames: subtractionsetS={1,3,4}x:01
234
5678
91011121314…Pos:PNPNNNNPNP
N
N
N
N
P…8/16/202412实战练习…kiki'sgame
8/16/202413第二部分Nim游戏8/16/202414Nim游戏简介有两个玩家;有三堆扑克牌(比如:可以分别是5,7,9张);游戏双方轮流操作;玩家的每次操作是选择其中某一堆牌,然后从中取走任意张;最后一次取牌的一方为获胜方;8/16/2024158/16/202416初步分析(0,0,0)(0,0,x)(0,1,1)(0,k,k)P-positionP-positionP-positionN-position(14,35,46)???8/16/202417引入概念: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(mod2)(k=0…m).8/16/202418定理一:
对于nim游戏的某个位置(x1,x2,x3),当且仅当它各部分的nim-sum等于0时(即x1⊕x2⊕x3=0),则当前位于必败点。定理一也适用于更多堆的情况~8/16/202419定理一的证明……
8/16/202420思考(1):有了定理一,如何判断某个游戏的先手是输还是赢?8/16/202421思考(2):对于必胜点,如何判断有几种可行的操作方案?8/16/202422实例分析(HDOJ_1850)BeingaGoodBoyinSpringFestival
8/16/202423第三部分GraphGames&Sprague-GrundyFunction8/16/202424Whatisthegraphgame?(1)PlayerImovesfirst,startingatx0.(2)Playersalternatemoves.(3)Atpositionx,theplayerwhoseturnitistomovechoosesapositiony∈F(x).(4)Theplayerwhoisconfrontedwithaterminalpositionathisturn,andthuscannotmove,loses.8/16/202425Exampleaboutgraphgame:0,0,01,0,00,0,10,1,05,7,92,0,0……8/16/202426TheSprague-GrundyFunction.Definition:
TheSprague-Grundyfunctionofagraph,(X,F),isafunction,g,definedonXandtakingnon-negativeintegervalues,suchthat
g(x)=min{n≥0:n<>g(y)fory∈F(x)}.(1)
Inwords,g(x)thesmallestnon-negativeintegernotfoundamongtheSprague-Grundyvaluesofthefollowersofx.
g(x)=mex{g(y):y∈F(x)}.(2)8/16/202427Useof
theSprague-GrundyFunction:
P-positions:Positionsxforwhichg(x)=0
N-positions:Positionsxforwhichg(x)>0
8/16/202428Exercise:WhatistheSG-valueofthesubtractiongamewithsubtractionsetS={1,2,3}?x01234567891011121314...g(x)012301230123012...8/16/202429Question:
WhatcantheS-Gvaluedescribe?8/16/202430Part4:SumsofCombinatorialGames8/16/202431What
isso-called——
“SumsofCombinatorialGames”?8/16/202432Theorem2.
Ifgi
istheSprague-GrundyfunctionofGi
, i=1,...,n,then G=G1+···+GnhasSprague-Grundyfunction g(x1,...,xn)=g1(x1)⊕···⊕gn(xn).8/16/202433Applications:SumsofthreeSubtractionGames.Inthefirstgame:m=3andthepilehas9chips.Inthesecond:m=5andthepilehas10chips.Inthethird:m=7andthepilehas14chips.g(9,10,14)=?8/16/202434附:参考源码(HDOJ-1536)#include<stdio.h>
#include<string.h>
#include<algorithm>
usingnamespacestd;
intk,a[100],f[10001];
int
mex(intp)
{
int
i,t;
boolg[101]={0};
for(i=0;i<k;i++)
{
t=p-a[i];
if(t<0)
break;
if(f[t]==-1)
f[t]=mex(t);
g[f[t]]=1;
}
for(i=0;;i++)
{
if(!g[i])
returni;
}
}
intmain()
{
int
n,i,m,t,s;
while(scanf("%d",&k),k)
{
for(i=0;i<k;i++)
scanf("%d",&a[i]);
sort(a,a+k);
memset(f,-1,sizeof(f));
f[0]=0;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
s=0;
while(m--)
{
scanf("%d",&t);
if(f[t]==-1)
f[t]=mex(t);
s=s^f[t];
}
if(s==0)
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 模拟芯片市场分析
- 宿迁辅警考试题库2025(有答案)
- 2025年山东省环保发展集团有限公司招聘考试试题(含答案)
- 老年清洁护理课件
- 老年护理沟通教学课件
- 2025年白板市场调研报告
- 2025年安全工作述职报告范例(三)
- 老师健康课件
- 景观园林彩钢房安装与维护合同
- 餐饮业员工权益保护与劳动仲裁协议
- 麻醉药品精神药品管理培训课件
- QCC品管圈活动表格汇编
- 2023年贵州省社区工作者公开招聘考试《公共基础知识》专项题库【真题精选+章节题库+模拟试题】
- 出租车大包车合同
- 银行副行长个人简历表格
- 第四讲 坚持以人民为中心PPT习概论2023优化版教学课件
- 麻精药品培训课件
- 医院全员聘用制度和岗位聘任管理制度
- 粗纱机任务与工艺流程
- 探究食育课程对小班幼儿良好饮食习惯形成的作用 论文
- 湖北武汉洪山区招考聘用社区干事235人模拟检测试卷【共1000题含答案解析】
评论
0/150
提交评论