add code for onr round of name game

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

1 files changed, 78 insertions, 14 deletions

diff --git a/src/main.cc b/src/main.cc
index 467c1ad..0f391eb 100644
--- a/src/main.cc
+++ b/src/main.cc
@@ -1,12 +1,17 @@
 #include <cassert>
 #include <iostream>
+#include <map>
 #include <random>
 
 #include <Snap.h>
 
 void name_game(int group_size, int cmsize);
 
+constexpr int memory_length = 12;
+std::mt19937 rng(std::random_device{}());
+
 int main(int argc, char* argv[]) {
+        rng.seed(std::random_device{}());
         int group_size = 100;
         for (int cmperc = 18; cmperc < 28; cmperc += 2) {
                 int cmsize = group_size * cmperc / 100;
@@ -16,40 +21,99 @@ int main(int argc, char* argv[]) {
         return 0;
 }
 
-// SNAP random chooses node, r is used to select one edge
-template <typename TD>
-typename TNodeNet<TD>::TEdgeI random_edge(const TNodeNet<TD>& g, int r) {
-        auto ni = g.GetRndNI();
-        return g.GetEI(ni.GetId(), ni.GetNbrNId(r % ni.GetDeg()));
+using ngData = TPair<TBool, TIntV>;
+
+template<typename TVal, typename TSizeTy>
+auto begin(const TVec<TVal, TSizeTy>& v) -> decltype(v.BegI()) {
+        return v.BegI();
+}
+
+template<typename TVal, typename TSizeTy>
+auto end(const TVec<TVal, TSizeTy>& v) -> decltype(v.EndI()) {
+        return v.EndI();
+}
+
+int best_move(const ngData& d) {
+        const auto& mem = d.Val2;
+        std::map<int, int> votes;
+        for (const auto& v : mem) {
+                if (votes.count(v)) votes[v] += 1;
+                else votes[v] = 1;
+        }
+        std::map<int, float> fractions;
+        for (auto kv : votes) fractions[kv.first] = kv.second * 1./mem.Len();
+        // Simple majority vote:
+        for (auto kv : fractions)
+                if (kv.second >= 1./mem.Len()) return kv.first;
+        return 0;
+}
+
+void update_memory(ngData& d, int move) {
+        if (!d.Val1) {
+                auto& mem = d.Val2;
+                mem.Ins(0, move);
+                mem.Trunc(memory_length);
+        }
+}
+
+void name_game_round(TNodeNet<ngData>& graph) {
+        std::uniform_int_distribution<> dist(0, graph.GetNodes());
+        // Select random speaker and hearer.
+        auto speaker = graph.GetNI(dist(rng));
+        auto hearer = graph.GetNI(
+                speaker.GetNbrNId(dist(rng) % speaker.GetDeg())
+        );
+
+        // Speaker chooses best strategy.
+        int s_strategy = best_move(speaker.GetDat());
+        std::cout << "speaker (" << speaker.GetId() << " "
+                << std::boolalpha << speaker().Val1
+                << ") chose: " << s_strategy << std::endl;
+
+        // Listener updates memory.
+        update_memory(hearer.GetDat(), s_strategy);
+
+        // Listener chooses best strategy.
+        int h_strategy = best_move(hearer.GetDat());
+        std::cout << "hearer (" << hearer.GetId() << " "
+                << std::boolalpha << hearer().Val1
+                << ") chose: " << h_strategy << std::endl;
+
+        // Speaker updates memory.
+        update_memory(speaker.GetDat(), s_strategy);
 }
 
 void name_game(int group_size, int cmsize) {
         assert(cmsize > 0 && group_size > 0);
         assert(cmsize < group_size);
-        TNodeNet<TPair<TBool, TIntV>> graph;
+        TNodeNet<ngData> graph;
         // Generate complete graph.
         for (int i = 0; i < group_size; ++i) graph.AddNode(i, {false, {}});
         for (int i = 0; i < group_size; ++i)
                 for (int j = 0; j < group_size; ++j)
                         if (i != j) graph.AddEdge(i, j);
         // Set committed minority.
-        std::mt19937 rnd(std::random_device{}());
-        std::uniform_int_distribution dist(0, group_size - 1);
+        std::uniform_int_distribution<> dist(0, group_size - 1);
         for (int i = 0; i < cmsize;) {
-                int r = dist(rnd);
+                int r = dist(rng);
                 if (!graph.GetNDat(r).Val1) {
                         graph.GetNDat(r).Val1 = true;
+                        auto& mem = graph.GetNDat(r).Val2;
+                        mem.Clr();
+                        mem.Add(2);
                         ++i;
                 }
         }
+        // Establish norm (fully memory of strategy 1)
+        for (int i = 0; i < group_size; ++i) {
+                auto& d = graph.GetNDat(i);
+                if (!d.Val1) while (d.Val2.Len() < memory_length) d.Val2.Add(1);
+        }
         std::cout << "Nodes: " << graph.GetNodes()
                 << " Edges: " << graph.GetEdges() << std::endl;
 
-        // Select random edge.
-        // Speaker chooses best strategy.
-        // Listener updates memory.
-        // Listener chooses best strategy.
-        // Speaker updates memory.
+        name_game_round(graph);
+
         // Track all plays and plays by non-CM.
         // Report average plays.
 }