当前位置:首页 » 《关注互联网》 » 正文

简单博弈论_是饿梦啊的博客

25 人参与  2022年01月19日 13:59  分类 : 《关注互联网》  评论

点击全文阅读


公平组合游戏ICG:

若一个游戏满足:

1. 由两名玩家交替行动;

2. 在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关;

3. 不能行动的玩家判负;

则称该游戏为一个公平组合游戏。

NIM博弈属于公平组合游戏,但城建的棋类游戏,比如围棋,就不是公平组合游戏。因为

棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和条件3。

 我们来看看什么是nim游戏。

NIM游戏

给定N堆物品,第i堆物品有Ai个。两名玩家轮流行动,每次可以任选一堆,取走任意多个

物品,可把一堆取光,但不能不取。取走最后一件物品者获胜。两人都采取最优策略,问先

是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的

称为先手,第二个行动的称为后手。若在某一局面下无论采取何种行动,就会输掉游戏,称该局面必败。 

所谓采取最优策略是指,若在某一局面下存在某种行动,使得行动后对面面临必败局面,则

优先采取该行动。同时,这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情

况,即两人均无失误,都采取最优策略行动时游戏的结果。

NIM博弈不存在平局,只有先手必胜先手必败两种情况。

定理: NIM博弈先手必胜,当且仅当 A1 ^ A2 ^ ... ^ An != 0

先手必胜态:可以走到某一个必败状态。

先手必败态:走不到任何一个必败状态。

我们来看一下这个nim游戏:

现在有两堆石子,一堆有3个 、一堆有5个。

先手只需要从最大的一堆中拿走两堆差的个数,后手不管拿多少,先手只需在另一堆中拿走镜像的个数,后手必败。

我们来看一下定理内容:

(1) 所有堆上的石子异或值为零 : 0 ^ 0 ^.......^ 0  = 0;(所有二进制位上 0 / 1 的个数为偶数)

(2) 所有堆上的石子异或值不为零: a1 ^ a2 ^ a3 ^ ......^an != 0

我们只需拿走若干的石子,使得所有堆上的石子异或值为零即可。

 那我们需要拿走多少呢:

假设 a1 ^ a2 ^ a3 ^ ai ^  ..... an = x;

x 的最高位的一个1 是 第 k 位 ,则a1 .... an中一定存在且至少一个ai 的的第 k 位 是 1;

那我们只需拿走 ai - (ai ^ x)

那ai 堆上的石子数量变成了 ai - (ai - (ai ^ x)) = ai ^ x;

则 a1 ^ a2 ^ a3 ^ ..... ai^x ^ a(i+1) ^ ......an = x ^ x = 0;

则结得证。

洛谷模板题:【模板】nim 游戏 - 洛谷

加点难度:取火柴游戏 - 洛谷

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;

int main()
{
	cin>>n;
	while(n--)
	{
		int t;
		int res = 0;
		cin>>t;
		while(t--)
		{
			int x;
			cin>>x;
			res ^= x;
		}
		if(res)puts("Yes");
		else puts("No");
	}
	return 0;
} 


点击全文阅读


本文链接:http://zhangshiyu.com/post/33544.html

先手  游戏  必败  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 男友霸道给我开黑卡,转头却骂我是捞女最新章节_肖年顾客黑卡热文_小说后续在线阅读_无删减免费完结_
  • 他在回忆尽头全集_贺南舟许清梨叶絮完结txt_小说后续在线阅读_无删减免费完结_
  • 旅游结婚那天未婚夫另娶女秘书,我让他们一无所有连载_老公迎宾超长版_小说后续在线阅读_无删减免费完结_
  • 完结文异界修仙我的直播间能打赏核弹列表_完结文异界修仙我的直播间能打赏核弹(江流年沈红菱)
  • 全书浏览陪弟弟混骑行圈,离婚你哭什么?(韩星河柳千雪)_陪弟弟混骑行圈,离婚你哭什么?(韩星河柳千雪)全书结局
  • 老公出轨我助攻虐心反转_秦绍卿卿阿溪后续加长_小说后续在线阅读_无删减免费完结_
  • 替老婆坐牢出狱那天,我被送去斗兽场精校文本_许言沈宇郑子番茄热门_小说后续在线阅读_无删减免费完结_
  • 沐巍澜温溪:结局+番外(爱如一刹花火)电子书畅享阅读无广告
  • 傅凌川林柚续集(傅凌川林柚)章节前文+全书阅读(替嫁燃婚:小祖宗嘴硬腰软)最新连载
  • 资助生把导盲犬做成火锅后,我家杀疯了!列表_资助生把导盲犬做成火锅后,我家杀疯了!(陈米雪波波)
  • 沈瑾钰林沐橙豪门废妻浴火复仇续集(豪门废妻浴火复仇)章节在线阅读最近章节
  • 明明图分手费,我怎么就入赘了?(顾池柳如烟),明明图分手费,我怎么就入赘了?

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1