Skip to content

Latest commit

 

History

History
920 lines (765 loc) · 30.2 KB

games.md

File metadata and controls

920 lines (765 loc) · 30.2 KB

Available games

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

🔶: implemented but lightly tested.

❌: known issues (see notes below and code for details).

Status Game
🔶 2048
🔶 Amazons
🔶 Atari
🟢 Backgammon
🔶 Bargaining
🔶 Battleship
🔶 Blackjack
🔶 Block Dominoes
🟢 Breakthrough
🟢 Bridge
🟢 (Uncontested) Bridge bidding
🔶 Catch
🔶 Checkers
🔶 Cliff Walking
🔶 Clobber
🔶 Coin Game
🔶 Colored Trails
🟢 Connect Four
🔶 Cooperative Box-Pushing
🟢 Chess
🔶 Crazy Eights
🔶 Dark Hex
🔶 Deep Sea
🟢 Dots and Boxes
🔶 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
🔶 Liar's Poker
🔶 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
🔶 Nine men's morris
🔶 Oh Hell
🟢 Oshi-Zumo
🟢 Oware
🔶 Pathfinding
🟢 Pentago
🔶 Phantom Go
🔶 Phantom Tic-Tac-Toe
🟢 Pig
🟢 Prisoner's Dilemma
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
🔶 Weighted Voting Games
🟢 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

Blackjack

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

Block Dominoes

  • Most simple version of dominoes.
  • Consists of 28 tiles, featuring all combinations of spot counts (also called pips or dots) between zero and six.
  • Traditional game.
  • Non-deterministic.
  • Imperfect information.
  • 2 players.
  • 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

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

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

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

Dots and Boxes

  • Players put lines between dots to form boxes to get points.
  • Traditional game.
  • Deterministic.
  • Perfect information.
  • 2 players.
  • Wikipedia

Crazy Eights

  • A precursor of UNO (see here).
  • Players try to match the rank or suit of the previous played card.
  • Eights are viewed as wild cards.
  • In an alternative version, special cards such as skip, reverse, draw-two are permitted.
  • Nondeterministic.
  • Imperfect 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

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.
  • Wikipedia

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

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

Kriegspiel

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

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

Liar's Poker

  • Players bid and bluff on the state of all hands, given only the state of their hand.
  • Cards with bidding.
  • Traditional game.
  • Non-deterministic.
  • Imperfect information
  • 2 or more 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

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

Nine men's morris

  • Two players put and move stones on the board to try to form mills (three adjacent stones in a line) to capture the other player's stones.
  • Traditional 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

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

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

Prisoner's Dilemma

  • Players decide on whether to cooperate or defect given a situation with different payoffs.
  • Simultaneous.
  • Traditional game.
  • Deterministic.
  • Perfect Information.
  • 2 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.
  • ❌ Known issues: see issues #778, #1033, and #1042.

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
  • ❌ Known issues: see #1158.

Reconnaissance Blind Chess

Routing game

Sheriff

Slovenian 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+)

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

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

Weighted Voting Games

  • Classic coalitional game.
  • Players each have a weight w_i, and there is a quota q.
  • Denote p the binary vector representing a coalition over n players. The utility is 1 is p dot w >= q, 0 otherwise.
  • n players.
  • Chalkiadakis, Elkind, & Wooldridge '12

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