git.sesse.net Git - wloh/blob - 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 }