From 2ce26bc034e52454b894a17c9665fb562c1559e4 Mon Sep 17 00:00:00 2001
From: "Steinar H. Gunderson" <sgunderson@bigfoot.com>
Date: Sun, 25 Mar 2012 15:58:32 +0200
Subject: [PATCH] Add a function to the MC simulator to find the most likely
 set of results resulting in a given outcome.

---
 mcwordfeud.cpp | 79 +++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 72 insertions(+), 7 deletions(-)

diff --git a/mcwordfeud.cpp b/mcwordfeud.cpp
index 63b98e1..3b55f01 100644
--- a/mcwordfeud.cpp
+++ b/mcwordfeud.cpp
@@ -17,6 +17,11 @@ using namespace Eigen;
 
 #define MAX_PLAYERS 16
 
+enum OutputMode {
+	PROBABILITY_MATRIX = 0,
+	MOST_LIKELY_MATCHING = 1,
+};
+
 float match_stddev = 70.0f;
 
 struct player {
@@ -70,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");
@@ -204,16 +223,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] - 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]);
+			}
 		}
-		printf("\n");
 	}
 }
-- 
2.39.2