本文主要是介绍博弈论入坑,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
我喜欢游戏,我知道有些游戏无论我怎样努力最后的结果一定是输的,或者是无论怎样玩我都是赢得,这样的一类游戏从一开始就知道结果的游戏,一定会有一种数学方法去描述。
Nim博弈
所谓的Nim的博弈就是一种从一开始就知道胜负的游戏。这是一种两个人玩的游戏,玩家双方面对一堆硬币(或者石头或者豆粒)。(假设有k>=1堆硬币,每堆分别有 n 1 , n 2 , n 3 … … n k {n_1,n_2,n_3……n_k} n1,n2,n3……nk枚硬币。游戏的目标就是取得最后一枚硬币。每个玩家只能任选一堆去拿不少于1个硬币。率先拿完所有硬币的玩家获胜。
我们来看其中的某种特殊情况:
首先是如果只有一堆,先手一下全拿完,先手必胜。第二种是有两堆,数量为n1、n2,如果n1!=n2先手的策略就是拿多的那一堆,拿完后使得两堆相等,这样重复让两堆相等那么肯定先手会赢;反之如果n1==n2先手必败。
而如果是很多堆,或者是玩法并不是拿任意>=1的硬币,而是规定硬币的个数怎么办呢???
SG函数
这里我就不给出证明过程了,直接说结论和解题方法。
首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0;
我们就可以定义一下sg(x) = mex{sg(y)|y是x的后继}这里的后继指的是存在x转换成y的方法,即对于1堆硬币来说原先有y个硬币,能通过一次move得到y枚硬币。sg(x)是对于一个游戏的子问题来说的,也就是其中一堆硬币,最后我们需要算出所有的sg值,然后进行异或运算g(G1)g(G2)…^g(Gn) = 0先手必败,不为0先手必胜。
get_sg代码
int f[maxn]; // 可以取的石子个数 idx[1~n]
int sg[maxn]; // 0 ~ n sg函数的值
int isin[maxn]; // mex{}
void getSG(int n)
{memset(sg, 0, sizeof(sg));for(int i = 1; i <= n; i++) {memset(isin, 0, sizeof(isin));for(int j = 1; f[j] <= i; j++) {isin[sg[i-f[j]]] = 1;}for(int j = 0; j <= n; j++) {if(isin[j]==0) { sg[i] = j;break;}}}
}
一些特例
1.可选步数为1~m的连续整数,直接取模即可,SG(x) = x % (m+1) 这其实就是巴什博奕。
2.可选步数为任意步,SG(x) = x,这其实是Nim博弈原型。
3.可选步数为一系列不连续的数,用getSG()计算,这是Nim博弈变式。
一道题
小米OJhttps://code.mi.com/problem/list/view?id=117&cid=4
这道题是在堆的数量为2,只能拿斐波那契数的一个特例。
代码:
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn = 1e4 + 10;
int f[maxn]; // 可以取的石子个数 idx[1~n]
int sg[maxn]; // 0 ~ n sg函数的值
int isin[maxn]; // mex{}
void get_f() {f[1] = 1;f[2] = 2;for(int i = 3; f[i-1] < maxn; i++) {f[i] = f[i-1] + f[i-2];}
}int main()
{get_f();getSG(maxn);int num1, num2;while(cin >> num1 >> num2) {if((sg[num1]^sg[num2])==0) {cout << "Xiaobing Win" << endl;}else {cout << "Xiaoai Win" << endl;}}return 0;
}
这篇关于博弈论入坑的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!