2008-09-30 17:47| 
12 Comments | 本文内容遵从 去年的高中同学会上，吃完饭后大家就坐成一圈开始玩猜数游戏了。主持人自己在手机上输入一个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。
这个动态规划的思路是不是正确的？在每一种具体问题下可以怎样简化和优化？程序运行的结果怎样呢？这个问题还可以怎样扩展？欢迎大家在下面留言谈谈自己的看法。
终于沙花了..呵呵，经常玩真心话的～
怎么总是欲火焚身……
好像可以看成离散的优选法问题？如果可以的话，最“欲火焚身”的做法是不是仍然是在黄金分割点处选？
色情...
范围是[a,b]，若a>maxn-b 则猜a+1否则猜b-1？
“主持人自己在手机上输入一个1到，比如说500，的数”
这一句的翻译腔可真浓……
我觉得这是一个心理学问题，揣测主持人对数字的喜好应该很有用……
策略的能否有用是要看由以后的运转过程能否按照可控情况进行的，在其他人的行为不可控的情况下，计划好的策略往往没有实际效果。。。
特别牛B的事是什么事呢...?
有遐想空间..
似乎很复杂……
难道还需要统计心理学知识？
我觉的事情很难控制，混沌学……
要是这个问题都能解决，那岂不真成神仙了
或许事情比我们想象的要复杂，但也许比我们想象的要简单……
等待高人指点……
概率不均等
所以要考虑的应该不只这些
忽忽～～我喜欢这个～好实用哟～～什么时候你和你的朋友们想出来了用通俗一点的话讲给我嘛～～