m_ipd/

lib.rs

//! This crate provides the necessary framework to simulate the iterated prisoner's dilemma in
//! cases where the history is not always entirely available.
//!
//! The mechanisms to provide one simulation are provided by the `simulate` function, and the full
//! details of how this works are provided by the associated documentation. If one is interested in
//! comparing many strategies against each other, the `tournament` function provides the necessary
//! interface.

pub use Choice::*;

/// Represents one of two possible choices that an actor can make.
#[derive(Debug, Clone, Copy, Eq, PartialEq)]
pub enum Choice {
    Cooperate,
    Defect,
}

/// Represents a choice that the other player made in the last round.
#[derive(Debug, Clone, Copy, Eq, PartialEq)]
pub enum Round {
    /// Contains the choice that the other player made
    Shown(Choice),
    /// Indicates that the information from the last round has been hidden by the revealing policy
    Hidden,
    /// Indicates that this is the first round of the game
    First,
}

/// Represents a playing strategy
///
/// This function will be invoked one time every time two players play the IPD. The closure that is
/// returned by the function will be repeatedly invoked with values of the `Round` enum; each
/// invocation of the closure corresponds to one round of gameplay. The closure is told the
/// other player's choice in the previous round, and asked to return the next round's choice.
///
/// A very simple strategy might be to always `Cooperate`. It could be written like this:
/// ```rust
/// use m_ipd::*;
/// 
/// fn always_cooperate() -> Box<dyn FnMut(Round) -> Choice> {
///     Box::new(|_| Cooperate)
/// }
/// 
/// let s: Strategy = always_cooperate;
/// ```
pub type Strategy = fn() -> Box<dyn FnMut(Round) -> Choice>;

/// Represents a policy that decides how history is revealed.
///
/// This type functions much like the `Strategy` type; the function is invoked once for each time
/// IPD is played. The returned closure is invoked once for each round of the game, with the
/// choices of the players; it should return true of false indicating whether the decisions from
/// that round should be revealed to the players.
pub type RevealPolicy = fn() -> Box<dyn FnMut(Choice, Choice) -> bool>;

// The standard reward function
fn reward(one: Choice, two: Choice) -> (u32, u32) {
    match (one, two) {
        (Cooperate, Cooperate) => (3, 3),
        (Cooperate, Defect) => (0, 5),
        (Defect, Cooperate) => (5, 0),
        (Defect, Defect) => (1, 1),
    }
}

// Simulates a match between two players.
fn simulate(
    one: Strategy,
    two: Strategy,
    policy: RevealPolicy,
) -> (u32, u32, u32) {
    let mut s1 = 0;
    let mut s2 = 0;
    let mut rounds = 0;
    for _ in 0..100 {
        let mut last = None;
        let mut one = one();
        let mut two = two();
        let mut policy = policy();

        while rand::random::<f32>() < 1f32 - 1f32 / 200f32 {
            let c1;
            let c2;

            if let Some((prev_one, prev_two, rev)) = last {
                c1 = one(if rev {
                    Round::Shown(prev_two)
                } else {
                    Round::Hidden
                });
                c2 = two(if rev {
                    Round::Shown(prev_one)
                } else {
                    Round::Hidden
                });
            } else {
                c1 = one(Round::First);
                c2 = two(Round::First);
            }

            let (r1, r2) = reward(c1, c2);
            s1 += r1;
            s2 += r2;
            rounds += 1;

            let show = policy(c1, c2);
            last = Some((c1, c2, show));
        }
    }

    (s1, s2, rounds)
}

/// Runs a tournament between a set of strategies.
///
/// This is a round-robin tournament; each strategy plays IPD against each other strategy 100
/// times. The output of the function is the average number of points each strategy earned per
/// round.
///
/// The reward function used is as follows:
///  - 1 point for mutual defection.
///  - 3 points for mutual cooperation.
///  - 5 points for successful betreyal.
pub fn tournament(
    strategies: &[Strategy],
    policy: RevealPolicy,
) -> Vec<f32> {
    let n = strategies.len();
    let mut points = vec![(0, 0); n];

    for i in 0..n - 1 {
        for j in i+1..n {
            let (p1, p2, rounds) = simulate(strategies[i], strategies[j], policy);
            points[i] = ((points[i].0 + p1), (points[i].1 + rounds));
            points[j] = ((points[j].0 + p2), (points[j].1 + rounds));
        }
    }
    points.into_iter().map(|(p, r)| p as f32 / r as f32).collect()
}

pub mod strategies {
    use crate::*;

    pub mod axelrod {
        use crate::*;

        /// Copies the opponents last shown move.
        pub fn tit_for_tat() -> Box<dyn FnMut(Round) -> Choice> {
            let mut old = Cooperate;
    
            Box::new(move |c| match c {
                Round::Shown(n) => {
                    old = n;
                    n
                }
                _ => old,
            })
        }

        /// Copies the opponents last move if it was shown, cooperating otherwise.
        pub fn optimistic_tit_for_tat() -> Box<dyn FnMut(Round) -> Choice> {
            Box::new(move |c| match c {
                Round::Shown(o) => o,
                _ => Cooperate
            })
        }

        /// Punishes the other player by one turn more each time the other player
        /// engages in a streak of defections.
        pub fn punishing_tit_for_tat() -> Box<dyn FnMut(Round) -> Choice> {
            let mut reset = 0u32;
            let mut retaliate = 0;
            let mut last = Cooperate;

            Box::new(move |c| match c {
                Round::Shown(Cooperate) => {
                    if last == Defect {
                        reset = retaliate;
                        retaliate += 1;
                    }
                    last = Cooperate;

                    if reset > 0 {
                        reset -= 1;
                        Defect
                    } else {
                        Cooperate
                    }
                }
                Round::Shown(Defect) => Defect,
                Round::Hidden => {
                    if reset > 0 {
                        reset -= 1;
                        Defect
                    } else {
                        Cooperate
                    }
                }
                Round::First => Cooperate
            })
        }

        /// Cooperates unless one betrayer betrayed the other in the last shown round, in which
        /// case it only cooperates with low probability.
        ///
        /// Adapted from a strategy created by Grofman
        pub fn betray_defect() -> Box<dyn FnMut(Round) -> Choice> {
            let mut last = Cooperate;
            let mut betray = false;
            Box::new(move |c| match c {
                Round::Shown(o) => {
                    let n = if last == o {
                        betray = false;
                        Cooperate
                    } else {
                        betray = true;
                        if rand::random::<f32>() < 2f32/7f32 { Cooperate } else { Defect }
                    };
                    last = n;
                    n
                }
                Round::Hidden => {
                    let n = if betray {
                        if rand::random::<f32>() < 2f32/7f32 { Cooperate } else { Defect }
                    } else {
                        Cooperate
                    };
                    last = n;
                    n
                }
                Round::First => Cooperate
            })
        }

        /// Defects in streaks increasing by length 1.
        ///
        /// Original strategy by Shubik.
        pub fn defect_streaks() -> Box<dyn FnMut(Round) -> Choice> {
            let mut next = 0;
            let mut current = 0;
            Box::new(move |c| match c {
                Round::Shown(o) => {
                    if current > 0 {
                        current -= 1;
                        Defect
                    } else {
                        if o == Defect {
                            current = next;
                            next += 1;
                            Defect
                        } else {
                            Cooperate
                        }
                    }
                },
                Round::Hidden => {
                    if current > 0 {
                        current -= 1;
                        Defect
                    } else {
                        Cooperate
                    }
                }
                Round::First => Cooperate
            })
        }

        /// Cooperates until the opponent defects even once.
        ///
        /// Adapted from an original strategy by Friedman.
        pub fn grudge_holder() -> Box<dyn FnMut(Round) -> Choice> {
            let mut action = Cooperate;
    
            Box::new(move |c: Round| match c {
                Round::Shown(Defect) => {
                    action = Defect;
    
                    action
                }
                _ => action,
            })
        }

        /// Plays tit for tat but cooperates with decreasing probability each turn
        ///
        /// Adapted from an original strategy by Feld
        pub fn decreasing_tit_for_tat() -> Box<dyn FnMut(Round) -> Choice> {
            let mut last = Cooperate;
            let mut prob = 1f32;
            Box::new(move |c| {
                prob *= 0.99654; // 200th root of 0.5
                if let Round::Shown(c) = c {
                    last = c;
                }

                if last == Cooperate {
                    if rand::random::<f32>() < prob { Cooperate } else { Defect }
                } else {
                    Defect
                }
            })
        }

        /// Copies the other's cooperation with probability 90%, otherwise defects.
        ///
        /// Adapted from a strategy by Joss.
        pub fn random_tit_for_tat() -> Box<dyn FnMut(Round) -> Choice> {
            let mut old = Cooperate;
    
            Box::new(move |c| {
                if let Round::Shown(o) = c {
                    old = o;
                }

                if old == Cooperate {
                    if rand::random::<f32>() < 0.9 { Cooperate } else { Defect }
                } else {
                    Defect
                }
            })
        }

        /// Plays randomly with probability `p`.
        ///
        /// This must be used like `|| random(0.5)` instead of `random` since the `Strategy` type
        /// does not allow for taking a parameter.
        pub fn random(p: f32) -> Box<dyn FnMut(Round) -> Choice> {
            Box::new(move |_| {
                if rand::random::<f32>() < p {
                    Cooperate
                } else {
                    Defect
                }
            })
        }
    }

    /// Always cooperates
    pub fn always_cooperate() -> Box<dyn FnMut(Round) -> Choice> {
        Box::new(|_| Cooperate)
    }

    /// Always defects
    pub fn always_defect() -> Box<dyn FnMut(Round) -> Choice> {
        Box::new(|_| Defect)
    }

    /// Plays tit for tat, but does not defect until the other player has defected twice
    /// in a row.
    pub fn tit_for_two_tats() -> Box<dyn FnMut(Round) -> Choice> {
        let mut prev = Cooperate;
        let mut next = Cooperate;

        Box::new(move |c| {
            if let Round::Shown(c) = c {
                match c {
                    Cooperate => {
                        prev = Cooperate;
                        next = Cooperate;
                    }
                    Defect => {
                        next = prev;
                        prev = Defect;
                    }
                }
            }

            next
        })
    }

    /// Plays tit for tat, but if the last two rounds were both hidden, defects.
    pub fn opportunistic() -> Box<dyn FnMut(Round) -> Choice> {
        let mut last = Cooperate;
        let mut hidden = 0;

        Box::new(move |c| {
            match c {
                Round::Shown(o) => {
                    hidden = 0;
                    last = o;
                    last
                },
                Round::Hidden => {
                    hidden += 1;
                    if hidden > 2 { Defect } else { last }
                }
                Round::First => Cooperate
            }
        })
    }

    /// Plays the inverse of the other player's move.
    pub fn inverse() -> Box<dyn FnMut(Round) -> Choice> {
        let mut next = Cooperate;

        Box::new(move |c| match c {
            Round::Shown(n) => {
                next = match n { Cooperate => Defect, Defect => Cooperate };
                n
            }
            _ => next,
        })
    }

    /// Plays the other player's majority move.
    pub fn majority() -> Box<dyn FnMut(Round) -> Choice> {
        let mut coop = 0;
        let mut def = 0;
        Box::new(move |c| {
            if let Round::Shown(n) = c {
                if n == Cooperate {
                    coop += 1;
                } else {
                    def += 1;
                }
            }

            if coop > def { Cooperate } else { Defect }
        })
    }

    /// Plays the other player's minority move.
    pub fn minority() -> Box<dyn FnMut(Round) -> Choice> {
        let mut coop = 0;
        let mut def = 0;
        Box::new(move |c| {
            if let Round::Shown(n) = c {
                if n == Cooperate {
                    coop += 1;
                } else {
                    def += 1;
                }
            }

            if coop < def { Cooperate } else { Defect }
        })
    }
}

pub mod policies {
    use crate::*;

    pub fn always_show() -> Box<dyn FnMut(Choice, Choice) -> bool> {
        Box::new(|_, _| true)
    }

    pub fn never_show() -> Box<dyn FnMut(Choice, Choice) -> bool> {
        Box::new(|_, _| false)
    }

    pub fn random(reveal_chance: f32) -> Box<dyn FnMut(Choice, Choice) -> bool> {
        Box::new(move |_, _| rand::random::<f32>() < reveal_chance)
    }

    pub fn show_cooperate(init: f32) -> Box<dyn FnMut(Choice, Choice) -> bool> {
        let mut coop = init;
        let mut total = 2.0 * init;
        Box::new(move |c1, c2| {
            if c1 == Cooperate && c2 == Cooperate {
                coop += 1.0;
            }
            total += 1.0;

            rand::random::<f32>() < coop / total
        })
    }
}