Add a Monte Carlo simulator.

[wloh] / mcwordfeud.cpp

diff --git a/mcwordfeud.cpp b/mcwordfeud.cpp
new file mode 100644 (file)
index 0000000..7470af3
--- /dev/null
+++ b/mcwordfeud.cpp
@@ -0,0 +1,188 @@
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <map>
+#include <vector>
+#include <string>
+#include <algorithm>
+
+#include "ziggurat.hpp"
+
+using namespace std;
+
+#define MAX_PLAYERS 16
+
+struct player {
+       int player_index;
+       int points, margin;
+};
+struct highest_ranking {
+public:
+       bool operator() (const player &a, const player &b) const {
+               if (a.points != b.points) {
+                       return a.points > b.points;
+               }
+               return a.margin > b.margin;
+       }
+};
+
+#if 0
+float draw_unit()
+{
+       return rand() * (1.0f / RAND_MAX);
+}
+
+// FIXME: replace rejection method with a better method! this one can only ever go to [-5z, +5z]
+// and is very slow.
+float draw_gaussian(float stddev)
+{
+       for ( ;; ) {
+               float z = draw_unit() * 10.0f - 5.0f;
+               float y = draw_unit();
+               if (y < exp(-z*z)) {
+                       return z * stddev;
+               }
+       }       
+}
+#else
+float draw_gaussian(float mu, float stddev)
+{
+       static bool inited = false;
+       static long unsigned seed = 123456789;
+       int kn[128];
+       float fn[128], wn[128];
+       if (!inited) {
+               r4_nor_setup(kn, fn, wn);
+               inited = true;
+       }
+
+       return r4_nor(&seed, kn, fn, wn) * stddev + mu;
+}
+#endif
+
+int main(int argc, char **argv)
+{
+       int trials = atoi(argv[1]);
+
+       int num_players;
+       if (scanf("%d", &num_players) != 1) {
+               fprintf(stderr, "Could't read number of players\n");
+               exit(1);
+       }
+
+       if (num_players > MAX_PLAYERS) {
+               fprintf(stderr, "Max %d players supported\n");
+               exit(1);
+       }
+
+       vector<string> players;
+       map<string, int> player_map;
+       float ratings[MAX_PLAYERS];
+       bool has_scores[MAX_PLAYERS][MAX_PLAYERS];
+       for (int pl1 = 0; pl1 < num_players; ++pl1) {
+               for (int pl2 = 0; pl2 < num_players; ++pl2) {
+                       has_scores[pl1][pl2] = false;
+               }
+       }
+
+       int scores[MAX_PLAYERS][MAX_PLAYERS];
+       for (int i = 0; i < num_players; ++i) {
+               char buf[256];
+               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;
+               }
+
+               players.push_back(buf);
+               player_map[buf] = i;
+               ratings[i] = rating;
+       }
+
+       for ( ;; ) {
+               char pl1[256], pl2[256];
+               int score1, score2;
+
+               if (scanf("%s %s %d %d", pl1, pl2, &score1, &score2) != 4) {
+                       break;
+               }
+
+               if (player_map.count(pl1) == 0) {
+                       fprintf(stderr, "Unknown player '%s'\n", pl1);
+                       exit(1);
+               }
+               if (player_map.count(pl2) == 0) {
+                       fprintf(stderr, "Unknown player '%s'\n", pl2);
+                       exit(1);
+               }
+
+               scores[player_map[pl1]][player_map[pl2]] = score1;
+               scores[player_map[pl2]][player_map[pl1]] = score2;
+               has_scores[player_map[pl1]][player_map[pl2]] = true;
+               has_scores[player_map[pl2]][player_map[pl1]] = true;
+       }
+
+       int placements[MAX_PLAYERS][MAX_PLAYERS];
+       for (int i = 0; i < num_players; ++i) {
+               for (int j = 0; j < num_players; ++j) {
+                       placements[i][j] = 0;
+               }
+       }
+
+       for (int i = 0; i < trials; ++i) {
+               // draw the missing 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 = ratings[pl1] - ratings[pl2];
+                               
+                               int score = lrintf(draw_gaussian(mu, 82.9f));
+                               scores[pl1][pl2] = score;
+                               scores[pl2][pl1] = -score;
+                       }
+               }
+
+               // sum up the points and margin for each player
+               player stats[MAX_PLAYERS];
+               for (int pl1 = 0; pl1 < num_players; ++pl1) {
+                       stats[pl1].player_index = pl1;
+                       stats[pl1].points = 0;
+                       stats[pl1].margin = 0;
+                       for (int pl2 = 0; pl2 < num_players; ++pl2) {
+                               if (pl1 == pl2) {
+                                       continue;
+                               }
+                               stats[pl1].margin += scores[pl1][pl2];
+                               stats[pl1].margin -= scores[pl2][pl1];
+                               if (scores[pl1][pl2] > scores[pl2][pl1]) {
+                                       stats[pl1].points += 2;
+                               } else if (scores[pl1][pl2] == scores[pl2][pl1]) {
+                                       stats[pl1].points++;
+                               }
+                       }
+               }
+
+               // 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];
+               }
+       }
+
+       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");
+       }
+}