Source-linked AI summary
OpenSpiel: A Framework for Reinforcement Learning in Games
Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, Daniel Hennes, Dustin Morrill, Paul Muller, Timo Ewalds, Ryan Faulkner, János Kramár, Bart De Vylder, Brennan Saeta, James Bradbury, David Ding, Sebastian Borgeaud, Matthew Lai, Julian Schrittwieser, Thomas Anthony, Edward Hughes, Ivo Danihelka, Jonah Ryan-Davis
TL;DR
OpenSpiel addresses the need for a broad framework spanning diverse games, reinforcement-learning environments, and search or planning methods. It provides a simple, extensible C++/Python platform with many games and algorithms, and identifies perfect recall as important for convergence guarantees. Its scope is constrained by platform support and by the episodic, undiscounted-return convention used in the game definitions.
Problem
Research on reinforcement learning and search in games spans many game types and related formalisms, motivating a general framework for studying them together.
Method
OpenSpiel combines over 20 game implementations with C++ and Python APIs, learning and search algorithms, and tools for evaluating learning dynamics and other metrics.
Results
Perfect recall is important for determining convergence guarantees for exact tabular algorithms.
Takeaways & Limitations
OpenSpiel offers a broad, simple, and extensible platform for research across diverse game structures and multiagent reinforcement-learning settings.
Takeaways & Limitations
OpenSpiel has been tested on Linux and macOS, offers limited Windows support, and defines rewards without discounting because most games are episodic.
Abstract
from arXiv · showhide
OpenSpiel is a collection of environments and algorithms for research in general reinforcement learning and search/planning in games. OpenSpiel supports n-player (single- and multi- agent) zero-sum, cooperative and general-sum, one-shot and sequential, strictly turn-taking and simultaneous-move, perfect and imperfect information games, as well as traditional multiagent environments such as (partially- and fully- observable) grid worlds and social dilemmas. OpenSpiel also includes tools to analyze learning dynamics and other common evaluation metrics. This document serves both as an overview of the code base and an introduction to the terminology, core concepts, and algorithms across the fields of reinforcement learning, computational game theory, and search.
1.2. OpenSpiel At a Glance
OpenSpiel provides a framework for writing games and algorithms and evaluating them across varied benchmark games. Its documented components included over 20 games and implementations in C++ and Python, with tables dated October 2019.
- OpenSpiel provides a framework for writing games, algorithms, and evaluations across varied benchmark games.
- The library included over 20 games spanning perfect-information, simultaneous-move, imperfect-information, gridworld, auction, and normal-form games.
- Game implementations were written in C++ and wrapped in Python, while algorithms were implemented in C++ and/or Python.
- OpenSpiel was tested on Linux and MacOS, with limited Windows support.
- As of October 2019, Tables 1 and 2 listed the implemented games and algorithms, but they were no longer maintained as current inventories.
2. Getting Started
OpenSpiel can be built and used through C++ and Python examples, with documented procedures for installation, testing, and extending games or algorithms. Platform support is strongest on Linux and macOS, with limited Windows support.
- Installation and platform support: OpenSpiel provides installation and build instructions for Ubuntu, Debian Linux, and macOS, with limited support for Windows.Linux instructions currently assume Debian-based distributions, although dependencies exist elsewhere under different package-manager names.
- Python setup: Python imports require adding the project and build directories to PYTHONPATH after installation.The instructions distinguish the Python modules from the pyspiel Python bindings.
- Running examples: After building, users can run binaries that list registered games, play Tic-Tac-Toe, and execute tests or other examples.Examples include C++ binaries such as games/backgammon_test and Python programs for Breakthrough and matrix games.
- Extending OpenSpiel: New games are added by copying an existing game’s header, source, and test files, implementing the API, then rebuilding and rerunning tests.Suggested starting points cover perfect-information, chance, simultaneous-move, and imperfect-information games.
- Extending OpenSpiel: New algorithms can start from existing C++ or Python implementations, but no specific algorithm structure or API is required.Algorithms are classes or functions used externally, with tests and example executables illustrating their use.
3. Design and API
OpenSpiel is designed as a simple, broad, and extensible framework for representing diverse multiagent games and connecting game-theoretic and reinforcement-learning concepts. Its API supports procedural game histories, hidden information, chance, simultaneous moves, and standard policy and transition abstractions.
- API and implementation: The framework uses a C++ foundation exposed through Python bindings, with games in C++ and most machine-learning algorithms in Python.This division supports efficient basic algorithms while retaining Python-based learning workflows.
- Design principles: OpenSpiel prioritizes simplicity, understandability, extensibility, and breadth, using reference implementations for learning and prototyping rather than fully optimized code.The framework is intended for researchers across potentially different fields and programming-language backgrounds.
- Game representation: Games are represented as procedural extensive-form games, with extensions for cyclic settings such as Markov decision processes and Markov games.The formalism begins with players, actions, histories, terminal histories, utilities, turn structure, and states.
- Game representation: A history represents the true world state, while legal actions are state-dependent and private actions may remain unrevealed through the chosen information partition.This distinction supports games with imperfect information.
- Game categories: OpenSpiel distinguishes constant-sum, zero-sum, identical-interest, and general-sum games by constraints on players’ terminal utilities.These correspond respectively to strictly competitive, strictly cooperative, and unconstrained or intermediate interactions.
- Move structure: Simultaneous-move games let all players choose a joint action at once and can also be represented as imperfect-information extensive-form games.Rock–Paper–Scissors illustrates the equivalence: sequentially writing hidden actions preserves simultaneous revelation.
- Move structure: Normal-form games are simultaneous-move games with one state, while matrix games additionally have two players.Turn-based games can be embedded in simultaneous-move games by assigning empty or pass-action sets to players who are not acting.
- RL abstractions: Policies map states to action distributions, transitions map state-action pairs to successor-state distributions, and chance follows a fixed stochastic policy.Transition functions can equivalently be represented with intermediate chance nodes.
3.2. Algorithms and Results
OpenSpiel implements algorithms for exact evaluation, dynamic programming, search, optimization, and reinforcement learning across varied game settings. Its methods accommodate chance, simultaneous moves, partial observability, and state-dependent legal actions.
- Evaluation and dynamic programming: Trajectory algorithms collect episode data under a joint policy, while expected returns computes all players’ expected returns exactly by tree traversal.Collected data include visited states, policies, sampled actions, returns, and episode lengths.
- Evaluation and dynamic programming: Value iteration supports single-agent games and two-player turn-taking zero-sum games using the identities V1(s) = −V2(s) and r1(s,a,s′) = −r2(s,a,s′).
- Search: OpenSpiel’s vanilla UCT MCTS uses random playouts and explicitly samples chance-node actions from their probability distributions.
- Search: Minimax computes depth-limited adversarial backups, maximizing at the current player’s states and minimizing at opponents’ states under deterministic transitions.The implementation also includes expectiminimax for chance nodes; ∗-minimax cutoffs are not currently implemented.
- Game-theoretic optimization: OpenSpiel includes matrix-game solvers, sequence-form linear programming for two-player zero-sum extensive-form games, and dominated-action checks.
- Reinforcement learning: DQN, A2C, and EVA operate in single-agent environments and can also run independently for players or compute approximate best responses.Implementations account for state-dependent legal actions, including masked softmax policies that assign zero probability to illegal actions.
- Partially observable games: OpenSpiel includes many algorithms for partially observable zero-sum games, reflecting the core team’s research focus.
Best Response and NashConv
OpenSpiel measures strategic stability through players’ incentives to deviate from a joint policy. NashConv aggregates these incentives, while approximate equilibria bound each individual deviation incentive.
- A best response maximizes player i’s return against the other players’ policies, and multiple best responses may exist.
- An approximate ϵ-Nash equilibrium requires δi(π) ≤ ϵ for every player, with exact Nash equilibrium at ϵ = 0.
- Convergence rates in practice are evaluated with aggregate deviation-based metrics, including NashConv and a related metric for two-player constant-sum games.
- Nash equilibria are often treated as optimal in two-player zero-sum games because they guarantee maximal worst-case returns against any opponent policy.The same statement is given for approximate equilibria, motivating convergence analysis in this class of games.
Fictitious Play and Best Response-Based Iterative Algorithms
OpenSpiel implements fictitious-play variants that iteratively respond to opponents’ average or meta-policies. Exploitability Descent replaces fictitious play’s second step to support policy convergence and reinforcement-learning-style function approximation.
- Fictitious play: Fictitious play starts from a uniform random policy and repeatedly computes each player’s best response to the opponents’ average policy.
- Fictitious play: XFP is equivalent to classical fictitious play, while Fictitious Self-Play uses supervised learning for average policies and reinforcement learning for approximate best responses.NFSP scales these ideas with neural networks and a reservoir-sampled buffer.
- Meta-policy methods: The fictitious-play average policy is equivalent to a meta-policy assigning uniform weight to all previous best-response policies.
- Meta-policy methods: PSRO generalizes fictitious play and double-oracle methods by analyzing the induced meta-game with empirical game-theoretic analysis.
- Exploitability Descent: Exploitability Descent replaces fictitious play’s second step with policy-gradient ascent against state-action values under opponents’ best responses.This enables convergence of the policies themselves and makes optimization compatible with reinforcement-learning-style general function approximation.
- Results: Figure 1 plots XFP and ED convergence on partially observable games using iterations on the x-axis and NashConv on the y-axis.
Counterfactual Regret Minimization
Counterfactual Regret Minimization computes approximate equilibria by assigning counterfactual values to information-state actions and independently minimizing regret at each information state.
- Scope and impact: CFR is a policy-iteration algorithm for approximate equilibria in two-player zero-sum games and has driven major advances in poker AI.
- Core procedure: CFR defines counterfactual state-action values and decomposes regret minimization across information states, causing the average policy of two CFR players to approach an approximate equilibrium.
- Counterfactual values: Reach probabilities multiply players’ state-action probabilities along a history and decompose into player i’s and opponents’ contributions.
- Counterfactual values: The counterfactual state-action value is defined for the player acting at state s using terminal histories passing through that state.
- Regret minimization: CFR begins with a uniform random policy, computes instantaneous counterfactual regret, accumulates regret, and updates policies using regret matching.
- Variants: Monte Carlo CFR variants include outcome sampling and external sampling, alongside CFR+.
Regression CFR
Regression CFR combines counterfactual-regret minimization with function approximation by learning cumulative or average regrets instead of storing them in a table. OpenSpiel also includes related regret-based policy-gradient methods and Neural Replicator Dynamics, with convergence evaluated in Leduc poker.
- Regression CFR: RCFR trains a regressor to predict cumulative or average counterfactual regrets rather than reading regrets from a table.OpenSpiel’s implementation uses neural networks with raw information-state inputs.
- Regression CFR: Deep CFR extends these ideas to larger games using convolutional networks, external-sampling Monte Carlo CFR, and a reservoir-sampled buffer.
- Regret Policy Gradients: CFR can be viewed as a tabular all-actions policy-gradient algorithm using generalized infinitesimal gradient ascent at each state.
- Regret Policy Gradients: OpenSpiel includes QPG, RPG, RMGP, and batched A2C; RPG optimizes toward a no-regret region using positive regret as its loss signal.The motivation given is that a policy with zero regret is an equilibrium policy.
- Neural Replicator Dynamics: NeuRD differentiates with respect to logits rather than through the softmax, avoiding the ℓ2 policy projections required by the earlier CFR policy-gradient connection.Its updates are not weighted by the policy, making it more adaptive to environmental changes in non-stationary domains.
- Evaluation: Figure 3 reports convergence rates for NFSP and regret-based policy-gradient algorithms in 2-player Leduc poker, with averaged curves over the top five seeds and hyperparameter settings.The dashed line marks the lowest exploitability, around 0.2, reached by any individual run.
3.3. Tools and Evaluation
OpenSpiel provides visualization and evaluation tools for game trees, learning dynamics, and evolutionary agent rankings. These include phase portraits for replicator dynamics and α-Rank analyses based on Markov transition matrices.
- Tools and Evaluation: OpenSpiel’s visualization and evaluation tools are contained primarily in the python/egt and python/visualizations directories.
- Visualizing a Game Tree: Graphviz can visualize game trees, with an example generated by the visualization example.
- Visualizing a Game Tree: The Kuhn poker visualization uses colored edges for chance and player actions, nodes for histories and information states, dotted boxes for information-state groupings, and diamonds for terminal utilities.
- Learning Dynamics: Phase portraits show vector fields or trajectories representing local policy changes under specified update dynamics.OpenSpiel provides examples for single-population replicator dynamics in Rock–Paper–Scissors and two-population dynamics in four bimatrix games.
- α-Rank: α-Rank ranks agents through an evolutionary-game-theoretic Markov transition matrix whose states are tuples of agents and whose rankings correspond to a Markov-Conley Chain.Unlike Elo, it can rank agents with intransitive relations such as Rock, Paper, and Scissors.
- α-Rank: OpenSpiel supports α-Rank for symmetric and multi-population games specified by payoff tables, payoff tensors, or Heuristic Payoff Tables.The framework can also visualize α-Rank transition matrices for Rock–Paper–Scissors and a 3-player Kuhn poker meta-game.
4. Guide to Contributing
The contribution process directs prospective contributors to OpenSpiel’s roadmap and design guidance while emphasizing coordination with the development team. Contributors should also account for possible copyright requirements for some games.
- Finding Contribution Opportunities: Potential contributors are directed to the roadmap and call for contributions on GitHub for future-work ideas and project direction.
- Contribution Process: Before making a contribution, developers should read the design philosophy and contact the team before writing a large piece of code.This helps identify overlapping work and obtain implementation advice.
- Legal Considerations: Some games may have copyrights requiring legal approval before contribution or distribution.
- Communication: Project-related questions should be raised through a GitHub issue so responses remain visible to the team and wider community.