这两天学习一下新的知识---博弈论。发现我们生活中司空见惯的博弈游戏，竟然有如此完美的结论，根据这个结论能够知道某个人必输或必败，真的很神奇。其实我还没有真正的了解博弈，只是粗浅的了解了一下博弈论中的take-away game理论。游戏的规则很简单：
（1）：必须有两个人参与
（2）：游戏每次所能做出的合法的移动是有限的
（3）：必须是两个人控制同一个游戏对象，不能各个控制各自的。比如象棋，是一个人控制白的，一个人控制黑的，这现在不在研究范围。
（4）：双方必须轮流操控
（5）：当某个完家根据规则无路可走的时候就算失败了
（6）：游戏不管怎么完，都会在有限的步骤内结束，并定输赢
（7）：两个人每次都用最优的走法
下面举一个例子来形象的说明这个游戏的完法；
有一堆石子21个，双方轮流来拿走石子，每次可以的拿走的石子数是1，2，3，但是不可以不拿。现在从某一个人开始，那么若干步骤之内，必然会结果（赢家和输家）
现在我要立即回答，最后谁会赢呢，可能你不能一时答出，因为你觉得这个太随机了，谁输谁赢很难确定。神奇的理论告诉我们，最后的输赢不是取决与中间的过程，而是取决了谁先走和石子的个数。。
假如游戏的完家是I,II I先拿
我们从最后的结果出发讨论
0的话 I就输了，因为他没有可拿的了。
1,2,3 的话I就赢了，因为I可以一次把所有的石子都拿走，那么II就没拿的了。。
4的话 I就输了，因为I可以拿走 1，2，3个石子，那么会剩下3,2,1个石子，这样II可以一次拿走。。
5 6 7的话 I就又赢了，因为I可以那走1,2,3个石子，使剩下的石子为4，转上面的分析。。
8的话，I就输了，因为那走1，2，3剩下的就是5,6,7，所以是II赢了。。。
。。。
。。。
20的话 I就输了
21的话I就赢了
所以最终的结果是I赢了，看出没。不是随机的把，而是肯定的说是I赢。。。
当然还有个前提：就是 I知道每次拿多少是对自己最有利的，也不是随便拿的。。
下面我们将得出这个游戏模型的理论：
P点：就是P个石子的时候，对方拿可以赢
N点：就是N个石子的时候，自己拿可以赢；
通俗的解释就这样：
现在我们对上面的游戏进行PN分析；
0是P，因为对方拿0也就意味这他失败了
|
0
|
1
|
2
|
3
|
4
|
5 …..
|
|
P
|
N
|
N
|
N
|
P
|
N ……
|
通过对表格的研究，可以发现P,N点完全可以根据游戏规则和最种态计算出来。
比如这个游戏的最种点是0那么是P
现在关于P,N的求解有三个规则
（1）：最终态都是P
（2）：按照游戏规则，到达当前态的前态都是N的话，当前态是P
（3）：按照游戏规则，到达当前态的前态至少有一个P的话，当前态是N
现在队上游戏重新计算，发现21点是N点，自己先肯定是赢
下面为了充分理解此结论，在举两个例子：
http://acm.hdu.edu.cn/showproblem.php?pid=2147 kiki’s game
题目的意思是：在一个m*n的棋盘内，从(1,m)点出发，每次可以进行的移动是：左移一
，下移一，左下移一。然后kiki每次先走，判断kiki时候会赢（对方无路可走的时候）
谁输谁赢，现在只取决于棋盘的大小了。。
可以这样想像，我们从后往前推。假如是5*5的棋盘
*****
*****
*****
*****
*****
用数学坐标系，终态在(1,1)，设为P
(1,1)->(1,2)->(2,1)->(2,2)->(1,3)->(2,3)->(3,1)->(3,2)->(3,3)…….
p N N N P …………
依次计算就 ok了，只要最后(m,n)是N则kiki赢。
测试用：
#include<iostream>
using namespace std;
bool map[2001][2001];//1 P 0 N;
int main(){
int i,j,k;
map[1][1]=1;
for(i=2;i<=2000;i++){
if(map[i-1][1])
map[i][1]=0;
else map[i][1]=1;
for(j=2;j<i;j++){
if(!map[i][j-1]&&!map[i-1][j-1]&&!map[i-1][j])
map[i][j]=1;
else map[i][j]=0;
}
if(map[1][i-1])
map[1][i]=0;
else map[1][i]=1;
for(j=2;j<i;j++){
if(!map[j-1][i]&&!map[j-1][i-1]&&!map[j][i-1])
map[j][i]=1;
else map[j][i]=0;
}
if(!map[i][i-1]&&!map[i-1][i-1]&&!map[i-1][i])
map[i][i]=1;
else map[i][i]=0;
}
int M,N;
for(i=1;i<=10;i++){
for(j=1;j<=10;j++)
printf("%c ",map[i][j]?'P':'N');
printf("\n");
}
while(scanf("%d%d",&M,&N)&&M&&N){
if(map[M][N]) printf("What a pity!\n");
else printf("Wonderful!\n");
}
return 0;
}
由于原题限制了内存，所以把pN输出找规律，发现只有m,n同时为奇的时候才输。。。。
另外一个例子是：
http://acm.hdu.edu.cn/showproblem.php?pid=1517 A Multiplication Game
题目意思是说：两个人游戏，每次都是前一个人说出的数的基础上乘以一个（2。。。9）的数，谁先超过预先设定的值n，那么谁就赢了，基数是1
还有有个人先，胜败只取决与n的值.从后往前分析
举个例子：162
（无穷,162）->(162,18)->(17,9)->(8,1)
p N p N
(无穷，34012226)->( 34012225-3779137)->( 3779136-1889569)->( 1889568-209953)->
p N p N
(209952-104977)->( 104976-1220)->( 1219-610)->( 609-68)->( 67-39)->( 38-5)->(4,3)->(2,1)
p N p N p N p N
source code:
#include<iostream>
using namespace std;
int main(){
__int64 N;
bool f;
while(scanf("%I64d",&N)!=-1){
f=1;
while(N!=1){
if(f){
N=N%9==0?N/9:(N/9+1);
f=0;
}
else{
N=N%2==0?N/2:(N/2+1);
f=1;
}
}
if(!f) printf("Stan wins.\n");
else printf("Ollie wins.\n");
}
return 0;
}