博弈及其应用——模型转化

在面向ACM/ICPC的博弈问题这一块，主要涉及组合游戏和延伸的SG函数，还有一些比较杂的问题，需要用找规律或者画NP表的方法来解决，这些问题在分析之前，都涉及将问题抽象成一些模型或者将抽象的问题具象化以便于后面方便得分析。这篇文章就是通过一些具体的问题，来探讨博弈模型的转化。

我们来看一道题目。(Problem source : hdu 5591)

博弈及其应用——模型转化

题目大意：实际上这道题目的叙述还是有一定歧义的。给出N，然后两个游戏玩家在[1,N]的范围猜数，谁先猜到X谁输(两个游戏玩家知道X的大小)，如果后手存在必胜策略，输出1，否则输出0。
数理分析：如果正确理解了题意，这道题目就很好分析了。基于题目的叙述"Host will tell all the players that the number now is bigger or smaller than X","Each player should guess in the legal range"，我们可以讲这个博弈转化得更加具象，我们将数轴上的[1,N]这段看成木棍，两个玩家分别从两端从整数点切这个木棍，最后切到X的人输。
那么我们可以看到，当N为偶数的时候，X两端的整数点是绝对无法对称起来的，那么先手比存在操作，是X两端的整数点对称，那么后手的操作就必须打破对称状态，那么先手再回复对称状态，反复操作下去，后手会面对X-1，X，X+1的情况，显然，后手是必败的。
那么N是奇数呢？如果X恰好等于(N+1) / 2，那么此时先手就面临打破对称状态的情况了，后手就有必胜策略。否则，后手还是必败。
综上，我们得出结论：n为偶数，后手没有必胜策略。n为奇数，后手有必胜策略。
基于以上分析，就可以很简单的编程实现了。参考代码如下。

#include<cstdio>
using namespace std;
int main()
{
     int t , n;
     scanf("%d",&t);
     while(t--)
     {
          scanf("%d",&n);
          if(n%2 == 0)  printf("0\n");
          else          printf("1\n");
     }
}

我们再来看一道有意思的博弈题目。(Problem source : hdu 1564)

Problem Description

New Year is Coming! ailyanlu is very happy today! and he is playing a chessboard game with 8600. The size of the chessboard is n*n. A stone is placed in a corner square. They play alternatively with 8600 having the first move. Each time, player is allowed to move the stone to an unvisited neighbor square horizontally or vertically. The one who can't make a move will lose the game. If both play perfectly, who will win the game?

Input

The input is a sequence of positive integers each in a separate line. The integers are between 1 and 10000, inclusive,(means 1 <= n <= 10000) indicating the size of the chessboard. The end of the input is indicated by a zero.

Output

Output the winner ("8600" or "ailyanlu") for each input line except the last zero. No other characters should be inserted in the output.

题目大意：给定变量n的值，游戏双方分别从n*n棋盘的左下角出发，可以上下移一格，可以左右移一格，无法移动到访问过的格点，请你判断游戏的双方谁存在必胜策略。
数理分析：这种类型的博弈问题，我们似乎联系不到已知的博弈类型，那么我们就要试图找到双方必胜策略的分布规律。
我们从n的奇偶性出发，假设n为奇数，那么n*n也是奇数，我们将整个棋盘看成多个1 * 2格子，则n*n = 2*m + 1，并且这种分割方式还是动态的，先手每次的操作可以看做填掉了1 * 2格子的第一个，而后后手不断填1 * 2格子的第二个，依次进行下去，我们可以看到，先手会填充多出来的那个格，即后手必胜。
反之，n为偶数的时候，性态就发生了改变。
这里值得注意的是，起始点一开始并没有认为是被访问过的，这一点是很关键的。
有了以上的数理逻辑，我们便可以编程实现了，参考代码如下。

#include<stdio.h>
using namespace std;

int main()
{
       int n;
       while(scanf("%d",&n),n)
       {
             if(n%2 != 0)  printf("ailyanlu\n");
             else          printf("8600\n");
       }
}

——未完

秒客网

博弈及其应用——模型转化

相关文章