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