最新消息:

博弈入门:从数学游戏开始

百家争鸣 admin 2300浏览

推理剧《古畑任三郎》之“数学家杀人事件”中有这么一个小插曲,这是古畑和数学家之间的一个小游戏:
  两个人轮流数数,从1开始数到16,每人每次可以数1到3个数,规定最后数到16的人就输了。我们可爱的古畑大叔并不知道其中诀窍,所以连着输了两局。
  但是过了两天,古畑从另一个数学家那里掌握到了诀窍,大致来看是这样的:要让对方数到16的话,自己就必须数到15才行,要数到15你会发现只要数到11即可,因为如果对方数一个数数到到12,你可以连着数3个数直到15;如果对方数2个数数到13,那么你也数两个数数到15;如果对方数三个数数到14,那么你就数一个数数到15。于是只要数到11就能确保自己数到15,那么同样的道理,要数到11就只要数到7,要数到7就要数到3,所以呢,谁先数到3,然后一步步数到7,11,15,最后把16丢给对方那就赢了。
  好了,诸如此类的博弈其实更接近一个纯数学问题,这类问题基本上有如下一些共性:
  有两名玩家,
  ① 游戏有一个确定的局面,该局面是双方可见的(完全信息);
  ② 规则对游戏双方是相同的(公平的),它规定了哪些操作(策略)是可行的;
  ③ 玩家的操作将使游戏从一个局面确定地走向另一个局面,无随机行动;
  ④ 游戏将会在有限步内结束,此时有唯一的一方成为赢家。
  满足上述条件的游戏,称为无偏博弈。
  比如说五子棋就不能算是无偏博弈,因为黑棋有禁手的缘故?就算是无禁手的五子棋也不属于无偏博弈。记住第②条,规则对双方是相同的,这意味着两名玩家面对同一局面时,能采取的策略是一样的。换句话说,或者让两个人都可以使用白色和黑色的棋子,或者让棋子只有黑色或只有白色,而且游戏结束条件也必须“无偏差”,你可以规定先使五子连成一条直线的人为赢家,但不能规定黑棋代表一个人,白棋代表另一个人。而这当然不能算是一般意义的五子棋了。同样的道理,凡是有固定颜色的棋子代表某方玩家的,诸如围棋,象棋,陆战旗等都不属于无偏博弈。
  无偏博弈在数学上有一定的章法可循。现在来考虑一个和上面古畑先生玩的相同性质的一个“取石子游戏”:桌子上有15个石子,每人每次可以拿去1到3个石子,拿走最后一个石子的人赢。
  这个游戏其实不管从推理还是从结论上说都和文章开头的游戏一样,不过这次我们尝试找出更普遍的规律。因为石子的数量总是递减的,所以这个游戏必将在有限步(15步)内结束。我们可以用余下石子的数目来表示局面,于是一共有16个局面。因为规定了拿走最后一个石子的人赢,换句话说当石子个数为0时,就是一个“轮到谁谁就输”的局面,我们通常叫这种局面为必败态。既然0是必败态,那么当局面为1,2,3时,先手就可以采取规则所允许的策略(拿走1个,2个,或是3个)来把局面变成0,于是称1,2,3为胜态;而当局面为4时,不论采取何种策略,局面都将走向胜态,从而4是一个必败态。
  现在不用再分析下去我们就知道,一个无偏博弈的局面可以分成两种:必败态和胜态。
  胜态一定可以通过某种策略走向必败态;而必败态采取任何策略都将走向胜态。
  假如游戏开始时的局面是胜态,那么先手总可以采取适当的策略使胜态走向必败态,然后交给后手。而后手面对必败态,无论他怎么行动,都将走向胜态。假如先手足够聪明的话,先手就让后手永远面临必败态,而自己永远面临胜态,直至游戏结束。这就是一个先手(采取适当策略)能必胜的游戏。反之,如果游戏开始的局面是必败态,那么这就是一个后手必胜的游戏。
  在文章的最后,大家来练练手吧,还是刚才的取石子游戏,桌子上有15个石子,每人每次可以拿去1个或3个石子,拿走最后一个石子的人赢,能否列出所有的必败态,找出先手的必胜策略呢?
 
 
 
 
本文未获果壳网(Guokr.com)授权转载
 
 
 
 

转载请注明:Kermit的网站 » 博弈入门:从数学游戏开始