1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <stdexcept>
#include <vector>
#include "NameGame.h"
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();
}
namespace tp {
NameGame::NameGame(int group_size, int cm_size, int memory) :
gsize(group_size), cmsize(cm_size), memlen(memory),
rng(std::random_device{}()), dist(0, group_size - 1),
graph(group_size, group_size * group_size)
{
if (group_size <= 0)
throw std::invalid_argument("NameGame invalid group_size");
if (cm_size < 0)
throw std::invalid_argument("NameGame invalid cm_size");
if (cm_size > group_size)
throw std::invalid_argument("NameGame cm_size > group_size");
if (memory <= 0)
throw std::invalid_argument("NameGame memory <= 0");
initGraph();
}
void NameGame::setCMsize(int cm_size) {
if (cm_size <= 0 || cm_size > gsize)
throw std::invalid_argument("NameGame::setCMsize invalid cm_size");
cmsize = cm_size;
}
void NameGame::initGraph() {
// Generate complete graph.
for (int i = 0; i < gsize; ++i) graph.AddNode(i, {false, {}});
for (int i = 0; i < gsize; ++i)
for (int j = 0; j < gsize; ++j)
if (i != j) graph.AddEdge(i, j);
initMemory();
}
void NameGame::initMemory() {
std::vector<int> ids(gsize);
std::iota(ids.begin(), ids.end(), 0);
// Set committed minority.
for (int i = 0; i < cmsize; ++i) {
int r = dist(rng) % ids.size();
int rId = ids[r];
auto& rDat = graph.GetNDat(rId);
rDat.Val1 = true;
rDat.Val2.Clr();
rDat.Val2.Add(1);
ids.erase(ids.begin() + r);
}
// Establish norm (fully memory of strategy 1) for remaining nodes.
for (int id : ids) {
auto& d = graph.GetNDat(id);
d.Val1 = false;
d.Val2.Clr();
while (d.Val2.Len() < memlen) d.Val2.Add(-1);
}
}
int NameGame::run(int rounds) {
if (rounds < 0) throw std::invalid_argument("NameGame::run rounds < 0");
size_t srlen = strategy_record.size();
for (int i = 0; i < rounds; ++i) runRound(i);
// Track all plays and plays by non-CM.
// Report average plays.
float avg = 0;
for (size_t i = srlen; i < strategy_record.size(); ++i) {
avg += strategy_record[i].strategy;
}
avg /= strategy_record.size() - srlen;
// std::cout << avg << std::endl;
int plays = 0;
for (int i = strategy_record.size() - gsize; i < strategy_record.size(); ++i) {
if (!strategy_record[i].committed && strategy_record[i].strategy == 1)
++plays;
}
return plays;
}
void NameGame::runRound(int r) {
bool verbose_flag = false;
// 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 strategy = best_move(speaker.GetId());
if (verbose_flag) {
char s_committed = speaker().Val1 ? 'C' : 'U',
h_committed = hearer().Val1 ? 'C' : 'U';
char oldfill = std::cout.fill('0');
std::cout << "S" << std::setw(2) << speaker.GetId()
<< '(' << s_committed << ") - H" << std::setw(2) << hearer.GetId()
<< '(' << h_committed << "): " << strategy << std::endl;
std::cout.fill(oldfill);
}
// Hearer updates memory.
update_memory(hearer.GetId(), strategy);
// Strategy is recorded.
strategy_record.push_back({r, speaker.GetId(), speaker().Val1, strategy});
}
int NameGame::best_move(int nId) const {
const auto& mem = graph.GetNDat(nId).Val2;
std::map<int, int> votes;
for (const auto& v : mem) {
if (votes.count(v)) votes[v] += 1;
else votes[v] = 1;
}
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;
}
void NameGame::update_memory(int nId, int strategy) {
auto& d = graph.GetNDat(nId);
if (!d.Val1) {
d.Val2.Ins(0, strategy);
d.Val2.Trunc(memlen);
}
}
void NameGame::clearRecord() {
strategy_record.clear();
}
void NameGame::writeRecord(const char* fname, bool append) {
auto mode = std::ios::in | std::ios::out;
if (append) mode |= std::ios::ate;
else mode |= std::ios::trunc;
std::fstream f(fname, mode);
if (!append || f.tellp() == 0) {
f << "group_size,cm_size,memlen,round,speaker,committed,strategy\n";
}
for (const auto& r : strategy_record) {
f << gsize << ',' << cmsize << ',' << memlen << ',' << r.round << ','
<< r.speaker << ',' << r.committed << ',' << r.strategy << '\n';
}
}
} // namespace tp
|
