games.md

Available games

: thoroughly-tested. In many cases, we verified against known values and/or reproduced results from papers.

~: implemented but lightly tested.

X: known issues (see code for details).

Status	Game
~	2048
~	Amazons
~	Atari
	Backgammon
~	Bargaining
~	Battleship
~	Blackjack
	Breakthrough
	Bridge
	(Uncontested) Bridge bidding
~	Catch
~	Checkers
~	Cliff Walking
~	Clobber
~	Coin Game
~	Colored Trails
	Connect Four
~	Cooperative Box-Pushing
	Chess
~	Dark Hex
~	Deep Sea
~	Dou Dizhu
~	Euchre
	First-price Sealed-Bid Auction
	Gin Rummy
	Go
	Goofspiel
	Hanabi
	Havannah
	Hearts
~	Hex
~	Kriegspiel
	Kuhn poker
~	Laser Tag
	Leduc poker
~	Lewis Signaling
	Liar's Dice
~	Mensch ärgere Dich nicht
~	Mancala
~	Markov Soccer
	Matching Pennies (Three-player)
	Mean Field Game : garnet
	Mean Field Game : crowd modelling
	Mean Field Game : crowd modelling 2d
	Mean Field Game : linear quadratic
	Mean Field Game : predator prey
	Mean Field Game : routing
~	Morpion Solitaire (4D)
	Negotiation
~	Nim
~	Oh Hell
	Oshi-Zumo
	Oware
~	Pathfinding
	Pentago
~	Phantom Go
~	Phantom Tic-Tac-Toe
	Pig
~	Poker (Hold 'em)
	Quoridor
~	Reconnaissance Blind Chess
	Routing game
~	Sheriff
~	Slovenian Tarok
~	Skat (simplified bidding)
~	Solitaire (K+)
	Tic-Tac-Toe
	Tiny Bridge
	Tiny Hanabi
	Trade Comm
~	Ultimate Tic-Tac-Toe
	Y

Details

2048

• A single player game where player aims to create a 2048 tile by merging other tiles.
• Numbers on a grid.
• Modern game.
• Non-deterministic.
• Perfect information.
• 1 player.
• Github

Amazons

• Move pieces on a board trying to block opponents from moving.
• Pieces on a grid.
• Modern game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Atari

• Agent plays classic games from Gym's Atari Environments, such as Breakout.
• Single player.
• Most games are non-deterministic.
• Perfect information.

Backgammon

• Players move their pieces through the board based on the rolls of dice.
• Idiosyncratic format.
• Traditional game.
• Non-deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Bargaining

• Agents negotiate for items in a pool with different (hidden) valuations.
• Research game.
• Non-deterministic (randomized pool and valuations).
• Imperfect information.
• 2 players.
• Lewis et al. '17, DeVault et al. '15

Battleship

• Players place ships and shoot at each other in turns.
• Pieces on a board.
• Traditional game.
• Deterministic.
• Imperfect information.
• 2 players.
• Good for correlated equilibria.
• Farina et al. '19, Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks. Based on the original game (wikipedia)

Blackjack

• Simplified version of blackjack, with only HIT/STAND moves.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 1 player.
• Wikipedia

Breakthrough

• Simplified chess using only pawns.
• Pieces on a grid.
• Modern game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Bridge

• A card game where players compete in pairs.
• Card game.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 4 players.
• Wikipedia

(Uncontested) Bridge bidding

• Players score points by forming specific sets with the cards in their hands.
• Card game.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Wikipedia

Catch

• Agent must move horizontally to 'catch' a descending ball. Designed to test basic learning.
• Agent on a grid.
• Research game.
• Non-deterministic.
• Perfect information.
• 1 players.
• Mnih et al. 2014, Recurrent Models of Visual Attention,
  Osband et al '19, Behaviour Suite for Reinforcement Learning, Appendix A

Checkers

• Players move pieces around the board with the goal of eliminating the opposing pieces.
• Pieces on a grid.
• Traditional game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Cliff Walking

• Agent must find goal without falling off a cliff. Designed to demonstrate exploration-with-danger.
• Agent on a grid.
• Research game.
• Deterministic.
• Perfect information.
• 1 players.
• Sutton et al. '18, page 132

Clobber

• Simplified checkers, where tokens can capture neighbouring tokens. Designed to be amenable to combinatorial analysis.
• Pieces on a grid.
• Research game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Coin Game

• Agents must collect their and their collaborator's tokens while avoiding a third kind of token. Designed to test divining of collaborator's intentions
• Agents on a grid.
• Research game.
• Non-deterministic.
• Imperfect information (all players see the grid and their own preferences, but not the preferences of other players).
• 2 players.
• Raileanu et al. '18, Modeling Others using Oneself in Multi-Agent Reinforcement Learning

Colored Trails

• Agents negotiations for chips that they they play on a colored grid to move closer to the goal.
• Agents on a grid.
• Research game.
• Non-deterministic (randomized board & chip configuration).
• Imperfect information.
• 3 players.
• Ya'akov et al. '10, Fecici & Pfeffer '08, de Jong et al. '11

Connect Four

• Players drop tokens into columns to try and form a pattern.
• Tokens on a grid.
• Traditional game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Cooperative Box-Pushing

• Agents must collaborate to push a box into the goal. Designed to test collaboration.
• Agents on a grid.
• Research game.
• Deterministic.
• Perfect information.
• 2 players.
• Seuken & Zilberstein '12, Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs

Chess

• Players move pieces around the board with the goal of eliminating the opposing pieces.
• Pieces on a grid.
• Traditional game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Dark Hex

• Hex, except the opponent's tokens are hidden. (Imperfect-information version)
• Uses tokens on a hex grid.
• Research game.
• Deterministic.
• Imperfect information.
• 2 players.

Deep Sea

• Agent must explore to find reward (first version) or penalty (second version). Designed to test exploration.
• Agent on a grid.
• Research game.
• Deterministic.
• Perfect information.
• 1 players.
• Osband et al. '17, Deep Exploration via Randomized Value Functions

Dou Dizhu

• A three-player games where one player (dizhu) plays against a team of two (peasants).
• Uses a 54-card deck.
• Non-deterministic.
• Imperfect information.
• Three players.
• Wikipeda

Euchre

• Trick-taking card game where players compete in pairs.
• Card game.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 4 players.
• Wikipedia

First-price Sealed-Bid Auction

• Agents submit bids simultaneously; highest bid wins, and that's the price paid.
• Idiosyncratic format.
• Research game.
• Non-deterministic.
• Imperfect, incomplete information.
• 2-10 players.
• Wikipedia

Gin Rummy

• Players score points by forming specific sets with the cards in their hands.
• Card game.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Wikipedia

Go

• Players place tokens on the board with the goal of encircling territory.
• Tokens on a grid.
• Traditional game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Goofspiel

• Players bid with their cards to win other cards.
• Card game.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 2-10 players.
• Wikipedia

Hanabi

• Players can see only other player's pieces, and everyone must cooperate to win.
• Idiosyncratic format.
• Modern game.
• Non-deterministic.
• Imperfect information.
• 2-5 players.
• Wikipedia and Bard et al. '19, The Hanabi Challenge: A New Frontier for AI Research
• Implemented via Hanabi Learning Environment

Havannah

• Players add tokens to a hex grid to try and form a winning structure.
• Tokens on a hex grid.
• Modern game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Hearts

• A card game where players try to avoid playing the highest card in each round.
• Card game.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 3-6 players.
• Wikipedia

Hex

• Players add tokens to a hex grid to try and link opposite sides of the board.
• Uses tokens on a hex grid.
• Modern game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia
• Hex, the full story by Ryan Hayward and Bjarne Toft

Kriegspiel

• Chess with opponent's pieces unknown. Illegal moves have no effect - it remains the same player's turn until they make a legal move.
• Traditional chess variant, invented by Henry Michael Temple in 1899.
• Deterministic.
• Imperfect information.
• 2 players.
• Wikipedia
• Monte Carlo tree search in Kriegspiel
• Game-Tree Search with Combinatorially Large Belief States, Parker 2005

Kuhn poker

• Simplified poker amenable to game-theoretic analysis.
• Cards with bidding.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Wikipedia

Laser Tag

• Agents see a local part of the grid, and attempt to tag each other with beams.
• Agents on a grid.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Leibo et al. '17, Lanctot et al. '17

Leduc poker

• Simplified poker amenable to game-theoretic analysis.
• Cards with bidding.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Southey et al. '05, Bayes’ bluff: Opponent modelling in poker

Lewis Signaling

• Receiver must choose an action dependent on the sender's hidden state. Designed to demonstrate the use of conventions.
• Idiosyncratic format.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Wikipedia

Liar's Dice

• Players bid and bluff on the state of all the dice together, given only the state of their dice.
• Dice with bidding.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Wikipedia

Mensch Aergere Dich Nicht

• Players roll dice to move their pegs toward their home row while throwing other players' pegs to the out area.
• Traditional game.
• Non-deterministic.
• Perfect information.
• 2-4 players.
• Wikipedia

Mancala

• Players take turns sowing beans on the board and try to capture more beans than the opponent.
• Idiosyncratic format.
• Traditional game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Markov Soccer

• Agents must take the ball to their goal, and can 'tackle' the opponent by predicting their next move.
• Agents on a grid.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Littman '94, Markov games as a framework for multi-agent reinforcement learning,
  He et al. '16, Opponent Modeling in Deep Reinforcement Learning

Matching Pennies (Three-player)

• Players must predict and match/oppose another player. Designed to have an unstable Nash equilibrium.
• Idiosyncratic format.
• Research game.
• Deterministic.
• Imperfect information.
• 3 players.
• "Three problems in learning mixed-strategy Nash equilibria"

Mean Field Game : routing

• Representative player chooses at each node where they go. They has an origin, a destination and a departure time and chooses their route to minimize their travel time. Time spent on each link is a function of the distribution of players on the link when the player reaches the link.
• Network with choice of route.
• Research game.
• Mean-field (with a unique player).
• Explicit stochastic game (only for initial node).
• Perfect information.
• Cabannes et. al. '21, Solving N-player dynamic routing games with congestion: a mean field approach.

Mean Field Game : Linear-Quadratic

• Players are uniformly distributed and are then incentivized to gather at the same point (The lower the distanbce wrt. the distribution mean position, the higher the reward). A mean-reverting term pushes the players towards the distribution, a gaussian noise term perturbs them. The players' actions alter their states linearly (alpha * a * dt) and the cost thereof is quadratic (K * a^2 * dt), hence the name. There exists an exact, closed form solution for the fully continuous version of this game.
• Research game.
• Mean-field (with a unique player).
• Explicit stochastic game (only for initial node).
• Perfect information.
• [Perrin & al. 2019 (https://arxiv.org/abs/2007.03458)]

Morpion Solitaire (4D)

• A single player game where player aims to maximize lines drawn on a grid, under certain limitations.
• Uses tokens on a grid.
• Traditional game.
• Deterministic
• Perfect information.
• 1 player.
• Wikipedia

Negotiation

• Agents with different utilities must negotiate an allocation of resources.
• Idiosyncratic format.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• Lewis et al. '17, Cao et al. '18

Nim

• Two agents take objects from distinct piles trying to either avoid taking the last one or take it. Any positive number of objects can be taken on each turn given they all come from the same pile.
• Traditional mathematical game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Oh Hell

• A card game where players try to win exactly a declared number of tricks.
• Card game.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 3-7 players.
• Wikipedia

Oshi-Zumo

• Players must repeatedly bid to push a token off the other side of the board.
• Idiosyncratic format.
• Traditional game.
• Deterministic.
• Imperfect information.
• 2 players.
• Buro, 2004. Solving the oshi-zumo game
  Bosansky et al. '16, Algorithms for Computing Strategies in Two-Player Simultaneous Move Games

Oware

• Players redistribute tokens from their half of the board to capture tokens in the opponent's part of the board.
• Idiosyncratic format.
• Traditional game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Pathfinding

• Agents must move to their desitnation.
• Agents on a grid. Single-agent game is the classic examples from Sutton & Barto.
• Research game.
• Non-deterministic (in multiagent, collisions resolved by chance nodes).
• Perfect information.
• 1-10 players.
• Similar games appeared in Austerweil et al. '15, Greenwald & Hall '03, and Littman '01.

Pentago

• Players place tokens on the board, then rotate part of the board to a new orientation.
• Uses tokens on a grid.
• Modern game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Phantom Go

• Go, except the opponent's stones are hidden. The analogue of Kriegspiel for Go.
• Research game.
• Deterministic.
• Imperfect information.
• 2 players.
• Cazenave '05, A Phantom Go Program

Phantom Tic-Tac-Toe

• Tic-tac-toe, except the opponent's tokens are hidden. Designed as a simple, imperfect-information game.
• Uses tokens on a grid.
• Research game.
• Deterministic.
• Imperfect information.
• 2 players.
• Auger '11, Multiple Tree for Partially Observable Monte-Carlo Tree Search,
  Lisy '14, Alternative Selection Functions for Information Set Monte Carlo Tree Search,
  Lanctot '13

Pig

• Each player rolls a dice until they get a 1 or they 'hold'; the rolled total is added to their score.
• Dice game.
• Traditional game.
• Non-deterministic.
• Perfect information.
• 2-10 players.
• Wikipedia

Poker (Hold 'em)

• Players bet on whether their hand of cards plus some communal cards will form a special set.
• Cards with bidding.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 2-10 players.
• Wikipedia
• Implemented via ACPC.

Quoridor

• Each turn, players can either move their agent or add a small wall to the board.
• Idiosyncratic format.
• Modern game.
• Deterministic.
• Perfect information.
• 2-4 players. (Note, from Wikipedia: "Though it can be played with 3 players, it's advised against. Since the 3rd player doesn't have player on the opposite side, they have an advantage.")
• Wikipedia

Reconnaissance Blind Chess

• Chess with opponent's pieces unknown, with sensing moves.
• Chess variant, invented by John Hopkins University Applied Physics Lab. Used in NeurIPS competition and Hidden Information Game Competition.
• Deterministic.
• Imperfect information.
• 2 players.
• JHU APL Main site
• Markowitz et al. '18, On the Complexity of Reconnaissance Blind Chess
• Newman et al. '16, Reconnaissance blind multi-chess: an experimentation platform for ISR sensor fusion and resource management

Routing game

• Players choose at each node where they go. They have an origin, a destination and a departure time and choose their route to minimize their travel time. Time spent on each link is a function of the number of players on the link when the player reaches the link.
• Network with choice of route.
• Research game.
• Simultaneous.
• Deterministic.
• Perfect information.
• Any number of players.
• Cabannes et. al. '21, Solving N-player dynamic routing games with congestion: a mean field approach.

Sheriff

• Bargaining game.
• Deterministic.
• Imperfect information.
• 2 players.
• Good for correlated equilibria.
• Farina et al. '19, Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks.
• Based on the board game "Sheriff of Nottingham" (bbg)

Slovenian Tarok

• Trick-based card game with bidding.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 3-4 players.
• Wikipedia
• Luštrek et al. 2003, A program for playing Tarok

Skat (simplified bidding)

• Each turn, players bid to compete against the other two players.
• Cards with bidding.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 3 players.
• Wikipedia

Solitaire (K+)

• A single-player card game.
• Card game.
• Traditional game.
• Non-deterministic.
• Imperfect information.
• 1 players.
• Wikipedia and Bjarnason et al. '07, Searching solitaire in real time

Tic-Tac-Toe

• Players place tokens to try and form a pattern.
• Uses tokens on a grid.
• Traditional game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Tiny Bridge

• Simplified Bridge with fewer cards and tricks.
• Cards with bidding.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2, 4 players.
• See implementation for details.

Tiny Hanabi

• Simplified Hanabi with just two turns.
• Idiosyncratic format.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2-10 players.
• Foerster et al 2018, Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning

Trade Comm

• Players with different utilities and items communicate and then trade.
• Idiosyncratic format.
• Research game.
• Non-deterministic.
• Imperfect information.
• 2 players.
• A simple emergent communication game based on trading.

Ultimate Tic-Tac-Toe

• Players try and form a pattern in local boards and a meta-board.
• Uses tokens on a grid.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia

Y

• Players place tokens to try and connect sides of a triangular board.
• Tokens on hex grid.
• Modern game.
• Deterministic.
• Perfect information.
• 2 players.
• Wikipedia