From: Steinar H. Gunderson <sgunderson@bigfoot.com>
Date: Tue, 20 Mar 2012 20:57:06 +0000 (+0100)
Subject: Use covariance matrix under Monte Carlo simulation, to draw better strengths.
X-Git-Url: https://git.sesse.net/?p=wloh;a=commitdiff_plain;h=707f9416afa19e2c92a0bd94d34fb4d5d1ba3f0e

Use covariance matrix under Monte Carlo simulation, to draw better strengths.
---

diff --git a/mcwordfeud.cpp b/mcwordfeud.cpp
index ce9dc5f..28a2a44 100644
--- a/mcwordfeud.cpp
+++ b/mcwordfeud.cpp
@@ -7,10 +7,13 @@
 #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
 
@@ -86,8 +89,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,8 +100,8 @@ 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);
@@ -107,15 +109,25 @@ int main(int argc, char **argv)
 		if (ret < 2) {
 			rating = 1500.0f;
 		}
-		if (ret < 3) {
-			rating_stddev = 0.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 +161,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,7 +174,7 @@ 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;
diff --git a/www/index.pl b/www/index.pl
index c7cfa40..580ad65 100755
--- a/www/index.pl
+++ b/www/index.pl
@@ -41,7 +41,7 @@ sub color {
 }
 
 sub make_table {
-	my ($lowest_division, $used_ratings, $used_ratings_stddev) = @_;
+	my ($lowest_division, $used_ratings, $used_cov) = @_;
 
 	print <<"EOF";
 
@@ -61,8 +61,19 @@ EOF
 
 	for my $id (keys %players) {
 		my $rating = $used_ratings->{$id} // 1500.0;
-		my $rating_stddev = $used_ratings_stddev->{$id} // $parms{-3};
-		printf MCCALC "%s %f %f\n", $id, $rating, $rating_stddev;
+		printf MCCALC "%s %f\n", $id, $rating;
+	}
+
+	# covariance matrix
+	for my $id1 (keys %players) {
+		for my $id2 (keys %players) {
+			if ($id1 == $id2) {
+				printf MCCALC "%f ", ($used_cov->{$id1}{$id2} // $parms{-3});
+			} else {
+				printf MCCALC "%f ", ($used_cov->{$id1}{$id2} // 0.0);
+			}
+		}
+		printf MCCALC "\n";
 	}
 
 	for my $match (@matches) {
@@ -263,6 +274,16 @@ while (my $ref = $q->fetchrow_hashref) {
 }
 $q->finish;
 
+# Pick up covariance matrix
+my $player_sql = '{' . join(',', keys %players ) . '}';
+my $q = $dbh->prepare('SELECT * FROM covariance WHERE player1=ANY(?::smallint[]) AND player2=ANY(?::smallint[])', { pg_prepare_now => 0 });
+$q->execute($player_sql, $player_sql);
+
+my $cov = {};
+while (my $ref = $q->fetchrow_hashref) {
+	$cov->{$ref->{'player1'}}{$ref->{'player2'}} = $ref->{'cov'};
+}
+
 my $lowest_division = ($division == $max_division);
 make_table($lowest_division, {}, {});
 
@@ -271,9 +292,9 @@ print <<"EOF";
       se <a href="/rating">ratingsiden</a>.</p>
 EOF
 
-make_table($lowest_division, \%ratings, \%ratings_stddev);
+make_table($lowest_division, \%ratings, $cov);
 
-print << "EOF";
+print <<"EOF";
   </body>
 </html>
 EOF