寻求真心话大冒险之猜数游戏的最佳策略

    去年的高中同学会上,吃完饭后大家就坐成一圈开始玩猜数游戏了。主持人自己在手机上输入一个1到,比如说500,的数,然后大家轮流猜数,并由主持人告之是猜大了还是猜小了。猜中了的那个人接受惩罚,真心话,或者大冒险,然后成为新的主持人。例如,我们班班长想了个数230。然后某男猜200,班长说“200到500”,意思就是200小了,以后的人只能猜200到500之间的数;接下来某女说“300”,美女班长说“200到300”;然后另一个MM猜250,班长回答“200到250”;然后就轮到我猜了,我说“230吧”,班长一脸坏笑把手机拿出来给大家看,说“哈哈,你猜中啦”。然后呢,我就和某个MM做了一件特别牛B的事情,细节呢就不在这里说了。
    当天同学会结束后我赶回学校机房继续讲课。我提出了这么一个问题:如果我不想猜中的话,怎么决策最好?如果我想猜中的话,又该猜什么呢?这个博弈过程复杂就复杂在,这是由多个人参与的游戏,目的不是尽早猜中或者最晚猜中,最佳决策很可能既不是猜正中间也不是猜最大或最小;游戏是一圈一圈地循环进行,策略要视总人数和数字范围而定,并且很可能每个人居心各不相同。


    写完前面那篇日志,我突然意识到:由于我们只能猜某个范围内的数,而该范围总是会变得越来越小,因此这个问题的状态有一个非常自然的拓扑序。我们立即想到,这是一个典型的动态规划模型:设f[i, j_1, j_2, k_1, k_2]表示还剩下i个数要猜,如果当前这个人(比如张三)希望用最少j_1次最多j_2次猜测结束游戏,而事实上在他的最优策略下猜测次数落在k_1到k_2范围内的概率。由于大家是围成一圈依次猜数,因此对j_1, j_2, k_1, k_2可能需要引入关于总人数同余的概念。枚举决策l,可能性分三种:有1/i的可能性直接猜中,有(l-1)/i的可能性猜大了,还有(i-l)/i的可能性猜小了。对于后两种情况,状态转移到下一个人(比如李四)在剩下的数中作出符合他(李四)的利益的最佳选择后,张三所期望的事实将会发生的概率。得出最佳决策后,还可以根据已有结果算出在张三的这种策略下实际上各种结局发生的概率。状态的具体定义和转移方程随着具体情况的变化而变化。例如,所有人都足够聪明并且都不想猜中,或者某些人将会像傻子一样的随机猜,或者男女各坐一个半圆两边想互相陷害,或者n-1个人合伙想整剩下的那个人,或者你反倒想猜中这个数从而有充分的借口猥亵一个多年来一直让你欲火焚身的漂亮MM。
    这个动态规划的思路是不是正确的?在每一种具体问题下可以怎样简化和优化?程序运行的结果怎样呢?这个问题还可以怎样扩展?欢迎大家在下面留言谈谈自己的看法。

14 条评论

发表评论