# Source code for axelrod.strategies.finite_state_machines

import itertools
from typing import Any, Dict, List, Sequence, Text, Tuple

from axelrod.action import Action
from axelrod.evolvable_player import (
EvolvablePlayer,
InsufficientParametersError,
copy_lists,
)
from axelrod.player import Player

C, D = Action.C, Action.D
actions = (C, D)
Transition = Tuple[int, Action, int, Action]

[docs]class SimpleFSM(object):
"""Simple implementation of a finite state machine that transitions
between states based on the last round of play.

https://en.wikipedia.org/wiki/Finite-state_machine
"""

def __init__(self, transitions: tuple, initial_state: int) -> None:
"""
transitions is a list of the form
((state, last_opponent_action, next_state, next_action), ...)

TitForTat would be represented with the following table:
((1, C, 1, C), (1, D, 1, D))
with initial play C and initial state 1.

"""
self._state = initial_state
self._state_transitions = {
(current_state, input_action): (next_state, output_action)
for current_state, input_action, next_state, output_action in transitions
}  # type: dict

callable_states = set(
pair[0] for pair in self._state_transitions.values()
)
for state in callable_states:

if (state, C) not in self._state_transitions or (
state,
D,
) not in self._state_transitions:
raise ValueError(
"state: {} does not have values for both C and D".format(state)
)

@property
def state(self) -> int:
return self._state

@state.setter
def state(self, new_state: int):
self._state = new_state

@property
def state_transitions(self) -> dict:
return self._state_transitions.copy()

def transitions(self) -> list:
return [
[x[0], x[1], y[0], y[1]] for x, y in self._state_transitions.items()
]

[docs]    def move(self, opponent_action: Action) -> Action:
"""Computes the response move and changes state."""
next_state, next_action = self._state_transitions[
(self._state, opponent_action)
]
self._state = next_state
return next_action

def __eq__(self, other) -> bool:
"""Equality of two FSMs"""
if not isinstance(other, SimpleFSM):
return False
return (self._state, self._state_transitions) == (
other.state,
other.state_transitions,
)

[docs]    def num_states(self):
"""Return the number of states of the machine."""
return len(set(state for state, action in self._state_transitions))

[docs]class FSMPlayer(Player):
"""Abstract base class for finite state machine players."""

name = "FSM Player"

classifier: Dict[Text, Any] = {
"memory_depth": 1,
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(
self,
transitions: Tuple[Transition, ...] = ((1, C, 1, C), (1, D, 1, D)),
initial_state: int = 1,
initial_action: Action = C,
) -> None:
Player.__init__(self)
self.initial_state = initial_state
self.initial_action = initial_action
self.fsm = SimpleFSM(transitions, initial_state)

[docs]    def strategy(self, opponent: Player) -> Action:
"""Actual strategy definition that determines player's action."""
if len(self.history) == 0:
return self.initial_action
else:
return self.fsm.move(opponent.history[-1])

[docs]class EvolvableFSMPlayer(FSMPlayer, EvolvablePlayer):
"""Abstract base class for evolvable finite state machine players."""

name = "EvolvableFSMPlayer"

classifier = {
"memory_depth": 1,
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(
self,
transitions: tuple = None,
initial_state: int = None,
initial_action: Action = None,
num_states: int = None,
mutation_probability: float = 0.1,
seed: int = None,
) -> None:
"""If transitions, initial_state, and initial_action are None
then generate random parameters using num_states."""
EvolvablePlayer.__init__(self, seed=seed)
(
transitions,
initial_state,
initial_action,
num_states,
) = self._normalize_parameters(
transitions, initial_state, initial_action, num_states
)
FSMPlayer.__init__(
self,
transitions=transitions,
initial_state=initial_state,
initial_action=initial_action,
)
self.mutation_probability = mutation_probability
self.overwrite_init_kwargs(
transitions=transitions,
initial_state=initial_state,
initial_action=initial_action,
num_states=self.num_states,
)

[docs]    @classmethod
def normalize_transitions(
cls, transitions: Sequence[Sequence]
) -> Tuple[Tuple[Any, ...], ...]:
"""Translate a list of lists to a tuple of tuples."""
normalized = []
for t in transitions:
normalized.append(tuple(t))
return tuple(normalized)

def _normalize_parameters(
self,
transitions: Tuple = None,
initial_state: int = None,
initial_action: Action = None,
num_states: int = None,
) -> Tuple[Tuple, int, Action, int]:
if not (
(transitions is not None)
and (initial_state is not None)
and (initial_action is not None)
):
if not num_states:
raise InsufficientParametersError(
"Insufficient Parameters to instantiate EvolvableFSMPlayer"
)
transitions, initial_state, initial_action = self.random_params(
num_states
)
transitions = self.normalize_transitions(transitions)
num_states = len(transitions) // 2
return transitions, initial_state, initial_action, num_states

@property
def num_states(self) -> int:
return self.fsm.num_states()

def random_params(
self, num_states: int
) -> Tuple[Tuple[Transition, ...], int, Action]:
rows = []
for j in range(num_states):
for action in actions:
next_state = self._random.randint(num_states)
next_action = self._random.choice(actions)
row = (j, action, next_state, next_action)
rows.append(row)
initial_state = self._random.randint(0, num_states)
initial_action = self._random.choice(actions)
return tuple(rows), initial_state, initial_action

def mutate_rows(self, rows: List[List], mutation_probability: float):
rows = list(rows)
randoms = self._random.random(len(rows))
# Flip each value with a probability proportional to the mutation rate
for i, row in enumerate(rows):
if randoms[i] < mutation_probability:
row[3] = row[3].flip()
# Swap Two Nodes?
if self._random.random() < 0.5:
nodes = len(rows) // 2
n1 = self._random.randint(0, nodes)
n2 = self._random.randint(0, nodes)
for j, row in enumerate(rows):
if row[0] == n1:
row[0] = n2
elif row[0] == n2:
row[0] = n1
rows.sort(key=lambda x: (x[0], 0 if x[1] == C else 1))
return rows

[docs]    def mutate(self):
initial_action = self.initial_action
if self._random.random() < self.mutation_probability / 10:
initial_action = self.initial_action.flip()
initial_state = self.initial_state
if self._random.random() < self.mutation_probability / (
10 * self.num_states
):
initial_state = self._random.randint(0, self.num_states)
try:
transitions = self.mutate_rows(
self.fsm.transitions(), self.mutation_probability
)
self.fsm = SimpleFSM(transitions, self.initial_state)
except ValueError:
# If the FSM is malformed, try again.
return self.mutate()
return self.create_new(
transitions=transitions,
initial_state=initial_state,
initial_action=initial_action,
)

def crossover_rows(
self, rows1: List[List], rows2: List[List]
) -> List[List]:
num_states = len(rows1) // 2
cross_point = 2 * self._random.randint(0, num_states)
new_rows = copy_lists(rows1[:cross_point])
new_rows += copy_lists(rows2[cross_point:])
return new_rows

[docs]    def crossover(self, other):
if other.__class__ != self.__class__:
raise TypeError(
"Crossover must be between the same player classes."
)
transitions = self.crossover_rows(
self.fsm.transitions(), other.fsm.transitions()
)
transitions = self.normalize_transitions(transitions)
return self.create_new(transitions=transitions)

"""
Read a serialized vector into the set of FSM parameters (less initial
state).  Then assign those FSM parameters to this class instance.

The vector has three parts. The first is used to define the next state
(for each of the player's states - for each opponents action).

The second part is the player's next moves (for each state - for
each opponent's actions).

Finally, a probability to determine the player's first move.
"""
num_states = self.fsm.num_states()
state_scale = vector[: num_states * 2]
next_states = [int(s * (num_states - 1)) for s in state_scale]
actions = vector[num_states * 2 : -1]

self.initial_action = C if round(vector[-1]) == 0 else D
self.initial_state = 1

transitions = []
for i, (initial_state, action) in enumerate(
itertools.product(range(num_states), [C, D])
):
next_action = C if round(actions[i]) == 0 else D
transitions.append(
[initial_state, action, next_states[i], next_action]
)
transitions = self.normalize_transitions(transitions)
self.fsm = SimpleFSM(transitions, self.initial_state)
self.overwrite_init_kwargs(
transitions=transitions,
initial_state=self.initial_state,
initial_action=self.initial_action,
)

[docs]    def create_vector_bounds(self):
"""Creates the bounds for the decision variables."""
size = len(self.fsm.transitions()) * 2 + 1
lb = [0] * size
ub = [1] * size
return lb, ub

[docs]class Fortress3(FSMPlayer):
"""Finite state machine player specified in http://DOI.org/10.1109/CEC.2006.1688322.

Note that the description in http://www.graham-kendall.com/papers/lhk2011.pdf
is not correct.

Names:

- Fortress 3: [Ashlock2006b]_
"""

name = "Fortress3"
classifier = {
"memory_depth": 2,
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(1, C, 1, D),
(1, D, 2, D),
(2, C, 1, D),
(2, D, 3, C),
(3, C, 3, C),
(3, D, 1, D),
)

super().__init__(
transitions=transitions, initial_state=1, initial_action=D
)

[docs]class Fortress4(FSMPlayer):
"""
Finite state machine player specified in
http://DOI.org/10.1109/CEC.2006.1688322.

Note that the description in
http://www.graham-kendall.com/papers/lhk2011.pdf is not correct.

Names:

- Fortress 4: [Ashlock2006b]_
"""

name = "Fortress4"
classifier = {
"memory_depth": 3,
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(1, C, 1, D),
(1, D, 2, D),
(2, C, 1, D),
(2, D, 3, D),
(3, C, 1, D),
(3, D, 4, C),
(4, C, 4, C),
(4, D, 1, D),
)

super().__init__(
transitions=transitions, initial_state=1, initial_action=D
)

[docs]class Predator(FSMPlayer):
"""
Finite state machine player specified in
http://DOI.org/10.1109/CEC.2006.1688322.

Names:

- Predator: [Ashlock2006b]_
"""

name = "Predator"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 0, D),
(0, D, 1, D),
(1, C, 2, D),
(1, D, 3, D),
(2, C, 4, C),
(2, D, 3, D),
(3, C, 5, D),
(3, D, 4, C),
(4, C, 2, C),
(4, D, 6, D),
(5, C, 7, D),
(5, D, 3, D),
(6, C, 7, C),
(6, D, 7, D),
(7, C, 8, D),
(7, D, 7, D),
(8, C, 8, D),
(8, D, 6, D),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=C
)

[docs]class Pun1(FSMPlayer):
"""FSM player described in [Ashlock2006]_.

Names:

- Pun1: [Ashlock2006]_
"""

name = "Pun1"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = ((1, C, 2, C), (1, D, 2, C), (2, C, 1, C), (2, D, 1, D))

super().__init__(
transitions=transitions, initial_state=1, initial_action=D
)

[docs]class Raider(FSMPlayer):
"""
FSM player described in http://DOI.org/10.1109/FOCI.2014.7007818.

Names

- Raider: [Ashlock2014]_
"""

name = "Raider"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 2, D),
(0, D, 2, D),
(1, C, 1, C),
(1, D, 1, D),
(2, C, 0, D),
(2, D, 3, C),
(3, C, 0, D),
(3, D, 1, C),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=D
)

[docs]class Ripoff(FSMPlayer):
"""
FSM player described in http://DOI.org/10.1109/TEVC.2008.920675.

Names

- Ripoff: [Ashlock2008]_
"""

name = "Ripoff"
classifier = {
"memory_depth": 3,
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(1, C, 2, C),
(1, D, 3, C),
(2, C, 1, D),
(2, D, 3, C),
(3, C, 3, C),  # Note that it's TFT in state 3
(3, D, 3, D),
)

super().__init__(
transitions=transitions, initial_state=1, initial_action=D
)

[docs]class UsuallyCooperates(FSMPlayer):
"""
This strategy cooperates except after a C following a D.

Names:

- Usually Cooperates (UC): [Ashlock2009]_
"""

name = "UsuallyCooperates"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = ((1, C, 1, C), (1, D, 2, C), (2, C, 1, D), (2, D, 1, C))

super().__init__(
transitions=transitions, initial_state=1, initial_action=C
)

[docs]class UsuallyDefects(FSMPlayer):
"""
This strategy defects except after a D following a C.

Names:

- Usually Defects (UD): [Ashlock2009]_
"""

name = "UsuallyDefects"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = ((1, C, 2, D), (1, D, 1, D), (2, C, 1, D), (2, D, 1, C))

super().__init__(
transitions=transitions, initial_state=1, initial_action=D
)

[docs]class SolutionB1(FSMPlayer):
"""
FSM player described in http://DOI.org/10.1109/TCIAIG.2014.2326012.

Names

- Solution B1: [Ashlock2015]_
"""

name = "SolutionB1"
classifier = {
"memory_depth": 2,
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(1, C, 2, D),
(1, D, 1, D),
(2, C, 2, C),
(2, D, 3, C),
(3, C, 3, C),
(3, D, 3, C),
)

super().__init__(
transitions=transitions, initial_state=1, initial_action=D
)

[docs]class SolutionB5(FSMPlayer):
"""

FSM player described in http://DOI.org/10.1109/TCIAIG.2014.2326012.

Names

- Solution B5: [Ashlock2015]_
"""

name = "SolutionB5"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(1, C, 2, C),
(1, D, 6, D),
(2, C, 2, C),
(2, D, 3, D),
(3, C, 6, C),
(3, D, 1, D),
(4, C, 3, C),
(4, D, 6, D),
(5, C, 5, D),
(5, D, 4, D),
(6, C, 3, C),
(6, D, 5, D),
)

super().__init__(
transitions=transitions, initial_state=1, initial_action=D
)

[docs]class Thumper(FSMPlayer):
"""
FSM player described in http://DOI.org/10.1109/TEVC.2008.920675.

Names

- Thumper: [Ashlock2008]_
"""

name = "Thumper"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = ((1, C, 1, C), (1, D, 2, D), (2, C, 1, D), (2, D, 1, D))

super().__init__(
transitions=transitions, initial_state=1, initial_action=C
)

[docs]class EvolvedFSM4(FSMPlayer):
"""
A 4 state FSM player trained with an evolutionary algorithm.

Names:

- Evolved FSM 4: Original name by Marc Harper
"""

name = "Evolved FSM 4"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 0, C),
(0, D, 2, D),
(1, C, 3, D),
(1, D, 0, C),
(2, C, 2, D),
(2, D, 1, C),
(3, C, 3, D),
(3, D, 1, D),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=C
)

[docs]class EvolvedFSM16(FSMPlayer):
"""
A 16 state FSM player trained with an evolutionary algorithm.

Names:

- Evolved FSM 16: Original name by Marc Harper

"""

name = "Evolved FSM 16"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 0, C),
(0, D, 12, D),
(1, C, 3, D),
(1, D, 6, C),
(2, C, 2, D),
(2, D, 14, D),
(3, C, 3, D),
(3, D, 3, D),
(5, C, 12, D),
(5, D, 10, D),
(6, C, 5, C),
(6, D, 12, D),
(7, C, 3, D),
(7, D, 1, C),
(8, C, 5, C),
(8, D, 5, C),
(10, C, 11, D),
(10, D, 8, C),
(11, C, 15, D),
(11, D, 5, D),
(12, C, 8, C),
(12, D, 11, D),
(13, C, 13, D),
(13, D, 7, D),
(14, C, 13, D),
(14, D, 13, D),
(15, C, 15, D),
(15, D, 2, C),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=C
)

[docs]class EvolvedFSM16Noise05(FSMPlayer):
"""
A 16 state FSM player trained with an evolutionary algorithm with
noisy matches (noise=0.05).

Names:

- Evolved FSM 16 Noise 05: Original name by Marc Harper
"""

name = "Evolved FSM 16 Noise 05"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 8, C),
(0, D, 3, D),
(1, C, 13, C),
(1, D, 15, D),
(2, C, 12, C),
(2, D, 3, D),
(3, C, 10, C),
(3, D, 3, D),
(4, C, 5, D),
(4, D, 4, D),
(5, C, 4, D),
(5, D, 10, D),
(6, C, 8, C),
(6, D, 6, D),
(8, C, 2, C),
(8, D, 4, D),
(10, C, 4, D),
(10, D, 1, D),
(11, C, 14, D),
(11, D, 13, C),
(12, C, 13, C),
(12, D, 2, C),
(13, C, 13, C),
(13, D, 6, C),
(14, C, 3, D),
(14, D, 13, D),
(15, C, 5, D),
(15, D, 11, C),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=C
)

# Strategies trained with Moran process objectives

[docs]class TF1(FSMPlayer):
"""
A FSM player trained to maximize Moran fixation probabilities.

Names:

- TF1: Original name by Marc Harper
"""

name = "TF1"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 7, C),
(0, D, 1, C),
(1, C, 11, D),
(1, D, 11, D),
(2, C, 8, D),
(2, D, 8, C),
(3, C, 3, C),
(3, D, 12, D),
(4, C, 6, C),
(4, D, 3, C),
(5, C, 11, C),
(5, D, 8, D),
(6, C, 13, D),
(6, D, 14, C),
(7, C, 4, D),
(7, D, 2, D),
(8, C, 14, D),
(8, D, 8, D),
(9, C, 0, C),
(9, D, 10, D),
(10, C, 8, C),
(10, D, 15, C),
(11, C, 6, D),
(11, D, 5, D),
(12, C, 6, D),
(12, D, 9, D),
(13, C, 9, D),
(13, D, 8, D),
(14, C, 8, D),
(14, D, 13, D),
(15, C, 4, C),
(15, D, 5, C),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=C
)

[docs]class TF2(FSMPlayer):
"""
A FSM player trained to maximize Moran fixation probabilities.

Names:

- TF2: Original name by Marc Harper
"""

name = "TF2"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 13, D),
(0, D, 12, D),
(1, C, 3, D),
(1, D, 4, D),
(2, C, 14, D),
(2, D, 9, D),
(3, C, 0, C),
(3, D, 1, D),
(4, C, 1, D),
(4, D, 2, D),
(7, C, 12, D),
(7, D, 2, D),
(8, C, 7, D),
(8, D, 9, D),
(9, C, 8, D),
(9, D, 0, D),
(10, C, 2, C),
(10, D, 15, C),
(11, C, 7, D),
(11, D, 13, D),
(12, C, 3, C),
(12, D, 8, D),
(13, C, 7, C),
(13, D, 10, D),
(14, C, 10, D),
(14, D, 7, D),
(15, C, 15, C),
(15, D, 11, D),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=C
)

[docs]class TF3(FSMPlayer):
"""
A FSM player trained to maximize Moran fixation probabilities.

Names:

- TF3: Original name by Marc Harper
"""

name = "TF3"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(0, C, 0, C),
(0, D, 3, C),
(1, C, 5, D),
(1, D, 0, C),
(2, C, 3, C),
(2, D, 2, D),
(3, C, 4, D),
(3, D, 6, D),
(4, C, 3, C),
(4, D, 1, D),
(5, C, 6, C),
(5, D, 3, D),
(6, C, 6, D),
(6, D, 6, D),
(7, C, 7, D),
(7, D, 5, C),
)

super().__init__(
transitions=transitions, initial_state=0, initial_action=C
)

[docs]class EvolvedFSM6(FSMPlayer):
"""
An 6 state FSM player trained with an evolutionary algorithm.

Evolved using axelrod-dojo version 0.0.8 and axelrod version 4.10.0, trained to maximize score against
the short_run_time_strategies with 10 machine states for 500 generations, population size of 40,
mutation rate at 0.1, bottleneck at 10, 200 turns, and 0 noise. The resulting strategy had only 6
states in its accessible component.

Names:

- Evolved FSM 6: Original name by Frederick Vincent & Dashiell Fryer
"""

name = "Evolved FSM 6"
classifier = {
"memory_depth": float("inf"),
"stochastic": False,
"long_run_time": False,
"inspects_source": False,
"manipulates_source": False,
"manipulates_state": False,
}

def __init__(self) -> None:
transitions = (
(2, C, 2, D),
(2, D, 7, D),
(3, C, 6, D),
(3, D, 4, C),
(4, C, 4, C),
(4, D, 6, D),
(5, C, 2, D),
(5, D, 7, D),
(6, C, 3, C),
(6, D, 5, D),
(7, C, 2, C),
(7, D, 3, D),
)

super().__init__(
transitions=transitions, initial_state=4, initial_action=C
)