ifaamas [AAMAS ’24]Proc. of the 23rd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2024)May 6 – 10, 2024 Auckland, New
ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.) 2024 2024 Czech
Technical University in Prague Prague Czech Republic Sony AI University of
Alberta, Alberta Machine Intelligence Institute Edmonton Canada Czech
Technical University in Prague Prague Czech Republic

# Look-ahead Search on Top of Policy Networks
in Imperfect Information Games

Ondřej Kubíček<EMAIL_ADDRESS>,  Neil Burch<EMAIL_ADDRESS>and
Viliam Lisý<EMAIL_ADDRESS>
###### Abstract.

Conducting additional search during test time is often used to improve the
performance of reinforcement learning algorithms. Performing search in
adversarial games with imperfect information is notoriously difficult and
often requires a complicated training process. We present an algorithm that
uses an arbitrary policy-gradient algorithm that learns from sampled
trajectories in the setting of fully adversarial two-player games with
imperfect information. Alongside the training of the policy network, the
algorithm trains an additional critic network, which provides multiple
expected values if both players follow one of a fixed set of transformations
of the policy given by the policy network. These values are then used for
depth-limited search. We show how the values from this critic can create a
value function for imperfect information games. Moreover, they can be used to
compute the summary statistics necessary to start the search from an arbitrary
decision point in the game. The presented algorithm is scalable to very large
games since it does not require any search in the training time. Furthermore,
given sufficient computational resources, our algorithm may choose whether to
use search or play the strategy according to the trained policy network
anywhere in the game. We evaluate the algorithm’s performance when trained
alongside Regularized Nash Dynamics, and we compare the performance of using
the search against the policy network in the standard benchmark game of Leduc
hold’em, multiple variants of imperfect information Goofspiel, and in a game
of Battleships.

###### Key words and phrases:

Imperfect Information Games, Safe Search, Multi-agent Reinforcement Learning,
Value Function, Multi-Valued States, Regularized Nash Dynamics, Counterfactual
Regret Minimization, Multi-agent Search with Policy Transformation Value
Network

##  1\. Introduction

The field of multi-agent deep reinforcement learning has achieved remarkable
success in training strong agents for two-player adversarial games through
selfplay. Many of these agents develop strategies represented by neural
networks, which subsequently provide probability distributions for actions
based on current observations during gameplay.

Despite their success, the neural networks can occasionally lead the agent to
make suboptimal decisions that an adversarial opponent may exploit. Wang et
al.Wang et al. (2023) have illustrated how policy networks trained via
AlphaZero-style algorithms in Go are susceptible to exploitation, as evidenced
by winning against the trained policy network 97% of the time. Similarly, the
authors of Perolat et al. (2022) report that their trained agents display
evident gameplay errors, necessitating the application of multiple heuristics
to rectify these errors. However, there are principled ways of using search to
avoid these mistakes, as evidenced by AlphaZero Silver et al. (2018),
DeepStack Moravčík et al. (2017), and Student of Games Schmid et al. (2023).

Algorithms that use policy-gradient methods in imperfect information games
like Regularized Nash Dynamics (RNaD) Perolat et al. (2022); Perolat et al.
(2021) rely on directly applying the neural network’s policy during gameplay.
Adding search to these methods could improve the strategy and mitigate these
mistakes. It is important to note that this enhancement comes at the expense
of transitioning previously model-free algorithms into a model-dependent
during gameplay.

Adding search to these policy-gradient methods in imperfect information games
presents multiple challenges that are non-existent in a perfect information
case. Firstly, the imperfect information search must be performed not only
from the current state of the game but from all possible states that share the
same public information amongst all players. Secondly, the state values are
dependent on the strategies employed by each player. Thirdly, the opponent’s
strategy is unknown, and the optimal strategies are not unique. This means
that we need to optimize over all possible strategies the opponent may deploy
both in the remainder of the game as well as unobserved past actions.

In this paper, we introduce the algorithm Multi-agent Search with Policy
Transformation Value Network (SePoT), which builds upon the concept of multi-
valued states Brown et al. (2018). SePoT trains a policy deviation critic
network, that estimates the expected value of policies derived from the policy
network. This critic is trained alongside a policy network with a policy-
gradient technique without requiring any additional trajectories beyond those
sampled by the original policy-gradient algorithm. The critic network is
trained with an off-policy V-trace that estimates expected values against a
multitude of potential opponent strategies derived from the policy represented
by the policy network. We show that this critic provides sufficient
information to perform a safe search addressing all complications of search in
imperfect information games.

Furthermore, we present an approach that enables safe search at any point
within a game, utilizing only the information provided by the introduced
critic network and the policy network. This eliminates the need for conducting
search in all the game parts from the root until the current decision point, a
departure from prior methods Brown et al. (2018); Moravčík et al. (2017);
Schmid et al. (2023). This flexibility allows us to perform search only in
those game segments where we expect the strategy to be undertrained and we
have enough computational resources while employing the neural network policy
in other parts of the game.

Finally, we establish a connection between value functions and multi-valued
states within imperfect information games. With this connection, it becomes
possible to train previously used imperfect information value functions
Moravčík et al. (2017); Schmid et al. (2023) without the expensive search in
the training time.

In our experiments, we show that SePoT can effectively be combined with RNaD
Perolat et al. (2022). We show that using search in head-to-head play in
imperfect information Goofspiel and Battleships improves the performance over
the network trained with RNaD. Furthermore, we demonstrate that the
exploitability of policy derived from the search is lower than that of the
policy network from RNaD in a small version of imperfect information Goofspiel
and comparable in the standard benchmark game Leduc hold’em. Lastly, we show
how using history critic to perform a safe search instead of keeping the
statistics from previous searches affects the quality of the final solution.

Our main contributions are: (1) Adding search on top of the policy-gradient
method without requiring additional training trajectories. (2) Introducing
search technique that may be performed anywhere in the game without needing to
perform search in previous parts of the game. (3) Establishing a practical
connection between the multi-valued states and the value functions. (4)
Showing that the additional search improves the performance of RNaD.

##  2\. Motivation

(a) Player

(b) Opponent

State | P1 ship | P2 ship
---|---|---
$w_{1}$ | A1-A2 | A1-A3
$w_{2}$ | A1-A2 | A3-C3
$w_{3}$ | A2-B2 | A1-A3
$w_{4}$ | A2-B2 | A3-C3

(c) Possible States

Figure 1. Current state in a smaller version of Battleships and all possible
states sharing the same public information

Board state in smaller version of Battleships,

Consider a smaller version of Battleships, in which two players take turns
secretly placing three ships of sizes 3, 2, and 2 on a square grid of size 5.
Players take turns shooting on an opponent’s board after all ships are placed.
The player that first hits all tiles occupied by the opponent’s ships wins the
game. Let us suppose we are in the middle of the game, and the current boards
are shown in Figure 1. Each player knows their ship’s position but does not
know the opponent’s. Based on the public shooting actions up until this point,
we know that there are only two possible positions for the player and the
opponent. The player may have either placed the ship horizontally with the
upper left corner at position A1 or vertically with the upper left corner at
position A2. Similarly, the opponent may have placed the ship horizontally
with the upper left corner at position A1 or vertically with the upper left
corner at position A3. Possible positions are shown on each board with the
dashed rectangle. There are four possible states, that is, all possible
combinations between the positions across both players, as shown in Figure
1(c). The player cannot distinguish between states $w_{1}$ and $w_{2}$,
neither between $w_{3},w_{4}$. Similarly, the opponent cannot distinguish
between $w_{1},w_{3}$ and between $w_{2},w_{4}$. Shooting anywhere else than
A1, A2, A3, B3, and C3 does not make sense for a rational player. However,
training RNaD for three days results in a policy that shoots to these rational
tiles with a probability slightly above $40\%$.

Employing additional search should improve this policy, but doing so naively
in imperfect information games introduces multiple issues. The first issue is
that starting search only from states that are possible from the player’s
point of view, which are $w_{1}$ and $w_{2}$, would search only in those parts
of the game where the player placed the ship at A1-A2. This means that the
player incorrectly assumes the opponent knows the ship’s position during this
search. The outcome of the search would be that the game always ends in 2
turns because the opponent would rationally shoot at the ship. Since the
player requires at least three turns to win, it could never win against this
informed opponent, and its strategy would be to play randomly. However, in the
real gameplay scenario, the opponent lacks knowledge of the player’s ship’s
location, providing the first player with a genuine opportunity to win.
Nevertheless, this issue can be easily fixed by starting the search from all
four possible states, which does not make the same error.

The second issue is more profound. In practice, for many different reasons,
the player may incorrectly assume that the opponent is slightly more likely to
place his ship at position A1 instead of C3. In such a case, the player would
always shoot at either of tiles A1, A2, or A3 since it provides more reward in
expectation from its point of view. This leads to a strategy that could be
exploited by an adversarial opponent who would never put the ship there in the
first place. This is a well-studied problem in imperfect information games
Burch et al. (2014); Moravcik et al. (2016); Brown and Sandholm (2017); Brown
et al. (2020). One possible solution during search is to assume that the
opponent can play any strategy in earlier parts of the game. This assumption
then allows computing a more robust strategy against possible play from the
game’s previous and subsequent parts Burch et al. (2014); Moravcik et al.
(2016); Brown and Sandholm (2017).

The third issue for applying full search in the situation in Figure 1 is not
tractable since there are more than $10^{9}$ possible terminal histories.
Using a depth-limited search with a value function at the depth limit enables
search even with much less computational resources Kovařík et al. (2023);
Moravčík et al. (2017).

##  3\. Background

Factored-observation stochastic game (FOSG) Kovařík et al. (2022) is a tuple
$\mathcal{G}=(\mathcal{N},\mathcal{W},p,w^{0},\mathcal{A},\mathcal{T},\mathcal{R},\mathcal{O})$,
where $\mathcal{N}=\\{1,\dots,N\\}$ is a player set, $\mathcal{W}$ is the set
of states and $w^{0}$ is an initial state, $p:\mathcal{W}\rightarrow
2^{\mathcal{N}}$ is a player function, which for given state $w\in\mathcal{W}$
assigns currently acting players from $\mathcal{N}$,
$\mathcal{A}=\Pi_{i\in\mathcal{N}}\mathcal{A}_{i}$ is the space of joint
actions. We denote $\mathcal{A}_{i}(w)$ legal actions for player $i$ in world
state $w$. $\mathcal{T}:\mathcal{W}\times\mathcal{A}\rightarrow\mathcal{W}$ is
the transition functiion,
$\mathcal{R}:\mathcal{W}\times\mathcal{A}\rightarrow\mathbb{R}^{\mathcal{N}}$
is the reward function and
$\mathcal{O}:\mathcal{W}\times\mathcal{A}\times\mathcal{W}\rightarrow\mathbb{O}$
is the observation function. $\mathcal{O}$ is factored as
$\mathcal{O}=(\mathcal{O}_{0},\mathcal{O}_{1},\dots\mathcal{O}_{N})$, where
$\mathcal{O}_{0}$ are a public observations given to all players and
$\mathcal{O}_{i}$ are a private observations of player $i$. In this work, we
focus on two-player zero-sum games, where $\mathcal{N}=\\{1,2,c\\}$ and
$\mathcal{R}_{1}(w,a)=-\mathcal{R}_{2}(w,a)\;\forall\mathcal{W}\times\mathcal{A}$.
$c$ denotes a chance player who has publicly announced a non-changeable policy
throughout the game. Moreover, we study only games where neither player
forgets information once it receives it. This is a standard assumption by most
of the algorithms, and it is called perfect recall.

Trajectory $\tau=w^{0}a^{0}w^{1}a^{1}\dots
w^{t}\in(\mathcal{W}\mathcal{A})^{*}\mathcal{W}$ for which
$a^{l}\in\mathcal{A}(w^{l})$ and $w^{l+1}=\mathcal{T}(w^{l},a^{l})$ is a
finite sequence of states and actions in the game. Trajectory utility for
player $i$ is a cumulative reward
$u_{i}(\tau)=\sum_{t=0}^{l-1}\mathcal{R}_{i}(w^{t},a^{t})$. We use
$\mathcal{H}$ to denote histories, which are trajectories that start in the
initial state $w^{0}$. $\mathcal{Z}=\\{z\in\mathcal{H}|z\text{ is
terminal}\\}$ are histories in which neither player has an action to play,
effectively ending the game. $h\sqsubseteq h^{\prime}$ means that $h^{\prime}$
extends $h$ and $h^{0}$ is an initial history, that corresponds to the initial
state $w^{0}$, before any player played any action. Each history ends with
some world state $w^{l}$. Therefore we denote
$\mathcal{R}_{i}(h,a)=\mathcal{R}_{i}(w^{l},a)$ as a reward given to player
$i$, if in history $h\in\mathcal{H}$ the players play joint action $a$. Since
player $i$ does not observe the state of the game directly, but only observes
its actions $\mathcal{A}_{i}$, private observations $\mathcal{O}_{i}$ and
public observations $\mathcal{O}_{0}$, it cannot distinguish between multiple
different histories. We say that these indistinguishable histories are in the
same infoset $s_{i}\in\mathcal{S}_{i}$. If two histories
$h,h^{\prime}\in\mathcal{H}$ belong to the same infoset $s_{i}$, then player
$i$ has to have the same actions in these histories and $s_{i}(h)$ denotes an
infoset of player $i$ in history $h$. We will use $\mathcal{A}_{i}(s_{i})$ to
denote these available actions in infoset $s_{i}$. Furthermore, we will use a
notion of public-states $s_{0}\in\mathcal{S}_{0}$, which may be viewed as an
information set for an external player which does not act in the game. Two
histories belong to the same public state if they have the same sequence of
public observations from the initial state. Each public state is made from
multiple information sets for a given player $i$. We will use
$\mathcal{S}_{i}(s_{0})$ to denote all infoset that are in public state
$s_{0}$ and $\mathcal{H}(s)$ to denote all histories in an infoset $s$.

Policy of player $i$ is a mapping
$\pi_{i}:\mathcal{S}_{i}\rightarrow\Delta\mathcal{A}_{i}$ s.t.
$\pi_{i}(s_{i})\in\Delta\mathcal{A}_{i}(s_{i})$. $\Pi_{i}$ is a set of all
policies of player $i$. We will use $\pi_{i}(s_{i},a_{i})$ to denote the
probability of playing action $a_{i}$ in $s_{i}$, while following the policy
$\pi_{i}$. A strategy profile is defined as $\pi=(\pi_{1},\dots,\pi_{N})$, and
$\pi_{-i}$ is used to denote a strategy profile without the policy of player
$i$.

Expected utility, if all players play according to strategy profile $\pi$ from
history $h$ onward is defined as
$u^{\pi}_{i}(h)=\mathbb{E}_{\tau\sim\pi|h}u_{i}(\tau)$.
$P^{\pi}(h)=\prod_{h^{\prime}aw\sqsubseteq
h}\prod_{j\in\mathcal{N}}\pi_{j}(s_{j}(h^{\prime}),a_{j})$ is a probability of
reaching history $h$ if all players play according to strategy profile $\pi$.
This may be separated into $P^{\pi}(h)=P^{\pi}_{i}(h)P^{\pi}_{-i}(h)$, where
$P^{\pi}_{i}(h)$ is only a players $i$ contribution to reaching history $h$,
similarly $P^{\pi}_{-i}(h)$ is a contribution of all the others players except
$i$, which is called counterfactual reach probability. Counterfactual values
for infoset $s_{i}$ is a sum of expected utilities of each history $h$ within
the same infoset, weighted by the counterfactual reach probability of this
history
$v_{i}^{\pi}(s_{i})=\frac{\sum_{s_{i}(h)=s_{i}}P^{\pi}_{-i}(h)u_{i}^{\pi}(h)}{\sum_{s_{i}(h)=s_{i}}P^{\pi}_{-i}(h)}$.

Best response against policy $\pi_{i}$ of a player $i$ is a policy
$\pi_{-i}^{{BR}}\in{BR}_{i}(\pi_{i})$, where
$u^{(\pi_{i},\pi^{{BR}}_{-i})}_{i}(h^{0})\geq
u^{(\pi_{i},\pi_{-i}^{\prime})}_{i}(h^{0})$ for all $\pi_{-i}^{\prime}$. If
all players play a best response to each other, then the resulting policy
profile $\pi^{{NE}}$ is called Nash equilibrium. The usual metric to compare
strategies in two-player zero-sum games is an exploitability
$\mathcal{E}(\pi_{i})=u^{(\pi_{i},\pi^{BR}_{-i})}_{-i}(h^{0})-u^{\pi^{NE}}_{-i}(h^{0})$,
that is how much utility can opponent get if it plays best response to the
player’s strategy, compared to the utility of Nash equilibrium. If player $i$
plays Nash equilibrium, then the exploitability is 0.

###  3.1. Depth-limited solving

Range $r_{i}\in\Delta\mathcal{S}_{i}(s_{0})$ for player $i$ in public state
$s_{0}$ is a probability distribution over infosets $s_{i}\leavevmode\nobreak\
\in\leavevmode\nobreak\ \mathcal{S}_{i}(s_{0})$ in public state $s_{0}$, which
corresponds to player’s contribution to the probability of reaching this
infoset if it followed the policy $\pi_{i}$. Furthermore range for public
state $s_{0}$ is defined as
$r=(r_{1},\dots,r_{N})\in\Delta\mathcal{S}_{1}(s_{0})\times\dots\times\Delta\mathcal{S}_{N}(s_{0})$.
A public belief state is a public state with associated range
$\beta=(s_{0},r)$. Optimal value function is a function
$\boldsymbol{v}^{*}(\beta)\in\mathbb{R}^{|\mathcal{S}_{1}(s_{0})|\dots|\mathcal{S}_{N}(s_{0})|}$,
that for given public belief state $\beta$ returns counterfactual values
$v^{\pi}_{i}(s_{i})$ for each player $i$ and infoset
$s_{i}\in\mathcal{S}_{i}(s_{0})$ associated with public belief state $\beta$
if both players played optimally from that point onward based on associated
ranges $r$. Value function $\boldsymbol{v}(\beta)$ is then defined similarly
as optimal value function, but it’s output could be noisy. For any public
belief state, we can construct subgame $\mathcal{G}(\beta)$, which is the same
FOSG as $\mathcal{G}$, but it starts in $s_{0}$ with initial ranges $r$
instead of the initial state. Depth-limited subgame is defined as
$\mathcal{G}^{\text{DL}}(\beta)$. However, after some depth limit, the value
function $\boldsymbol{v}$ is called and returned counterfactual values are
used as a terminal values.

Resolving some subgame to improve blueprint policy $\pi$ naively would involve
fixing policy $\pi$ for all players in previous parts of the game and using
single $w^{A}$, where players act with corresponding ranges. However, this may
result in a much more exploitable strategy Burch et al. (2014); Moravcik et
al. (2016); Brown and Sandholm (2017) than the original blueprint $\pi$.
Multiple techniques were developed to deal with this issue in two-player zero-
sum games Burch et al. (2014); Moravcik et al. (2016); Brown and Sandholm
(2017); Brown et al. (2020). In this work we will focus on the one proposed in
Burch et al. (2014). When resolving from the perspective of player $i$, it
constructs a slightly modified subgame called a gadget game
$\mathcal{G}^{G}_{i}(\beta,v^{\pi}_{o})$, where $v^{\pi}_{o}$ are
counterfactual values for each infoset $s_{o}\in\mathcal{S}_{o}(s_{0})$ of
opponent $o$ in a current public state $s_{0}$, when players play according to
policy $\pi$. This subgame has the artificial state $w^{A}$ as an initial
state, but instead of using full ranges $r$, it uses only ranges $r_{i}$ and
$r_{c}$. Directly after this artificial state, $|\mathcal{H}(s_{0})|$
opponent’s decision nodes are separated into multiple infosets based on the
information player has in a given history. The opponent $o$ has a choice to
either terminate the game and receive the counterfactual value
$v^{\pi}_{o}(s_{o})$ or continue the game as in the original subgame.

Suppose that after the depth limit, the optimal value function is used and
that the counterfactual values $v^{\pi^{{NE}}}_{o}(s_{o})$ used in the gadget
game are computed for Nash equilibrium policy $\pi^{{NE}}$. Then the solution
of gadget game $\mathcal{G}^{G}_{i}(\beta,v^{\pi}_{o})$ is part of a Nash
equilibrium in the entire game Burch et al. (2014); Kovařík et al. (2023).

In this work, we focus on an alternative to the value function called multi-
valued states Brown et al. (2018), which, after the depth limit, gives the
opponent the choice to fix its strategy until the end of the game. Then, the
game terminates with the reward corresponding to the reward if player $i$
follows some blueprint policy $\pi_{i}$, while the opponent follows the fixed
strategy. Authors of Kovařík et al. (2023) pointed out that multi-valued
states could be viewed as a form of a value function. We further discuss this
in Section 4.2

###  3.2. Regularized Nash Dynamics

Using usual reinforcement learning techniques to find an optimal policy with
self-play does not guarantee convergence to Nash equilibrium and can be
exploited Lanctot et al. (2017). However, regularizing the reward leads to
establishing this guarantee Perolat et al. (2022); Sokota et al. (2023).

Reward regularization with KL-Divergence is

$\mathcal{R}_{i}^{R}(h,a,\pi):=\mathcal{R}_{i}(h,a)-\eta\log(\frac{\pi(s_{i},a_{i})}{\pi^{R}(s_{i},a_{i})})+\eta\log(\frac{\pi(s_{-i},a_{-i})}{\pi^{R}(s_{-i},a_{-i})})$

where $\pi^{R}$ is a regularization policy and $\eta$ is a hyperparameter for
adjusting the regularization effect. Games with such a regularized reward have
a single unique fixed point $\pi_{\text{fix}}$ for any regularization policy
$\pi^{R}$ Perolat et al. (2021). Follow the Regularized Leader McMahan (2011)
may be used to converge to $\pi_{\text{fix}}$. This $\pi_{\text{fix}}$ is not
Nash equilibrium, but setting $\pi^{R}=\pi_{\text{fix}}$ will change the
unique fixed point. If this is done repetitively, the fixed point will
gradually converge to the Nash equilibrium. More regularizations were proposed
in Sokota et al. (2023).

In order to converge to a Nash equilibrium in large games with reward
regularization, the authors in Perolat et al. (2022) propose using two-player
V-trace with Neural Replicator Dynamics Hennes et al. (2020) as a loss
function for policy head and usual L2 loss for value head. With this method,
it is possible to achieve human-level performance in Stratego.

V-trace estimates infoset action values and infoset values with low bias and
low variance for a policy $\pi$ by sampling full trajectories according to
some sampling policy $\mu$. The estimate is done from the end of the
trajectory to the start. Because of the importance sampling clipping, the
estimated value is for a mix between $\pi$ and $\mu$, but the ratio may be
tuned with a single hyperparameter Espeholt et al. (2018).

##  4\. Multi-agent Search with Policy Transformation Value Network

In this section, we present an algorithm Multi-agent Search with Policy
Transformation Value Network (SePoT) that trains an additional critic
alongside a policy network with some policy-gradient algorithm for imperfect
information games, like RNaD Perolat et al. (2022). During gameplay, this
critic is used to construct a depth-limited gadget game that is then solved
with some search algorithm, in our case CFR+ Tammelin et al. (2015).

###  4.1. Network Training

Performing a depth-limited search in imperfect information games requires a
value function that, after the depth limit, assigns value to each infoset
based on ranges Kovařík et al. (2023). In order to use a value function based
on multi-valued states, it is necessary for each history $h$ to learn multiple
values that correspond to the expected values if the opponent plays some fixed
policies against the player’s blueprint policy. Training such value function
presents two difficulties to overcome. The first is the selection of the
opponent policies to be used as a basis to compute the expected values. In
large games, it is not viable to simply use some predefined policy due to the
sheer size that full policies have. The second is estimating the expected
value of these policies.

To find different opponent policies, we decided to use a similar method to the
”bias approach” in Brown et al. (2018). The main idea is to use just a single
policy, which in our case is the policy from the policy network, and then
applying some predefined mapping, that maps the network policy to a different
policy. We call this mapping a policy transformation.

######  Definition .

Policy transformation $f^{T}:\Pi_{i}\times\mathcal{S}_{i}\rightarrow\Pi_{i}$
for player $i$ is a function that maps policy to a different one based on a
current infoset.

In poker, an example of a transformation is folding more frequently Bowling et
al. (2009); Bard et al. (2014). Similarly, in Goofspiel, certain
transformations may increase the probability of playing cards with lower value
if the player is winning or decrease the probability of playing even-valued
cards. These transformations do not have to be game-domain specific. However,
the effectiveness of different transformations may vary across different
games. These transformations aim to cover the strategy space as much as
possible. Constant transformations that transform any policy into each pure
strategy cover this space fully Brown et al. (2018); Kovařík et al. (2023).
This work does not extensively delve into the specific methodology or criteria
for selecting these transformations, and we leave it open for future work.

To estimate the expected value of these transformed policies against the
player’s blueprint, we propose to train an additional critic network
$\boldsymbol{u}_{i}(h)[f^{T}]$, that takes history $h$ as an input and outputs
the player’s $i$ expected value for each policy transformation $f^{T}$. To
avoid sampling additional trajectories, which may be impossible in continuing
tasks, we would like to use already sampled trajectories by the original
policy-gradient algorithm more effectively. This may be achieved by using some
off-policy training algorithm. In this work, we have used a V-trace estimator.

We define the V-trace operator $\mathcal{V}$ for histories, while following
some sampling policy $\mu$ as

$\displaystyle\begin{split}\mathcal{V}v_{i}(h)=&v_{i}(h)\\\
+&\mathbb{E}_{\mu}\left[\sum^{l}_{t=0}\rho^{t}\Big{(}\prod_{0\leq
q<t}c^{q}\Big{)}\Big{(}R_{i}^{t}+v_{i}(h^{t+1})-v_{i}(h^{t})\Big{)}|h^{0}=h,\mu\right]\end{split}$
(1)

where $h^{t}$ is history at timestep $t$ in trajectory $\tau$ with initial
history being $h^{0}$.
$\rho^{t}=\min(\overline{\rho},\frac{\pi(s_{i}(h^{t}),a_{i}^{t})}{\mu(s_{i}(h^{t}),a_{i}^{t})})$
and
$c^{t}=\min(\overline{c},\frac{\pi(s_{i}(h^{t}),a_{i}^{t})}{\mu(s_{i}(h^{t}),a_{i}^{t})})$
are truncated importance sampling weights. If player does not act in timestep
$t$, or if the $t\geq l$, we say that $v_{i}(h^{t})=0$.

(Inspired by Espeholt et al. (2018)): Let
$\rho^{t}=\min{(\overline{\rho},\frac{\pi(s_{i}(h^{t}),a_{i}^{t})}{\mu(s_{i}(h^{t}),a_{i}^{t})})}$,
$c^{t}=\min{(\overline{c},\frac{\pi(s_{i}(h^{t}),a_{i}^{t})}{\mu(s_{i}(h^{t}),a_{i}^{t})})}$,
$\overline{\rho}\geq\overline{c}\geq 1$ and $\mu(s,a)>0\;\;\forall s,a$.
Assuming there exists $\kappa\in(0,1]$, such that
$\mathbb{E}_{\mu}\rho^{l}\Big{(}\prod_{{0\leq q<l}}c^{q}\Big{)}\geq\kappa$,
where $l$ is a length of the trajectory. Then the V-trace operator
$\mathcal{V}$ has a unique fixed point $v^{\pi_{\overline{\rho}}}$, which is
the expected value of following policy

$\pi_{\overline{\rho}}(s_{i}(h^{t}),a_{i}^{t})=\frac{\min(\overline{\rho}\mu(s_{i}(h^{t}),a_{i}^{t}),\pi(s_{i}(h^{t}),a_{i}^{t}))}{\sum_{b\in\mathcal{A}_{i}(s_{i}(h^{t}))}\min(\overline{\rho}\mu(s_{i}(h^{t}),b),\pi(s_{i}(h^{t}),b))}$
(2)

Using $\overline{\rho}\rightarrow\infty$ will result in convergence to the
$v^{\pi}$, that is, the expected value of the policy $\pi$ in given history.
For training the history network, we use standard L2 loss.

###  4.2. Constructing public belief state

After the training phase, the original policy-gradient algorithm ends up with
a trained policy network, which is then used at each decision point to
retrieve policy. Based on this policy, the action is sampled, and the game
proceeds. SePoT finishes the training with the additional history value
network.

As discussed in the Section 2, naively employing search in the game could lead
to highly exploitable strategies. Using resolving gadget Burch et al. (2014),
which limits the opponent’s counterfactual value in root infosets, bounds the
error after performing search in a subgame. Constructing a gadget game
requires the opponent’s counterfactual values $v^{\pi}_{o}$ in each root
infoset and public belief state $\beta=(s_{0},r)$. Most previous methods
stored counterfactual values $v^{\pi}_{o}$, public state $s_{0}$ and ranges
$r$ from previous searches Burch et al. (2014); Moravčík et al. (2017); Schmid
et al. (2023). SePoT could leverage the same idea, but we propose a different
approach, using the trained history network to compute counterfactual values,
trained policy network to retrieve ranges for searching player $i$ and
function that reconstructs the public state. This allows running the search
from an arbitrary public state without the need to search in all parent public
states.

Safe search in imperfect information games has to be performed from all
possible histories based on public information. This requires all histories
$\mathcal{H}(s_{0})$ from current public state $s_{0}$ to construct the gadget
game $\mathcal{G}^{G}_{i}$. Let us assume a function $f^{Rec}$ that generates
all histories in the public state $s_{0}$ from the publicly available
information to all players. While the details of reconstructing the public
state $s_{0}$ are not explored in detail here, for games like Goofspiel or
Battleships, the public state can potentially be reconstructed using
Constraint Satisfaction Problem (CSP) Russell and Norvig (2009); Seitz et al.
(2021), which we also used in our experiments.

Gadget game $\mathcal{G}^{G}_{i}$ requires ranges for the player $i$ and the
chance player. Chance player ranges $r_{c}$ can easily be stored during
gameplay in the same way as older methods Moravčík et al. (2017); Schmid et
al. (2023); Brown and Sandholm (2018). Suppose the player $i$ played only by
using the policy from the neural network during current gameplay and decides
to perform a search at some public state $s_{0}$. In that case, it has to
recompute the ranges $r_{i}$ for each infoset
$s_{i}\in\mathcal{S}_{i}(s_{0})$. This requires backtracking from all of these
infosets to all previous decision points and acquiring the policy from the
policy network for each of them. Because we are in a perfect recall setting,
each infoset cannot have more parenting infosets than the maximal trajectory
length $l^{\text{max}}$ to this infoset from the initial state $w^{0}$, so
this backtracking involves at most $|\mathcal{S}_{i}(s_{0})|l^{\text{max}}$
queries to the policy network.

In order to compute the counterfactual values in root infosets for the
opponent, let us assume that one of the transformations we used in training is
identity transformation, meaning that the network output corresponds to the
expected value if both players follow the policy from the network, which
serves as an approximation of a Nash equilibrium. The opponent’s
counterfactual values are the expected values multiplied by the reaches of
both chance and resolving players. As discussed, these ranges are always
available, so the counterfactual values can always be computed from the
definition. Thanks to this, we have both counterfactual values $v^{\pi}_{o}$
and $\beta$ available at each point of the game, so we can construct a gadget
game and perform a safe search.

###  4.3. Value Function

$s_{0}^{1}$$s_{0}^{2}$$s_{0}^{3}$

(a) Subgame

$s_{0}^{1}$$h_{1}$$h_{2}$$h_{3}$$h_{4}$$s_{1}^{1}$$s_{1}^{2}$$s_{2}^{1}$$s_{2}^{2}$$a_{2}^{1}$$a_{2}^{2}$$a_{2}^{1}$$a_{2}^{2}$$a_{2}^{3}$$a_{2}^{4}$$a_{2}^{3}$$a_{2}^{4}$

(b) Single public state

Figure 2. Modified subgame with multi-valued states, that contains 3 leaf
public states. Right part shows detail of public state $s_{0}^{1}$ that
contains 4 histories and 2 information sets for each player. The multi-valued
states technique modifies this public state by giving player 2 a choice
between two strategies in each history against blueprint policy of player 1.

Multi-valued states Brown et al. (2018) are used as a modification of the
original game, where after the depth limit, the opponent has one more decision
point, in which it chooses its strategy for the remainder of the game against
some fixed blueprint policy. This modified game is a standard game and can be
solved by any game solving algorithm unaware of value functions. Authors of
Moravčík et al. (2017) trained value function for Poker, which served as a
generalization of the value function from perfect information games. This
value function returns counterfactual values based on ranges at the depth
limit. These were then specially adapted for Counterfactual Regret
Minimization.

These two approaches to the depth-limited search may not seem connected, but
the authors of Kovařík et al. (2023) show this connection by explaining that
the multi-valued states could be viewed as a value function, which is not
trained for all possible strategies in the game, but only for some subset.
However, their explanation does not explicitly clarify how this connection
could be leveraged.

Let us assume a depth-limited subgame, as in Figure 2, with three leaf public
states $s_{0}^{1},s_{0}^{2},s_{0}^{3}$. Further examining public state
$s_{0}^{1}$ in Figure 2(b), there are four possible states in this public
state, which are separated into different infosets. First player has infoset
$s_{1}^{1}$, that contains histories $h_{1},h_{3}$ and $s_{1}^{2}$ containing
historis $h_{2},h_{4}$. Similarly second player has infosets
$s_{2}^{1},s_{2}^{2}$, that contains histories $h_{1},h_{2}$ and $h_{3},h_{4}$
respectively. The value function would return counterfactual values for each
infoset, namely
$v^{\pi}_{1}(s_{1}^{1}),v^{\pi}_{1}(s_{1}^{2}),v^{\pi}_{2}(s_{2}^{1}),v^{\pi}_{2}(s_{2}^{2})$.

In the same example, using multi-valued states as proposed in Brown et al.
(2018) gives the opponent, which is player 2, another choice to pick between
two different strategies in each infoset, as shown in Figure 2(b). The
counterfactual values are in this case computed as
$v^{\pi}_{i}(s_{i})=\frac{\sum_{h\in
s_{i}}P_{-i}(h)\sum_{a\in\mathcal{A}(s_{2}(h))}\pi_{2}(s_{2}(h),a)\mathcal{R}_{i}(h,a)}{\sum_{h\in
s_{i}}P_{-i}(h)}$ for each player $i$ and it’s infosets
$s_{i}\in\mathcal{S}_{i}(s_{0})$. Reward in this case corresponds to the value
taken from the critic $\mathcal{R}_{i}(h,a)=\boldsymbol{u}_{i}(h)[f^{T}]$,
where each action $a$ corresponds to a single policy transformation $f^{T}$.

Performing Counterfactual Regret Minimization (CFR) requires storing multiple
statistics in each infoset, like regret and average strategy. These statistics
must be stored even for these artificial infosets created by the multi-valued
states. In such a scenario, the multi-valued states could be viewed as a
stateful value function where these statistics determine the value function
state. Each CFR iteration, this value function updates its state and returns
counterfactual values based on its current state and input ranges $r$.
However, let us assume that instead of performing regret matching and storing
these necessary statistics, the opponent would always pick a best response
based on input ranges. In such a case, we could use multi-valued states as a
usual value function with just additional computation step, without keeping
the state inside the value function. Let us rephrase the value function in
terms of using a history network with policy transformations for player $i$.

$\boldsymbol{v}(\beta)[s_{i}]=\min_{f^{T}\in
F^{T}}\frac{\sum_{h\in\mathcal{H}(s_{i})}P^{\pi}_{-i}(h)\boldsymbol{u}_{i}(h)[f^{T}]}{\sum_{h\in\mathcal{H}(s_{i})}P^{\pi}_{-i}(h)}$
(3)

where $F^{T}$ is a set of all used policy transformations and $P^{\pi}_{-i}$
are directly taken from ranges $r_{-i}$ in $\beta$. Since we are in a two-
player zero-sum setting and the network returns an expected value for the
player $i$, choosing a best response by the opponent is taking such
transformation that minimizes the counterfactual value of the player $i$.

With the constructed gadget game and a corresponding value function, any
previously developed search algorithm for imperfect information games may
conduct the subsequent search. During our experiments, we used CFR+ Tammelin
et al. (2015) exclusively. When using CFR+, a subclass of Growing tree-CFR
(GT-CFR) introduced in Schmid et al. (2023), the bounds already established by
the GT-CFR authors in Theorem 3 also apply to our approach. However, the
quality of this value function $\xi$, which is the distance between values
returned by the optimal value function and the trained value function, is
affected by additional errors, even if the value function is trained
perfectly. The first of these errors is that the blueprint strategy of
resolving player $i$ is not Nash equilibrium but just some approximation.
Second is that the opponent’s strategies used for multi-valued states may not
be best responses to any strategy. As stated by authors of Brown et al. (2018)
in Proposition 1, if the blueprint strategy is Nash equilibrium, the opponent
strategies are all pure actions, then the resulting strategy is also part of a
Nash equilibrium.

The multi-valued states could be expanded by giving both players a choice to
pick from multiple strategies for the rest of the game Brown and Sandholm
(2019); Kovařík et al. (2023). This would increase the number of values that
must be trained quadratically because each pair of strategies between players
yields different values. In Figure 2, the opponent can choose which of the two
strategies it will follow for the rest of the game against the blueprint. If
we would give both players a choice to pick between two strategies to follow,
then there would be four joint actions as a combination between these two
strategies. Multi-agent Search with Policy Transformation Value Network is
compatible with this approach, and the only required change is to compute a
Nash equilibrium of the underlying normal-form game at the depth limit during
search instead of a best response.

We have already shown how the history critic trained for multi-valued states
can be used as a value function. However, we could go one step further and
train the usual value function out of this history critic. This would
completely avoid the need to call the critic for each history and further
compute a best response or Nash equilibrium when using multi-valued states for
single or both players. The value function may be trained before the gameplay
phase by randomly sampling possible ranges, computing the counterfactual
values, and then training the value function on these counterfactual values.
Such trained value function can then be used in already developed algorithms
Moravčík et al. (2017); Schmid et al. (2023) without any changes. The quality
of such a value function depends on the chosen transformations when training
multi-valued states. In our work, we have always used the history critic and
have done computation of a best response during the search.

##  5\. Experiments

We have conducted three main experiments to validate our approach’s
effectiveness. In the first experiment, we compare head-to-head play in larger
games to validate that the inclusion of search improves the strategy from the
policy network. Head-to-head play may not be a good indicator of strategy
quality in imperfect information games, so we further conducted experiments to
show that using search decreases overall exploitability even in smaller games.
The exploitability as a metric shows how well a best-responding opponent can
play against the policy. Strategies with small exploitability are, therefore,
robust against any opponent. The third experiment shows how computing
counterfactual values from the history critic in gadget games affects the
quality of the solution. Appendix B provides a detailed description of the
game rules. All Goofspiel and Battleships experiments have used the same 22
transformations that are described in Appendix C, along with other
hyperparameters. All of our experiments have used the framework OpenSpiel
Lanctot et al. (2019). The depth-limited search was conducted on a single core
of the CPU Intel Xeon Scalable Gold 6146, operating at a frequency of 3.2 GHz,
while the network training additionally used a single GPU Tesla V100.

###  5.1. Head-to-head play in large games

Our first experiment shows the scalability and effectiveness of SePoT on large
games. We separately trained RNaD and RNaD with SePoT, each three times, with
the same hyperparameter setting. These were then used in head-to-head play
against each other, where RNaD directly followed the policy network and SePoT
applied search in those subgames that contained less than 25000 or 100000
unique histories. The evaluation encompassed these games: Goofspiel with eight
cards and descending order of point cards, which contains approximately
$2\cdot 10^{9}$ unique histories; Goofspiel with eight cards and randomized
order of point cards, having $9\cdot 10^{13}$ unique histories; Goofspiel with
thirteen cards and descending order of point cards, containing approximately
$5\cdot 10^{19}$ unique histories; Goofspiel with thirteen cards and
randomized order of point cards, having roughly $3\cdot 10^{29}$ unique
histories; Battleships on a square grid of size 3 with 2 ships of sizes 2 and
2 containing roughly $10^{14}$ unique histories and Battleships on square grid
of size 5 with 3 ships of sizes 3,2 and 2 that have roughly $10^{57}$ unique
histories.

For each game, we have trained 3 RNaD policy networks and 3 different RNaD
policy networks along with SePoT’s history critic. Each network was trained
for 3 days. We have run over one million game simulations of RNaD against
SePoT for each game. In half of them, the SePoT was a first player; in half,
it was a second player. The average rewards multiplied by 100 from these
simulations are presented in Table 1 along with a 95% confidence interval.
Employing search outperformed the RNaDs policy network with statistical
significance in all the games tested.

Increasing the size of subgames that we use search in slightly improves the
performance of SePoT in almost all cases, which shows that incorporating
additional search leads to better results. The only exception is a Goofspiel
13 with descending point card ordering. This is most likely because there are
only slightly more subgames in which the search is used with this increased
limit, and in those, the RNaDs policy network performs well. The usage of
search improves the performance in larger Battleships much more than in any
other game. This is because, in Goofspiel, most of the subgames are quite
large, so the search is used sparingly. However, Battleships have a lot of
smaller subgames where the search is used. Moreover, the Battleships is a much
larger game than the Goofspiel, and similar subgames in Battleships may have
vastly different optimal policies. This suggests that training RNaD in
Battleships is harder than in Battleships. On the other hand, the smaller
Battleships are small enough that the policy network could be sufficiently
trained, and the performance of search there is almost on par with the policy
network.

| Max subgame
---
size
| Goofspiel 8
---
descending
| Goofspiel 8
---
randomized
| Goofspiel 13
---
descending
| Goofspiel 13
---
randomized
| Battleships
---
3x3
| Battleships
---
5x5
25000 | $1.42\pm 0.01$ | $3.71\pm 0.03$ | $6.31\pm 0.01$ | $1.17\pm 0.01$ | $0.44\pm 0.06$ | $34.58\pm 0.16$
100000 | $1.66\pm 0.02$ | $4.47\pm 0.11$ | $6.28\pm 0.08$ | $1.47\pm 0.16$ | $2.83\pm 0.06$ | $36.54\pm 0.2$

Table 1. Average rewards from head-to-head play of RNaD against RNaD with
SePoT. The average rewards are multiplied by 100.

###  5.2. Exploitability in smaller games

In the second experiment, we aim to evaluate the effect of depth-limited
search with multi-valued states on the exploitability of the resulting policy
compared to the policy network. In the experiments, we compare the
exploitability of the policy network from RNaD and the SePoT when using
different look-ahead lengths. Firstly, we compared the exploitability in Leduc
hold’em, where we split the game on the part before dealing a public card and
after. We used constant transformations that transformed any policy into each
pure action. We trained ten networks with different random seeds while
computing exploitability every 2,000 iterations up to iteration 1,000,000. The
results in Figure 3(a) show the mean and 95% confidence interval of the
exploitability throughout these runs with increasing iterations. We see that
SePoT cannot exceed the performance of the RNaD in Leduc hold’em, but during
the training the SePoT seems to be more stable.

We conducted the same experiment in Goofspiel with five cards and randomized
point card ordering for 100,000 RNaD iterations. This game consists of 2.4
million unique histories. We used different depth limits for search, where
DL=$n$ means that both players play $n$ actions before the value function is
called from the root of the current subgame. The plots in Figure 3(b) show how
the exploitability changes with additional iterations. Using the depth limit 2
or 3 yields similar results that both outperform depth limit 1 and the policy
network. This experiment shows that with additional training, the search still
improves over the network policy. Furthermore, it confirms the intuition that
having a longer look-ahead increases the quality of the search solution.

(a) Leduc hold’em

(b) Goofspiel

Figure 3. Exploitability based on the RNaD training comparing policy network
from RNaD and the search with SePoT.

Exploitability

###  5.3. Counterfactual values in gadget games

Our final experiment aims to show that using the counterfactual values
computed from history critic does not significantly worsen the solution
compared to using them from previous resolves. We trained ten critic networks
with the same hyperparameter setting for Leduc hold’em and Goofspiel with five
cards and randomized point card ordering. Then, we solved each subgame
separately, either by computing the counterfactual values for the gadget game
from the history critic or reusing them from previous searches. In Leduc
hold’em, we split the game before dealing a public card and after. In
Goofspiel, each subgame had a depth limit of 1, so the value function is
called after a single action by each player from the root of the subgame. The
action in the gadget game is not counted towards the depth limit. We then
combine these subgame policies into a policy for a whole game and compute the
exploitability.

The results are shown in Figure 4, where we show the mean and the 95%
confidence interval for both approaches. Using the counterfactual values from
previous searches significantly outperforms using the history critic. On the
other hand, using the counterfactual values in Goofspiel only slightly
improves the performance of the search. In large games, where we cannot do all
the previous searches, using the history critic is the only possibility to
perform a search. This experiment shows that using the history critic may harm
the final solution in some games. With this insight, the remainder of our
experiments were conducted with the computation of the counterfactual values
from the critic network.

(a) Leduc hold’em

(b) Goofspiel

Figure 4. Exploitability based on the training iterations, when using the
counterfactual values from previous searches or computing them from history
critic.

Goofspiel and Leduc Exploitability

##  6\. Related work

The model-free policy-gradient techniques, which serve as a main building
block of our algorithm, are applicable to huge imperfect information games,
with the only limitation being the size of the player’s private knowledge that
serves as an input to the neural network. However, safe search is a much more
limited technique since it requires a model of the game to construct the
subgame. Moreover, safe search is much more computationally demanding, since
it requires storing the subgame in a memory.

Some techniques to overcome this issue include either abstracting the game
Brown and Sandholm (2018) or revealing part of the private information Zhang
and Sandholm (2021). These methods decrease the size of the subgame at the
cost of the final solution. Since previous algorithms use search in both train
and test time Brown et al. (2020); Brown and Sandholm (2018); Moravčík et al.
(2017); Schmid et al. (2023), it becomes necessary to use these techniques to
downsize some subgames in huge games, even to be able to train the value
functions and apply the search algorithms.

In our work, we use a policy-gradient training algorithm that trains at
arbitrarily sized games. We can choose whether the search should be used at
each point independently during gameplay. This enables our search in larger
games than previously possible without using these subgame reduction
techniques. However, SePoT is flexible enough to be used in unison with these
subgame reduction techniques to increase the number of subgames that the
search may be applied in even further.

Imagine a game of Battleships as an example. After placing the ships, there
are more than $10^{20}$ possible states in a public state. Safe search in such
a subgame is infeasible. However, after several more rounds, the information
is steadily being revealed to both players, and eventually, the size of the
public state gets small enough. Our proposed algorithm can perform search in
such a situation, which was previously not possible.

Our method is heavily based on the Brown et al. (2018), with the notable
differences being a more principled way to train the blueprint policy with
policy-gradient algorithms, more thoroughly connecting the multi-valued states
with value functions. We show how the multi-valued states may be used to train
the value function or how to use them as a value function. Furthermore, we
discuss how the multi-valued states could be expanded to the setting where
both players can choose their strategy until the end of the game. Lastly, we
present a way to further leverage an already trained critic network to
construct a gadget game anywhere in the game without the need to perform
search in previous parts.

We have exclusively used RNaD Perolat et al. (2022) as a policy-gradient
training algorithm. SePoT could be trained alongside any different multi-agent
reinforcement learning algorithms for imperfect-information games that
approximate Nash Equilibrium from sampled trajectories. Since SePoT trains on
the same trajectories, it uses them more effectively. SePoT could be used even
with an already trained policy, but the training then requires sampling
additional trajectories, which is not always possible.

Since the search is more computationally costly than following the policy from
the neural network, with SePoT it is possible to argue when to perform search
to improve the gameplay performance only in important parts of the game
according to some heuristic.

Model-free deep reinforcement learning methods based on regret minimization
Steinberger et al. (2020); Gruslys et al. (2020); McAleer et al. (2023) use
search in the gameplay and still can be scaled to very large games similarly
to SePoT. The main limitation of these methods is the need to compute the
average strategy, which either requires storing all the trajectories used in
learning or approximating this average, which is prone to error. In games like
Battleships, the training may consist of hundreds of millions of trajectories
to train properly. Storing all of these trajectories is memory-demanding, and
computing the average out of them is also computation-demanding. SePoT uses a
policy-gradient algorithm that approximates the optimal strategy in immediate
strategies, so it does not require computing the average strategy. For search
in the gameplay phase, all the necessary statistics are stored within the
trained policy network and history critic.

Algorithms for imperfect information games outside of two-player zero-sum
scope like Pluribus for multiplayer Poker Brown and Sandholm (2019), Sparta
for cooperative game Hanabi Lerer et al. (2020) or Cicero for the multiplayer
adversarial game with cooperative elements Diplomacy (FAIR)† et al. (2022) all
used search to achieve strong performances. These advancements underscore the
significance of search as an integral component in gameplaying algorithms.

##  7\. Conclusion

Policy-gradient algorithms proved to be powerful algorithms for solving huge
problems in various settings. Recently, these algorithms were successfully
applied to two-player zero-sum imperfect information games and outperformed
human professionals in Stratego. However, the inability of these algorithms to
incorporate search did not allow them to improve mistakes caused by network
inaccuracies. We have presented an algorithm SePoT that can be used alongside
any trajectory sampling policy-gradient algorithm in two-player zero-sum
imperfect information games to train additional critic network without the
need to perform search during training. We have shown that this network is
sufficient to enable safe search during test time. The search we use differs
from previous approaches since it is independent of the application of search
in previous parts of the game, with the only limitation being the local size
of the subgame. Thanks to this, SePoT can employ search even in larger games
than previously possible while still having a choice to follow policy from the
policy network.

The search in SePoT relies on the accurate reconstruction of the public state.
Although a Constraint Satisfaction Problem Russell and Norvig (2009) can be
utilized for games like Goofspiel, an efficient function to reconstruct public
states remains an open problem for further investigation.

We introduced the notion of policy transformations, which allows training
multiple expected values from just a single actor policy. The main limitation
of SePoT stems from the fact that choosing the transformations affects search
performance. A structured way to learn these transformations would further
improve the performance of SePoT.

We showed how the multi-valued states connect to the value functions and how
to use them as a usual value function, with just the added computation of a
best response or by training the value function out of the multi-valued
states. Furthermore, we have discussed how the multi-valued states could be
expanded to allow both players to pick a strategy for the remainder of the
game and how to use them with SePoT in this setting.

Our experimental results clearly demonstrate that the integration of search
effectively reduces the exploitability compared to the trained policy network,
even when using simple policy transformations. In head-to-head play, SePoT
consistently outperforms RNaD with statistical significance in all tested game
scenarios. We have shown that using the history critic to compute
counterfactual values is possible. Still, in some games, it produces worse
solutions than using these counterfactual values from previous resolves.

This research is supported by Czech Science Foundation (grant no. 18-27483Y).
Computational resources were supplied by the project ”e-Infrastruktura CZ”
(e-INFRA CZ LM2018140) supported by the Ministry of Education, Youth and
Sports of the Czech Republic and also the OP VVV funded project
CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics” which are
both gratefully ac- knowledged.

## References

  * (1)
  * Bard et al. (2014) Nolan Bard, Michael Johanson, and Michael Bowling. 2014\.  Asymmetric abstractions for adversarial settings. In _Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems_. 501–508.
  * Bowling et al. (2009) Michael Bowling, Nicholas Risk, Nolan Bard, Darse Billings, Neil Burch, Joshua Davidson, John Hawkin, Robert Holte, Michael Johanson, Morgan Kan, Bryce Paradis, Jonathan Schaeffer, David Schnizlein, Duane Szafron, Kevin Waugh, and Martin Zinkevich. 2009\.  A demonstration of the Polaris poker system.. In _Adaptive Agents and Multi-Agent Systems_. 1391–1392.  https://doi.org/10.1145/1558109.1558310
  * Brown et al. (2020) Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. 2020.  Combining Deep Reinforcement Learning and Search for Imperfect-Information Games. In _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 17057–17069.  https://proceedings.neurips.cc/paper_files/paper/2020/file/c61f571dbd2fb949d3fe5ae1608dd48b-Paper.pdf
  * Brown and Sandholm (2017) Noam Brown and Tuomas Sandholm. 2017.  Safe and Nested Subgame Solving for Imperfect-Information Games. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper_files/paper/2017/file/7fe1f8abaad094e0b5cb1b01d712f708-Paper.pdf
  * Brown and Sandholm (2018) Noam Brown and Tuomas Sandholm. 2018.  Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.  _Science_ 359, 6374 (2018), 418–424.  https://doi.org/10.1126/science.aao1733 arXiv:https://www.science.org/doi/pdf/10.1126/science.aao1733
  * Brown and Sandholm (2019) Noam Brown and Tuomas Sandholm. 2019.  Superhuman AI for multiplayer poker.  _Science_ 365, 6456 (2019), 885–890.  https://doi.org/10.1126/science.aay2400 arXiv:https://www.science.org/doi/pdf/10.1126/science.aay2400
  * Brown et al. (2018) Noam Brown, Tuomas Sandholm, and Brandon Amos. 2018\.  Depth-Limited Solving for Imperfect-Information Games. In _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc.  https://proceedings.neurips.cc/paper_files/paper/2018/file/34306d99c63613fad5b2a140398c0420-Paper.pdf
  * Burch et al. (2014) Neil Burch, Michael Johanson, and Michael Bowling. 2014\.  Solving Imperfect Information Games Using Decomposition.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 28, 1 (Jun. 2014).  https://doi.org/10.1609/aaai.v28i1.8810
  * Espeholt et al. (2018) Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, Shane Legg, and Koray Kavukcuoglu. 2018\.  IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures. In _Proceedings of the 35th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 80)_ , Jennifer Dy and Andreas Krause (Eds.). PMLR, 1407–1416.  https://proceedings.mlr.press/v80/espeholt18a.html
  * (FAIR)† et al. (2022) Meta Fundamental AI Research Diplomacy Team (FAIR)†, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, Athul Paul Jacob, Mojtaba Komeili, Karthik Konath, Minae Kwon, Adam Lerer, Mike Lewis, Alexander H. Miller, Sasha Mitts, Adithya Renduchintala, Stephen Roller, Dirk Rowe, Weiyan Shi, Joe Spisak, Alexander Wei, David Wu, Hugh Zhang, and Markus Zijlstra. 2022\.  Human-level play in the game of Diplomacy by combining language models with strategic reasoning.  _Science_ 378, 6624 (2022), 1067–1074.  https://doi.org/10.1126/science.ade9097 arXiv:https://www.science.org/doi/pdf/10.1126/science.ade9097
  * Gruslys et al. (2020) Audrunas Gruslys, Marc Lanctot, Rémi Munos, Finbarr Timbers, Martin Schmid, Julien Pérolat, Dustin Morrill, Vinícius Flores Zambaldi, Jean-Baptiste Lespiau, John Schultz, Mohammad Gheshlaghi Azar, Michael Bowling, and Karl Tuyls. 2020\.  The Advantage Regret-Matching Actor-Critic.  _CoRR_ abs/2008.12234 (2020).  arXiv:2008.12234 https://arxiv.org/abs/2008.12234
  * Hennes et al. (2020) Daniel Hennes, Dustin Morrill, Shayegan Omidshafiei, Rémi Munos, Julien Perolat, Marc Lanctot, Audrunas Gruslys, Jean-Baptiste Lespiau, Paavo Parmas, Edgar Duèñez Guzmán, and Karl Tuyls. 2020\.  Neural Replicator Dynamics: Multiagent Learning via Hedging Policy Gradients. In _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ (Auckland, New Zealand) _(AAMAS ’20)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 492–501.
  * Kovařík et al. (2022) Vojtěch Kovařík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisý. 2022.  Rethinking formal models of partially observable multiagent decision making.  _Artificial Intelligence_ 303 (2022), 103645.  https://doi.org/10.1016/j.artint.2021.103645
  * Kovařík et al. (2023) Vojtěch Kovařík, Dominik Seitz, Viliam Lisý, Jan Rudolf, Shuo Sun, and Karel Ha. 2023.  Value functions for depth-limited solving in zero-sum imperfect-information games.  _Artificial Intelligence_ 314 (2023), 103805.  https://doi.org/10.1016/j.artint.2022.103805
  * Lanctot et al. (2019) 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, and Jonah Ryan-Davis. 2019.  OpenSpiel: A Framework for Reinforcement Learning in Games.  _CoRR_ abs/1908.09453 (2019).  arXiv:1908.09453 [cs.LG] http://arxiv.org/abs/1908.09453
  * Lanctot et al. (2017) Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, and Thore Graepel. 2017\.  A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper_files/paper/2017/file/3323fe11e9595c09af38fe67567a9394-Paper.pdf
  * Lerer et al. (2020) Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. 2020\.  Improving Policies via Search in Cooperative Partially Observable Games.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 34 (04 2020), 7187–7194.  https://doi.org/10.1609/aaai.v34i05.6208
  * McAleer et al. (2023) Stephen Marcus McAleer, Gabriele Farina, Marc Lanctot, and Tuomas Sandholm. 2023.  ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret. In _The Eleventh International Conference on Learning Representations_.  https://openreview.net/forum?id=35QyoZv8cKO
  * McMahan (2011) Brendan McMahan. 2011\.  Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization. In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 15)_ , Geoffrey Gordon, David Dunson, and Miroslav Dudík (Eds.). PMLR, Fort Lauderdale, FL, USA, 525–533.  https://proceedings.mlr.press/v15/mcmahan11b.html
  * Moravcik et al. (2016) Matej Moravcik, Martin Schmid, Karel Ha, Milan Hladik, and Stephen Gaukrodger. 2016.  Refining Subgames in Large Imperfect Information Games.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 30, 1 (Feb. 2016).  https://doi.org/10.1609/aaai.v30i1.10033
  * Moravčík et al. (2017) Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. 2017\.  DeepStack: Expert-level artificial intelligence in heads-up no-limit poker.  _Science_ 356, 6337 (2017), 508–513.  https://doi.org/10.1126/science.aam6960 arXiv:https://www.science.org/doi/pdf/10.1126/science.aam6960
  * Perolat et al. (2022) Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. 2022\.  Mastering the game of Stratego with model-free multiagent reinforcement learning.  _Science_ 378, 6623 (2022), 990–996.
  * Perolat et al. (2021) Julien Perolat, Remi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, Georgios Piliouras, Marc Lanctot, and Karl Tuyls. 2021.  From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization. In _Proceedings of the 38th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 139)_ , Marina Meila and Tong Zhang (Eds.). PMLR, 8525–8535.  https://proceedings.mlr.press/v139/perolat21a.html
  * Russell and Norvig (2009) Stuart Russell and Peter Norvig. 2009.  _Artificial Intelligence: A Modern Approach_ (3rd ed.).  Prentice Hall Press, USA.
  * Schmid et al. (2023) Martin Schmid, Matej Moravčík, Neil Burch, Rudolf Kadlec, Josh Davidson, Kevin Waugh, Nolan Bard, Finbarr Timbers, Marc Lanctot, G. Zacharias Holland, Elnaz Davoodi, Alden Christianson, and Michael Bowling. 2023.  Student of Games: A unified learning algorithm for both perfect and imperfect information games.  _Science Advances_ 9, 46 (2023), eadg3256.  https://doi.org/10.1126/sciadv.adg3256 arXiv:https://www.science.org/doi/pdf/10.1126/sciadv.adg3256
  * Seitz et al. (2021) Dominik Seitz, Nikita Milyukov, and Viliam Lisý. 2021\.  Learning to guess opponent’s information in large partially observable games. In _Proc. AAAI Workshop Reinforcement Learning in Games_.
  * Silver et al. (2018) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. 2018.  A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.  _Science_ 362, 6419 (2018), 1140–1144.  https://doi.org/10.1126/science.aar6404 arXiv:https://www.science.org/doi/pdf/10.1126/science.aar6404
  * Sokota et al. (2023) Samuel Sokota, Ryan D’Orazio, J. Zico Kolter, Nicolas Loizou, Marc Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. 2023.  A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games.  arXiv:2206.05825 [cs.LG]
  * Steinberger et al. (2020) Eric Steinberger, Adam Lerer, and Noam Brown. 2020.  DREAM: Deep Regret minimization with Advantage baselines and Model-free learning.  _CoRR_ abs/2006.10410 (2020).  arXiv:2006.10410 https://arxiv.org/abs/2006.10410
  * Tammelin et al. (2015) Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. 2015.  Solving Heads-Up Limit Texas Hold’em. In _Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015_ , Qiang Yang and Michael J. Wooldridge (Eds.). AAAI Press, 645–652.  http://ijcai.org/Abstract/15/097
  * Wang et al. (2023) Tony Tong Wang, Adam Gleave, Nora Belrose, Tom Tseng, Michael D Dennis, Yawen Duan, Viktor Pogrebniak, Sergey Levine, and Stuart Russell. 2023.  Adversarial Policies Beat Professional-Level Go AIs.  https://openreview.net/forum?id=Kyz1SaAcnd
  * Zhang and Sandholm (2021) Brian Zhang and Tuomas Sandholm. 2021.  Subgame solving without common knowledge. In _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 23993–24004.  https://proceedings.neurips.cc/paper_files/paper/2021/file/c96c08f8bb7960e11a1239352a479053-Paper.pdf

##  Appendix A Proofs

This proof is heavily based on the proof of the original V-trace Espeholt et
al. (2018), with the notable difference being that we discuss only the proof
for finite horizon with discount factor $\gamma=1$. We can reformulate the
V-trace operator as

$\displaystyle\mathcal{V}v_{i}(h)$
$\displaystyle=v_{i}(h)+\mathbb{E}_{\mu}\left[\sum^{l}_{t=0}\rho^{t}\Big{(}\prod_{0\leq
q<t}c^{q}\Big{)}\Big{(}R_{i}^{t}+v_{i}(h^{t+1})-v_{i}(h^{t})\Big{)}\right]$
$\displaystyle=(1-\mathbb{E}_{\mu}\rho^{0})v_{i}(h)$
$\displaystyle+\mathbb{E}_{\mu}\left[\sum^{l}_{t=0}\Big{(}\prod_{0\leq
q<t}c^{q}\Big{)}\Big{(}\rho^{t}R_{i}^{t}+[\rho^{t}-c^{t}\rho^{t+1}]v_{i}(h^{t+1})\Big{)}\right]$

Now we can find the contraction coefficients

$\displaystyle\mathcal{V}v_{i}(h)-\mathcal{V}\overline{v}_{i}(h)=$
$\displaystyle=(1-\mathbb{E}_{\mu}\rho^{0})(v_{i}(h)-\overline{v}_{i}(h))$
$\displaystyle+\mathbb{E}_{\mu}\left[\sum^{l}_{t=0}\Big{(}\prod_{0\leq
q<t}c^{q}\Big{)}\Big{(}[\rho^{t}-c^{t}\rho^{t+1}][v_{i}(h^{t+1})-\overline{v}_{i}(h^{t+1})]\Big{)}\right]$
$\displaystyle=\mathbb{E}_{\mu}\left[\sum^{l}_{t=0}\Big{(}\prod_{0\leq
q<t-1}c^{q}\Big{)}\Big{(}[\rho^{t-1}-c^{t-1}\rho^{t}][v_{i}(h^{t})-\overline{v}_{i}(h^{t})]\Big{)}\right]$

where $\rho^{-1}=c^{-1}=1$ and ${0\leq q<t-1}c^{q}=1$ for $t\in{0,1}$. Now we
can show that all coefficient are non-negative, if
$\overline{\rho}\geq\overline{c}$

$\mathbb{E}_{\mu}\Big{[}\rho^{t-1}-c^{t-1}\rho^{t}\Big{]}\geq\mathbb{E}_{\mu}\Big{[}c^{t-1}(1-\rho^{t})\Big{]}\geq
0$

In order to show that the V-trace operator is a contraction, we have to show
that coefficients are strictly less than 1.

$\displaystyle\mathbb{E}_{\mu}\left[\sum^{l}_{t=0}\Big{(}\prod_{0\leq
q<t-1}c^{q}\Big{)}\Big{(}[\rho^{t-1}-c^{t-1}\rho^{t}]\Big{)}\right]=$
$\displaystyle=$
$\displaystyle\sum^{l}_{t=0}\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<t-1}c^{q}\Big{)}\rho^{t-1}\right]-\sum^{l}_{t=0}\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<t}c^{q}\Big{)}\rho^{t}\right]$ $\displaystyle=$
$\displaystyle\sum^{l}_{t=0}\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<t-1}c^{q}\Big{)}\rho^{t-1}\right]-\sum^{l}_{t=0}\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<t}c^{q}\Big{)}\rho^{t}\right]+\rho^{-1}-\rho^{-1}$ $\displaystyle=$
$\displaystyle\sum^{l}_{t=0}\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<t-1}c^{q}\Big{)}\rho^{t-1}\right]-\sum^{l+1}_{t=0}\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<t-1}c^{q}\Big{)}\rho^{t-1}\right]+1$ $\displaystyle=$ $\displaystyle
1-\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<l}c^{q}\Big{)}\rho^{l}\right]\leq 1-\kappa<1$

Therefore
$||\mathcal{V}v_{i}(h)-\mathcal{V}\overline{v}_{i}(h)||\leq\lambda||v_{i}-\overline{v}_{i}||_{\infty}$,
where $\lambda=1-\mathbb{E}_{\mu}\left[\Big{(}\prod_{0\leq
q<l}c^{q}\Big{)}\rho^{l}\right]\leq 1-\kappa<1$ Let us now show what is the
fixed point of $\mathcal{V}$

$\displaystyle\mathbb{E}_{\mu}\rho^{t}\Big{(}R_{i}^{t}+v^{\pi_{\overline{\rho}}}_{i}(h^{t+1})-v^{\pi_{\overline{\rho}}}_{i}(h^{t})|h^{t}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}(h^{t})}\mu(s_{i}(h^{t}),a_{i})\min\big{(}\overline{\rho},\frac{\pi(s_{i}(h^{t}),a_{i})}{\mu(s_{i}(h^{t}),a_{i})}\big{)}$
$\displaystyle\hskip
25.0pt\Big{(}R_{i}^{t}+\sum_{h^{\prime}\in\mathcal{H}}p(h^{\prime}|h^{t},a_{i})v^{\pi_{\overline{\rho}}}_{i}(h^{\prime})-v^{\pi_{\overline{\rho}}}_{i}(h^{t})\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}(h^{t})}\pi_{\overline{\rho}}(s_{i}(h^{t}),a_{i})\Big{(}R_{i}^{t}+\sum_{h^{\prime}\in\mathcal{H}}p(h^{\prime}|h^{t},a_{i})v^{\pi_{\overline{\rho}}}_{i}(h^{\prime})-v^{\pi_{\overline{\rho}}}_{i}(h^{t})\Big{)}$
$\displaystyle\hskip
25.0pt\sum_{a_{i}^{\prime}\in\mathcal{A}_{i}(h^{t})}\min\big{(}\overline{\rho}\mu(s_{i}(h^{t}),a_{i}^{\prime}),\pi(s_{i}(h^{t}),a_{i}^{\prime})\big{)}=0$

The first part of the last equation is Bellman equation for
$\mathcal{V}v^{\pi_{\overline{\rho}}}_{i}$. Therefore we deduce
$\mathcal{V}v^{\pi_{\overline{\rho}}}_{i}=v^{\pi_{\overline{\rho}}}_{i}$. ∎

##  Appendix B Game Rules

###  B.1. Leduc hold’em

Leduc hold’em is a simplified version of a Texas hold’em poker. The game is
played with a deck comprising six cards: two pairs of King, Queen, and Jack.
The game starts with each player putting a single chip into the pot.

The game consists of two rounds, where players take turns playing. Each turn,
the player can either call, raise, or fold. When either player plays fold
action, the game terminates, and the winner is the other player. By playing
the call action, the player puts into pot chips so that the total amount of
chips by both players in the pot is the same. This means that when the amount
of chips in the pot is already the same, the player does not put any chips
into it. Each round, the players can raise at most two times. In the first
round, when either player plays raise action, it calls the other player and
then puts two additional chips into the pot. In the second round, the
additional chips increase to four. The round ends when both players play call
action immediately after each other.

After the first round, the public card is revealed. After the second round,
the game ends, and the player who holds the same card as the public card wins.
Otherwise, the player with a higher rank card wins. The descending order of
ranks is King, Queen, and Jack. The utility given to the winning player is the
amount of chips the opponent puts into the pot.

###  B.2. Imperfect Information Goofspiel

Imperfect Information Goofspiel is a strategic card game where players are
dealt a private hand of thirteen cards, each with a value ranging from one to
thirteen. A deck containing the same set of thirteen unique point cards is
placed face-up on the table.

During each round, players make secret bids by selecting one card from their
hand. The player with the highest bid wins the round and claims the
corresponding point card from the table. However, if multiple players happen
to make the same highest bid, the point card is discarded, leaving all
participants empty-handed for that round. Throughout the game, bids are never
revealed to the other players.

The game progresses through thirteen rounds, after which all players have
played all their cards, and there are no remaining point cards on the table.
At this point, the game concludes, and the player with the highest sum of won
point card values emerges as the winner.

In this work, we use two different versions of Goofspiel based on the shuffled
order of the point cards. The first variation shuffles the point cards
randomly. The second variation arranges the point cards from the highest value
to the lowest, eliminating the chance player from the game. Original Goofspiel
is played with thirteen cards. However, in this work, we also use Goofspiel,
played with only five and eight private and point cards.

###  B.3. Battleships

Battleships is a game played by two players on two square grid boards of size
ten. Each player sees only its board but does not see the opponent’s board.
The game starts with each player secretly placing five ships on its board. The
ships have the following sizes: 5, 4, 3, 3, 2.

After both players place their ships, the game proceeds with players taking
turns to shoot at the opponent’s board. These shootings are public, and the
shooting player knows if the ship was missed, hit, or sunken. The ship is
sunken if all the tiles that it occupies are hit. The player that sinks all
the opponent’s ships wins.

We have also used different versions of the Battleships, played on smaller
boards, and each player has fewer ships.

##  Appendix C Additional experimental details

We used the same setting for all the hyperparameters for all the experiments.
The setting is shown in Table 2. For the majority of hyperparameters, we
adopted the settings established by the original authors in their work on RNaD
Perolat et al. (2022). The differences are setting importance sampling
clipping $\overline{\rho}$ to $\infty$ to ensure that the estimate of V-trace
is unbiased. Furthermore, we changed the rate of updating the regularization
policy, learning rate, batch size, and size of hidden layers to compensate for
training on smaller games than the original authors did with Stratego. As a
sampling policy $\mu$, we have used the actor policy, effectively avoiding
importance sampling clipping by working on-policy.

Parameter | Value
---|---
reward regularization constant $\eta$ | 0.2
regularization policy change $\Delta_{m}$ | 500 for first 200 steps
| 10000 afterwards
learning rate $\alpha_{l}$ | 0.0003
gradient clip $c_{g}$ | 10000
NeuRD threshold $\beta$ | 2
NeuRD clipping $c_{n}$ | 10000
importance sampling clipping $\overline{c}$ | 1
importance sampling clipping $\overline{\rho}$ | $\infty$
decay rate $b_{1}$ in ADAM | 0
decay rate $b_{2}$ in ADAM | 0.999
$\epsilon$ in ADAM | $10^{-8}$
target network update $\gamma_{a}$ | 0.001
batch size | 128
hidden layers size | 512, 512
CFR+ iterations in resolving | 1500
Table 2. Parameters used during evaluation of SeRNaD

###  C.1. Policy Transformations

We have utilized a consistent set of 22 policy transformations across all the
experiments on Goofspiel and Battleships. All of our transformations were
independent of the infoset and kept throughout the whole game, meaning that,
for example, the expected value of transformation 3 in a given history is if
the opponent used this transformation in each decision point from this history
onward. We introduce function $I:\mathcal{A}_{i}\rightarrow\mathbf{N}$ that
for action $a_{i}$ returns the natural number. In Goofspiel, this corresponds
to the card played. In Battleships, it corresponds to the row-major order of
the tile on the grid. Additionally, we define $I^{R}(a_{i})$ as a
complementary value, calculated as
$I^{R}(a_{i})=\max_{a_{i}^{\prime}\in\mathcal{A}_{i}}I(a_{i}^{\prime})-I(a_{i})+1$.
We split the transformations into multiple categories and elaborate on them.
Identity transformation is required so that we can construct gadget game

  1. (1)

$\pi^{\prime}(s_{i},a_{i})=\pi(s_{i},a_{i})$

Uniform policy

  1. (2)

$\pi^{\prime}(s_{i},a_{i})=\frac{1}{|\mathcal{A}_{i}(s_{i})|}$

Transformation that increases probability of playing actions that are played
with small probability in the original policy

  1. (3)

$\pi(s_{i},a)=\pi(s_{i},a)$

Increasing the probability of playing actions with higher value of $I$

  1. (4)

$\pi(s_{i},a)=I(a)\pi(s_{i},a)$

  2. (5)

$\pi(s_{i},a)=I(a)^{2}\pi(s_{i},a)$

  3. (6)

$\pi(s_{i},a)=e^{I(a)}\pi(s_{i},a)$

Increasing the probability of playing actions with higher value of $I^{R}$

  1. (7)

$\pi(s_{i},a)=I^{R}(a)\pi(s_{i},a)$

  2. (8)

$\pi(s_{i},a)=I^{R}(a)^{2}\pi(s_{i},a)$

  3. (9)

$\pi(s_{i},a)=e^{I^{R}(a)}\pi(s_{i},a)$

Increasing the probability of playing actions that have both high values of
$I$ and $I^{R}$

  1. (10)

$\pi(s_{i},a)=\min\Big{(}I(a)\pi(s_{i},a),I^{R}(a)\pi(s_{i},a)\Big{)}$

  2. (11)

$\pi(s_{i},a)=\min\Big{(}I(a)^{2}\pi(s_{i},a),I^{R}(a)^{2}\pi(s_{i},a)\Big{)}$

  3. (12)

$\pi(s_{i},a)=\min\Big{(}e^{I(a)}\pi(s_{i},a),e^{I^{R}(a)}\pi(s_{i},a)\Big{)}$

Increasing the probability of playing actions that either have high value of
$I$ or $I^{R}$

  1. (13)

$\pi(s_{i},a)=\max\Big{(}I(a)\pi(s_{i},a),I^{R}(a)\pi(s_{i},a)\Big{)}$

  2. (14)

$\pi(s_{i},a)=\max\Big{(}I(a)^{2}\pi(s_{i},a),I^{R}(a)^{2}\pi(s_{i},a)\Big{)}$

  3. (15)

$\pi(s_{i},a)=\max\Big{(}e^{I(a)}\pi(s_{i},a),e^{I^{R}(a)}\pi(s_{i},a)\Big{)}$

Removing some actions from the policy

  1. (16)

$\pi(s_{i},a)=\begin{dcases*}\pi(s_{i},a)&if $I(a)$ mod $2=0$\\\
0&otherwise\end{dcases*}$

  2. (17)

$\pi(s_{i},a)=\begin{dcases*}\pi(s_{i},a)&if $I(a)$ mod $2=1$\\\
0&otherwise\end{dcases*}$

  3. (18)

$\pi(s_{i},a)=\begin{dcases*}\pi(s_{i},a)&if $I(a)$ mod $3=0$\\\
0&otherwise\end{dcases*}$

  4. (19)

$\pi(s_{i},a)=\begin{dcases*}\pi(s_{i},a)&if $I(a)$ mod $3=1$\\\
0&otherwise\end{dcases*}$

  5. (20)

$\pi(s_{i},a)=\begin{dcases*}\pi(s_{i},a)&if $I(a)$ mod $3=2$\\\
0&otherwise\end{dcases*}$

  6. (21)

$\pi(s_{i},a)=\begin{dcases*}0&if $I(a)=1$\\\
\pi(s_{i},a)&otherwise\end{dcases*}$

  7. (22)

$\pi(s_{i},a)=\begin{dcases*}0&if $I^{R}(a)=1$\\\
\pi(s_{i},a)&otherwise\end{dcases*}$

##  Appendix D Additional experimental results

In this section we show some additional results from experiments in Section
5.2 and 5.3. All of these experiments are performed on small Goofspiel and
confirms the results in Section 5.

###  D.1. Exploitability in smaller games

(a) Player 1

(b) Player 2

Figure 5. Exploitability in Goofspiel 5 with descending point card ordering
from perspective of each player

Exploitability in Goofspiel 5 with descending point card ordering from
perspective of each player

(a) Player 1

(b) Player 2

Figure 6. Exploitability in Goofspiel 5 with randomized point card ordering
from perspective of each player

Exploitability in Goofspiel 5 with randomized point card ordering from
perspective of each player

We further examine the exploitability in small Goofspiel. In Figure 5, we show
how the exploitability changes with additional training iterations in
Goofspiel 5 with descending point card ordering with roughly 18 thousand
unique histories. In Figure 6, we show the same experiment in Goofspiel 5 with
randomized point card ordering. In both of these experiments, we see that
using look-ahead 2 and 3 has roughly the same results, which are better than
look-ahead 1 or playing according to the policy network.

###  D.2. Counterfactual values in gadget games

(a) Player 1

(b) Player 2

Figure 7. Exploitability in Goofspiel 5 with descending point card ordering
from perspective of each player with look-ahead limit 1.

Exploitability in Goofspiel 5 with descending point card ordering from
perspective of each player with look-ahead limit 1.

(a) Player 1

(b) Player 2

Figure 8. Exploitability in Goofspiel 5 with descending point card ordering
from perspective of each player with look-ahead limit 2.

Exploitability in Goofspiel 5 with descending point card ordering from
perspective of each player with look-ahead limit 2.

(a) Player 1

(b) Player 2

Figure 9. Exploitability in Goofspiel 5 with descending point card ordering
from perspective of each player with look-ahead limit 3.

Exploitability in Goofspiel 5 with descending point card ordering from
perspective of each player with look-ahead limit 3.

(a) Player 1

(b) Player 2

Figure 10. Exploitability in Goofspiel 5 with randomized point card ordering
from perspective of each player with look-ahead limit 1.

Exploitability in Goofspiel 5 with randomized point card ordering from
perspective of each player with look-ahead limit 1.

(a) Player 1

(b) Player 2

Figure 11. Exploitability in Goofspiel 5 with randomized point card ordering
from perspective of each player with look-ahead limit 2.

Exploitability in Goofspiel 5 with randomized point card ordering from
perspective of each player with look-ahead limit 2.

(a) Player 1

(b) Player 2

Figure 12. Exploitability in Goofspiel 5 with randomized point card ordering
from perspective of each player with look-ahead limit 3.

Exploitability in Goofspiel 5 with randomized point card ordering from
perspective of each player with look-ahead limit 3.

In this section, we present additional results that compare using the critic
network to compute counterfactual values or those from previous resolves
within continual resolution. In Figure 7-9 we compare the effect of using
these counterfactual values in Goofspiel 5 with descending point card ordering
for different look-ahead limits. Results from the same experiment in Goofspiel
5 with randomized point card ordering are shown in Figure 10-12. In all of
these Goofpsiel experiments, using the history critic to compute the
counterfactual values yields the only slightly worse solutions than reusing
them from previous searches.