X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=mcwordfeud.cpp;h=049a2196b998b2c53d38c296733f1d243493e89a;hb=fde909c294de9806dd6337f5acb0ed87c41557c6;hp=b48936d4a36c43a606fe57a95061a6e486bd9f89;hpb=d963a5d96352ece425d76233351d3f9c879dbf30;p=wloh diff --git a/mcwordfeud.cpp b/mcwordfeud.cpp index b48936d..049a219 100644 --- a/mcwordfeud.cpp +++ b/mcwordfeud.cpp @@ -7,14 +7,22 @@ #include #include #include +#include +#include #include "ziggurat.hpp" using namespace std; +using namespace Eigen; #define MAX_PLAYERS 16 -float match_variance = 70.0f * 70.0f; +enum OutputMode { + PROBABILITY_MATRIX = 0, + MOST_LIKELY_MATCHING = 1, +}; + +float match_stddev = 70.0f; struct player { int player_index; @@ -67,15 +75,26 @@ float draw_gaussian(float mu, float stddev) int main(int argc, char **argv) { int trials = atoi(argv[1]); - float match_stddev; + OutputMode output_mode; + int match_player_num = -1, match_position = -1; + if (argc >= 3) { + match_player_num = atoi(argv[2]); + match_position = atoi(argv[3]); + output_mode = MOST_LIKELY_MATCHING; + } else { + output_mode = PROBABILITY_MATRIX; + } + + // For most likely matching. + bool has_mlm = false; + double mlm_likelihood = 0.0f; + int mlm_scores[MAX_PLAYERS][MAX_PLAYERS]; if (scanf("%f", &match_stddev) != 1) { fprintf(stderr, "Could't read match stddev\n"); exit(1); } - match_variance = match_stddev * match_stddev; - int num_players; if (scanf("%d", &num_players) != 1) { fprintf(stderr, "Could't read number of players\n"); @@ -89,8 +108,7 @@ int main(int argc, char **argv) vector players; map player_map; - float ratings[MAX_PLAYERS]; - float ratings_variance[MAX_PLAYERS]; + Matrix ratings(num_players); bool has_scores[MAX_PLAYERS][MAX_PLAYERS]; for (int pl1 = 0; pl1 < num_players; ++pl1) { for (int pl2 = 0; pl2 < num_players; ++pl2) { @@ -101,24 +119,34 @@ int main(int argc, char **argv) int scores[MAX_PLAYERS][MAX_PLAYERS]; for (int i = 0; i < num_players; ++i) { char buf[256]; - float rating, rating_stddev; - int ret = scanf("%s %f %f", buf, &rating, &rating_stddev); + float rating; + int ret = scanf("%s %f", buf, &rating); if (ret < 1) { fprintf(stderr, "Couldn't read player %d\n", i); exit(1); } if (ret < 2) { - rating = 1500.0f; - } - if (ret < 3) { - rating_stddev = 0.0f; + rating = 500.0f; } players.push_back(buf); player_map[buf] = i; - ratings[i] = rating; - ratings_variance[i] = rating_stddev * rating_stddev; + ratings(i) = rating; + } + + Matrix ratings_cov(num_players, num_players); + for (int i = 0; i < num_players; ++i) { + for (int j = 0; j < num_players; ++j) { + float f; + if (scanf("%f", &f) != 1) { + fprintf(stderr, "Couldn't read covariance matrix element (%d,%d)\n", i, j); + exit(1); + } + ratings_cov(i, j) = f; + } } + Matrix ratings_cholesky = + ratings_cov.llt().matrixLLT(); for ( ;; ) { char pl1[256], pl2[256]; @@ -151,6 +179,13 @@ int main(int argc, char **argv) } for (int i = 0; i < trials; ++i) { + // draw true strength for all players + Matrix drawn_normals(num_players); + for (int p = 0; p < num_players; ++p) { + drawn_normals(p) = draw_gaussian(0.0f, 1.0f); + } + Matrix drawn_ratings = ratings_cholesky * drawn_normals + ratings; + // draw the missing matches for (int pl1 = 0; pl1 < num_players; ++pl1) { for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) { @@ -158,12 +193,16 @@ int main(int argc, char **argv) continue; } - float mu = ratings[pl1] - ratings[pl2]; - float stddev = sqrt(match_variance + ratings_variance[pl1] + ratings_variance[pl2]); + float mu = drawn_ratings(pl1) - drawn_ratings(pl2); - int score = lrintf(draw_gaussian(mu, stddev)); - scores[pl1][pl2] = score; - scores[pl2][pl1] = -score; + int score = lrintf(draw_gaussian(mu, match_stddev)); + if (score >= 0) { + scores[pl1][pl2] = score; + scores[pl2][pl1] = 0; + } else { + scores[pl1][pl2] = 0; + scores[pl2][pl1] = -score; + } } } @@ -189,16 +228,62 @@ int main(int argc, char **argv) // order by points and then margin sort(stats, stats + num_players, highest_ranking()); - for (int j = 0; j < num_players; ++j) { - ++placements[stats[j].player_index][j]; + + if (output_mode == PROBABILITY_MATRIX) { + for (int j = 0; j < num_players; ++j) { + ++placements[stats[j].player_index][j]; + } + } + if (output_mode == MOST_LIKELY_MATCHING) { + if (stats[match_position].player_index != match_player_num) { + continue; + } + + // compute the log-likelihood of this situation (ignoring the constant terms) + double llh = 0.0f; + + // strength of all players (ignore the constant terms) + for (int p = 0; p < num_players; ++p) { + llh -= drawn_normals(p) * drawn_normals(p) * 0.5f; + } + + // all the matches + for (int pl1 = 0; pl1 < num_players; ++pl1) { + for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) { + if (has_scores[pl1][pl2]) { + continue; + } + float mu = drawn_ratings(pl1) - drawn_ratings(pl2); + float z = (scores[pl1][pl2] - scores[pl2][pl1] - mu) / match_stddev; + llh -= z * z * 0.5f; + } + } + + if (!has_mlm || llh > mlm_likelihood) { + has_mlm = true; + mlm_likelihood = llh; + memcpy(mlm_scores, scores, sizeof(mlm_scores)); + } } } - for (int i = 0; i < num_players; ++i) { - printf("%-15s", players[i].c_str()); - for (int j = 0; j < num_players; ++j) { - printf(" %5d", placements[i][j]); + if (output_mode == PROBABILITY_MATRIX) { + for (int i = 0; i < num_players; ++i) { + printf("%-15s", players[i].c_str()); + for (int j = 0; j < num_players; ++j) { + printf(" %5d", placements[i][j]); + } + printf("\n"); + } + } + if (output_mode == MOST_LIKELY_MATCHING && has_mlm) { + for (int pl1 = 0; pl1 < num_players; ++pl1) { + for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) { + if (has_scores[pl1][pl2]) { + continue; + } + printf("%s %s %d\n", players[pl1].c_str(), players[pl2].c_str(), mlm_scores[pl1][pl2] - mlm_scores[pl2][pl1]); + } } - printf("\n"); } }