锐客网

  1. 首页 > it技术 > >

c++|组合博弈入门

简单描述 组合博弈定义
①有两个玩家
②游戏的操作状态是一个有限集合（比如：限定的总的牌的数量
③游戏双方轮流操作
④双方每次操作符合游戏规定（按规定取牌数量取牌
⑤当一方不能继续进行的时候，游戏结束，同时，对方为获胜方
⑥无论如何操作，游戏总能在有限次数操作后结束
必败点、必胜点 定义：
必败点（P点）：前一个选手（Previous player）将取胜的位置称为必败点（即将要在这个点操作的玩家，一定会输）
必胜点（N点）：下一个选手（Next player）将取胜的位置称为必胜点（在必胜点的玩家不一定赢，是要在不犯错误的情况下，整个游戏才会赢）
属性：
一、所有终结点是必败点（P点）；（终结点有限且易标记）
（终结状态：是游戏进行不下去的点；而必败点是游戏可能还能进行下去，改变不了要输的命运）
举个例子：每次取牌规则是两张或三张；则终结点为 剩0张 或 剩1张
所以：必败点不一定是终结点，但终结点一定是必败点
二、从任何必胜点（N点）操作，至少有一种方式可以进入必败点（P点）；
因为必胜点不一定怎么走都赢，一定至少一种方式进入必败点
举个例子：剩三张牌，取牌规则（1，2，3），若取了两张或一张，一定是对方赢自己输
Nim游戏 游戏简介：
①有两个玩家
②有三堆扑克牌（比如; 5,7,9
③游戏双方轮流操作
④玩家每次操作是选择其中某一堆牌，然后从中取走任意张
⑤最后一次取牌的一方为获胜方
由题引入：
Nim-Sum：按位的异或运算
SG函数的含义以及实现 sg函数的定义：
X节点的sg值是除去后继点的sg值得最小非负整数。
sg函数的使用：
必败点：节点sg值等于0
必胜点：节点sg值大于0
解决的问题：组合游戏
引入定理：
如果图游戏G有若干个子图游戏Gi组成，即：G=G1+G2+···+Gn，假设gi是Gi（i=1，，，n）的SG函数值，那么，图游戏的SG值计算如下：
g（x1···xn）=g1（x1）^···gn（xn）
例
多个组合游戏的并
给定若干个组合游戏，可以按照下面的规则将它们并成一个新的游戏。
l 对每个游戏给定初始状态。
l 两人轮流走步，从A开始。
l 每一轮，选择一个未到达终止状态的游戏，在这个游戏中按照规则走一步，其他游戏的状态不变。
l 最后一个走步者获胜，即走完之后所有游戏都到达终止状态。
我们称这个新的游戏为“多个组合游戏的并”。我们要来看如何用每一个游戏的SG函数来求这个新的组合游戏的SG函数。
g（x1···xn）=g1（x1）^···gn（xn）
简单例题

题述
c++|组合博弈入门
文章图片

题目大意
有n堆苹果，每堆有mi个
两人轮流取，每次可以从一堆苹果中取任意连续个苹果
最后取光者为输
Fra先下，问是否可以获胜
输入输出
c++|组合博弈入门
文章图片

代码
#include #include #include #include #include #include #include #include #include #include #include #include //#include using namespace std; int main() {int n,m,a,sum,i; while(cin>>n) {m=0; //判断是否是孤单堆 sum=0; for(i=0; i>a; if(a>1)//如果a=1即是孤单堆 m=1; sum^=a; } if(m==0) {if(n%2==0) cout<<"Yes"<

【c++|组合博弈入门】所以我们只要判断孤单堆和富裕堆然后用尼姆博弈公式（nimm game)即可

    推荐阅读


    上一篇：nginx|Nginx服务器高性能优化的配置--轻松实现10万并发访问量

    下一篇：面试|作为一个刚刚入职Android开发的应届生,该如何走向架构师?