首页 > 其他分享 >尼姆博弈

尼姆博弈

时间:2022-10-26 20:01:21浏览次数:83  
标签:博弈 策略 尼姆 必胜 物品 一堆 手方

尼姆博弈:一种在博弈论中有基石作用的策略

提醒:接下的分析有点烧脑

描述:尼姆博弈是一个两人博弈,2名玩家轮流从数堆物品中拿取一定数量的物品,每次拿取时先选择某一堆,再从中拿取任意数量个物品,至少拿1个,至多将这一堆物品全部拿走,不能不拿。拿到最后一个物品的玩家获胜。

策略:min-sum(以下称s) s等于0 ,后手必胜,s != 0 先手必胜;

引用百度[https://baike.baidu.com/item/尼姆博弈/58986985]


两堆的情形

我们从最简单的两堆物品的情形开始分析,并使用二元组(n,m)来表示这两堆物品当前的数量。当(n,m)情形下先手方\后手方有必胜策略时,我们称(n,m)为制胜位置。
我们将说明:当n=m时,后手有必胜策略,否则先手有必胜策略。
当n=m=1时,先手方仅能够将其中一堆完全取走,故后手方只需要将另一堆的1个物品取走即可获胜。即(1,1)是后手方的制胜位置。
当n=m=k>1时,无论先手方选择哪一堆,取走多少数量的物品,后手方只需要选择另一堆,并取走相同数量的物品,就可以将物品堆的状态从(k,k)转换到(j,j),其中j<k。如此操作下去,由于两堆物品的数量保持相等且严格递减,故后手方玩家总能将物品堆的数量转换为(1,1)或(0,0)。由上面的讨论与游戏规则知,后手方必胜。即(n,m),n=m是后手方的制胜位置。
当时,先手方只需要从较多的一堆物品中拿取适量的物品,使得两物品堆物品数量一致,就将情形转换为了上述两种情况之一,且自身处于后手方。由上面的讨论知,先手方必胜。即(n,m),是先手方的制胜位置。

  • 两个数的尼姆和(nim-sum)若相同,则两个数一定相同,反之也成立,再者若两个数不等,尼姆和也不相等;但是三个数就不成立;
  • 两个数的nim-sum 是两个数转化成二进制后每个位取异或的二进制数;

两个数相等等价于nim-sum = 0

接下来可以将k个数的s为零的情况转化成两个数的情况

定理1:在尼姆和为0时,无论如何拿取物品,拿取之后物品堆的尼姆和一定不为0;

定理2:在尼姆和不为0时,总存在一种拿取物品的方式,使得拿取之后物品堆的尼姆和为0;

用定理该如何推出上面的转化

若物品堆的尼姆和为0,则无论先手方如何拿取,操作之后物品堆的尼姆和一定不为0,先手方总是不能将物品拿完。后手方总是可以选择拿取方式使得物品堆的尼姆和再次为0,同时物品的数量严格减小,这样操作下去,有限多轮之后即可使得后手方拿取物品后所有物品均被拿取,即后手方有必胜策略。
若物品堆的尼姆和不为0,则先手方总可以选择拿取方式使得拿取之后物品堆的尼姆和为0,且处于后手方的位置。由上述讨论可知,先手方有必胜策略。

定理证明

自行点链接

变体

策略:

若尼姆和为0且所有堆中仅有1个物品,则先手方有必胜策略;
若尼姆和不为0且至少有一堆物品数量大于1,则先手方有必胜策略;
否则后手方有必胜策略。

标签:博弈,策略,尼姆,必胜,物品,一堆,手方
From: https://www.cnblogs.com/zzxs-blog/p/16829813.html

相关文章

  • 巴什博弈
    一种简单的有必胜策略的减法博弈情况参考百度的论述[https://baike.baidu.com/item/巴什博弈/1819345]描述:有n个石头你可以拿最少一个最多m个,拿走最后一个石头的人获......
  • 放球游戏(a^b博弈)
    Problem3放球游戏(ball.cpp/c/pas)【题目描述】    Stas和Masha发明了一个游戏。游戏道具是a个两两不同的箱子和b个两两不同的皮球,Stas和Masha轮流操作,且每次操作新......
  • 博弈论专题3
    题目链接在这里:​​C-PalindromeGame(hardversion)_牛客竞赛博弈专题班组合游戏基本概念、对抗搜索、Bash游戏、Nim游戏习题(nowcoder.com)​​先占个坑,首先这不是经典......
  • 帆软杯武汉大学新生赛 I 犹太棋(博弈,SG函数)
    题目链接题意"犹太棋"是一种经典的巴什博弈游戏,本题的游戏由其玩法改编而来。你并不需要了解关于"犹太棋"的知识,只需要仔细阅读以下的规则说明:有一个长为\(n\),宽为\(......
  • atcoder ARC C 01-Game (博弈, Grundy数)
    https://atcoder.jp/contests/arc151/tasks/arc151_c题意:有1*n的的网格,有一些位置填有0和1,现在A和B进行游戏,往网格上填0/1,要保证相邻两个格子不能相同。A先手,问最后谁赢......
  • 博弈论学习笔记
    learnmoreuselessthings.0x01:从Nim游戏入手P2197【模板】nim游戏甲,乙两个人玩Nim取石子游戏。Nim游戏的规则是这样的:地上有\(n\)堆石子,每人每次可从任意......
  • 博弈论
    《基础博弈思考方向》题目链接:https://ac.nowcoder.com/acm/contest/21592/H博客链接:https://blog.csdn.net/qq_51354600/article/details/120940918......
  • AcWing 算法提高课 博弈论
    1、SG函数SG函数的定义:可以到达的全部点的SG函数中没有出现的最小自然数可以解决棋子移动的博弈论问题推导方式基于nim游戏,https://www.acwing.com/solution/content/1......
  • P6560 [SBCOI2020] 时光的流逝(DAG图上博弈模板)
    P6560[SBCOI2020]时光的流逝(DAG图上博弈模板)题意:​ 给出一个有向图(可能有环),每轮游戏有一个起点和终点,A和B一起玩游戏。A先移动,然后他们交替移动,当谁把棋子移动至终点,谁......
  • LCCL网络:相互指导博弈来提升目标检测精度(附源代码)
    公众号ID|ComputerVisionGzq学习群|扫码在主页获取加入方式论文地址:https://openaccess.thecvf.com/content/ACCV2020/papers/Zhang_Localize_to_Classify_and_Classify_to_Lo......