Crate t4t

Expand description

Tit-for-tat (t4t) is a game theory library with a focus on experimentation over formal analysis, and expressiveness over performance. It provides flexible types and traits for defining games and strategies, then executing them to observe the results.

The companion crate t4t-games provides some example games and strategies.

§Expressiveness over performance

This library prioritizes expressiveness over performance. It aims to provide a powerful set of abstractions for defining arbitrary games and strategies, without sacrificing type safety.

This tradeoff is easy to see in the representation of normal-form games, which are represented not as, say, a matrix of float-tuples, but instead as a function from generic move profiles to generic payoffs. This enables normal-form games of arbitrary size, between arbitrary numbers of players, and with arbitrary move and utility values, but is somewhat less efficient than a simple matrix.

A subtler but more extreme case of this tradeoff is how games are executed. The Game trait is quite generic, and implementers of this trait do not implement the execution of their game directly, but rather produce a description of how the game is executed. This is much less efficient, but enables generically transforming the execution of a game, for example, defining new games that modify the behavior of existing games.

An example of this capability in action is the Repeated type, which transforms any game into a repeated game, modifying the original game’s state and execution to enable players of the game to see the history of games played so far.

Of course, all things being equal, I’d still like things to run as fast as possible! However, if your application deals only with 2x2 numeric, normal-form games, and you need to run billions of iterations, this might not be the library you’re looking for.

§Experimentation over formal analysis

The library emphasizes exploring strategic situations through executing games and strategies and observing the results, rather than through formal, mathematical analysis of games. This is consistent with the expressiveness goal above, since many games that can be defined with the library may not be amenable to formal analysis.

However, the library will aim to provide analytic solutions where possible, since often a goal of experimental game theory is to compare various analytic solutions with each other and with other strategies.

§Example

The following example illustrates defining a few simple games and strategies, then executing them.

use itertools::*;
use std::sync::Arc;
use t4t::*;

// Possibles moves in social dilemma games, like the Prisoner's Dilemma.
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
enum DilemmaMove { Cooperate, Defect }

// The type of a 2-player social dilemma game with integer payoffs.
type Dilemma = Normal<DilemmaMove, i32, 2>;

// Define the Prisoner's Dilemma.
let pd: Dilemma = Normal::symmetric(
    vec![DilemmaMove::Cooperate, DilemmaMove::Defect],
    vec![2, 0, 3, 1]
).unwrap();

// Define two functions that produce players for playing social dilemma games. The game type is
// generic so that we can reuse these players later for repeated prisoner's dilemma.
fn nice<G: Game<2, Move = DilemmaMove>>() -> Player<G, 2> {
    Player::new("Nice".to_string(), || Strategy::pure(DilemmaMove::Cooperate))
}

fn mean<G: Game<2, Move = DilemmaMove>>() -> Player<G, 2> {
    Player::new("Mean".to_string(), || Strategy::pure(DilemmaMove::Defect))
}

// Play the game!
let result = pd.play(&Matchup::from_players([nice(), mean()]));
assert_eq!(result.unwrap().payoff(), &Payoff::from([0, 3]));

// Define the repeated prisoner's dilemma.
let rpd: Repeated<Dilemma, 2> = Repeated::new(Arc::new(pd), 100);

// Define a player that plays the famous tit-for-tat strategy.
let tit_for_tat: Player<Repeated<Dilemma, 2>, 2> = Player::new(
    "Tit-for-Tat".to_string(),
    || Strategy::new(|context: &Context<RepeatedState<Dilemma, 2>, 2>| {
        context
            .state_view() // get the repeated game state
            .history() // get the completed game history from the state
            .moves_for_player(context.their_index()) // get the moves for the other player
            .last() // take their last move only
            .unwrap_or(DilemmaMove::Cooperate) // play that, or cooperate if it's the first move
    }),
);

// Create a tournament in which every player plays every player, including themselves.
let tournament = Tournament::combinations_with_replacement(
    Arc::new(rpd),
    &vec![Arc::new(nice()), Arc::new(mean()), Arc::new(tit_for_tat)],
);

// Run all the matches in parallel and accumulate the resulting scores.
let results = tournament.play();
assert_eq!(
    results.score().best_to_worst(),
    vec![
        ("Tit-for-Tat", 699),
        ("Mean", 602),
        ("Nice", 600),
    ],
);

If you’d like to define your own new game forms or transformations, your best bet is currently to look at the source code for this crate and the t4t-games crate.

§This is a work in progress!

The library is very much a work-in-progress and will continue expanding and evolving.

The type- and method-level documentation is very good in places, minimal in others.

Normal-form games are in good shape, and repeated games are solid for perfect-information games. You can define players and strategies for these games, and they can be played.

There is a mechanism to efficiently run tournaments by playing a game with all combinations or permutations of a set of entrants.

There is a lot of infrastructure in place for sequential and state-based types, but the library is still missing the main top-level types to make this convenient to use.

Long-term, I’d like to add ways to visualize game executions and build games and strategies interactively, but we’ll see!

Modules§

for1
Defines indexes into a collection of type PerPlayer<T, 1>.
for2
Defines indexes into a collection of type PerPlayer<T, 2> and a move type for 2-player games.
for3
Defines indexes into a collection of type PerPlayer<T, 3> and a move type for 3-player games.
for4
Defines indexes into a collection of type PerPlayer<T, 4> and a move type for 4-player games.
for5
Defines indexes into a collection of type PerPlayer<T, 5>.
for6
Defines indexes into a collection of type PerPlayer<T, 6>.
for7
Defines indexes into a collection of type PerPlayer<T, 7>.
for8
Defines indexes into a collection of type PerPlayer<T, 8>.
for9
Defines indexes into a collection of type PerPlayer<T, 9>.
for10
Defines indexes into a collection of type PerPlayer<T, 10>.
for11
Defines indexes into a collection of type PerPlayer<T, 11>.
for12
Defines indexes into a collection of type PerPlayer<T, 12>.
for13
Defines indexes into a collection of type PerPlayer<T, 13>.
for14
Defines indexes into a collection of type PerPlayer<T, 14>.
for15
Defines indexes into a collection of type PerPlayer<T, 15>.
for16
Defines indexes into a collection of type PerPlayer<T, 16>.

Structs§

Context
The strategic context in which a player makes a move during a game.
Distribution
A weighted probability distribution over a set of discrete elements, such as moves.
Dominated
Captures a domination relationship between moves in a simultaneous move game.
Error
An error that occurred while playing a game and the current state when it occurred.
History
For repeated games, a history of previously played games.
Matchup
A collection of players ready to play a game.
Normal
A game represented in normal form.
Past
An iterator over past events while playing a game.
Payoff
A collection containing the utility values awarded to each player at the end of a game.
PerPlayer
A collection that stores one element corresponding to each player in a game.
PlayedMoves
An iterator over the moves played in a game.
Player
A player consists of a name and a function that produces its strategy.
PlayerIndex
An index into a per-player collection that is guaranteed to be in-range for a game with P players.
PlayerIndexes
An iterator that produces all player indexes of a given index type.
Ply
A ply is a single move played during a sequential game.
PossibleMoves
An iterator over the possible moves at a particular point in a game with a finite move set.
PossibleOutcomes
An iterator over all possible outcomes of a normal-form game.
PossibleProfiles
An iterator over all pure strategy profiles for a normal-form game.
Profile
A pure strategy profile for a simultaneous game: one move played by each player.
Repeated
A finitely repeated or iterated version of game G.
RepeatedState
The intermediate state of a repeated game.
Score
The cumulative utility for each player across all matchups in a tournament.
SequentialOutcome
A (potential) outcome of a sequential game.
Simultaneous
A game in which each player plays a single move without knowledge of the other players’ moves.
SimultaneousOutcome
A (potential) outcome of a simultaneous game.
Strategy
A strategy is a function from an intermediate game context to a move.
Summary
Tracks the number of moves played so far in a game.
Tournament
A tournament in which several players play a game against each other in a series of matchups.
TournamentResult
The collected results from running a tournament.
Transcript
A transcript of the moves played (so far) in a sequential game.
Turn
A description of one step in a game’s execution.

Enums§

Action
The next action to perform while playing a game.
ErrorKind
The kind of error that occurred.

Traits§

Game
A root trait that all games implement.
Move
A trait that collects the trait requirements of moves.
NextTurn
A function that yields the next turn in the game, given the current state and the result of the previous turn.
Outcome
A (potential) outcome of a game. A payoff combined with a record of the moves that produced it.
Record
A record of moves played during a game.
State
A trait that collects the trait requirements of a game state.
Utility
A trait that collects the trait requirements of payoff utility values.

Type Aliases§

PlayResult
The result of playing a game. Either an outcome or an error.
Plies
An iterator over the plies in a game.

Crate t4tCopy item path