# Meta-Strategies¶

## Finite State Machines¶

A finite state machine (FSM) is a general computation model. In the context of Axelrod, it’s a set of states and “transitions.” A transition for a given state/previous-opponent-action combination says how the strategy will respond, both in what action it will take and in what state it will transitions to. That is a transition will specify that in state $$a$$, the strategy will respond to action $$X$$ by taking action $$Y$$ and moving to state $$b$$ (which will tell us which transitions to use in later moves). We may write this transition $$(a, X, b, Y)$$. For Axelrod, a FSM must have a full set of transitions, which specifies a unique response for each state/previous-opponent-action combination.

See [Harper2017] for a more-detailed explanation.

Representing a strategy as a finite state machine has been useful in some research (see [Harper2017] or [Ashlock2006b]). Though it’s theoretically possible to represent all strategies as FSMs, this is impractical for most strategies. However, some strategies lend themselves naturally to a FSM representation. For example, for the Iterated Prisoner’s Dilemma, we could consider a strategy that cooperates (C) until the opponent defects (D) twice in a row, then defect forever thereafter. (We’ll call this strategy grudger_2 for the example.) We could call state 1, the state where the opponent hasn’t started a defect streak; state 2, the state where the opponent is on a 1-defect streak; and state 3, the state where the opponent has defected twice in a row at some point. Then the transitions would be:

>>> from axelrod import Action
>>> C, D = Action.C, Action.D
>>> grudger_2_transitions = (
...    (1, C, 1, C),
...    (1, D, 2, C),
...    (2, C, 1, C),
...    (2, D, 3, D),
...    (3, C, 3, D),
...    (3, D, 3, D)
... )


The Axelrod library includes a FSM meta-strategy player, which will you let you specify a player’s strategy by this transition matrix, along with an initial state and initial action. The syntax for this is:

>>> from axelrod.strategies.finite_state_machines import FSMPlayer
>>> grudger_2 = FSMPlayer(transitions=grudger_2_transitions,
...                       initial_state=1, initial_action=C)


The library also includes the functionality to compute the memory from the set of transitions. In the grudger_2 example, the memory would be 2. Because either the strategy’s own previous move was a defect (in which case, continue to defect) or we just need to check if the last two opponent moves were defects or not. Though this function takes the transitions in a slightly different format:

>>> transition_dict = {
...    (t[0], t[1]): (t[2], t[3]) for t in grudger_2_transitions
... }
>>> from axelrod.compute_finite_state_machine_memory import *
>>> get_memory_from_transitions(transitions=transition_dict,
...                             initial_state=1)
2