博弈论_博弈论

博弈论_博弈论游戏使用一堆物品,例如棋子、石头或者硬币,这些物品被分成几堆,每堆可以有任意数量的物品

目录

概念: 

公平组合游戏ICG

有向图游戏

Nim游戏

先手)必胜状态

先手)必败状态

如何确定先手是否必胜或者必败(都采用最优策略)

证明:全部异或为0则是必败状态

   综上:

例子


概念: 

公平组合游戏ICG

    若一个游戏满足:
        1.由两名玩家交替行动;
        2.在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关;
        3.不能行动的玩家判负;
     则称该游戏为一个公平组合游戏。
     NIM博弈属于公平组合游戏,但城建的棋类游戏,比如围棋,就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和条件3。 

有向图游戏

     给定一个有向无环图,图中有一个唯一的起点,在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动,每次可以移动一步,无法移动者判负,该游戏被称为有向图游戏。

     任何一个公平组合游戏都可以转化为有向图游戏。具体方法是,把每个局面看成图中的一个节点,并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。 

Nim游戏

    NIm就是一种公平组合游戏。

     Nim游戏是一个古老的数学游戏,通常由两名玩家轮流进行。游戏使用一堆物品,例如棋子、石头或者硬币,这些物品被分成几堆,每堆可以有任意数量的物品。玩家在每一回合可以选择一堆物品,并且从中取走任意数量的物品,但是至少要取走一个。最后取走最后一个物品的玩家获胜。

     Nim游戏的关键在于掌握取物品的策略,因为有正确的方法可以确保你获胜,无论对手怎么移动。这个策略涉及到让每一堆物品的数量保持在特定的模式,这样你就可以控制游戏的走向,迫使对手进入必败局面。

     Nim游戏可以有很多变种和扩展,包括多堆物品、多个玩家或者其他规则的变化。

  • 先手)必胜状态

    先手进行某一个操作,留给后手是一个必败状态 时,对于先手来说是一个必胜状态。即先手可以走到某一个必败状态

  • 先手)必败状态

    先手不管使用什么策略,都只留给后手必胜的状态。

  • 如何确定先手是否必胜或者必败都采用最优策略)

   我们使用异或(XOR)运算来确定每一堆物品的数量。

  1. 如果所有堆物品的数量进行异或结果为0,则这是一个必败状态。
  2. 否则,是一个必胜状态。
  • 证明:全部异或为0则是必败状态

分情况讨论:

      1.当所有堆的物品数目都为 博弈论_博弈论00\oplus0\oplus0....\oplus0 = 0

      2.当前存在 a_1\oplus a_2...\oplus a_ n = x \neq 0 

        证明,一定可以通过某种方式(减少某些物品的数量)使得情况2的异或值变为 博弈论_博弈论0 。

           假如 x 的二进制表示中最高的一位 1 在第 k 位。

           那么意味着 a_1,\ a_2,\ ...a_n 中必然至少存在一个数 a_ia_i 的第 k 位的值是 1 。

           那么 博弈论_博弈论 a_i \oplus x”>  , a_i - (a_i \oplus x ) 是合法的 。

           现在将拿走 a_i 中 a_i - (a_i \oplus x ) 数量的东西,则a_i-(a_i - (a_i \oplus x )) = a_i\oplus x 。

           拿走之后所有堆的物品数目再进行异或: a_1\oplus a_2...\oplus a_i\oplus x\oplus a_ n = x\oplus x = 0

           证明完成。

      3.当前 a_1\oplus a_2...\oplus a_ n = 0

         证明,不管证明去拿多少数目(\neq 0),剩下的所有数异或值都不是0

            反证:假设拿出 a_i 中 k(k \neq 0) 个数目,剩余 a_i^`   ,剩下所有数的异或值为 博弈论_博弈论0 

            则有 a_1\oplus a_2...\oplus a_i^`\oplus a_ n = 0        ①

            原有  a_1\oplus a_2...\oplus a_i\oplus a_ n = 0      ②

            再将 ① 和 ② 者进行异或运行,相同的数就被抵消掉,剩余 a_i^` \oplus a_i = 0

            a_i^` \oplus a_i = 0   说明 a_i^` = a_i ,与假设矛盾。证明完成

   综上:

        当全是0的时候,那么先手必输。

        如果当前先手中数目异或不为 博弈论_博弈论0,那么可以取出某个数的值使得轮到后手时,手中数目异或值为 博弈论_博弈论0。后手不管怎么拿,再次轮到先手时,异或值都不会为 博弈论_博弈论0。保证了先手始终 异或不为 博弈论_博弈论0 的状态,而后手始终为 博弈论_博弈论0 的状态,最后后手会首先遇到全 博弈论_博弈论0 状态,先手始终处于必胜态

        如果先手一开始 异或值就为 博弈论_博弈论0 ,那么后手可以始终保持最优策略使得先手 异或为 博弈论_博弈论0先手处于必败态

 

K-Nim游戏:每次只能取k个

 

例子

给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

输入格式

第一行包含整数 n。

第二行包含 n 个数字,其中第 i 个数字表示第 i 堆石子的数量。

输出格式

如果先手方必胜,则输出 Yes

否则,输出 No

数据范围

1≤n≤10^5,
1≤每堆石子数≤10^9

输入样例:

2 2 3 

输出样例:

Yes
import java.io.*; class Main{ static int n; public static void main(String[] args) throws IOException{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(in.readLine()); String[] s = in.readLine().split(" "); int res = 0; for(int i=0;i<n;i++) res ^= Integer.parseInt(s[i]); if(res==0) System.out.println("No"); else System.out.println("Yes"); } }

 后续会更新更多版本的Nim游戏。

今天的文章
博弈论_博弈论分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/80279.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注