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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
#include <cmath>
#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});
}
#undef 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()) {
float x = weight_table.size();
weight_table.push_back(std::exp(-x));
}
return weight_table[i];
}
#endif
int NameGame::best_move(int nId) const {
const auto& mem = graph.GetNDat(nId).Val2;
#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;
}
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
|
