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

发表于 | 分类于 ， | | 阅读次数

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

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

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

公式

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

$$E_a = \frac{1} {1 + 10 ^ {(R_b - R_a) / 400}}$$

  • $E_a$就是a的期望胜率.
  • $R_b,R_a$是b与a的Rank分数.
  • 当$R_a,R_b$都相同时,它们的期望胜率都为0.5,即$E_a = \frac{1} {1+10^0} = 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 = \frac{1} {1 + 10 ^ {(1395 - 1405) / 400}} \approx 0.51439 $
  • $R_b = \frac{1} {1 + 10 ^ {(1405 - 1395) / 400}} \approx 0.48561$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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),转载请务必指明原文链接.

分享