(过新年了, 找到了以前写的一篇没发出来的旧文章, 算作一篇贺岁吧)

最近日本著名演员饭岛老师去世了. 在我这个年龄段的人中, 熟悉饭岛老师的相信十有八九都是通过奇妙的叫做 bt 或者 电驴 的软件认识的. 今天我们就来八卦一下程序设计人员是如何_设计这些客户端的策略使得您既能下载欣赏到饭岛老师的片子, 又不会浪费您太多的上传带宽_的. 简单的说, 就是 P2P 软件的客户端的策略该如何设计, 使得整个系统能够帮助每个用户获得相应的利益最大化.

要研究这个问题, 我们得从博弈论谈起. 但是因为这个是给程序员看的八卦, 不是数学专业课, 我们不在这里说太多的数学, 而是用例子和八卦引入.

大家都知道, 1994 年的诺贝尔经济学奖给了一个数学家, 约翰.纳什 (电影”美丽心灵”为证). 纳什的理论工作是推广了冯诺伊曼开创的极大极小定理(博弈论的基本定理). 而在通俗的对博弈论的介绍中, 提到纳什, 一般都是着重在纳什均衡和囚徒困境上. 我们不具体深究纳什均衡的数学意义, 而是以下面一个具体的极其简化的例子来说明囚徒困境:

假设 BT 网络中两个节点 阿强(A) 和 B哥(B) 要交换文件. 文件很大, 我们假设需要非常多轮交换才能完成. 每一轮, 每个节点可以选择 平衡上传/下载 和 几乎不上传/贪婪下载两组策略. 我们按照博弈论的一般用语, 把第一种策略称为 C(合作), 第二种称为 D(叛变). 同时, 假设A, B 都是使用 ADSL 网络, 所以上传成本比下载成本要高很多, 我们在计算回报的时候考虑这样的不对称. 现在, 假设 A 和 B 各自有对方需要的文件, 那么, 如果 A, B 同时选择策略 C, 即平衡的上传和下载, 他们得到的回报都是 3, 如果其中一个人偷鸡选择 D, 即几乎不上传, 光下载; 而另一个节点选择 C, 则选择 D 的能够下载到所要的文件且几乎不需要付出上传的代价, 我们记回报为 5, 而另一个人付出了上传的费用, 却得到了一点点的下载, 可以把回报看成是0. 如果两个人都选择贪婪下载, 几乎不上传, 那么两个人都得到了一点点下载, 现在这样的下载量没有3多, 但是因为本身付出的上传成本也少, 我们把这时候两者的回报都定为 1.

说了这么多, 只是为了让问题更加的真实. 这些交代的条件的数学本质, 可用表格表示, 博弈论中称之为支付矩阵:

C D

C (3,3) (0, 5)

D (5,0) (1, 1)

现在的问题是, 阿强和B哥都是理性的, 也是自私的, 因此, 他们都认为, “假如我选 C, 对方可能选 C 或者 D, 那么我这个策略最糟糕的情况下收益是 0, 而假如我选 D, 最糟糕的情况下收益是 1″ 那么, 因为 D 下最糟糕的收益比 C 最糟糕的情况下收益要大, 理智的人肯定选D. 我们看到, 两者选择 D 都是理性的, 但是实际上从对两者的收益分析看, 两者都选择 C 才是更加优的. 这个表面上看上去很理智但是最后没有到达对双方最好的结果的困境, 就是所谓的囚徒困境. (看过这篇八卦, 您也可以叫做饭岛老师困境)

关于囚徒/饭岛困境的简单介绍就到这里, 现在我们看我们的原始问题. 我们知道, BT 交换文件是分成一块一块的, 也就是说, 是一次一次的交换的. 我们把每次交换叫做一轮的话, 整个系统是一个多轮的博弈问题(或者叫做多阶段的博弈问题). 这个博弈问题, 就显得好玩起来了. 为什么呢, 因为多阶段博弈, 居然能够让自私的A和B两个节点为了自己的利益, 进化出合作来.

我们先简单的说明一下多阶段博弈不必然的能跳出囚徒困境. 比方说, 如果 A 和 B 知道一共有 N 轮博弈, 那么最后一轮, 理智的他们肯定都陷入了囚徒困境, 在第 N 轮 的策略清楚之后, N 的问题就转化为 N-1 轮的问题. 所以, 必然的, A 和 B 在所有 N 轮上, 都会陷入囚徒困境 (好比奸商一辈子只和你做有限次买卖的话, 就会一直黑你, 不黑白不黑). 他们等到花儿也谢了, 也不能得到自己想要的内容. 但是, 问题的奥妙在于, 假如A 和 B 不知道一共多少轮, 或者有无限轮呢? 假如阿强在某轮选择平衡的上传和下载(C), 则可能正好碰上 B 哥 也选择”友好合作”, 那么, 两个人都舒舒服服的交换了饭岛老师的片片. 所以, 对于一个设计良好的BT客户端, 问题的关键在于怎么选择自己的策略, 使得既能完成自己自私的下片目标, 又能注意和其他客户端良好的合作使得自己的收益最大, 而不在于在特定的一轮中自己的得失.

这里, 我们的目标是设计一个良好的策略. 通常, 在设计一个实践中性能良好的算法的时候, 数学家和计算机科学家在这里的方法就鲜明的分野了. 数学家, 会证明这样算法的存在性, 性能上下界, 和众多的必要条件, 以及算法之间在最理想的情况下的好坏比较. 而计算机科学家, 会像搭积木一样, 用不同的基本模块, 直接尝试不同的组合, 一一做实验, 看哪种方法最好. 在这里, 我仅介绍一种计算机科学家的方法: 通过让不同方法比赛, 取出赢家, 赢家的方法最好的方法. 其实准确的说, 这个就是达尔文的适者生存的方法. 而这个比赛本身又是一段非常有趣的八卦, 因此我着重花笔墨介绍一下.

在心理学和行为学领域, 有一本非常著名的书, 叫做<合作的进化>. 其作者, 记载了在80年代, 他组织的两次比赛, 叫做IPD (Iterative Prisoner’s Dilemma, 多轮囚徒困境). 竞赛的目的是在一个多轮的囚徒困境中找出最好的策略, 参赛者自己写好算法程序, 然后由组织者让这些程序两两对弈, 看谁在多轮囚徒困境中得到最多的分. 在所有的数学家计算机科学家等提交的很多程序中, 表现最好的一个策略, 超乎寻常的只有四行简单的 Basic 程序. 这四行 Basic 程序, 勾勒出了一个叫做 “针锋相对” 的算法(Tit for Tat).  这个算法策略很简单, 一开始采用合作, 假如对方上一轮合作, 则本轮合作. 如果对方上一轮对抗, 则本轮对抗. 用中国人熟悉的话说, 叫做”人不犯我, 我不犯人; 人若犯我, 我必犯人”. (四句话正好对应四行程序, 不是巧合). 其他的算法, 比如随机算法呀, 永远敌对的算法呀, 都比不过这个算法. 因此, 这个算法赢得了第一年的竞赛.

第二次, 各位吸取教训, 继续开发好算法. 猜猜第二次谁赢了? 居然还是那四行程序! 在合作的进化中, 作者从”宽容, 以牙还牙”等社会学的角度去解释为啥这四行程序会赢. 或许对人生有深刻思考的人会感叹, 这四行程序的确蕴含了深刻的智慧. 但是, 很不幸的是, 这个程序在现实中, 有一个非常大的漏洞, 而因为这个漏洞, 使得BT程序如果不修改策略, 先现实中会寸步难行. 这个看上去非常理智非常聪明的策略到底是怎样的大漏洞呢, 我先卖个关子, 下回分解.

(想看剧透的, 可以看 Wikipedia 的条目: Tit for Tat: http://en.wikipedia.org/wiki/Tit_for_Tat )

新年快乐!

1. 最近挺忙的, “编程珠玑番外篇”更新不快了, 闲散的短篇反而多了. (我和霍炬说过, 写技术八卦非常的耗时间, 平均写一篇要做50次以上的Google, 还要整理很多书的读书笔记查资料等等, 耗时基本在三小时左右). <编程珠玑番外篇> 是一个我自己也非常中意的系列文章, 用师兄[刘未鹏](http://blog.csdn.net/pongba)的话说, “这个系列传播力很强”. 所以, 我会一直坚持写下去, 写完了汇成一个 PDF 大家取用.

2. 今天技术牛人 DBAnotes 推荐我的博客了, 他说:

4G Spaces

地址: http://blog.youxu.info/

作者: 徐宥

我和作者不认识。他的《编程珠玑番外篇》是今年见到的最好的技术八卦(并非贬义)；”完全用键盘”工作的系列文章很好的体现了 Geek 精神。

感谢他的推荐和表扬. 希望这个技术八卦系列在2009年依然是质量上乘的技术八卦 :)

1. 下面的写作计划其实我早就有了, 苦于没有时间码字 (事实上从最近到1月12日, 我都没时间码字了). 为了让大家保持一个好胃口, 趁着 DBAnotes 的推荐, 说一下剧透好了 (有兴趣的快订阅本博客啊):

协程的八卦: 抢占式多任务 协作式多任务的概念, 协程在编程语言里的实现的历史, yield 关键字的来历. 协程在现代编程语言中的消亡和复兴.

关于用户级线程库的八卦: 内核线程还是用户线程, 历史的演变, 各大编程语言的实现, 为啥Python 不能在多核上提高效率而Java 能. 用户级线程库在现代编程语言中的复兴.

Java平台的动态化: JSR292 的前世今生, 一个静态语言的平台如何加入一个指令就能动态化? PVM 和 JVM 的区别在哪里, 谁是下一代一统江湖的语言平台?

…

我相信, 后面会写的越来越精彩, 希望大家持续关注.

»»>各位读者,新年和圣诞节快乐««

junyu 和我暑假无聊的时候曾经搞笑写过一段文字:

我们正在工作在一个火狐狸的实现, 而且已经要完成了基本上, 并且可以让火狐狸直接呈现 CHTML 页面. 对不起微软的用户, 因为我们没有得到任何英特网探险家的超文本解析库的授权, 按照新千禧年数字法案, 我们的工程师不能加 CHTML 的支持通过反向工程. 我们感到很抱歉为此.

服务器捐赠是被欢迎的. 你也可以捐赠我们通过 Paypal.

反正不知道当时是谁突然灵光一闪, 想起来我们小时候用过很土的那种翻译软件的风格, 然后两个人都很有感触, 就像回到 windows 95 一样. 所以我们一起人工模仿恶搞出了古老的翻译软件的效果. 为了保证“看上去”真实, 我们在后面加上了一段:

鸣谢: 谷歌翻译 提供了很多便利为我们的工作, 我们感谢它!

于是, 有了以下的评论:

1. 这些文字感觉是翻译过来的。。。在国内土生土长的人写文章会写以下这样的语句？

2. “服务器捐赠是被欢迎的. 你也可以捐赠我们通过 Paypal”,这是怎么翻译的,难道是直接通过翻译工具将英文转化出来的?

3. 我测试过，是把中文用翻译软件翻译成英文，再用翻译软件把翻译的英文翻译回中文的产物。

4. 很明显是故意这样写的，目的是搞笑嘛

5. 谷歌翻译 提供了很多便利为我们的工作, 我们感谢它!

——————————主页上写的很清楚!

1. 撒比，是先用英文写好，再用Google翻译的，就做出了这种“特效”。

这些评论, 特别是3 和 6, 完全不顾我和junyu 花了十几分钟人脑翻译的事实. 我们看了这些以后, 不禁莞尔.

网上流行几条面试题, 都和经典的采样洗牌问题有关, 网上每过一段时间都有哥们拿出来问一下. 正好最近在翻的 TAoCP Vol 2 上有详细专门的讲解, 因此在此一并介绍.

这几道面试题是:

1.  Given a random number generator which can generate the number in range (1,5) uniformly. How can you use it to build a random number generator which can generate the number in range (1,7) uniformly?

(http://discuss.joelonsoftware.com/default.asp?interview.11.489564.8)

1. Generate a random permutation for a deck of cards.

2. Given a long log file (not sure how long), pick 1000 items evenly from them. (Google Interview)

其中, 第一条是随机数的生成问题. 第二条是生成一个序列的随机排列的问题, 第三条等价于生成一个序列的随机组合的问题. 实质上洗牌问题就是从集合中选取随机排列, 而采样问题就是从集合中选取随机组合.

第一条的解法要用到拒绝采样定理. 简单的说, 把 1-5 的随机数发生器用两次, 拼成一个5进制的数, 就是1-25. 将这 1-25 平均分配的25种情况映射到7种情况上, 问题就解决了. 因为21是7的倍数, 我们可以每三个映射到一个, 即1-3 映射到1, …, 19-21 映射到7. 可见, 这些情况之间的概率是一样的. 那么, 要是拼成的数字正好是 22-25 这四个呢? 有两种方法, 第一种是丢弃这个数字, 从头再来, 直到拼成的数字在1-21之间. 因为这个是个概率算法, 不能保证每次都能落在1-21, 所以采样的密度不高. 还有一种方法, 是说, 假如落到了 22-25, 那这次的采样结果就用上次的. 可以证明, 这看上去两个互相矛盾的算法, 结果都能均等的得到等概率的分布. (前者叫做 Reject Sampling, 后者叫做 Metropolis Algorithm, 都是数学物理模拟里面常用的方法)

第二条的解法很简单, 从后往前第k步的时候, 每次取一个1-52k (假如牌有52张) [感谢读者评论指出这个错误 不是1-52, 而是1-k] 的随机数 j, 交换 k 和 j. 这样, 每一位都是等概率的被交换, 最后的排列也是等概率的得到.

这个方法有一个趣闻. 我们知道, 计算机里的随机数发生器是伪随机数发生器. 伪随机数发生器的原理是用线性同余实现的, 即本次的随机数 乘以一个常数, 加上另一个常数, 再对一个大数c求同余. 我们可以把从一个随机数到下一个随机数的映射看成一个函数, 这个函数是必然形成循环的 (您把这个操作和集合整体当成循环群理解也是对的, 因为好的伪随机数发生器都设计得使得所有的数是各态遍历的). 这个循环的周期, 最长就是就是c. 所以, 如果您用伪随机数发生器来生成以上的排列的话, 只会得到最多 c 种不同的交换方案. 假设我们使用 32 位机器, 那么最大的可以用在做同余的c 就是 \(2^{32}\). 可是 13! 就已经是这个数量级了, 更不要说是 52 的阶乘. 这就意味着, 用计算机里的随机数发生器, 只能生成总体可能排列中极其有限的一部分. 所以, 假如您在电脑上玩扑克牌, 而扑克牌的洗牌算法又正好是上面我们说的那种的话, 您可能一辈子也抓不到某种组合. 这个不是概率很小的问题, 而是完全不可能. (此例来自 TAoCP, Vol 2)

第三条也不难, 虽然听上去吓人. 本质上只需要知道在已经处理了前 t (\(t \ge 1000\))个的情况下, 第 t +1 个被选中的概率. 实际上就是 1000/(t+1). 因此, 用这个概率去替换已经选中的1000个当中的某个. 可以证明, 任何时间停下来, 算法都是等概率的挑出了前面 t 个里面的1000 个. 这种任何时间能停下来还能获得正确结果的算法, 叫做 Anytime Algorithm, 在计算机科学领域随处可见, 尤其是 AI Search 方面.

第三条的算法在 TAoCP 第二卷里面交代得更加全面, 因为考虑了这 1000 个记录在内存里面放不下的情况. 这时候, 一个叫做 reservoir 的缓存被引入. 每次仅仅把选中的记录加入 reservoir, 而只保留记录在其中的序号. 在序号的数据结构上作替换, 最后, 按照最终留下来的那些序号, 再走一遍 reservoir, 就得到了要选的记录. 这个采样的方法在分析不定长网络日志的时候比较有用, 所以也是 Google 亲睐的面试题.

采样和洗牌的更多内容, 请参考 TAoCP Vol 2. 3.4.2.