10 #include <Eigen/Cholesky>
11 #include <Eigen/Dense>
13 #include "ziggurat.hpp"
16 using namespace Eigen;
18 #define MAX_PLAYERS 16
21 PROBABILITY_MATRIX = 0,
22 MOST_LIKELY_MATCHING = 1,
25 float match_stddev = 70.0f;
31 struct highest_ranking {
33 bool operator() (const player &a, const player &b) const {
34 if (a.points != b.points) {
35 return a.points > b.points;
37 return a.margin > b.margin;
44 return rand() * (1.0f / RAND_MAX);
47 // FIXME: replace rejection method with a better method! this one can only ever go to [-5z, +5z]
49 float draw_gaussian(float stddev)
52 float z = draw_unit() * 10.0f - 5.0f;
53 float y = draw_unit();
60 float draw_gaussian(float mu, float stddev)
62 static bool inited = false;
63 static long unsigned seed = time(NULL);
65 static float fn[128], wn[128];
67 r4_nor_setup(kn, fn, wn);
71 return r4_nor(&seed, kn, fn, wn) * stddev + mu;
75 int main(int argc, char **argv)
77 int trials = atoi(argv[1]);
78 OutputMode output_mode;
79 int match_player_num = -1, match_position = -1;
81 match_player_num = atoi(argv[2]);
82 match_position = atoi(argv[3]);
83 output_mode = MOST_LIKELY_MATCHING;
85 output_mode = PROBABILITY_MATRIX;
88 // For most likely matching.
90 double mlm_likelihood = 0.0f;
91 int mlm_scores[MAX_PLAYERS][MAX_PLAYERS];
93 if (scanf("%f", &match_stddev) != 1) {
94 fprintf(stderr, "Could't read match stddev\n");
99 if (scanf("%d", &num_players) != 1) {
100 fprintf(stderr, "Could't read number of players\n");
104 if (num_players > MAX_PLAYERS) {
105 fprintf(stderr, "Max %d players supported\n", MAX_PLAYERS);
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;
119 int scores[MAX_PLAYERS][MAX_PLAYERS];
120 for (int i = 0; i < num_players; ++i) {
123 int ret = scanf("%s %f", buf, &rating);
125 fprintf(stderr, "Couldn't read player %d\n", i);
132 players.push_back(buf);
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) {
141 if (scanf("%f", &f) != 1) {
142 fprintf(stderr, "Couldn't read covariance matrix element (%d,%d)\n", i, j);
145 ratings_cov(i, j) = f;
148 Matrix<float, Dynamic, Dynamic, 0, MAX_PLAYERS, MAX_PLAYERS> ratings_cholesky =
149 ratings_cov.llt().matrixLLT();
152 char pl1[256], pl2[256];
155 if (scanf("%s %s %d %d", pl1, pl2, &score1, &score2) != 4) {
159 if (player_map.count(pl1) == 0) {
160 fprintf(stderr, "Unknown player '%s'\n", pl1);
163 if (player_map.count(pl2) == 0) {
164 fprintf(stderr, "Unknown player '%s'\n", pl2);
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;
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;
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);
187 Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> drawn_ratings = ratings_cholesky * drawn_normals + ratings;
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]) {
196 float mu = drawn_ratings(pl1) - drawn_ratings(pl2);
198 int score = lrintf(draw_gaussian(mu, match_stddev));
200 scores[pl1][pl2] = score;
201 scores[pl2][pl1] = 0;
203 scores[pl1][pl2] = 0;
204 scores[pl2][pl1] = -score;
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) {
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]) {
229 // order by points and then margin
230 sort(stats, stats + num_players, highest_ranking());
232 if (output_mode == PROBABILITY_MATRIX) {
233 for (int j = 0; j < num_players; ++j) {
234 ++placements[stats[j].player_index][j];
237 if (output_mode == MOST_LIKELY_MATCHING) {
238 if (stats[match_position].player_index != match_player_num) {
242 // compute the log-likelihood of this situation (ignoring the constant terms)
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;
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]) {
256 float mu = drawn_ratings(pl1) - drawn_ratings(pl2);
257 float z = (scores[pl1][pl2] - scores[pl2][pl1] - mu) / match_stddev;
262 if (!has_mlm || llh > mlm_likelihood) {
264 mlm_likelihood = llh;
265 memcpy(mlm_scores, scores, sizeof(mlm_scores));
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]);
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]) {
285 printf("%s %s %d\n", players[pl1].c_str(), players[pl2].c_str(), mlm_scores[pl1][pl2] - mlm_scores[pl2][pl1]);