main.py

"""
	Simple model for the evolutionary-game-theoretic explanation
	of the emergence language as a tool for coordination.

	Populations of sender and receiver Agents play games where the sender
	is given information about the winning move sends a signal to the receiver
	who then chooses what move to play. The Community develops an
	association of "meaning" (in a behaviourist sense) to the signal
	and begins using it to communicate information about the winning move,
	essentially creating a very simple language.
"""

import typing as tpg
import math as mth
import random as rdm
import statistics as sts
import matplotlib.pyplot as mpt

def random_nonzero() -> float:
	"""
		Wrapper for random.random
		returning a value from the interval (0,1) instead of [0,1).
	"""
	# 0 would cause probability_to_log_odds to fail
	# since log(0) approaches -infinity, so I'm excluding it.
	# According to documentation random.random never returns 1
	# so the opposite problem doesn't occur.
	candidate: float = 0
	while not candidate:
		candidate = rdm.random()
	return candidate

def probability_to_log_odds(probability: float) -> float:
	return mth.log(- 1 / (probability - 1) - 1)

def log_odds_to_probability(log_odds: float) -> float:
	return - 1 / (mth.exp(log_odds) + 1) + 1

class Agent:
	__slots__: tuple[str, ...] = (
		'prob_true_given_true', 'prob_true_given_false', 'fitness'
	)

	@tpg.overload
	def __init__(self: tpg.Self) -> None:
		"""
			Initialize a zeroth-generation Agent
			with uniformly-distributed random parameters.
		"""
		...

	@tpg.overload
	def __init__(
		self: tpg.Self, parent: tpg.Self, mutation_sigma: float
	) -> None:
		"""
			Initialize a positive-generation Agent
			with parameters based on a parent and a random mutation.
		"""
		...

	def __init__(
		self: tpg.Self,
		parent: tpg.Self | None = None,
		mutation_sigma: float | None = None
	) -> None:
		# Bahaviour paramaters - probabilities that during a game the Agent
		# sends True depending on the value it received.
		# These attributes are inherited and mutated between generations.
		self.prob_true_given_true: float
		self.prob_true_given_false: float

		# Score depending on how well the Agent has done
		# in the games it played. Determines how many descendants it passes
		# its behaviour parameters onto on average.
		self.fitness: float = 0

		match parent, mutation_sigma:
			case None, None:	# Zeroth-generation overload.
				self.prob_true_given_true = random_nonzero()
				self.prob_true_given_false = random_nonzero()
			case Agent(), float():	# Positive-generation overload.
				# Probabilities are transformed into log-odds,
				# translated by a gaussian random variable
				# and transformed back.
				# This prevents them from going outside (0,1)
				# during mutation in a natural, smooth manner.
				self.prob_true_given_true = log_odds_to_probability(
					probability_to_log_odds(parent.prob_true_given_true)
					+ rdm.gauss(sigma = mutation_sigma)
				)
				self.prob_true_given_false = log_odds_to_probability(
					probability_to_log_odds(parent.prob_true_given_false)
					+ rdm.gauss(sigma = mutation_sigma)
				)
			case _:
				raise ValueError(
					"Either both of parent and mutation_sigma"
					"must be provided or neither."
				)

	def make_move(self: tpg.Self, input_value: bool) -> bool:
		"""
			Choose move based on input value and probabilities.

			If input_value is True, return True with probability
			prob_true_given_true and False otherwise.
			If input_value is False, return True with probability
			prob_true_given_false and False otherwise.
		"""
		return rdm.random() < (
			self.prob_true_given_true if input_value
			else self.prob_true_given_false
		)

	def update_fitness(self: tpg.Self, success: bool) -> None:
		"""
			Update fitness based on whether the Agent won or lost game.
		"""
		self.fitness += 1 if success else - 1

def evolve_population(pop: list[Agent], mutation_sigma: float) -> list[Agent]:
	"""
		Create a new generation of agents inheriting traits from parents
		with probability proportional to exp of fitness.
	"""
	# math.exp recovers an always positive number from fitness
	# which allows a coherent distribution to be constructed
	# in a smooth manner.
	return [Agent(parent, mutation_sigma) for parent in rdm.choices(
		pop, [mth.exp(agent.fitness) for agent in pop], k = len(pop)
	)]

class Community:
	"""
		A pair of populations of sender and receiver Agents.
	"""

	__slots__: tuple[str, ...] = (
		'sender_population',
		'receiver_population',
		'stats'
	)

	def __init__(self: tpg.Self, population_size: int) -> None:
		"""
			Initialize two populations of zeroth-generation Agents.
		"""
		self.sender_population: list[Agent] = [
			Agent() for _ in range(population_size)
		]
		self.receiver_population: list[Agent] = [
			Agent() for _ in range(population_size)
		]
		# Initially empty stats.
		self.stats: dict[str, dict[str, list[float]]] = {
			"senders' probability of sending True given True":
				{'mean': [], 'std_dev': []},
			"senders' probability of sending True given False":
				{'mean': [], 'std_dev': []},
			"receivers' probability of playing True given True":
				{'mean': [], 'std_dev': []},
			"receivers' probability of playing True given False":
				{'mean': [], 'std_dev': []}
		}
		# Register behaviour parameters of the zeroth generation.
		self.register()
	
	def register(self: tpg.Self) -> None:
		"""
			Save current mean and standard deviation
			of Agents' behaviour parameters to later display in plots.
		"""
		# Prepare lists of Agents' behaviour parameters to summarize.
		senders_ptgt: list[float] = [
			agent.prob_true_given_true for agent in self.sender_population
		]
		senders_ptgf: list[float] = [
			agent.prob_true_given_false for agent in self.sender_population
		]
		receivers_ptgt: list[float] = [
			agent.prob_true_given_true for agent in self.receiver_population
		]
		receivers_ptgf: list[float] = [
			agent.prob_true_given_false for agent in self.receiver_population
		]
		# Register means of parameters.
		self.stats["senders' probability of sending True given True"] \
			['mean'].append(sts.mean(senders_ptgt))
		self.stats["senders' probability of sending True given False"] \
			['mean'].append(sts.mean(senders_ptgf))
		self.stats["receivers' probability of playing True given True"] \
			['mean'].append(sts.mean(receivers_ptgt))
		self.stats["receivers' probability of playing True given False"] \
			['mean'].append(sts.mean(receivers_ptgf))
		# Register standard deviations of parameters.
		self.stats["senders' probability of sending True given True"] \
			['std_dev'].append(sts.stdev(senders_ptgt))
		self.stats["senders' probability of sending True given False"] \
			['std_dev'].append(sts.stdev(senders_ptgf))
		self.stats["receivers' probability of playing True given True"] \
			['std_dev'].append(sts.stdev(receivers_ptgt))
		self.stats["receivers' probability of playing True given False"] \
			['std_dev'].append(sts.stdev(receivers_ptgf))

	def simulate(
		self: tpg.Self,
		generation_number: int,
		turns_per_generation: int,
		mutation_sigma: float
	) -> None:
		"""
			Simulate multiple generations of Agents playing coordination
			games, receiving fitness based on their results and producing
			randomly mutated descendants.
		"""
		for _ in range(generation_number):
			# Pair senders and receivers and simulate interactions.
			for _ in range(turns_per_generation):
				# Shuffle the receiver population to ensure
				# that there are new random pairings between agents each turn.
				rdm.shuffle(self.receiver_population)
				for sender, receiver in zip(
					self.sender_population, self.receiver_population
				):
					# Randomly choose the winning move.
					winning_move: bool = rdm.choice([True, False])
					# Information about the winning move is given to the sender
					# and must be communicated to the receiver in order
					# for both Agents to win.
					success: bool = winning_move == \
						receiver.make_move(sender.make_move(winning_move))
					sender.update_fitness(success)
					receiver.update_fitness(success)
			# After a multiple turns, create new generations
			# of senders and receivers.
			self.sender_population = evolve_population(
				self.sender_population, mutation_sigma
			)
			self.receiver_population = evolve_population(
				self.receiver_population, mutation_sigma
			)
			# Register the bahaviour parameters of the new generation.
			self.register()
		# After simulating multiple Communities, display results.
		_, axs = mpt.subplots(2, 2, figsize = (10, 10))
		for i, (key, value) in enumerate(self.stats.items()):
			axs[i // 2][i % 2].set_xlim(
				[- len(value['mean']) / 20, len(value['mean']) * 1.05]
			)
			axs[i // 2][i % 2].set_ylim([-0.05, 1.05])
			axs[i // 2][i % 2].errorbar(
				range(len(value['mean'])),
				value['mean'],
				yerr = value['std_dev'],
				label = key
			)
			axs[i // 2][i % 2].set_xlabel('Generation')
			axs[i // 2][i % 2].set_ylabel('Values')
			axs[i // 2][i % 2].set_title(key)
		mpt.show()

if __name__ == '__main__':
	# Example parameters for the genetic algorithm.

	GENERATION_NUMBER: int = 100

	# Number of isolated pairs of sender and receiver populations.
	COMMUNITY_NUMBER: int = 10

	POPULATION_SIZE: int = 100

	# Number of games each agent plays before fitness evaluation.
	TURNS_PER_GENERATION: int = 10

	# Standard deviation of Gauss distribution
	# of translation of agents' log-odds.
	MUTATION_SIGMA: float = 0.1

	for _ in range(COMMUNITY_NUMBER):
		Community(POPULATION_SIZE).simulate(
			GENERATION_NUMBER, TURNS_PER_GENERATION, MUTATION_SIGMA
		)