logo

您所在位置网站首页 > 海量文档  > 计算机 > 软件编程

游戏策略石子问题.ppt 40页

本文档一共被下载: ,您可全文免费在线阅读后下载本文档。

  • 支付并下载
  • 收藏该文档
  • 百度一下本文档
  • 修改文档简介
全屏预览

下载提示

1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值,立即自动返金币,充值渠道很便利
特别说明: 下载前务必先预览,自己验证一下是不是你要下载的文档。
  • 上传作者 爱是你我(上传创作收益人)
  • 发布时间:2019-05-15
  • 需要金币100(10金币=人民币1元)
  • 浏览人气
  • 下载次数
  • 收藏次数
  • 文件大小:507 KB
下载过该文档的会员
你可能关注的文档:
游戏策略 Nim问题 取石子问题 有N堆石子,其中第i堆有Pi颗石子,每次从某一堆里选出若干石子去掉(但不能不去石子),两人轮流取石,谁不能继续取谁就输了。 什么情况下先手必胜,什么情况下后手必胜? 第一堆:a1=3 第二堆:a2=3 第三堆:a3=1 分析 从上述博弈树可以看出3,3,1是必胜点,那么我们可以这么想,如果某个点是必胜点,则取完棋子后,必须使得对方落在必败点。 若只有一堆石子,先收走必胜 若有m堆石子,每堆只有一颗石子, m堆为奇数时,先手必胜。 若有m堆石子,每堆有k颗石子, m堆为奇数时,先手必胜。 第1次,先手取k棵,轮到对手走时,若对手取k棵,则先手也取k棵,若对手取x<k棵,则先手也取另外一堆的x棵,因为剩下的是偶数堆,总能将剩下的堆变成若干个两两相等的堆。只要始终保持这种取法,先手总能取到最后的石子。 一般情况? 假设某个初始局面为先手必胜,那么先手每走一步都必须使得对手落在必败节点。 因此,对于每一个局面,要么为胜局面,要么为负局面,如果我们将胜局面非0表示,那么负局面就可以用0表示。 因此,对于某一个局面,若为非0局面,它的任务就是要寻找某一种取法,使得局面变为0局面。那么他的对手无论怎么取,都会使得局面又变成0局面。 有什么规律呢? 结论 定理: 如果一个局面先手必胜,就称之为N局面,反之称之为P局面。对于一个局面,令S=P1 XOR P2 XOR P3 XOR … XOR Pn。若S=0则为P局面,否则为N局面。 证明: 当P1=P2=….=Pn=0时,S=0,满足终状态是P局面。 若S=0,即P1 XOR … XOR Pn=0,若取堆i中的石子,Pi>Pi’,S ->S’,Pi>Pi’,则Pi XOR Pi’<>0。所以S’ XOR Pi XOR Pi’=S=0,即S’=Pi XOR Pi’<>0。满足P局面的所有子局面都是N局面。 若S<>0,设S的二进制位是A1…An,考虑第一位是1的。在P中取出该位同是1的,不妨设为P1。可知P1 XOR S<P1,令P1’=P1 XOR S。可知P1’ XOR P2 XOR … XOR Pn=0。即N局面存在至少一个子局面是P局面。 示例 Nim问题的扩展 取石子问题 有N堆石子,其中第i堆有Pi颗石子,每次去掉某一堆里最多m棵石子(m>0),两人轮流取石,谁不能继续取谁就输了。 什么情况下先手必胜,什么情况下后手必胜? 示例m=2 a1=7 a2=3 a3=5 1 2 3 4 5 6 7 将P1P2P3 … Pn 对m+1求余得到P1 ’ P2 ’ P3 ’ … Pn ’ ,然后符合定理一的结果,记S=P1’ XOR P2 ’ XOR P3 ’ XOR … XOR Pn ’ 。若S=0则为P局面,否则为N局面。 证明: 将P1P2P3 … Pn分解成为两部分P1 ’ P2 ’ P3 ’ … Pn ’和 R1R2R3 …Rn,其中R1R2R3 …Rn 都是m+1的倍数。 若对P1 ’ P2 ’ P3 ’ … Pn ’部分取子,则按NIM方法走步,若对R1R2R3 …Rn部分取子,则后手取k颗,先手方取m-k+1颗,先手始终保持不对R1R2R3 …Rn部分先取子。 若初始局面为胜局面,P1 ’ P2 ’ P3 ’ … Pn ’部分NIM方法取子必胜,由于R1R2R3 …Rn都为m+1的倍数,因此,按m+1互补的取法,先手一定能取到最后K<=m颗石子。 结论 Nimk问题 取石子问题 有N堆石子,其中第i堆有Pi颗石子,每次可以从最多K堆中选出若干石子去掉(但不能不去石子),两人轮流取石,谁不能继续取谁就输了。 什么情况下先手必胜,什么情况下后手必胜? 结论 K=1,为Nim问题。 对于K>1的情况,我们令把P1~Pn这n个数,转成二进制,然后每位分别相加,每位最后结果mod (K+1)即可。如果每一位结果都是0,则为P局面,否则是N局面 示例 P1P2P3P4=3,5,10,15 ,K=2 3—————— 1 1 5—————— 1 0 1 10—————— 1 0 1 0 15 —————— 1 1 1 1 2 2 0 0 所以这是N局面。 证明与NIM证明类似。下面我们看看具体的取法。 Nimk问题的取石子方法 设P1P2P3 … Pn 为n堆石子数目。Pi已标记的石子堆,D0[i]和 D1[i]分别表示所有已标记的石子堆中第i位为0

发表评论

请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
用户名: 验证码: 点击我更换图片

2010-2013 max.book118.com在线文档投稿赚钱网. All Rights Reserved 蜀ICP备08101938号