X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=mcwordfeud.cpp;h=049a2196b998b2c53d38c296733f1d243493e89a;hb=79ca58ab629b09e8fe59415578d2ee1ea5cb2079;hp=ce9dc5fd482058895b2577817d1282d51e955e6f;hpb=d76a4688b44cd0b1fcef71ea52d5a70bc9df3d00;p=wloh

diff --git a/mcwordfeud.cpp b/mcwordfeud.cpp
index ce9dc5f..049a219 100644
--- a/mcwordfeud.cpp
+++ b/mcwordfeud.cpp
@@ -7,13 +7,21 @@
 #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
 
+enum OutputMode {
+	PROBABILITY_MATRIX = 0,
+	MOST_LIKELY_MATCHING = 1,
+};
+
 float match_stddev = 70.0f;
 
 struct player {
@@ -67,6 +75,20 @@ float draw_gaussian(float mu, float stddev)
 int main(int argc, char **argv)
 {
 	int trials = atoi(argv[1]);
+	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");
@@ -86,8 +108,7 @@ int main(int argc, char **argv)
 
 	vector<string> players;
 	map<string, int> player_map;
-	float ratings[MAX_PLAYERS];
-	float ratings_stddev[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) {
@@ -98,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_stddev[i] = 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];
@@ -149,10 +180,11 @@ int main(int argc, char **argv)
 
 	for (int i = 0; i < trials; ++i) {
 		// draw true strength for all players
-		float drawn_ratings[MAX_PLAYERS];
+		Matrix<float, Dynamic, 1, 0, MAX_PLAYERS, 1> drawn_normals(num_players);
 		for (int p = 0; p < num_players; ++p) {
-			drawn_ratings[p] = draw_gaussian(ratings[p], ratings_stddev[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) {
@@ -161,11 +193,16 @@ int main(int argc, char **argv)
 					continue;
 				}
 
-				float mu = drawn_ratings[pl1] - drawn_ratings[pl2];
+				float mu = drawn_ratings(pl1) - drawn_ratings(pl2);
 				
 				int score = lrintf(draw_gaussian(mu, match_stddev));
-				scores[pl1][pl2] = score;
-				scores[pl2][pl1] = -score;
+				if (score >= 0) {
+					scores[pl1][pl2] = score;
+					scores[pl2][pl1] = 0;
+				} else {
+					scores[pl1][pl2] = 0;
+					scores[pl2][pl1] = -score;
+				}
 			}
 		}
 
@@ -191,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");
 	}
 }