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 float match_stddev = 70.0f;
  21
  22 struct player {
  23         int player_index;
  24         int points, margin;
  25 };
  26 struct highest_ranking {
  27 public:
  28         bool operator() (const player &a, const player &b) const {
  29                 if (a.points != b.points) {
  30                         return a.points > b.points;
  31                 }
  32                 return a.margin > b.margin;
  33         }
  34 };
  35
  36 #if 0
  37 float draw_unit()
  38 {
  39         return rand() * (1.0f / RAND_MAX);
  40 }
  41
  42 // FIXME: replace rejection method with a better method! this one can only ever go to [-5z, +5z]
  43 // and is very slow.
  44 float draw_gaussian(float stddev)
  45 {
  46         for ( ;; ) {
  47                 float z = draw_unit() * 10.0f - 5.0f;
  48                 float y = draw_unit();
  49                 if (y < exp(-z*z)) {
  50                         return z * stddev;
  51                 }
  52         }
  53 }
  54 #else
  55 float draw_gaussian(float mu, float stddev)
  56 {
  57         static bool inited = false;
  58         static long unsigned seed = time(NULL);
  59         static int kn[128];
  60         static float fn[128], wn[128];
  61         if (!inited) {
  62                 r4_nor_setup(kn, fn, wn);
  63                 inited = true;
  64         }
  65
  66         return r4_nor(&seed, kn, fn, wn) * stddev + mu;
  67 }
  68 #endif
  69
  70 int main(int argc, char **argv)
  71 {
  72         int trials = atoi(argv[1]);
  73
  74         if (scanf("%f", &match_stddev) != 1) {
  75                 fprintf(stderr, "Could't read match stddev\n");
  76                 exit(1);
  77         }
  78
  79         int num_players;
  80         if (scanf("%d", &num_players) != 1) {
  81                 fprintf(stderr, "Could't read number of players\n");
  82                 exit(1);
  83         }
  84
  85         if (num_players > MAX_PLAYERS) {
  86                 fprintf(stderr, "Max %d players supported\n", MAX_PLAYERS);
  87                 exit(1);
  88         }
  89
  90         vector<string> players;
  91         map<string, int> player_map;
  92         Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> ratings(num_players);
  93         bool has_scores[MAX_PLAYERS][MAX_PLAYERS];
  94         for (int pl1 = 0; pl1 < num_players; ++pl1) {
  95                 for (int pl2 = 0; pl2 < num_players; ++pl2) {
  96                         has_scores[pl1][pl2] = false;
  97                 }
  98         }
  99
 100         int scores[MAX_PLAYERS][MAX_PLAYERS];
 101         for (int i = 0; i < num_players; ++i) {
 102                 char buf[256];
 103                 float rating;
 104                 int ret = scanf("%s %f", buf, &rating);
 105                 if (ret < 1) {
 106                         fprintf(stderr, "Couldn't read player %d\n", i);
 107                         exit(1);
 108                 }
 109                 if (ret < 2) {
 110                         rating = 1500.0f;
 111                 }
 112
 113                 players.push_back(buf);
 114                 player_map[buf] = i;
 115                 ratings(i) = rating;
 116         }
 117
 118         Matrix<float, Dynamic, Dynamic, 0, MAX_PLAYERS, MAX_PLAYERS> ratings_cov(num_players, num_players);
 119         for (int i = 0; i < num_players; ++i) {
 120                 for (int j = 0; j < num_players; ++j) {
 121                         float f;
 122                         if (scanf("%f", &f) != 1) {
 123                                 fprintf(stderr, "Couldn't read covariance matrix element (%d,%d)\n", i, j);
 124                                 exit(1);
 125                         }
 126                         ratings_cov(i, j) = f;
 127                 }
 128         }
 129         Matrix<float, Dynamic, Dynamic, 0, MAX_PLAYERS, MAX_PLAYERS> ratings_cholesky =
 130                 ratings_cov.llt().matrixLLT();
 131
 132         for ( ;; ) {
 133                 char pl1[256], pl2[256];
 134                 int score1, score2;
 135
 136                 if (scanf("%s %s %d %d", pl1, pl2, &score1, &score2) != 4) {
 137                         break;
 138                 }
 139
 140                 if (player_map.count(pl1) == 0) {
 141                         fprintf(stderr, "Unknown player '%s'\n", pl1);
 142                         exit(1);
 143                 }
 144                 if (player_map.count(pl2) == 0) {
 145                         fprintf(stderr, "Unknown player '%s'\n", pl2);
 146                         exit(1);
 147                 }
 148
 149                 scores[player_map[pl1]][player_map[pl2]] = score1;
 150                 scores[player_map[pl2]][player_map[pl1]] = score2;
 151                 has_scores[player_map[pl1]][player_map[pl2]] = true;
 152                 has_scores[player_map[pl2]][player_map[pl1]] = true;
 153         }
 154
 155         int placements[MAX_PLAYERS][MAX_PLAYERS];
 156         for (int i = 0; i < num_players; ++i) {
 157                 for (int j = 0; j < num_players; ++j) {
 158                         placements[i][j] = 0;
 159                 }
 160         }
 161
 162         for (int i = 0; i < trials; ++i) {
 163                 // draw true strength for all players
 164                 Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> drawn_normals(num_players);
 165                 for (int p = 0; p < num_players; ++p) {
 166                         drawn_normals(p) = draw_gaussian(0.0f, 1.0f);
 167                 }
 168                 Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> drawn_ratings = ratings_cholesky * drawn_normals + ratings;
 169
 170                 // draw the missing matches
 171                 for (int pl1 = 0; pl1 < num_players; ++pl1) {
 172                         for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) {
 173                                 if (has_scores[pl1][pl2]) {
 174                                         continue;
 175                                 }
 176
 177                                 float mu = drawn_ratings(pl1) - drawn_ratings(pl2);
 178
 179                                 int score = lrintf(draw_gaussian(mu, match_stddev));
 180                                 scores[pl1][pl2] = score;
 181                                 scores[pl2][pl1] = -score;
 182                         }
 183                 }
 184
 185                 // sum up the points and margin for each player
 186                 player stats[MAX_PLAYERS];
 187                 for (int pl1 = 0; pl1 < num_players; ++pl1) {
 188                         stats[pl1].player_index = pl1;
 189                         stats[pl1].points = 0;
 190                         stats[pl1].margin = 0;
 191                         for (int pl2 = 0; pl2 < num_players; ++pl2) {
 192                                 if (pl1 == pl2) {
 193                                         continue;
 194                                 }
 195                                 stats[pl1].margin += scores[pl1][pl2];
 196                                 stats[pl1].margin -= scores[pl2][pl1];
 197                                 if (scores[pl1][pl2] > scores[pl2][pl1]) {
 198                                         stats[pl1].points += 2;
 199                                 } else if (scores[pl1][pl2] == scores[pl2][pl1]) {
 200                                         stats[pl1].points++;
 201                                 }
 202                         }
 203                 }
 204
 205                 // order by points and then margin
 206                 sort(stats, stats + num_players, highest_ranking());
 207                 for (int j = 0; j < num_players; ++j) {
 208                         ++placements[stats[j].player_index][j];
 209                 }
 210         }
 211
 212         for (int i = 0; i < num_players; ++i) {
 213                 printf("%-15s", players[i].c_str());
 214                 for (int j = 0; j < num_players; ++j) {
 215                         printf(" %5d", placements[i][j]);
 216                 }
 217                 printf("\n");
 218         }
 219 }