path: root/src/NameGame.cc

#include <cmath>
#include <fstream>
#include <iomanip>
#include <iostream>
#define TP_BESTMOVE_STATIC
#ifndef TP_BESTMOVE_STATIC
#include <map>
#endif
#include <stdexcept>
#include <vector>

#include "NameGame.h"

#ifdef TP_MEMLIST
template<typename TVal>
class TLstIter {
public:
	TLstIter(typename TLst<TVal>::PLstNd nd_) : nd(nd_) {}
	const TVal& operator*() const {
		return nd->GetVal();
	}
	TVal& operator*() {
		return nd->GetVal();
	}
	TLstIter<TVal>& operator++() {
		nd = nd->Next();
		return *this;
	}
	bool operator==(const TLstIter<TVal>& rhs) const {
		return nd == rhs.nd;
	}
private:
	typename TLst<TVal>::PLstNd nd;
};

template<typename TVal>
TLstIter<TVal> begin(const TLst<TVal>& l) {
	return TLstIter<TVal>(l.First());
}

template<typename TVal>
TLstIter<TVal> end(const TLst<TVal>& l) {
	return TLstIter<TVal>(nullptr);
}

template<typename TVal>
TLst<TVal>::TLst(const TLst<TVal>& l) : TLst() {
	for (const auto& val : l) AddBack(val);
}

template<typename TVal>
TLst<TVal>& TLst<TVal>::operator=(const TLst<TVal>& l) {
	if (this != &l) {
		Clr();
		for (const auto& val : l) AddBack(val);
	}
	return *this;
}

template TLst<TInt>& TLst<TInt>::operator=(const TLst<TInt>& l);
#else
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();
}
#endif

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::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");
	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();
#ifdef TP_MEMLIST
		rDat.Val2.AddFront(1);
#else
		rDat.Val2.Add(1);
#endif
		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) {
#ifdef TP_MEMLIST
			d.Val2.AddFront(-1);
#else
			d.Val2.Add(-1);
#endif
		}
	}
}

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;
#ifdef TP_ALLSTRAT
	for (int i = strategy_record.size() - gsize; i < strategy_record.size(); ++i) {
		if (!strategy_record[i].committed && strategy_record[i].strategy == 1)
			++plays;
	}
#else
	for (int i = strategy_record.size() - 1, j = 0; i >= 0 && j < gsize; --i) {
		if (!strategy_record[i].committed) {
			++j;
			if (strategy_record[i].strategy == 1) ++plays;
		}
	}
#endif
	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});
}

#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()) {
		float x = weight_table.size();
		weight_table.push_back(std::exp(-x));
	}
	return weight_table[i];
}
#endif

#undef TP_BESTMOVE_CONFBIAS
int NameGame::best_move(int nId) {
	const auto& mem = graph.GetNDat(nId).Val2;
#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]++;
	}
#endif
	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) {
	auto& d = graph.GetNDat(nId);
	if (!d.Val1) {
#ifdef TP_MEMLIST
		d.Val2.AddFront(strategy);
		d.Val2.DelLast();
#else
		d.Val2.Ins(0, strategy);
		d.Val2.DelLast();
#endif
	}
}

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