博弈问题小述

Nim游戏

问题描述:
甲乙两人面对若干堆石子,其中每一堆石子的数目可以任意确定。例如图1所示的初始局面:共n=3堆,其中第一堆的石子数a1=3,第二堆石子数a2=3,第三堆石子数a3=1。
两人轮流按下列规则取走一些石子,游戏的规则如下:
1.每一步应取走至少一枚石子;
2.每一步只能从某一堆中取走部分或全部石子;
3.如果谁无法按规则取子,谁就是输家。
如果甲乙两人都采取最优的策略,请问,是甲必胜还是乙必胜.。

这题是经典的Nim游戏,我当时看到这道题,第一反应就是simple!堆数是偶数就乙胜,奇数就是甲胜。因为假设是奇数,那么甲先取走一整堆,接下来如果乙取走一整堆,那么甲也取一整堆,堆数始终是成偶数减少,最后一定是乙无法取。如果乙取一部分,那么甲把这堆剩下的取了。然后我想了很久,为什么这样想不对。就和另一个同学讲了一下我的想法(这种方法亲测有效,被我班一大佬称为小黄鸭法),就发现,如果这时乙取了一部分,甲取了剩下的部分,这时堆数就是奇数了,乙如果取整堆呢,就不能用之前的方法了。这个想法因此是错误的。
然后我坚信本题一定有巧妙的方法。上网一查,果不其然,异或法映入眼帘。附上异或法的代码:

#include <iostream>

using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int n, a[10010];
        int p = 0;
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> a[i];
            p = p ^ a[i];
        }
        if(p != 0) cout << "Win" << endl;
        else cout << "Lost" << endl; 
    }
    return 0;
}

这个异或法不是很好懂。我先是自己琢磨了半天,愣是没有琢磨出来,只能网上搜解释。

根据定义,证明一种判断position的性质的方法的正确性,只需证明三个命题: 1、这个判断将所有terminal
position判为P-position;2、根据这个判断被判为N-position的局面一定可以移动到某个P-position;3、根据这个判断被判为P-position的局面无法移动到某个P-position。
第一个命题显然,terminal position只有一个,就是全0,异或仍然是0。
第二个命题,对于某个局面(a1,a2,...,an),若a1a2...an<>0,一定存在某个合法的移动,将ai改变成ai'后满足a1a2...ai'...an=0。不妨设a1a2...an=k,则一定存在某个ai,它的二进制表示在k的最高位上是1(否则k的最高位那个1是怎么得到的)。这时aik<ai一定成立。则我们可以将ai改变成ai'=aik,此时a1a2
第三个命题,对于某个局面(a1,a2,...,an),若a1a2...an=0,一定不存在某个合法的移动,将ai改变成ai'后满足a1a2...ai'...an=0。因为异或运算满足消去率,由a1a2...an=a1a2...ai'

附上这篇文章的链接,写得还挺不错的:
http://blog.csdn.net/peteryuanpan/article/details/39272183

Grundy博弈

Grundy博弈是一个分钱币的游戏。有一堆数目为N的钱币,由两位选手轮流进行分堆,要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如,选手甲把N分成两堆后,轮到选手乙就可以挑其中一堆来分,如此进行下去,直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。
我一开始理解成了如果把7分成3和4,接下来如果选择把3分成1和2,那么下一次就没得分了,其实还可以选4的。按我原来的想法,你们不妨去思考一下,问题就变得很简单了,就是一个有着必胜策略的问题,考虑初始n,如果n%3 == 1那么后手必赢,否则先手必赢。回到我们本身的问题,要用博弈树来解决。所谓的博弈树,其实就是一个极大极小搜索然后再为了提高效率进行α—β剪枝。另外为了更好地用这个剪枝,还可以对扩展的结点进行排序。博弈树还可以运用到很多地方,比如下次我就要跟大家分享用博弈树写人机交互的五子棋啦,现在还没写好orz。下次再跟大家细细讲一下极大极小搜索和α—β剪枝。

另外讲点跟博弈无关的内容,是我今天刚发现的好东西,我们都知道printf可以很好地控制输出格式,其实cout也可以。附上代码,看了就明白了:

#include <iostream>

using namespace std;

int main(){
    int a = 1;
    cout.fill('0');
    cout.width(4);
    cout << a << endl;
    return 0;
}

今天就到这里啦,大家晚安~


信息:
XinyaoShen
标签:
其他:
0
368

评论 :