]> git.sesse.net Git - wloh/blob - mcwordfeud.cpp
Store all player IDs as ints instead of strings. Less flexibility, but chops off...
[wloh] / mcwordfeud.cpp
1 #include <stdio.h>
2 #include <math.h>
3 #include <string.h>
4 #include <stdlib.h>
5
6 #include <map>
7 #include <vector>
8 #include <string>
9 #include <algorithm>
10 #include <Eigen/Cholesky>
11 #include <Eigen/Dense>
12
13 #include "ziggurat.hpp"
14
15 using namespace std;
16 using namespace Eigen;
17
18 #define MAX_PLAYERS 16
19
20 enum OutputMode {
21         PROBABILITY_MATRIX = 0,
22         MOST_LIKELY_MATCHING = 1,
23 };
24
25 float match_stddev = 70.0f;
26
27 struct player {
28         int player_index;
29         int points, margin;
30 };
31 struct highest_ranking {
32 public:
33         bool operator() (const player &a, const player &b) const {
34                 if (a.points != b.points) {
35                         return a.points > b.points;
36                 }
37                 return a.margin > b.margin;
38         }
39 };
40
41 #if 0
42 float draw_unit()
43 {
44         return rand() * (1.0f / RAND_MAX);
45 }
46
47 // FIXME: replace rejection method with a better method! this one can only ever go to [-5z, +5z]
48 // and is very slow.
49 float draw_gaussian(float stddev)
50 {
51         for ( ;; ) {
52                 float z = draw_unit() * 10.0f - 5.0f;
53                 float y = draw_unit();
54                 if (y < exp(-z*z)) {
55                         return z * stddev;
56                 }
57         }       
58 }
59 #else
60 float draw_gaussian(float mu, float stddev)
61 {
62         static bool inited = false;
63         static long unsigned seed = time(NULL);
64         static int kn[128];
65         static float fn[128], wn[128];
66         if (!inited) {
67                 r4_nor_setup(kn, fn, wn);
68                 inited = true;
69         }
70
71         return r4_nor(&seed, kn, fn, wn) * stddev + mu;
72 }
73 #endif
74
75 int main(int argc, char **argv)
76 {
77         int trials = atoi(argv[1]);
78         OutputMode output_mode;
79         int match_player_num = -1, match_position = -1;
80         if (argc >= 3) {
81                 match_player_num = atoi(argv[2]);
82                 match_position = atoi(argv[3]);
83                 output_mode = MOST_LIKELY_MATCHING;
84         } else {
85                 output_mode = PROBABILITY_MATRIX;
86         }
87
88         // For most likely matching.
89         bool has_mlm = false;
90         double mlm_likelihood = 0.0f;
91         int mlm_scores[MAX_PLAYERS][MAX_PLAYERS];
92
93         if (scanf("%f", &match_stddev) != 1) {
94                 fprintf(stderr, "Could't read match stddev\n");
95                 exit(1);
96         }
97
98         int num_players;
99         if (scanf("%d", &num_players) != 1) {
100                 fprintf(stderr, "Could't read number of players\n");
101                 exit(1);
102         }
103
104         if (num_players > MAX_PLAYERS) {
105                 fprintf(stderr, "Max %d players supported\n", MAX_PLAYERS);
106                 exit(1);
107         }
108
109         vector<string> players;
110         map<string, int> player_map;
111         Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> ratings(num_players);
112         bool has_scores[MAX_PLAYERS][MAX_PLAYERS];
113         for (int pl1 = 0; pl1 < num_players; ++pl1) {
114                 for (int pl2 = 0; pl2 < num_players; ++pl2) {
115                         has_scores[pl1][pl2] = false;
116                 }
117         }
118
119         int scores[MAX_PLAYERS][MAX_PLAYERS];
120         for (int i = 0; i < num_players; ++i) {
121                 char buf[256];
122                 float rating;
123                 int ret = scanf("%s %f", buf, &rating);
124                 if (ret < 1) {
125                         fprintf(stderr, "Couldn't read player %d\n", i);
126                         exit(1);
127                 }
128                 if (ret < 2) {
129                         rating = 500.0f;
130                 }
131
132                 players.push_back(buf);
133                 player_map[buf] = i;
134                 ratings(i) = rating;
135         }
136
137         Matrix<float, Dynamic, Dynamic, 0, MAX_PLAYERS, MAX_PLAYERS> ratings_cov(num_players, num_players);
138         for (int i = 0; i < num_players; ++i) {
139                 for (int j = 0; j < num_players; ++j) {
140                         float f;
141                         if (scanf("%f", &f) != 1) {
142                                 fprintf(stderr, "Couldn't read covariance matrix element (%d,%d)\n", i, j);
143                                 exit(1);
144                         }
145                         ratings_cov(i, j) = f;
146                 }
147         }
148         Matrix<float, Dynamic, Dynamic, 0, MAX_PLAYERS, MAX_PLAYERS> ratings_cholesky =
149                 ratings_cov.llt().matrixLLT();
150
151         for ( ;; ) {
152                 char pl1[256], pl2[256];
153                 int score1, score2;
154
155                 if (scanf("%s %s %d %d", pl1, pl2, &score1, &score2) != 4) {
156                         break;
157                 }
158
159                 if (player_map.count(pl1) == 0) {
160                         fprintf(stderr, "Unknown player '%s'\n", pl1);
161                         exit(1);
162                 }
163                 if (player_map.count(pl2) == 0) {
164                         fprintf(stderr, "Unknown player '%s'\n", pl2);
165                         exit(1);
166                 }
167
168                 scores[player_map[pl1]][player_map[pl2]] = score1;
169                 scores[player_map[pl2]][player_map[pl1]] = score2;
170                 has_scores[player_map[pl1]][player_map[pl2]] = true;
171                 has_scores[player_map[pl2]][player_map[pl1]] = true;
172         }
173
174         int placements[MAX_PLAYERS][MAX_PLAYERS];
175         for (int i = 0; i < num_players; ++i) {
176                 for (int j = 0; j < num_players; ++j) {
177                         placements[i][j] = 0;
178                 }
179         }
180
181         for (int i = 0; i < trials; ++i) {
182                 // draw true strength for all players
183                 Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> drawn_normals(num_players);
184                 for (int p = 0; p < num_players; ++p) {
185                         drawn_normals(p) = draw_gaussian(0.0f, 1.0f);
186                 }
187                 Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> drawn_ratings = ratings_cholesky * drawn_normals + ratings;
188
189                 // draw the missing matches
190                 for (int pl1 = 0; pl1 < num_players; ++pl1) {
191                         for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) {
192                                 if (has_scores[pl1][pl2]) {
193                                         continue;
194                                 }
195
196                                 float mu = drawn_ratings(pl1) - drawn_ratings(pl2);
197                                 
198                                 int score = lrintf(draw_gaussian(mu, match_stddev));
199                                 if (score >= 0) {
200                                         scores[pl1][pl2] = score;
201                                         scores[pl2][pl1] = 0;
202                                 } else {
203                                         scores[pl1][pl2] = 0;
204                                         scores[pl2][pl1] = -score;
205                                 }
206                         }
207                 }
208
209                 // sum up the points and margin for each player
210                 player stats[MAX_PLAYERS];
211                 for (int pl1 = 0; pl1 < num_players; ++pl1) {
212                         stats[pl1].player_index = pl1;
213                         stats[pl1].points = 0;
214                         stats[pl1].margin = 0;
215                         for (int pl2 = 0; pl2 < num_players; ++pl2) {
216                                 if (pl1 == pl2) {
217                                         continue;
218                                 }
219                                 stats[pl1].margin += scores[pl1][pl2];
220                                 stats[pl1].margin -= scores[pl2][pl1];
221                                 if (scores[pl1][pl2] > scores[pl2][pl1]) {
222                                         stats[pl1].points += 2;
223                                 } else if (scores[pl1][pl2] == scores[pl2][pl1]) {
224                                         stats[pl1].points++;
225                                 }
226                         }
227                 }
228
229                 // order by points and then margin
230                 sort(stats, stats + num_players, highest_ranking());
231
232                 if (output_mode == PROBABILITY_MATRIX) {
233                         for (int j = 0; j < num_players; ++j) {
234                                 ++placements[stats[j].player_index][j];
235                         }
236                 }
237                 if (output_mode == MOST_LIKELY_MATCHING) {
238                         if (stats[match_position].player_index != match_player_num) {
239                                 continue;
240                         }
241
242                         // compute the log-likelihood of this situation (ignoring the constant terms)
243                         double llh = 0.0f;
244
245                         // strength of all players (ignore the constant terms)
246                         for (int p = 0; p < num_players; ++p) {
247                                 llh -= drawn_normals(p) * drawn_normals(p) * 0.5f;
248                         }
249
250                         // all the matches
251                         for (int pl1 = 0; pl1 < num_players; ++pl1) {
252                                 for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) {
253                                         if (has_scores[pl1][pl2]) {
254                                                 continue;
255                                         }
256                                         float mu = drawn_ratings(pl1) - drawn_ratings(pl2);
257                                         float z = (scores[pl1][pl2] - scores[pl2][pl1] - mu) / match_stddev;
258                                         llh -= z * z * 0.5f;
259                                 }
260                         }
261
262                         if (!has_mlm || llh > mlm_likelihood) {
263                                 has_mlm = true;
264                                 mlm_likelihood = llh;
265                                 memcpy(mlm_scores, scores, sizeof(mlm_scores));
266                         }
267                 }
268         }
269
270         if (output_mode == PROBABILITY_MATRIX) {
271                 for (int i = 0; i < num_players; ++i) {
272                         printf("%-15s", players[i].c_str());
273                         for (int j = 0; j < num_players; ++j) {
274                                 printf(" %5d", placements[i][j]);
275                         }
276                         printf("\n");
277                 }
278         }
279         if (output_mode == MOST_LIKELY_MATCHING && has_mlm) {
280                 for (int pl1 = 0; pl1 < num_players; ++pl1) {
281                         for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) {
282                                 if (has_scores[pl1][pl2]) {
283                                         continue;
284                                 }
285                                 printf("%s %s %d\n", players[pl1].c_str(), players[pl2].c_str(), mlm_scores[pl1][pl2] - mlm_scores[pl2][pl1]);
286                         }
287                 }
288         }
289 }