LiteEFG

<p align="center"> <img src="resources/logo.webp" alt="Logo" width="120" height="120"> </p>

<h1 align="center">LiteEFG</h1>

<p align="center"> An effective and easy-to-use library for solving Extensive-form games. </p>

Table of Contents

• About the Project
• Installation
• Usage
• Example
• Baselines

About the Project

LiteEFG is an efficient Python library for solving Extensive-form games (EFGs) based on computation graph. By defining the local update-rule for an information set (infoset) with Python, LiteEFG will automatically distribute the computation graph to all infosets of the game. Compared to implementing purely by Python, LiteEFG can provide up to 100x aaceleration.

Speed of LiteEFG

To demonstrate the efficiency of LiteEFG, the computation time of running Counterfactual Regret Minimization (CFR) [1] for $100,000$ iterations, without sampling, in the following environments are provided.

The results are tested on Ubuntu with CPU: 13th Gen Intel(R) Core(TM) i7-13700K 3.40 GHz.

• Kuhn Poker: $\leq 0.5s$
• Leduc Poker: $10s$
• Goofspiel: $10s$
• 4-sided Liar's Dice: $45s$
• Liar's Dice: $2$ hours

Installation

pip install LiteEFG

or

git clone --recursive https://github.com/liumy2010/LiteEFG.git
cd LiteEFG
pip install .

Prerequisites

• open_spiel >= 1.2
• A compiler with C++17 support
• Pip 10+ or CMake >= 3.4 (or 3.14+ on Windows, which was the first version to support VS 2019)
• Ninja or Pip 10+

Usage

Structure of LiteEFG

To use LiteEFG, the user first need to specify the computation graph of the algorithm. The computation graph has 2 parts: backward, and forward.

Graphs

• Backward Graph. LiteEFG will enumerate the infosets in the reversed breadth-first order of infosets, and the computation defined in backward graph will be executed. The variables of backward graph are stored locally in each infoset
• Forward Graph. LiteEFG will enumerate the infosets in the breadth-first order of infosets, and the computation defined in forward graph will be executed. The variables of forward graph are stored locally in each infoset

To define graph nodes for backward / forward graph, user may use the following two class

• LiteEFG.backward(is_static=False, color=0): Within the with statement of this class, all graph nodes in the following will be defined in the backward graph
  • is_static indicates whether the graph node is static. If it is, then it will only be updated at initialization, otherwise update every time when calling Environment.update
  • color: Indicates the color of the nodes defined below. Then, during each update, the user may specify the node color that will be updated
• LiteEFG.forward(is_static=False, color=0): Within the with statement of this class, all graph nodes in the following will be defined in the forward graph

Here's an example of computing the Fibonacci sequence.

with LiteEFG.backward(is_static=True):
    a = LiteEFG.const(size=1, val=1.0)
    b = LiteEFG.const(size=1, val=1.0)

with LiteEFG.backward(is_static=False):
    c = a + b
    a.inplace(b.copy()) # change the value of a to b
    b.inplace(c.copy()) # change the value of b to c
    # The details of inplace and copy can be found in 
    # the following

Order of Update

• Initialize. The static computation will be executed once when initialize the environment. The order is still backward->forward. Initialization will be automatically done when calling env.set_graph(graph)
• Update. At every iteration when calling environment.update, the backward graph will be updated first. Then, the forward graph will be updated

Default Variables

LiteEFG prepare several default variables for easier implementation of algorithms. Note that all variables are stored locally for each infoset.

• utility: Updated every iteration. It stores the expected utility of each action of an infoset. For a two-player zero-sum game $\max_{\mathbf{x}}\min_{\mathbf{y}}\mathbf{x^\top A y}$, where $\mathbf{A}$ is the utility matrix, utility=$(\mathbf{Ay}^{tr})_{(I,a)}$ for max-player $\mathbf{x}$. $(\mathbf{x}^{tr}, \mathbf{y}^{tr})$ is the strategy fed into env.update
• action_set_size: The size of action set of an infoset
• reach_prob: The reach probabiltiy of player $p$ of an infoset, where $p$ is the player to take actions at that infoset
• opponent_reach_prob: The reach probability of players other than $p$ of an infoset
• subtree_size: A vector with size action_set_size, which stores the number of terminal (infoset, action) pairs in the subtree when taking an action

Operations

Basic Operations

• LiteEFG.set_seed: Set the seed for the pseudo-random number generator
• LiteEFG.random.uniform(x, lower=0.0, upper=1.0): Return a node with the same shape as x whose elements are sampled from uniform distribution in [lower, upper)
• LiteEFG.random.normal(x, mean=0.0, stddev=1.0): Return a node with the same shape as x whose elements are sampled from normal distribution
• LiteEFG.random.exponential(x, lambda_=1.0): Return a node with the same shape as x whose elements are sampled from exponential distribution with rate lambda_
• GraphNode.inplace(expression): The value of the expression will be stored to the original address of GraphNode
• GraphNode.sum() / LiteEFG.sum(x): Return sum of all elements of GraphNode
• GraphNode.mean() / LiteEFG.mean(x): Return mean of all elements of GraphNode
• GraphNode.max() / LiteEFG.max(x): Return max of all elements of GraphNode
• GraphNode.min() / LiteEFG.min(x): Return min of all elements of GraphNode
• GraphNode.copy(): Return the copy of GraphNode
• GraphNode.exp() / LiteEFG.exp(x): Return exponential of all elements of GraphNode. For every index $i$, let $x_i\to e^{x_i}$
• GraphNode.log() / LiteEFG.log(x): Return log of all elements of GraphNode. For every index $i$, let $x_i\to \ln(x_i)$
• GraphNode.argmax() / LiteEFG.argmax(x): Return argmax of GraphNode
• GraphNode.argmin() / LiteEFG.argmin(x): Return argmin of GraphNode
• GraphNode.euclidean() / LiteEFG.euclidean(x): Return $\frac{1}{2}\sum_i x_i^2$, where $\mathbf{x}$ is the vector stored at GraphNode GraphNode.negative_entropy(shifted=False) / LiteEFG.negative_entropy(x, shifted=False): Return $\sum_i x_i\ln(x_i)+\mathbf{1}(\text{shifted})\log N$, where $\mathbf{x}\in\mathbf{R}^N$ is the vector stored at GraphNode
• GraphNode.normalize(p_norm, ignore_negative=False) / LiteEFG.normalize(x, p_norm, ignore_negative=False): Normalize $\mathbf{x}$ by its $p$-norm. Specifically, $x_i\to \frac{x_i}{(\sum_j |x_j|^p)^{1/p}}$. When ignore_negative=True, $x_i\to \frac{[x_i]^+}{(\sum_j ([x_j]^+)^p)^{1/p}}$, where $[x_i]^+=x_i\cdot \mathbf{1}(x_i\geq 0)$.
• GraphNode.dot(y) / LiteEFG.dot(x, y): Return $\langle \mathbf{x}, \mathbf{y}\rangle$
• GraphNode.maximum(y) / LiteEFG.maximum(x, y): Return $\mathbf{z}$ with $z_i=\max(x_i,y_i)$. Also supports GraphNode.maximum(scalar) / LiteEFG.maximum(x, scalar)
• GraphNode.minimum(y) / LiteEFG.minimum(x, y): Return $\mathbf{z}$ with $z_i=\min(x_i,y_i)$. Also supports GraphNode.minimum(scalar) / LiteEFG.minimum(x, scalar)
• x**y: y should be a scalar and it will return $(x_1^y, x_2^y, ..., x_n^y)$
• LiteEFG.cat(nodes_list: list): Concatenate all nodes in the nodes_list

Game Specific Operations

• GraphNode.project(distance_name : ["L2", "KL"], gamma=0.0, mu=uniform_distribution): Project $\mathbf{x}\in\mathbf{R}^N$ to the perturbed simplex $\Delta_N:=\{\mathbf{v}\succeq \gamma\mathbf{\mu}\colon \sum_i v_i=1\}$, with respect to either Euclidean distance or KL-Divergence. By default, $\gamma=0.0$ and $\mathbf{\mu}=\frac{1}{N}\mathbf{1}$
• LiteEFG.project(x, distance_name, gamma=0.0, mu=uniform_distribution): Return x.project(distance_name, gamma, mu)
• LiteEFG.aggregate(x, aggregator_name : ["sum", "mean", "max", "min"], object_name : ["children", "parent"]="children", player : ["self", "opponents"]="self", padding=0.0): Aggregate variables from either object_name infoset. By default, object_name="children"
  • object_name="children": For each action a of infoset I, the vector stored in GraphNode x of subsequent infosets under (I,a) will be concatenated into one vector. Then, the vector will be aggregated via aggregator_name. At last, the resulted scalars of each (I,a) pair will be concatenated again and returned. Therefore, the returned GraphNode stores a vector of size action_set_size. If there's no subsequent infoset under an (I,a) pair, use padding as the scalar for (I,a)
  • object_name="parent": Assume I is a children of infoset-action pair (I',a'). If the vector stored at GraphNode x is of size action_set_size of infoset I', then its $(a')^{th}$ component will be returned. Otherwise, if x is simply a scalar, x will be returned. If no parent exists, return padding
  • player indicates whether to aggregate infosets belong to the player herself or aggregate infosets belong to opponents. An example can be found in LiteEFG/baselines/QFR.py

Environments

• Environment.update(strategies, upd_player=-1, upd_color=[-1], traverse_type="default"): Update the computation graph stored in the environment. strategies is a list of length num_players which specify the strategy used to traverse the game for each player. upd_player=-1 means that the graph of all players will be updated. Otherwise, only update the graph of upd_player. upd_color=[-1] means that all nodes will be updated. Otherwise, only node with the color in upd_color will be updated. An example can be found in LiteEFG/baselines/CMD.py. When traverse_type is "de