Crate t4t

Expand description

Tit-for-tat (t4t) is a game theory library focusing on expressiveness, type safety, and experimentation. 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.

§Features

Defining games

The library provides a variety of types for defining common kinds of games:

GameTree: A very generic game-tree representation. This is not very convenient to use directly, but all games are eventually translated into this type in order to be executed.
Normal: A general representation of n-ary normal-form games. An arbitrary number of players simultaneously play a single move selected from a finite set of available moves.
Simultaneous: N-ary simultaneous games. Similar to Normal, except the set of moves available to each player may be non-finite.
Extensive (coming soon): A simple representation of extensive-form games, that is, games represented as complete game trees, where players take turns making moves, possibly with moves of chance interspersed.
Combinatorial: A trait for defining combinatorial games, that is, perfect-information games where players interact by sequentially making moves to modify a shared state.
Repeated: Games where another game is played repeatedly a given number of times.

Each of these game types represents a class of games that work in a similar way. Most new games can can be defined using the constructors on these types.

Each game type implements two or three traits:

Game: Defines associated types used by the rest of the library, such as the type of moves played by players during the game, the type of the intermediate game state, and the type of utility values awarded to players at the end of the game.
Playable: Defines a common interface for playing games via translation to the GameTree type.
Finite: Provides a method to enumerate the moves available to a player in games where this set is finite.

If you’d like to define your own completely new game forms or transformations, you will need to implement these traits. The best way to learn how to do this is currently to look at the source code for this crate and the t4t-games crate.

Defining players and strategies

A Player consists of an identifying name and a Strategy.

A Strategy provides a method to get the next move to play in a game, given the current strategic context. For example, for repeated games, the strategic context includes the history of games played so far.

There are several associated functions on the Strategy type for defining common types of strategies.

Running tournaments

The Tournament type provides a convenient way to efficiently play many instances of a game in parallel, with all combinations or permutations of a set of players, aggregating the results.

§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: Playable<2, Move = DilemmaMove>>() -> Player<G, 2> {
    Player::new("Nice".to_string(), || Strategy::pure(DilemmaMove::Cooperate))
}

fn mean<G: Playable<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(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<Repeated<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),
    ],
);

§Design priorities

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 evident 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 example of this tradeoff is how games are executed. The Game and Playable traits are quite generic. Implementers of these traits do not implement the execution of their game directly, but rather define a translation of the game into a generic game tree representation. This is less efficient, but enables manipulating game trees to modify 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 tree and extending the state stored at each node 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.

§Work in progress!

The library is a work-in-progress and will continue expanding and evolving. For now, expect breaking changes on even patch-level version changes. Minor version changes will indicate significant new features.

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.
History
For repeated games, a history of previously played games.
InvalidMove
An error caused by a player playing an invalid move.
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 in a series of matchups, executed in parallel.
TournamentResult
The collected results from running a tournament.
Transcript
A transcript of the moves played (so far) in a sequential game.

Enums§

GameTree
A node in a game tree.

Traits§

Combinatorial
A trait for defining combinatorial games.
Finite
In a finite game, there is a finite set of moves available on each turn.
Game
A root trait that all games implement.
Move
A trait that collects the trait requirements of moves.
NextGameTree
The outgoing edges of a node in a game tree, represented as a function.
NextMove
A function computing the next move for a player given a strategic context.
Outcome
A (potential) outcome of a game. A payoff combined with a record of the moves that produced it.
Playable
A shared interface for playing games.
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§

MatchupResults
A list of all results from a single matchup in a tournament.
PlayResult
A result while playing a game. Either a value of type T or an InvalidMove error.
Plies
An iterator over the plies in a game.
RepeatedGameTree
Game tree type for a Repeated game with stage game G.

Crate t4tCopy item path