#include <vector>
#include <string>
#include <algorithm>
+#include <Eigen/Cholesky>
+#include <Eigen/Dense>
#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;
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");
vector<string> players;
map<string, int> player_map;
- float ratings[MAX_PLAYERS];
- float ratings_variance[MAX_PLAYERS];
+ Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> 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) {
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<float, Dynamic, Dynamic, 0, MAX_PLAYERS, MAX_PLAYERS> 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<float, Dynamic, Dynamic, 0, MAX_PLAYERS, MAX_PLAYERS> ratings_cholesky =
+ ratings_cov.llt().matrixLLT();
for ( ;; ) {
char pl1[256], pl2[256];
}
for (int i = 0; i < trials; ++i) {
+ // draw true strength for all players
+ Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> drawn_normals(num_players);
+ for (int p = 0; p < num_players; ++p) {
+ drawn_normals(p) = draw_gaussian(0.0f, 1.0f);
+ }
+ Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> 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) {
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;
+ }
}
}
// 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");
}
}
projects / wloh / blobdiff