一个小游戏怎么样必胜（数学必胜策略、推理、计算）

来源：蜘蛛抓取(WebSpider) 时间：2020-10-19 13:33 标签： 数学必胜策略

推理剧《古畑任三郎》之“数学必胜策略家杀人事件”中有这么一个小插曲这是古畑和数学必胜策略家之间的一个小游戏：

两个人轮流数数，从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个石子拿走最后一个石子的人赢，能否列出所有的必败态找出先手的必胜策略呢？

在研究Nim游戏的时候和同学突然想箌了这个小游戏但是发现貌似和Nim游戏不是一类的游戏，所以咨询一下求解！！

这周David Eppstein教授的算法分析课上提到了Sylver coinage 這样一个数学必胜策略游戏 大致给懒得看wiki的人讲一下游戏规则：游戏…

我要回帖

更多关于 数学必胜策略 的文章

 

随机推荐