add confirmation bias and exp weights

- src/NameGame.cc: remove std::map best_move implementation.
- add explicit confirmation bias macro.
- add default random tie-breaker.
- src/many-async.cc: reseed for each committed minority value because
  entropy may be exhausted.

Signed-off-by: Aiden Woodruff <woodra@rpi.edu>

3 files changed, 33 insertions, 29 deletions

diff --git a/src/NameGame.cc b/src/NameGame.cc
index 7561946..2a77db5 100644
--- a/src/NameGame.cc
+++ b/src/NameGame.cc
@@ -88,6 +88,10 @@ NameGame::NameGame(int group_size, int cm_size, int memory) :
         initGraph();
 }
 
+void NameGame::seed(int s) {
+        rng.seed(s);
+}
+
 void NameGame::setCMsize(int cm_size) {
         if (cm_size <= 0 || cm_size > gsize)
                 throw std::invalid_argument("NameGame::setCMsize invalid cm_size");
@@ -191,12 +195,12 @@ void NameGame::runRound(int r) {
         strategy_record.push_back({r, speaker.GetId(), speaker().Val1, strategy});
 }
 
-#undef USE_EXP_WEIGHT
+#define USE_EXP_WEIGHT
 #ifdef USE_EXP_WEIGHT
 float weight(int i) {
         static std::vector<float> weight_table;
         if (i < 0) throw std::invalid_argument("bad weight input");
-        while (i < weight_table.size()) {
+        while (i >= weight_table.size()) {
                 float x = weight_table.size();
                 weight_table.push_back(std::exp(-x));
         }
@@ -204,37 +208,33 @@ float weight(int i) {
 }
 #endif
 
-int NameGame::best_move(int nId) const {
+#undef TP_BESTMOVE_CONFBIAS
+int NameGame::best_move(int nId) {
         const auto& mem = graph.GetNDat(nId).Val2;
-#ifdef TP_BESTMOVE_STATIC
+#ifdef USE_EXP_WEIGHT
+        float votes[2] = {0.f, 0.f};
+        int i = 0;
+        for (const auto& strategy : mem) {
+                if (strategy == -1) votes[0] += weight(i);
+                else votes[1] += weight(i);
+                ++i;
+        }
+#else
         int votes[2] = {0, 0};
         for (const auto& strategy : mem) {
                 if (strategy == -1) votes[0]++;
                 else votes[1]++;
         }
-        return votes[0] > votes[1] ? -1 : 1;
-#else
-#ifdef USE_EXP_WEIGHT
-        std::map<int, float> votes;
-        for (int i = 0; i < mem.Len(); ++i) {
-                int strategy = mem[i];
-                if (votes.count(strategy)) votes[strategy] += weight(i);
-                else votes[strategy] = weight(i);
-#else
-        std::map<int, int> votes;
-        for (const auto& strategy : mem) {
-                if (votes.count(strategy)) votes[strategy] += 1;
-                else votes[strategy] = 1;
 #endif
-        }
-        if (votes.empty()) return 0;
-        int best = std::max_element(votes.begin(), votes.end(),
-                [](const auto& v1, const auto& v2) {
-                        return v1.second < v2.second;
-                }
-        )->first;
-        return best;
+        if (votes[0] == votes[1]) {
+#ifdef TP_BESTMOVE_CONFBIAS
+                return -1;
+#else
+                static std::bernoulli_distribution tie_dist;
+                return tie_dist(rng) ? -1 : 1;
 #endif
+        } else return votes[0] > votes[1] ? -1 : 1;
+        return votes[0] >= votes[1] ? -1 : 1;
 }
 
 void NameGame::update_memory(int nId, int strategy) {
diff --git a/src/NameGame.h b/src/NameGame.h
index 21a58b8..0c0552e 100644
--- a/src/NameGame.h
+++ b/src/NameGame.h
@@ -15,6 +15,7 @@ public:
 
         void setCMsize(int cm_size);
 
+        void seed(int s);
         void initGraph();
         void initMemory();
         void clearRecord();
@@ -26,7 +27,7 @@ public:
         void writeRecord(const char* fname, bool append = false);
 
 protected:
-        int best_move(int nId) const;
+        int best_move(int nId);
         void update_memory(int nId, int strategy);
 
 private:
diff --git a/src/many-async.cc b/src/many-async.cc
index 9df475b..557c8ae 100644
--- a/src/many-async.cc
+++ b/src/many-async.cc
@@ -5,14 +5,16 @@
 
 #include "NameGame.h"
 
-constexpr int group_size = 1000, T = 100;
-constexpr int cmsize_min = 200, cmsize_max = 600;
+constexpr int group_size = 1000, T = 200;
+constexpr int cmsize_min = 200, cmsize_max = 400;
 constexpr int trials = 100;
 constexpr int workers = 6;
+constexpr const char* csv_file = "many-async-T200-exp.csv";
 
 using RunVec = std::vector<std::pair<int, int>>;
 
 RunVec run_trials(int cmsize_start, int cmsize_end) {
+        std::random_device seeder;
         tp::NameGame namegame(group_size, 0, 12);
         RunVec runs;
         for (int i = cmsize_start; i < cmsize_end; ++i) {
@@ -23,6 +25,7 @@ RunVec run_trials(int cmsize_start, int cmsize_end) {
                         int a = namegame.run(group_size * T);
                         runs.push_back({i, a});
                 }
+                namegame.seed(seeder());
                 std::cout << "finished cmsize " << i << std::endl;
         }
         return runs;
@@ -47,7 +50,7 @@ int main(int argc, char* argv[]) {
                 RunVec v = futs[i].get();
                 all_runs.insert(all_runs.end(), v.begin(), v.end());
         }
-        std::ofstream f("many-async.csv");
+        std::ofstream f(csv_file);
         if (!f) {
                 std::cerr << "ERROR: opening many-async.csv" << std::endl;
                 return 1;