电影<<社交网络>>中的"FaceMash"算法

最近在看<<社交网络>>时,发现了一个用于投票排名的算法,自己折腾实现了一下.

在影片中,卷西饰演的扎克伯格在被妹子甩了之后(其实是他自己直男癌),一气之下黑了附近女生宿舍的照片数据库打算做一个FaceMash(通过投票的方式来选出漂亮的女生,同时它也是Facebook的前身,后来这个网站由于流量太大,搞崩了哈佛大学的网络而被强行关闭了),并使用了他的好基友爱德华多用于计算国际象棋排名的算法.

这是一部很好看的电影,如果没有看过我强烈推荐去看一看.

公式

这个算法是用来计算期望胜率的,但影片中其实写的是错误的,正确的公式应该为:

E a =1 1 +10( Rb −Ra)/ 400

E a 就是a的期望胜率.

R b ,R a 是b与a的Rank分数.

当R a ,R b 都相同时,它们的期望胜率都为0.5,即E a =1 1 +100 =0.5 .

电影中只给出了计算期望胜率的算法,但我们还需要一个计算新的Rank分数的算法,公式如下:

R n =R o +K( W−E)

R n 代表新的Rank,R o 自然就是旧的Rank了.

K为一个定值,我把它设为10.

W是胜负值,胜者为1,败者为0;E就是我们上面计算的期望胜率.

实现

有了这两个核心公式,我们就可以开始实现这个算法了,但在代码实现之前,我们先验证一下公式:

假设有两个女孩A与B,她们的基础Rank都为1400,通过上述的推论我们已经得知,当A,B的分值相同时,她们的期望胜率都为0.5.

如果,我选择了A,则A的胜负值变为1,B的胜负值为0,然后我们套用公式2可以得出:

R a =1400+ 10∗( 1−0.5) =1405

R b =1400+ 10∗( 0−0.5) =1395

由于她们的分数不再相同,所以套用公式1计算现在的期望胜率:

R a =1 1 +10( 1395−1405)/ 400 ≈0.51439

R b =1 1 +10( 1405−1395)/ 400 ≈0.48561

下面是我用C写的一个小程序,它初始化了两个”女孩”,然后根据输入来判断哪个胜出,并动态计算Rank与期望胜率.

#include < stdio.h>
#include < math.h>
typedef struct {
    const char *name;
    int rank;
    double expect_rate;
} girl;
const int K = 10;
void read_girl(girl g) {
    printf("Girl name: %s, rank: %d, expect_rate: %.5f\n",g.name,g.rank,g.expect_rate);
}
void compute_expect_rate(girl *a,girl *b) {
    int a_rank = a->rank;
    int b_rank = b->rank;
    // expect rate formula
    // Ea = 1 / (1 + 10 ^ ((Rb-Ra) / 400))
    double a_rank_differ = (double) (b_rank - a_rank) / 400;
    double a_rank_rate = pow(10,a_rank_differ);
    a->expect_rate = 1 / (1 + a_rank_rate);
    // Eb = 1 / (1 + 10 ^ ((Ra-Rb) / 400))
    double b_rank_differ = (double) (a_rank - b_rank) / 400;
    double b_rank_rate = pow(10,b_rank_differ);
    b->expect_rate = 1 / (1 + b_rank_rate);
}
// new rank formula: Rn = Ro + K(W - E)
void compute_rank(girl *a,girl *b,int a_win_rate,int b_win_rate) {
    a->rank = a->rank + K * (a_win_rate - a->expect_rate);
    b->rank = b->rank + K * (b_win_rate - b->expect_rate);
}
int main(int argc,char *argv[]) {
    char a_girl_name[20];
    char b_girl_name[20];
    girl a = {.name = "A Gril",.rank = 1400};
    girl b = {.name = "B Gril",.rank = 1400};
    compute_expect_rate(&a,&b);
    read_girl(a);
    read_girl(b);
    while (1) {
        char choice[2];
        printf("Choice A or B?\n");
        scanf("%s",choice);
        if (choice[0] == 'A') {
            compute_rank(&a,&b,1,0);
            compute_expect_rate(&a,&b);
        } else if (choice[0] == 'B') {
            compute_rank(&a,&b,0,1);
            compute_expect_rate(&a,&b);
        } else {
            printf("Invalid choice!\n");
            break;
        }
        read_girl(a);
        read_girl(b);
    }
}

本文作者为SylvanasSun(sylvanassun_xtz@163.com),转载请务必指明原文链接.