# Astrophysical Distance Scale VII:
A Self-Consistent, Multi-Wavelength Calibration of the Slopes and Relative
Zero Points for the
Run of Luminosity with Color of Stars Defining the Tip of the Red Giant Branch

Barry F. Madore The Observatories, Carnegie Institution for Science, 813 Santa
Barbara St., Pasadena, CA 91101, USA  Department of Astronomy & Astrophysics,
University of Chicago, 5640 S. Ellis Ave., Chicago, IL 60637, USA
<EMAIL_ADDRESS>Wendy L. Freedman Department of Astronomy &
Astrophysics, University of Chicago, 5640 S. Ellis Ave., Chicago, IL 60637,
USA  Kavli Institute for Cosmological Physics, University of Chicago, 5640 S.
Ellis Ave., Chicago, IL 60637, USA<EMAIL_ADDRESS>Kayla Owens
Department of Astronomy & Astrophysics, University of Chicago, 5640 S. Ellis
Ave., Chicago, IL 60637, USA  Kavli Institute for Cosmological Physics,
University of Chicago, 5640 S. Ellis Ave., Chicago, IL 60637, USA
<EMAIL_ADDRESS>
###### Abstract

Given the recent successful launch of the James Webb Space Telescope,
determining robust calibrations of the slopes and absolute magnitudes of the
near- to mid-infrared Tip of the Red Giant Branch (TRGB) will be essential to
measuring precise extragalactic distances via this method. Using ground-based
data of the Large Magellanic Cloud from the Magellanic Clouds Photometric
Survey along with near-infrared (NIR) data from 2MASS and mid-infrared (MIR)
data collected as a part of the SAGE survey using the Spitzer Space Telescope,
we present slopes and zero-points for the TRGB in the optical (VI), NIR (JHK)
and MIR ([3.6] & [4.5]) bandpasses. These calibrations utilize stars
+0.3$\pm$0.1 mag below the tip, providing a substantial statistical
improvement over previous calibrations which only used the sample of stars
narrowly encompassing the tip.

Unified Astronomy Thesaurus concepts: Observational cosmology (1146); Galaxy
distances (590); Carbon Stars (199); Asymptotic giant branch stars (2100);
Hubble constant (758)

##  1 Introduction

With the successful launch of the James Webb Space Telescope (JWST) and the
continuing uncertainty in the local value of the Hubble constant (Freedman
2021), the Tip of the Red Giant Branch (TRGB) Method has become even more
important in the endeavor to calibrate the local expansion rate of the
Universe. Given the light-gathering power and unequalled point spread function
(PSF) resolution of JWST in the near-infrared (NIR) and mid-infrared (MIR), it
now seems an appropriate time to enumerate and quantify the advantages, as
well as to assess any disadvantages, in application of the TRGB method into
the infrared. In addition, it is useful to explore optimal filter combinations
and observing strategies for calibrating those relations.

In the following we present a fully empirical approach to robustly and self-
consistently calibrating optical (VI), NIR (JHK) and for the first time, the
MIR (3.6 and 4.5 $\mu$m) TRGB relations spanning the wavelengths covered most
sensitively by the NIRSS and NIRCAM imagers on JWST. The calibrations
presented here will be indicative of the slopes and zero points expected for
closely similar filters available on those cameras. Ultimately those flight
magnitudes will have to be tied into the ground-based calibrations presented
here using short exposures on very nearby TRGB fields as already observed from
the ground and from space (by HST). Two obvious “bridging galaxies” are WLM
(Wolf-Lundmark-Melotte) and IC 1613, given that the Magellanic Clouds are too
close to be effectively and efficiently used for this purpose. Other galaxies
(NGC 2403, NGC 253, M81 and NGC 300), two to three times further away, are
part of a calibration program being undertaken by McQuinn and her
collaborators using both HST (Prop 15917) and JWST (Prop 1638)111 In that
combined program McQuinn has obtained optical imaging data in F606W & F814W
filters using ACS, NIR imaging data in F110W & F160W filters using WFC3-IR on
HST. And, NIR imaging data in F090W, F150W & F115W filters on both NIRCam and
NIRISS, and MIR imaging data in F356W, F277W & F444W filters on NIRCam, all
using JWST.

.

##  2 The Ground-based/Space-based Calibration

Our fiducial bandpass/wavelength for undertaking this self-consistent
calibration, is the ground-based I-band filter (centered at 8000Å) and its
space-based equivalent filters, F814W on ACS and F814W on WFC3-UVIS, both on
HST (and conceivably the F090W filter on JWST/NIRCAM). The HST filters are
very similar, with effective wavelengths of about 7970Å (see Deustua & Mack
2018) but, for the purposes of this paper, we will concentrate on examining
the ground-based I-band data which has already been cross-matched to the rich
sets of multi-wavelength observations reaching into the MIR, as provided by
Spitzer and the SAGE Survey (Meixner et al. 2006). The VIJHK data come from
the Large Magellanic Cloud (LMC) stellar catalog published by Zaritsky et al.
(2004) and cross-matched with 2MASS. Zaritski et al. (2002) have compared
their BVI photometry with the OGLE calibration (both of which are strictly on
the Johnson-Cousins system) and conclude that their “average, global,
photometric zero points are good to better than 0.03 mag” and, more
specifically, that the individual offsets are 0.011, 0.038 and 0.002 mag for
B,V and I, respectively222One caveat, noted by the referee, concerns the later
revisions of the OGLE photometry, resulting from their introduction of ultra-
precise interference filters for OGLE-IV, which subsequently fixed their OGLE-
III photometry. OGLE-I and -II photometry may still be affected by long red
tails in the original filters. However, the impact of these changes on this
our results are far beyond the scope of this paper.. We have adopted the
I-band extinction of $A_{I}=$ 0.160 mag for the LMC TRGB stars, as discussed
in detail in Freedman et al. (2019), which is consistent with the independent
detailed study of Hoyt (2023)333 Lower values of the total line-of-sight
reddening to the LMC have been reported by Skowron et al. (2021) and Nataf et
al. (2021). The interested reader is referred to the latest discussion of Red
Clump extinction mapping found in Section 2 of Hoyt (2021). Longer wavelength
values were scaled using the Cardelli et al. (1989) extinction curve. However,
we note that there are a number of alternative extrapolation available in the
literature including Fitzpatrick & Massa (2009), Fitzpatrick et al. (2019),
Indebetouw et al. (2005), Schlafly & Finkbeiner (2011) (as given in NED
galactic foreground extinction calculator) and most recently Newman et al.
(2023). We use the differences in these various extrapolations to assign an
uncertainty on our adopted values. For $A_{J},A_{H}$ and $A_{K}$ we find
externally calculated uncertainties of $\pm$0.015, 0.011 and 0.006 mag,
respectively. In extrapolating our adopted total line-of-sight I-band
extinction of 0.160 mag into the near-infrared those extinctions each carry a
15% uncertainty.

###  2.1 The Basic Equations

We start by making explicit a simple but powerful point, which, in retrospect
is obvious, but still needs to be stated. The colors of TRGB stars, in
whatever wavelength combinations that one cares to consider, can be expected
to be linearly related, from band to band, over the small range of color
defining the tip of the RGB population.

We adopt the $(J-K)_{o}$ color as fiducial for the most of this paper, while
noting that any of other colors can be easily substituted once the distance-
independent color-color transformations are defined.

Figure 1 (left panel) shows the color-color transformation between $(V-I)_{o}$
and $(J-K)_{o}$ using LMC red giant branch (RGB) stars selected to fall within
a $\pm$0.1 magnitude slice centered +0.3 mag below the flat trace of the
I-band TRGB magnitude, as a function of color (see Figure 6). The right panel
shows the same correlation run for stars centered on the +0.4 mag slice, +0.1
mag further, below the tip. No significant differences were found between the
two solutions. We proceed with the sample defined by the brighter slice. These
stars significantly outnumber the number of stars defining the tip, but they
all have colors that are sufficiently the same as the TRGB stars themselves
and so they provide a much more (statistically) secure means of making the
transformation of tip magnitude calibrations from one color to the next
without explicitly attempting to measure the individually more ill-defined
slopes and zero points of new relations in any new color/magnitude
combinations. 1550 RGB stars contributed to the solutions given here. They
were constrained to fall within the color range $0.9<(J-K)<1.2$ and
$1.4<(V-I)<2.0$ mag. The dispersion around the fit is $\pm$0.158 mag. Based on
1,550 stars, this gives an error on the mean of $\pm$0.004 mag. The fit in
Figure 1 is

$(V-I)_{o}=2.41~{}[(J-K)_{o}-1.00]+1.61~{}(\pm 0.004)~{}~{}[1]$

The three sub-panels in Figure 2 are color-color plots of the combinations of
most immediate interest here: (J-K) vs (I-J), (J-K) vs (I-H) and (J-K) vs
(I-K),top to bottom.

$(I-J)_{o}=0.86~{}[(J-K)_{o}-1.00]+1.10~{}(\pm 0.02)~{}~{}[2]$

$(I-H)_{o}=1.67~{}[(J-K)_{o}-1.00]+1.93~{}(\pm 0.04)~{}~{}[3]$

$(I-K)_{o}=1.86~{}[(J-K)_{o}-1.00]+2.10~{}(\pm 0.02)~{}~{}[4]$

As given in Freedman (2021) and in the majority of other recent calibrations
555Updating Table 1 in Freedman (2021) and centering all values at fiducial
color of (V-I) = 1.5 mag, we have $M_{I}=$ -4.05 mag, Rizzi et al. (2007);
-4.05 mag, Bellazzini et al. 2008; -4.05 mag, Tammann et al. 2008; -4.05 mag,
Madore et al. 2009; -4.01 mag, Jang & Lee 2017; Reid et al. 2019; -3.97 mag,
Yuan et al, 2019, reddened; -4.05 mag, Freedman et al 2020; -4.05 mag, Hoyt et
al. 2021, LMC; -4.05 mag, Hoyt et al. 2021, SMC. To be complete, it can be
mentioned that Soltis et al. 2021 obtained a value of $M_{I}=$ -3.97$\pm$0.06
mag, based on a Gaia parallax to $\omega$ Cen, the uncertainty of which has
been challenged by Vasiliev & Baumgardt 2021.

$M(I)_{o}=-4.05$

mag it then immediately follows that

$M(V)_{o}=-4.05+1.00~{}(V-I)_{o}~{}~{}[5]$

and then using Equation 1

$M(V)_{o}=-2.44+2.41~{}[(J-K)_{o}-1.00]~{}~{}[6]$

after transforming to $(J-K)_{o}$ and re-centering the color. It then also
follows that

$[M(I)_{o}-M(J)_{o}]=0.86~{}[(J-K)_{o}-1.00]+1.10~{}~{}[7]$

$[M(I)_{o}-M(H)_{o}]=1.67~{}[(J-K)_{o}-1.00]+1.93~{}~{}[8]$

$[M(I)_{o}-M(K)_{o}]=1.86~{}[(J-K)_{o}-1.00]+2.10~{}~{}[9]$

Again, by substituting $M(I)_{o}=-4.05$ into the above three equations,
collecting the respective zero points and re-centering the equations at
$(J-K)_{o}=1.00$ gives

$M(J)_{o}=-5.15-0.86~{}[(J-K)_{o}-1.00]~{}~{}[10]$

$M(H)_{o}=-5.98-1.67~{}[(J-K)_{o}-1.00]~{}~{}[11]$

$M(K)_{o}=-6.15-1.86~{}[(J-K)_{o}-1.00]~{}~{}[12]$

Similarly, for the mid-infrared absolute magnitudes we derive the following
relations,

$M(3.6)_{o}=-6.29-2.30~{}[(J-K)_{o}-1.00]~{}~{}[13]$

$M(4.5)_{o}=-6.18-2.30~{}[(J-K)_{o}-1.00]~{}~{}[14]$

and

$M(J)_{o}=-5.15-0.72~{}[(J-3.6)_{o}-1.20]~{}~{}[15]$

After adjusting for the slightly (5%) shorter central wavelength of the JWST
F115W filter, and the longer color baseline of [(F115W -3.6] compared to
(J-K), we get a first estimate of

$M(F115W)_{o}=-5.01-0.72~{}[(F115W-3.6)_{o}-1.34]~{}~{}[16]$

with the formal error on the color term being $\pm$0.06. This slope of -0.72
is well within the range of values (weighted least squares: -0.74 $\pm$ 0.17;
unweighted least squares: -0.70 $\pm$ 0.16; theory for a 10 Gyr population:
-0.74 $\pm$ 0.03) quoted by Hoyt et al. (2023) for the JWST observations of
the TRGB found in the galaxy NGC 4536, where the color baseline used F444W
which is largely degenerate with 3.6 microns for these stars.

Figure 1: (V-I) vs (J-K) Color-Color Plots. Left Panel: Stars are selected to
be +0.3 ($\pm$ 0.1) mag below the I-band TRGB. Right Panel: Stars are chosen
to be +0.4 ($\pm$ 0.1) mag below the TRGB. No significant difference is found
between these two solutions for color-color correlation used in Equation [1].
Figure 2: Color-Color Transformation Plots: Upper plot: (I-J) to (J-K), middle
plot: (I-H) to (J-K), and lower plot: (I-K) to (J-K). Solid red lines are the
adopted linear fits to the data. Yellow points represent one in five of the
blue data points and are over-plotted to give a visual sense of the surface
density of points in high-overlap regions. Figure 3: Rotated Color-Color Plots
for (J-K) versus the Mid-Infrared blended colors: (J-3.6) and (J-4.5) in the
left and right panels, respectively. See text for additional details. Figure
4: NIR Color-Magnitude Diagrams centered on the TRGB in J, H and K versus
(J-K), top to bottom. The red slanting line is defined by the color-color
transformations shown in three panels of Figure 2.

Figure 5: The trends, with increasing wavelength (bandpass) of the absolute
magnitude of TRGB stars at the blue [(J-K) = 0.6 mag] metal-poor end and at
the red [(J-K) = 1.2 mag] metal-rich end of the fits shown in Figure 6. The
thin black lines indicate where the F115W filter on JWST/NIRCam is expected to
show its slanting tip which because of that band’s slightly blue effective
wavelength than ground-based J, it will be slightly fainter over-all and
slightly shallower in its slope than the J-band values shown here and
elsewhere. The JWST absolute mean-magnitude zero point is set at the fiducial
color [F115W - F365W] = 1.34 mag, corresponding to (J-K) = 1.00 mag.

##  3  Conclusions

Figure 6 graphically summarizes the results of this paper. The black circled
points map out $I_{o}$ vs $(V-I)_{o}$ color-magnitude diagram for stars in the
LMC. One star in 10 is colored yellow (and then one star in 5 is colored red)
so as to give some sense of the density of points in heavily crowded regions
of the diagram. Large yellow points mark the stars (found below the flat
I-band TRGB) that are used in all of the subsequent color-color
transformations. Their mean level is indicated by the horizontal red line. The
fiducial I-band TRGB is shown by the horizontal blue line, parallel to and 0.3
mag above the red line. The positively-sloped lines above the I-band TRGB are
the NIR and MIR tracers of the TRGB in the JHK NIR bands, followed by the
(overlapping) 3.6 and 4.5$\mu$m MIR TRGB relations. These lines are at their
magnitudes in their respective filters (still plotted against the common
$(J-K)$ color. The downward sloping blue line, well below the I-band, is the
$V_{o}$ vs $(J-K)_{o}$ TRGB relation; it has a slope of unity. The dramatic
increase in luminosity of the TRGB stars seen in the longer-wavelength filters
is impressive, but it needs to be pointed out that this advantage saturates in
the MIR where the long-wavelength colors become zero on the Raleigh-Jeans
portion of the spectral energy distribution.

Figure 6: The individual traces (in blue) of the tip of the red giant branch in VIJHK and in 3.6 & 4.5 microns (the latter two having identical slopes). The TRGB I-band slope is flat blue line. Below it is a red line, +0.3 mag fainter, going through larger yellow dots that are the tracer stars used to define the color-color plots shown in this paper. Table 1: LMC Vega magnitudes and LMC AB magnitudes of Multi-Wavelength Tip Calibrations. Blue ends of the tip in Columns 2 and 3; Red ends in Columns 4 and 5.  Filter | Vega (B) | AB(B) | Vega(R) | AB(R)
---|---|---|---|---
$V$ | $15.08$ | $15.08$ | $16.22$ | $16.22$
$I$ | $14.43$ | $14.87$ | $14.43$ | $14.87$
$J$ | $13.76$ | $14.66$ | $13.10$ | $14.00$
$H$ | $13.30$ | $14.68$ | $12.17$ | $13.55$
$K_{s}$ | $13.16$ | $14.99$ | $11.90$ | $13.73$
$[3.6]$ | $13.11$ | $15.84$ | $11.73$ | $14.46$
$[4.5]$ | $13.22$ | $16.28$ | $11.84$ | $14.88$

##  4 Acknowledgements

We thank the University of Chicago and Observatories of the Carnegie
Institution for Science for their support of our long-term research into the
calibration and determination of the expansion rate of the Universe. Support
for this work was also provided in part by NASA through grant number HST-
GO-13691.003-A from the Space Telescope Science Institute, which is operated
by AURA, Inc., under NASA contract NAS 5-26555.

We thank both Margaret Meixner and Dennis Zaritsky for making their individual
catalogs of resolved-star photometry of the LMC publicly available. We also
thank the referee for suggesting that we investigate the effects of alpha-
enhanced metallicities on the level of the TRGB and on the slopes in the near-
infrared. APPENDIX A

BASTI Models

We have accessed the stellar evolutionary models provide by Cassisi & Salaris
available at their website (http://albione.oa-teramo.inaf.it/) as described in
Pietrinferni et al. (2004, 2006). Six isochrones for two sets of models were
downloaded. One adopted a standard solar composition; the other was enhanced
in alpha-elements. Each of the six models (shown in Figure 7) had the
following metallicities: Z = 0.0001, 0.003, 0.006, 0.010, 0.020 and 0.040. As
is well known the terminal points of the RGB stars (in color) are a monotonic,
increasing function of increasing metallicity. This is demonstrated in both
the alpha-enhanced model (right panel) and somewhat more dramatically in the
solar mixture models (left panel).

The effect of alpha enhancement on the absolute magnitude of the TRGB is
small, and is highlighted by the two horizontal lines duplicated in each of
the two panels. The dashed line represents the approximate level of the TRGB
averaged over the three brightest tips corresponding to metallicities of Z =
0.003, 0.008 and 0.010. That TRGB level is $M_{I}=$ -4.037 mag for the solar
mixture model, and $M_{I}=$ -4.050 mag for the alpha-enhanced mode.666Note
that we have offset the two BASTI magnitude scales by +0.186 mag so as to have
the alpha-enhanced TRGB shown in Figure 8 to have an absolute magnitude of
$M_{I}=$ -4.05 mag, simply to make the CMDs correspond more closely to the
generally adopted empirical zero point.

The downward sloping arrow attached to the TRGB of the lowest metallicity
isochrone in each of the plots is the full range of the color and luminosity
effect due to age shown in the accompanying Figure 8 (below). If, in a given
galaxy halo, there are a range of ages the net result would be to have the
oldest population always defining the observed TRGB with more recent
populations simply adding counts to the fainter extension of the summed RGB
luminosity function. Assuming that every halo has first-generation, low-mass,
low-metallicity stars that enrich the gas with metals for subsequent
generations of halo stars, then they will be the same stars in all galaxies
determining their TRGB distances. Later (merger) events would only contribute
fainter RGB stars and not impact that fact.

If there were a compelling reason to suspect that galaxies had varying amounts
of populations of RGB stars differing randomly in their solar versus alpha-
enhanced elemental mixtures, then the range in the magnitude of the TRGB seen
here ($\Delta M_{I}$ = 0.013 mag), expressed as a dispersion, would
effectively blur the tip by only $\pm$0.004 mag.

For readers who are not familiar with the effects of age on the brightness and
color of the TRGB, we have included Figure 8, which we note has a highly
magnified color range emphasizing the small (but still systematic) effect of
age. To emphasize this point, the full effect of age as given in Figure 8 is
also shown in Figure 7 as a downward-pointing arrow attached to the terminal
point of the lowest-metallicity isochrone in the two panels, with younger
populations falling systematically below the oldest stars of all
metallicities. In other words, if there are predominantly old halos with a
contribution of younger stars (produced by whatever mechanism) their presence
will not affect the detected magnitude of the TRGB.

Figure 7: The trends of RGB isochrones with metallicity for alpha-enhanced
models (in the right panel) and solar models (in the left panel). The
horizontal dashed lines are at the approximate level of the brightest TRGB
stars (at -4.037 mag) having a solar mixture; the solid horizontal line marks
the level of the TRGB (at -4.050 mag) for alpha-enhanced models. See text for
additional details. Figure 8: BASTI Models of the the Red Giant Branches of
stellar populations having the same solar abundances but differing in ages,
ranging from 6 Gyr (blue points, to the left) up to 14 Gyr (red points, to the
right). Note that the color range spanned by these models at the TRGB is very
small (0.08 mag) in (V-I) with a trend toward bluer colors and fainter TRGB
magnitudes with decreasing age. The full run of color and magnitude with age
is shown as a downward slanting arrow in Figure 7 (left and right panels).

Figure 9: Near-Infrared (JHK) Basti models of red giant branch isochrones for
a variety of metallicities (in each panel) and for a solar mixture in the
three (JHK, top to bottom) panels in left column, and an alpha-enhanced
mixture in the three (JHK) panels in the right column. The dashed black line
is a fit to the TRGB as defined by the five highest metallicity isochrones.
Those slopes are individually given in the lower right portion of each of the
color-magnitude diagrams.

Finally, we use the same set of BASTI models to examine the effects of alpha-
element enhancements on the slopes of the tips of the red giant branches in
the three near-infrared JH & K bandpasses. A mosaic of those color-magnitude
diagrams is found in Figure 9. The left column of plots are for a solar
metallicity, running from J vs (J-K) at the top, followed by H vs (J-K) and
then K vs (J-K) at the bottom. The right column follows the same sequence, but
it is for alpha-enhanced models. Slopes (fit by dashed black lines to the five
highest metallicity isochrones) are given to the lower right of each of the
panels.

The main conclusions to be gleaned from these plots are as follows: (a) the
solar models are more spread out to the red than the alpha-enhanced models,
but (b) they have slightly larger slopes in J (-0.67 vs -0.83) and K (-1.67 vs
-1.83)777Note however that the J and K slope solutions are not independent,
but it is easily shown that Slope(K) = Slope(J) -1.0 is true by definition.

, and a smaller slope in H (-2.13 vs -2.00) for the alpha-enhance models.
These slopes can be compared with the LMC slopes (-0.86, -1.67 & -1.86) given
above (Section 2.1, Equations 10, 11, and 12) and the other set of empirical
slopes given by Madore et al. (2018) for the NIR TRGB data of stars in IC 1613
and the LMC (Hoyt et al. 2018). Those slopes are -0.85, -1.62 and -1.85 in JK
& K, respectively. They, in turn, are closely matched by the self-consistent J
and K slopes (-0.811 and -1.811, respectively) theoretically modelled by
Serenelli et al. (2017) for the color range 0.76 $<$ 1.50 mag. These values
may be suggesting that the alpha-enhanced models are more representative of
the halo stars in the LMC and IC 1613. How this geneneralizes out to other
halos will have to await high-precision slopes being independently measured in
more galaxy halos.

##  5 References

Bellazzini, M. 2008, MmSAI, 79, 440

Cardelli, J.A., Clayton, G.C., Mathis, J.S. 1989, ApJ, 345, 245

Deustua, S.E. & Mack, J. 2018, Comparing the ACS/WFC and WFC3/UVIS Calibration
and Photometry,

HST Instrument Science Reports: ACS-2017-02 and WFC3-2018-02

Fitzpatrick, E.L., & Massa, D., Gordon, K.D. 2009, ApJ, 886, 108

Fitzpatrick, E.L., & Massa, 2019, ApJ, 699, 1209

Freedman, W.L., Madore, B.F., Hatt, D. 2019, ApJ, 882, 24 arXiv: 1907.05922

Freedman, W.L., Madore, B.F., Hoyt, T., et al. 2020, ApJ, 891, 57

Freedman, W.L. 2021, ApJ, 919, 16 arXiv: 2106.15656

Hoyt,T.J., Beaton, R.L., Freedman, W.L., et al. 2021, ApJ, 915, 34

Hoyt, T.J. 2023, NatAs, 7, 590

Hoyt, T.J., Freedman, W.L., Madore, B.F., et al. 2018, ApJ, 858, 12

Hoyt, T.J., Jang, I.-S., Freedman, W.L. et al. 2023, ApJ, (submitted).

Indebetouw, R., Mathis, J.S., Babler, B.L. et al. 2005, ApJ, 619, 931

Jang, I.S., & Lee, M.G. 2017, ApJ, 835, 28

Lee, A. J., Freedman, W. L., Madore, B. F., et al., 2021, ApJ, 907, 112.

Madore, B.F., Mager,V., & Freedman, W.L. 2009, ApJ, 690, 389

Madore, B.F., Freedman, W.L, Hatt, D., et al. 2018, ApJ, 858, 11

Madore, B.F., & Freedman, W.L. 2020, AJ, 160, 170

Newman, M.J.B., McQuinn, K.B.W., Skillman, E.D. 2023, ApJ, submitted

Pietrzynski, G., Graczyk, D., Gallenne, A., et al. 2019, Nature, 567, 200

Pietrinferni, A., Cassisi, S., Salaris, M. & Castelli, F. 2004, ApJ, 612, 168

Pietrinferni, A., Cassisi, S., Salaris, M. & Castelli, F. 2006, ApJ, 642, 797

Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020, A&A, 641, A6.

Reid, M.J., Pesce, D.W., & Riess, A.G. 2019, ApJL, 886, L27

Rizzi, L., Tully, R.B., Makarov, D., et al. 2007, ApJ, 661, 815

Schlafly, E.F., & Finkbeiner, D.P. 2011, ApJ, 737, 103

Serenelli, A., Weiss, A., Cassisi, S. 2017, A&A, 606, A33

Tammann, G.A., Sandage, A., & Reindl, B. 2008, ApJ, 679, 52

Vasiliev, E., & Baumgardt, H. 2021, MNRAS, 505, 5978

Yuan,W., Riess, A.G., Macri, L.M., et al. 2019, ApJ, 886, 61

Zaritsky, D., Harris, J., Thompson, I.B., et al. 2004, AJ, 128, 1606


none [ALA ’23]Proc. of the Adaptive and Learning Agents Workshop (ALA 2023)
May 29-30, 2023London, UK, https://alaworkshop2023.github.io/Cruz, Hayes,
Wang, Yates (eds.) 2023 2023 printacmref=false Technical University of
Darmstadt Darmstadt Germany Technical University of Darmstadt Darmstadt
Germany Technical University of Darmstadt Darmstadt Germany Technical
University of Darmstadt, hessian.ai, DFKI Darmstadt Germany

# Know your Enemy: Investigating Monte-Carlo Tree Search
with Opponent Models in Pommerman

Jannis Weil$\ast$ 0000-0001-5439-9131<EMAIL_ADDRESS>,  Johannes
Czech$\ast$ 0000-0002-9568-8965<EMAIL_ADDRESS>,  Tobias
Meuser  0000-0002-2008-5932 and  Kristian Kersting  0000-0002-2873-9152

###### Abstract.

In combination with Reinforcement Learning, Monte-Carlo Tree Search has shown
to outperform human grandmasters in games such as Chess, Shogi and Go with
little to no prior domain knowledge. However, most classical use cases only
feature up to two players. Scaling the search to an arbitrary number of
players presents a computational challenge, especially if decisions have to be
planned over a longer time horizon. In this work, we investigate techniques
that transform general-sum multiplayer games into single-player and two-player
games that consider other agents to act according to given opponent models.
For our evaluation, we focus on the challenging Pommerman environment which
involves partial observability, a long time horizon and sparse rewards. In
combination with our search methods, we investigate the phenomena of opponent
modeling using heuristics and self-play. Overall, we demonstrate the
effectiveness of our multiplayer search variants both in a supervised learning
and reinforcement learning setting.

###### Key words and phrases:

Multi-agent planning, supervised learning, reinforcement learning

MCTS

    Monte-Carlo Tree Search
RL

    Reinforcement Learning
SL

    Supervised Learning
MARL

    Multi-Agent Reinforcement Learning
LSTM

    Long Short-Term Memory
GRU

    Gated Recurrent Unit
FFA

    Free For All
A2C

    Advantage Actor-Critic
A3C

    Asynchronous Advantage Actor-Critic
PPO

    Proximal Policy Activation
IMPALA

    Importance Weighted Actor-Learner Architecture
BRS

    Best Reply Search
PUCT

    Predictor Upper Confidence Bounds
00footnotetext: These authors contributed equally to this work.

##  1\. Introduction

Monte-Carlo Tree Search (MCTS) is widely know as a powerful search algorithm
for both, single player environments such as Atari, and two player zero-sum
games like the game of Go Schrittwieser et al. (2020). In environments with
more players, MCTS is usually combined with domain-specific heuristics to make
search feasible Świechowski et al. (2023).

Multiplayer games with more than two players introduce new challenges to
search-based methods. In particular, the size of the search tree explodes when
move combinations for multiple players have to be considered Luckhart and
Irani (1986). This leads to an exponentially increasing computational
complexity of the search, depending on the number of players. Combinations
with MCTS Nijssen (2013) lead to improvements across multiple domains, but
perform poorly under limited resources due to a shallow search depth Baier and
Kaisers (2020a). Multiplayer search methods like Parandoid search Sturtevant
and Korf (2000), Best Reply Search Schadd and Winands (2011) and recent
extensions Baier and Kaisers (2020b) improve the search depth by reducing the
time spent to simulate opponents and expectedly suboptimal moves.
Additionally, the search can be guided with value estimates Szita et al.
(2009); Nijssen and Winands (2011) and learned value functions Petosa and
Balch (2019); Ozair et al. (2021).

With this work, we focus on the combinatorial aspect of multiplayer games and
investigate learning-based MCTS variants that effectively reduce the search
space to single- and two-player games. Other players act according to given
opponent models, hence drastically reducing the branching factor. We give
insights regarding the applicability in a Reinforcement Learning (RL) setting
and evaluate our approach in the multiplayer game Pommerman Resnick et al.
(2018a).

We provide the following contributions:

  * •

Based on learning-based MCTS, we propose techniques to reduce the search space
by transforming competitive n-player games to single-player and two-player
games.

  * •

We compare learning from demonstrations, reinforcement learning, and different
opponent models in terms of resulting performance and behavior.

  * •

We show that the proposed agent achieves a proficient level of play in the
Free For All (FFA) Pommerman environment.

Our code is available at https://github.com/jw3il/PommerLearn. We begin by
introducing our approach in a general setting. Next, we go over our
experiments in the Pommerlearn environment for both, learning from
demonstration data, as well as learning in a reinforcement learning setting.
Afterwards we discuss the results and the limitations of our approaches. At
last, we present related work and conclude with an outlook for potential
future work.

Figure 1. Exemplary search graphs of Single-Player Search (B) and Two-Player
Search (C) next to a Pommerman board (A). The Single-Player Search allows a
deeper search with fully heuristic-based play for all opponents, whereas the
Two-Player Search allows a full exploration of a selected opponent at each
step with the downside of achieving a lower search depth.

Figure containing three subfigures A, B, and C. Subfigure A shows a Pommerman
board with four players labeled red, green, blue and purple. The red player is
marked as the player agent and the green agent as the selected opponent.
Subfigure B shows an exemplary search graph for the Single-Player Search
approach. The deepest path is expanded over the actions of the red player, the
opponent models of the purple, green, blue players and then again the red
player. Subfigure C shows an exemplary search graph for the Two-Player Search
approach. The deepest path is expanded over the actions of the red player, the
green player, and then the opponent models of the purple and blue players. The
Single-Player Search allows a deeper search with fully heuristic-based play
for all opponents, whereas the Two-Player Search allows a full exploration of
a selected opponent at each step with the downside of achieving a lower search
depth.

##  2\. Approach

When a model of the environment is available, leveraging this knowledge with
model-based algorithms comes with several advantages. Our work builds upon
MCTS, a general search method that aims to find a sequence of moves leading a
player to the expectantly most advantageous states, i.e. states in which the
they can win the game. This requires a model of the environment and a way to
evaluate states, which could both be provided or learned. By expanding
potential future states, the search can make use of additional game knowledge
to correct decisions where a suboptimal agent alone would fail. This allows to
filter potential dangers instead of having to face them. Additionally, search
methods usually return a principal variation, which is the sequence of future
moves that are considered best under the current knowledge. By iterating over
this sequence, it is possible to give a more throughout explanation of the
planned behavior of the agent.

Search methods require a strategy for selecting and expanding nodes in a
search tree. In our case, this is provided by a neural network model that
predicts value and policy distributions for each state, as we will detail
later. The search focuses on potential future states that appear to be
promising, while also exploring other paths. We use a variant of the Predictor
Upper Confidence Bounds (PUCT) algorithm Rosin (2011) to select and expand new
nodes. In particular, we refer to the algorithm adjusted by Silver et al.
(2017):

$\displaystyle
a_{t}=\text{argmax}_{a}\left(\text{Q}(s_{t},a)+U(s_{t},a)\right)\;,$ (1)
$\displaystyle\text{where}\quad
U(s_{t},a)=c_{\text{puct}}P(s_{t},a)\frac{\sqrt{\sum_{b}N(s_{t},b)}}{1+N(s_{t},a)}\;.$
(2)

Here, $a_{t}$ refers to the selected action at time step $t$, and
$\text{Q}(s_{t},a)$ is the action value for action $a$ of state $s_{t}$. The
action values of a node are updated by calculating a simple moving average of
all backpropagated value estimates of its subtree. The term $U(s_{t},a)$
describes the utility function for a particular action. It is given by the
product of its policy estimate $P(s_{t},a)$ and the total number of visits of
its parent divided by the number of visits $N(s_{t},a)$ of the selected
action. This prioritizes actions that have a higher policy estimate or were
chosen less frequently. The denominator ${1+N(s_{t},a)}$ is used to avoid
division by zero, and so that the nodes do not have to be fully expanded over
each action. The scalar $c_{\text{puct}}$ is a weighting parameter which
controls the amount of exploration compared to the greedy action selection of
choosing the highest Q-value.

Extensions of MCTS to games with more than two players come with conceptual
and practical challenges. In particular, the search space grows exponentially
with the number of players if all of them are considered in the search.

To address this issue, we propose two simple yet effective methods that reduce
multiplayer games to single and two-player games. They allow for the
application of AlphaZero-like frameworks without major adjustments. We
describe the methods in the following sections and provide a visualization
with Fig. 1.

###  2.1. Single-Player Monte-Carlo Tree Search

A straightforward approach for simplifying the search is to transform the
multi-player environment into a single-player environment by treating the
opponents as part of the environment. Instead of modifying the environment’s
dynamics, we simplify the search space by using deterministic opponent models
for other players. This also builds the basis of our second approach, which we
will introduce in the next section. Instead of searching through all actions
of all players, we limit the search to our player agent. In Fig. 1 (B), this
is the red player. The search tree is expanded solely using the actions of
this player. To execute a step in the deterministic environment, we then
gather actions for other players with their deterministic opponent models.
With all actions, the environment advances from state $s_{0}$ to the next
state $s_{1}$. Using this method, an n-player game effectively reduces to a
single-player game.

The quality of the resulting policy depends on the given opponent model. If
the opponent model differs from the actual behavior of the opponents, the
paths that are explored during search can get highly inaccurate and diverge
from potential future trajectories in the real environment. Convergence
guarantees towards optimal behavior are lost and a higher search depth could
even lead to deteriorations of the resulting policy.

Despite these unfavorable preconditions, our hypothesis is that this approach
can allow to assess the current situation in order to make good decisions with
respect to immediate dangers and the near future. The better the opponent
model fits the behavior of our opponents, the better we can exploit their
behavior. As we simulate a single agent, we can perform many simulation steps
that, although being inaccurate, could help to estimate the value of the
available actions. If one would use an optimal player as the opponent model,
our agent would plan how to act in the worst-case scenario, irrespective of
the actual behavior of the opponents.

Given an action space $\mathcal{A}$, the maximum branching factor per step is
$\lvert\mathcal{A}\rvert$ as we only expand moves of one agent.

This search method is summarized in Alg. 1. The function SelectLeafNode
corresponds to the node selection phase in MCTS and selects a leaf node by
following Eq. (1), SelectAction then selects a new action in this leaf. After
gathering the remaining actions with the given opponent models, performing a
step in the environment yields a new state. This state is evaluated from the
perspective of the player agent and the results are stored in a new node which
is appended to the tree. Finally, the value from the new node is
backpropagated without depth-wise negation using BackpropagateSP, returning
the updated tree.

1

2 Function  _SP_MCTS(_$tree$ , $playerID$, $opponentIDs$_)_:

3 $node,\,state\leftarrow$ SelectLeafNode($tree$)

4 $action\leftarrow$ SelectAction($node$)

5 $actions[playerID]\leftarrow action$

6

7 for  _$idx\in opponentIDs$_ do

8 $actions[idx]\leftarrow$ OpponentModel($idx$, $state$)

9

10 $state^{\prime}\leftarrow$ EnvironmentStep($state$, $actions$)

11 $result\leftarrow$ Evaluate($state^{\prime}$, $playerID$)

12 $tree^{\prime},node^{\prime}\leftarrow$ ExpandTree($tree$, $node$,
$action$, $result$)

13 return BackpropagateSP($tree^{\prime}$, $node^{\prime}$)

Algorithm 1 Single-player MCTS for multiplayer games. Shown is a single tree
search update iteration (simulation).

###  2.2. Two-Player Monte-Carlo Tree Search

The main limitation of our single-player search is that the play behavior of
our opponents remains deterministic, alternative moves are not considered, and
it cannot converge to an optimal strategy during the search if there is a
discrepancy between the opponent model and the actual opponent behavior. To
overcome these limitations to some extend, we propose an approach which we
call two-player search. This approach expands our single-player search by
exploring the moves of a selected opponent in each step, e.g. the green agent
in Fig. 1 (C). Instead of following the deterministic opponent model, the move
nodes for this opponent can be fully expanded. The selected opponent makes use
of the same prior policy for move selection as our agent. All remaining
opponents perform actions according to their given models. Note that the
selected opponent can change across steps in the simulation. Ideally, one
would select the opponent that, when allowed to deviate from the given
opponent model, results in the most reduction in our agent’s estimated value.
This can be seen as an instance of Best Reply Search (BRS) Schadd and Winands
(2011) where the opponent with the best reply is assumed to be known. For
simplicity, we choose the closest agent. While BRS skips moves of opponents
that are not selected, BRS+ Esser et al. (2013) uses move orderings to select
valid moves. We use opponent models to advance other opponents during the
search. In the example in Fig. 1 (C), our approach additionally expands the
actions of the green player. Like in vanilla MCTS, the values of the green
player are negated and then backpropagated to the red player. The other
opponents are seen as a part of the environment during this step.

The two-player search expands moves for selected opponents, thus leading to a
higher branching factor compared to the single-player search. Given an action
space $\mathcal{A}$, the maximum branching factor per step is now
$\lvert\mathcal{A}\rvert^{2}$. This is magnitudes smaller than the maximum
branching factor of complete enumeration with $\lvert\mathcal{A}\rvert^{n}$
for $n$ agents and of BRS with $(n-1)\lvert\mathcal{A}\rvert^{2}$.

The pseudocode is shown in Alg. 2. We alternately select a new action for the
player agent and a selected opponent and expand the tree accordingly. After
selecting both actions, the opponent models fill in the remaining actions to
perform a step in the environment. Note that this uses regular backpropagation
with negated values.

###  2.3. Combination with Learned Models

Based on the idea of AlphaZero Silver et al. (2017), we leverage an agent
model $f_{\theta}(o)=(\mathbf{p},v)$ to predict move probabilities
$\mathbf{p}$ and a value $v$ for a given observation $o$. These predictions
are used to guide the previously described search approaches. In the PUCT
formula (see Eq. 1), $P(s_{t},a)$ evaluates to $\mathbf{p}$ and $v$ is used to
update $Q(s_{t},a)$ upon expanding non-terminal nodes. The loss is defined as

$l=\alpha(z-v)^{2}-(1-\alpha)\mathbf{\pi}^{\intercal}\text{log}\,\mathbf{p}\;,$
(3)

where $z$ is the target value and $\pi$ the move probability according to the
search. The total loss consists of both the value loss, that is given as a
mean squared error, and the policy loss, that is formulated as a cross-entropy
loss. Hyperparameter $\alpha$ weights the value loss, Silver et al. (2017)
suggested using a low weight to reduce the chance of overfitting to the value
target. We iteratively update the model with the AdamW optimizer Loshchilov
and Hutter (2019).

1

2

3Function  _TP_MCTS(_$tree$ , $playerID$, $opponentIDs$_)_:

4 $node,\,state\leftarrow$ SelectLeafNode($tree$)

5 $agentID\leftarrow$ GetActiveAgent($node$)

6 $action\leftarrow$ SelectAction($node$)

7 if  _$agentID=playerID$_ then // player node

8 $result\leftarrow$ Evaluate($state$, $playerID$)

9

10 else // opponent node and step

11 $actions[agentID]\leftarrow action$

12 $actions[playerID]\leftarrow$ GetLastAction($node$)

13 for  _$idx\in opponentIDs\setminus\\{agentID\\}$_ do

14 $actions[idx]\leftarrow$ OpponentModel($idx$, $state$)

15 $state^{\prime}\leftarrow$ EnvironmentStep($state$, $actions$)

16 $result\leftarrow$ Evaluate($state^{\prime}$, $agentID$)

17

18 $tree^{\prime},node^{\prime}\leftarrow$ ExpandTree($tree$, $node$,
$action$, $result$)

19 return Backpropagate($tree^{\prime}$, $node^{\prime}$)

20

Algorithm 2 Two-player MCTS for multiplayer games. Shown is a single tree
search update iteration (simulation).

##  3\. Experiments in Pommerman

Pommerman Resnick et al. (2018a) is a multi-agent environment inspired by the
video game series _Bomberman_. Up to four bomber agents move across a discrete
grid-world and try to defeat their opponents by placing bombs. In the FFA
mode, each agent plays on their own and observes the the whole board except
for hidden power ups. In the _team_ and _radio_ modes, there are two teams of
two agents each. Agents can only observe their local surroundings up to a
distance of 4 blocks from their current position, horizontally or vertically.
In the radio mode, agents can additionally use a discrete communication
channel and send six bits per step. The FFA mode has been used in a
preliminary competition in 2018 Resnick et al. (2018a), the teams mode at
NeurIPS 2018 Resnick et al. (2020) and the radio mode at NeurIPS
2019111https://nips.cc/Conferences/2019/CompetitionTrack..

The Pommerman environment is very challenging, mainly because it is a
multiplayer game, its long time horizon of up to $800$ steps and partial
observability. With four players and $\lvert\mathcal{A}\rvert=6$ actions,
exhaustively exploring the search tree for $10$ steps in order to see a newly
placed bomb explode would require evaluating around $(6^{4})^{10}\approx
1.34e^{31}$ states. Given the environment’s time limit of $100$ milliseconds
per move, there is a need for more efficient solutions.

###  3.1. Training Setup

We implement our approach on top of CrazyAra Czech et al. (2021), an
AlphaZero-like MCTS framework that includes several extensions. Our agent
model $f_{\theta}$ uses a RISEv2 mobile architecture Czech et al. (2020)
adapted for the game Pommerman. The input of the model is of board size
$11\times 11$ with $23$ feature channels that encode the agent’s observation.
Further details are provided in our repository. The learning target $z$ is the
outcome of an episode and either win ($1$), draw ($0$) or loss ($-1$). Custom
intermediate rewards and discounting are not used.

Each training iteration is performed in a supervised manner on given datasets
according to the loss in Eq. (3) with $\alpha=0.1$ to avoid overfitting to the
value target. We perform data augmentation to mirror and rotate all
observations jointly with the targets to improve the sample efficiency.
Depending on the experiment, the datasets either originate from expert
demonstrations or from samples generated by our search approaches.

The official Pommerman environment Resnick et al. (2018a) is implemented in
Python and provides baseline agents called SimpleAgent. Our approach is
implemented in C++ and makes use of a faster reimplementation of the Pommerman
environment Weil and Alic (2021). This includes an agent called
SimpleUnbiasedAgent that improves upon the provided C++ SimpleAgent and
reduces the decision bias depending on the agent’s id.222We found that the C++
SimpleAgent behaves differently depending on its agent id and start position,
resulting in varying average win rates. Most of the results presented in the
following sections use this reimplementation and the FFA mode, but we conclude
with preliminary results in the Python environment.

An overview of the considered agents is presented in Tab. 1.

Table 1. Overview of used agents. Abbreviation |  Description
---|---
SimplePy |  SimpleAgent from the Python environment.
SimpleCpp |  SimpleUnbiasedAgent from pomcpp2.
RawNet |  Chooses the action with the highest Q-value of the player model.
SP-MCTS |  Our approach with the single-player search.
TP-MCTS |  Our approach with the two-player search.

###  3.2. Learning from Demonstrations

To investigate the effectiveness of our search approaches, we first study
their combination with learning from demonstrations. We generate a data set
with one million samples of SimpleCpp agents playing FFA games with random
start conditions for up to $800$ steps. This includes samples from the
perspective of each player, i.e. we collect four trajectories per episode. The
model is trained using our loss from Eq. (3) with Supervised Learning (SL),
where the target policy equals the actions chosen by the agents. The resulting
model is used as the player agent in conjunction with the search methods SP-
MCTS and TP-MCTS. For these experiments, we set the opponent models to
SimpleCpp with random seeds. Thus, the search cannot foreshadow the exact
moves that will be selected by the actual opponents, but captures their
overall behavior.

Figure 2. TP-MCTS SL outperforms SP-MCTS SL for higher number of simulations.
When random initialized models are used, SP-MCTS has consistently higher win
rates than TP-MCTS. Shown are the win rates of SP-MCTS and TP-MCTS against
SimpleCpp in the FFA mode. The suffix SL indicates that the search uses a
model trained on demonstrations. The standard deviation of five runs is
highlighted in the shaded area.

Shown is a line plot of the win rates of SP-MCTS and TP-MCTS against SimpleCpp
in the FFA mode, depending on the number of search simulations per step. The
plot contains the results for both, randomly initialized models and for the
models trained on demonstrations. In all cases, the win rate saturates with a
higher number of simulations. However, the initial win rate at 0 simulations
differs. The SL models achieve a win rate of around 40 percent, while the
randomly initialized models achieve a win rate around 10 percent. With a
higher number of simulations and the SL models, TP-MCTS outperforms SP-MCTS.
For randomly initialized models, SP-MCTS has consistently higher win rates
than TP-MCTS. The standard deviation of five runs is highlighted in a shaded
area, showing a small standard deviation except for the SP-MCTS runs.

Fig. 2 shows the win rate of our approaches over $1000$ games against
SimpleCpp opponents for increasing simulations per step. For zero simulations,
we use the respective RawNet agent that chooses an action based on the maximum
probability of the root nodes’s policy distribution without any look-ahead.
The results are averaged over five models trained on the same data set with
different seeds. Note that with four agents in the FFA mode, a win rate of
$25\%$ indicates equal performance if there are no draws. We include the
results for randomly initialized models as a baseline.

We can see in Fig. 2 that for the randomly initialized models, SP-MCTS
highlighted in blue greatly outperforms TP-MCTS highlighted in green. This is
because TP-MCTS uses the given model to guide the search of the closest
opponent. Our agent tries to exploit the mistakes of its opponents. If the
opponent model is poor, the agent gets overconfident in taking bad actions and
the search results do not transfer well to the real environment.

This is consistent with the comparably good results of TP-MCTS SL when the
expert model is used. While SP-MCTS SL outperforms TP-MCTS SL for a low number
of simulations, TP-MCTS SL achieves higher win rates for $250,\,500$ and
$1000$ simulations per step. The win rate for zero simulation steps of the
learned model is greater than $25\%$, which indicates that its combination
with action filtering already performs better than SimpleCpp. With a high
number of simulations, TP-MCTS SL can reach a sufficient search depth and
benefit from an increased exploration of the opponent’s actions.

To summarize, the result for the model initialized with expert demonstrations
are promising and we see that both search approaches greatly improve the
performance of a randomly initialized model. We now investigate whether these
models can be improved by iteratively training on samples generated by the
search.

Figure 3. In reinforcement learning, both SP-MCTS versions appear to perform
better than TP-MCTS. Shown are the win rates of RL-based SP-MCTS and TP-MCTS
against SimpleCpp in the FFA mode over $50$ training iterations with $250$
simulations. The configurations with suffix SL are initialized with the model
trained on demonstrations. The standard deviation of five runs is highlighted
in the shaded area.

Shown is a line plot with the win rates of the RL-based SP-MCTS and TP-MCTS
approaches against SimpleCpp in the FFA mode over 50 training iterations with
250 simulations. The plot contains the results for both, randomly initialized
models and for the models trained on demonstrations. Both SP-MCTS runs and TP-
MCTS with a random model improve over the initial win rates. The win rate of
TP-MCTS SL decreases. The standard deviation of five runs is highlighted in a
shaded area and shows that TP-MCTS has a slightly higher variance. In
reinforcement learning, both SP-MCTS versions appear to perform better than
TP-MCTS.

###  3.3. Optimization with Reinforcement Learning

As the next step, we aim to improve the models from the previous section with
RL. We simulate FFA games against SimpleCpp opponents for $100\,000$ steps and
use the search’s results as the learning target for the policy and value
functions. The resulting model is then used in the next iteration and the
process is repeated. As before, all agent and opponent models are set to
SimpleCpp. We train our agent for $50$ iterations with $250$ simulations per
step. This setting has been chosen as a trade-off between required simulation
time and win rate based on the previous experiments.

Table 2. Win rate, tie rate, search depth, search runtime per step and environment steps for our approaches with 1000 simulations and different opponent models against SimpleCpp opponents for 1000 games. All results are averaged over five models. Model | Method | Opponent Model | Win Rate | Tie Rate | Search Depth | Search Time [ms] | Environment Steps
---|---|---|---|---|---|---|---
SL | SP-MCTS | SimpleCpp | $0.78\pm 0.03$ | $0.07\pm 0.02$ | $17.91\pm 7.60$ | $35.30\pm 7.57$ | $188.99\pm 3.20$
RawNet | $0.76\pm 0.03$ | $0.10\pm 0.02$ | $21.46\pm 22.09$ | $266.62\pm 138.13$ | $191.02\pm 2.91$
TP-MCTS | SimpleCpp | $\mathbf{0.91\pm 0.01}$ | $0.06\pm 0.01$ | $11.57\pm 6.05$ | $36.89\pm 7.52$ | $246.40\pm 5.93$
RawNet | $\mathbf{0.92\pm 0.01}$ | $0.06\pm 0.01$ | $12.14\pm 7.17$ | $164.61\pm 64.46$ | $254.79\pm 11.26$
SRL | SP-MCTS | SimpleCpp | $\mathbf{0.94\pm 0.01}$ | $0.02\pm 0.01$ | $21.39\pm 7.45$ | $37.34\pm 6.74$ | $275.23\pm 9.40$
RawNet | $\mathbf{0.90\pm 0.01}$ | $0.04\pm 0.01$ | $25.52\pm 10.37$ | $315.74\pm 139.75$ | $288.47\pm 10.26$
RL | SP-MCTS | SimpleCpp | $0.82\pm 0.01$ | $0.07\pm 0.00$ | $21.98\pm 8.65$ | $36.49\pm 6.52$ | $331.99\pm 7.38$
RawNet | $0.71\pm 0.03$ | $0.08\pm 0.01$ | $28.30\pm 11.73$ | $309.40\pm 140.20$ | $316.81\pm 9.46$

During our experiments, we noticed that the results highly depend on the
amount of noise introduced by exploration within the search. With the regular
policy target $\pi$, the agents get stuck in local optima with low win rates
after around 15 iterations. In the following, we focus on a configuration with
a modified policy target
$\pi^{\prime}=0.5\cdot\pi+0.5\cdot\mathbbm{1}\\{\pi=\max\pi\\}$, as we found
the corresponding results to be more insightful. This reduces the noise
introduced by the search and in turn increases the probability of choosing the
best action with the highest visit count by 50%.

The results in Fig. 3 are averaged over five runs using the models from the
previous section. We can see that the win rate of SP-MCTS and TP-MCTS
increases, suggesting improvements of the corresponding models. However, the
win rate of SP-MCTS reaches its peak at around 15 iterations and starts to
slowly decline afterwards. While the win rate of SP-MCTS SL slightly increases
from 80% to 90%, the win rate of TP-MCTS SL decreases over time. Investigating
the resulting policies reveals that the agents learn to play passively with
RL, i.e. they wait for their opponents and evade bombs when necessary. This
strategy is unexpected but expedient, as SimpleCpp opponents are suboptimal
and often put themselves in unfavorable situations.

This is particularly visible in the SP-MCTS SL configuration with a win rate
of around 90% after training with RL. We show our agent’s action distribution
for selected training iterations in Fig. 4. For iteration 0, this is the
action distribution of the original SL models. It can be seen that the model
gradually shifts from an initially active policy with few idle actions to a
policy that predominantly idles. While the results show that this is a
successful strategy against SimpleCpp, the passive behavior will fail against
better opponents.

Figure 4. SP-MCTS SL becomes more passive during reinforcement learning over
time, reflected by the higher use of idle actions. Shown is the action
distribution of SP-MCTS SL during training with RL at iterations 0, 15, 25 and
50. The standard deviation of five runs is highlighted by the error bars.

Shown is a bar plot of the action distribution of SP-MCTS SL during training
with RL at iterations 0, 15, 25 and 50. The standard deviation of five runs is
highlighted by error bars. They show a comparably higher standard deviation
for idle actions. One can see that SP-MCTS becomes more passive during
reinforcement learning over time, reflected by a higher use of idle actions
after more training iterations.

The decreasing win rate of TP-MCTS SL is consistent with these findings. While
SP-MCTS SL assumes the opponents to behave like SimpleCpp, TP-MCTS SL uses its
own policy to expand the moves of the closest opponent. By selecting idle with
a higher probability, the opponent model diverges more and more from the
actual opponent playing behavior and the win rate of this approach decreases.

###  3.4. Learned Opponent Models

In the previous sections, we investigated our search methods in combination
with supervised and reinforcement learning. However, we still used the
heuristic SimpleCpp as the opponent model during planning. As SimpleCpp is
clearly suboptimal, this may lead to problems when applying the agent against
opponents with strategies that differ significantly. Consequently, we explore
the usage of RawNet opponent models within this section. As the combination of
our model learned from demonstrations with our simple action filter is
apparently better than SimpleCpp, agents using RawNet opponent models should
be capable of adapting to better players.

Tab. 2 shows the results of our search approaches for SimpleCpp and RawNet
opponent models against SimpleCpp opponents. The search uses 1000 simulations
to be comparable to the results from Fig. 2. We focus on SP-MCTS in the RL
setting due to the weak performance of TP-MCTS and show the results for the
models initialized from zero (RL) and the ones initialized with SL and refined
with RL (SRL). For both, we use the models after $15$ training iterations due
to the peak in Fig. 3. All experiments were performed for each of the five
respective models and we report the mean results. Ties include episodes that
are not done.

For the SL models, we can see that the win, tie rates and environment steps
are nearly unaffected when using RawNet instead of SimpleCpp for both of our
approaches. However, it is noticeable that the search depth increases slightly
and the search time increases drastically. We hypothesize that the increase in
search depth is caused by the better opponent behavior, i.e. episodes within
the search do not end as quickly as RawNet is a stronger opponent. However, as
the actual opponents are still SimpleCpp, this is not reflected in the real
environment, as visible in similar numbers of environment steps. The increase
in search time can be explained by our prototypical implementation of the
RawNet opponent models. While the model inference for SP-MCTS and TP-MCTS is
executed in batches, we currently use batch size one for RawNet opponent
models within the search. This drastically increases the time to evaluate the
opponent models per step. With an halved search depth in TP-MCTS, the search
time also decreases greatly as there are fewer inference calls of the opponent
model.

For the SRL and RL models, we notice that the win rate slightly decreases when
using RawNet opponent models. However, the SRL model yields higher win rates
than SP-MCTS with the SL model and is comparable to TP-MCTS with the SL model.
The win rate of the RL model without training on demonstrations is similar to
the initial SL model for SP-MCTS. For the SRL and RL models, there is high
increase in environment steps compared to the SL models. This indicates that
the agents play more passively.

We conclude that in most cases, the RawNet opponent model has a neglectable
effect on the win rate against opponents that were seen in training. With a
more efficient implementation, it could be a good alternative to hand-crafted
heuristics. The best agents are TP-MCTS with the SL model and SP-MCTS with the
SRL model.

###  3.5. Evaluation in the Official Environment

Finally, we evaluate our approach in the official Python environment Resnick
et al. (2018a) to investigate whether our previous results transfer to the
Python environment and the SimplePy opponent. The starting positions are
randomized to reduce their influence on the results. As the previous section
showed a high search time when using RawNet, we restrict the number of
simulations to 250 in this case to stay below the official time constraint of
100 ms.

Table 3. Win rate and tie rate of our approaches against SimplePy opponents in the official environment for 100 games. We use 1000 simulations for SimpleCpp and 250 simulations for RawNet. All results are averaged over five models. Model | Method | Opponent Model | Win Rate | Tie Rate
---|---|---|---|---
SL | SP-MCTS | SimpleCpp | $\mathbf{0.78\pm 0.04}$ | $0.12\pm 0.02$
RawNet | $\mathbf{0.67\pm 0.06}$ | $0.25\pm 0.04$
TP-MCTS | SimpleCpp | $0.66\pm 0.05$ | $0.32\pm 0.05$
RawNet | $0.61\pm 0.06$ | $0.34\pm 0.06$
SRL | SP-MCTS | SimpleCpp | $0.65\pm 0.09$ | $0.30\pm 0.09$
RawNet | $0.63\pm 0.05$ | $0.32\pm 0.04$
RL | SP-MCTS | SimpleCpp | $\mathbf{0.74\pm 0.03}$ | $0.22\pm 0.03$
RawNet | $\mathbf{0.72\pm 0.04}$ | $0.23\pm 0.03$

ABC

Figure 5. Visited board positions of the SP-MCTS SL (A) and RL agents (B)
against SimplePy in the official environment. Subfigure (C) complements this
with the number of unique positions visited within $20$ steps. While the SP-
MCTS SL agents show active movement behavior, the agents trained with RL are
very passive. The results are averaged over 5 models with 100 games each.

Three subfigures labeled A, B and C. A and B show heatmaps of the visited
board positions of the SP-MCTS SL and RL agents against SimplePy in the
official environment. Subfigure C complements this with bar plots for both
agents that illustrate the number of unique positions visited within 20 steps.
While the SP-MCTS SL agents show active movement behavior, the agents trained
with RL are very passive. This is indicated by very low color intensities
except for the starting area in B and by fewer unique visited positions in C.
The results are averaged over 5 models with 100 games each.

The results against SimplePy agents in the FFA mode are shown in Tab. 3. In
contrast to our previous evaluation against SimpleCpp in Tab. 2, SP-MCTS
outperforms TP-MCTS by a noticeable margin for the SL models. While the
results of SP-MCTS are similar to our previous evaluation, the win rate of TP-
MCTS strongly decreases. A potential reason for that could be the difference
between the actual opponent behavior and the one considered during planning.
The search might assume that opponents play too well, resulting in an overly
defensive play style. This is also indicated by the high reduction in the win
rate when using the RawNet opponent model in SP-MCTS with the SL models.
Another indicator for the defensive playing style is the high tie rate and the
high similarity of the results to the SRL models. Interestingly, the RL models
outperform the SRL models in this setup. It could be that they generalize
better against other opponents because they were not trained on
demonstrations. We notice that the tie rates of all agents are very high,
especially for the agents with lower win rates. Most of these ties are caused
by episodes that do not terminate within the environment’s limit of 800 steps.
In turn, the average number of environment steps per episode also increases
greatly to up to $490\pm 230$ steps for SP-MCTS with the RL model. We omit the
steps in the table, their overall trend for the individual models and methods
is similar to the previous results. Despite the reduced win rates, our agents
still loose very few games due to a defensive play style.

Recent related work with learning-based MCTS and reward shaping reports a win
rate of around $0.7$ against SimplePy opponents in the FFA mode Yang et al.
(2021). Our approaches reach competitive win rates without reward shaping.
Additionally, the RL agent was trained from scratch and did not use learning
from demonstrations.

We show further details regarding the movement behavior of the SP-MCTS SL and
RL agents with SimpleCpp opponent models in Fig. 5. Subfigures (A) and (B)
show the average steps on the individual board positions per game. For the
visualizations, we rotated the board according to the agents’ starting
positions such that they always start at the upper left corner. This allows us
to see how much the agents explore the map, irrespective of their starting
position. In Fig. 5 (A), we can see that the SP-MCTS SL agent actively
explores the map while avoiding the border, except for the tiles close to its
starting position. This is reasonable, as agents at the border have fewer
options for evasion. The noticeable ring across the map at distance one to the
border is due to the randomization of the map. Only destructible objects and
passages are placed at these positions, ensuring that the agents can reach
each other. In Fig. 5 (B) and (C), we can see that the SP-MCTS RL agents stay
very close to their starting positions and rarely move across the map,
confirming that they develop a very defensive playing style.

##  4\. Discussion

Next, we discuss the insights and limitations of our approach. One major
insight is that in Pommerman, focusing on the win rate alone is not enough.
While a high win rate is an indicator for subjectively good agent behavior,
further analysis of the behavior of the agents is required to assess the
quality of their policies.

We have shown that no custom reward shaping is necessary to significantly
improve agent models with our search methods. Our approach SP-MCTS can reach
proficient level of play in the FFA environment and even compensate for a bad
model. TP-MCTS can outperform SP-MCTS with a higher number of simulations, but
only when a good model is given. Our evaluation with SimplePy opponents
suggest that there might not be a single opponent model that allows the agents
to perform well in all cases. If the real opponents show suboptimal behavior
that is not captured by the opponent model, our approaches become overly
defensive. One limitation of our experiments is that we only considered
deterministic opponent models and models trained on SimpleCpp agents. Instead,
one could collect samples from the best available agents and train models to
imitate their behavior. We expect that combining these models with our search
approaches could further increase their playing strength. Stochastic opponent
models could be considered by expanding multiple different opponent actions
into individual nodes or merging different opponent trajectories into a single
node with the expected or worst-case behavior. This would greatly increase the
sample complexity, but could reduce wrongful exploitation when facing
different opponents and make the search more applicable to realistic
scenarios. Another direction for future work lies in the way opponents are
selected by TP-MCTS. In our case, we always expand the actions of the closest
opponent. Extensions could predict the most dangerous opponent or selectively
expand opponents based on a computational budged. Finally, we think that
combining more computationally expensive search methods Esser et al. (2013);
Baier and Kaisers (2020b) with learned opponent models poses an interesting
direction for future research.

While RL improved the win rate of some configurations, the resulting behavior
did subjectively deteriorate. In particular, the agents trained via RL were
predominantly passive. Providing a fine-grained reward signal might be
necessary to learn the desired behavior, at the cost of introducing additional
bias. Another interesting aspect of RL would be to investigate pure self-play,
e.g. having four learning SP-MCTS agents play against each other. Preliminary
experiments not discussed in this paper suggest that self-play agents also
develop a passive playing style, further strengthening the need for
intermediate rewards when using RL. A different approach to stabilize training
in a self-play setting could be to anticipate the learning of other agents in
the environment Foerster et al. (2018). One problem that emerges without self-
play is that high win rates lead to unbalanced data sets. We experimented with
resampling techniques to draw samples for each value and action target with
equal probability, but this did not lead to noticeable improvements. To avoid
overfitting on specific opponents, population-based approaches with different
opponents would also be worth investigating.

Lastly, we focused on the FFA mode. Extensions of our approach to the team and
radio mode would be interesting. Initial results show that our agent performs
well against a team of SimplePy opponents, but struggles against docker agents
from previous challenges. To deal with the partial observability in form of
the now limited view, agent models leveraging recurrent neural networks and
learned communication can be explored. We think that including bomb kicks in
the demonstration data set, e.g. by considering samples from different agents,
could greatly help our agents to react appropriately when facing these
opponents. It would also be interesting to combine our approaches with learned
environment models, especially to avoid hand-crafting environment dynamics
that can handle the limited view in the team and radio modes.

##  5\. Related Work

The combination of RL and tree search has been extensively studied in the
domain of games, in particular board games. One breakthrough in this field is
the work by Anthony et al. (2017), which applied tree search and reinforcement
learning to learn the game of Hex. This approach was later followed and
popularized in the AlphaZero (Silver et al., 2018) algorithm by learning the
games Go, Shogi and Chess from zero knowledge. AlphaZero has then been re-
implemented and extended for Go Wu (2019) and multiple chess variants Czech et
al. (2021). Later works in the form of MuZero Schrittwieser et al. (2020)
emphasized the environment model by learning a model that is used for planning
rather than relying on the actual environment itself.

Planning approaches using tree search have also been successfully applied in
multiplayer games with more than two players Luckhart and Irani (1986);
Nijssen (2013). However, they can suffer from a shallow search depth Baier and
Kaisers (2020a) in practice due to the high combinatorial complexity. Many
approaches increase the search depth by reducing the time spent to simulate
opponents and expectedly suboptimal moves Sturtevant and Korf (2000); Schadd
and Winands (2011); Baier and Kaisers (2020b). In addition to simplifying the
search tree, integrating domain knowledge in the form of value heuristics into
MCTS has shown to greatly improve performance in multiplayer games Szita et
al. (2009); Nijssen and Winands (2011). Petosa and Balch (2019) extend the
idea of AlphaZero and apply learned value estimation in multiplayer games, but
iterate over all players during search. On contrast, Ozair et al. (2021)
consider opponents to be part of the environment’s dynamics and learn a latent
variable to sample state transitions for MCTS that include the opponent’s
moves. While they only considered games with up to two players in their
evaluation, the idea should be generally applicable.

Previous work in Pommerman Resnick et al. (2018a) ranges from learning- and
planning-based approaches to the combination of both. Due to the sparse reward
and long time horizon, approaches leveraging model-free RL struggle to beat
simple heuristics without further modifications of the environment or training
procedure Gao et al. (2019b). Resnick et al. (2018b) suggest to start training
close to terminal states, Peng et al. (2018) use pathfinding-based actions
instead of direct movement and Gao et al. (2019a) employ reward shaping,
action filtering and curriculum learning. However, agents using model-free RL
have shown inferior performance compared to planning-based approaches. Their
main limitations are the time constraints for decision making and the high
branching factor. The winners of the NeurIPS 2018 competition combine planning
with deterministic and pessimistic rollouts to increase the search depth
Osogami and Takahashi (2019). Rollouts with more than ten steps allow the
agents to account for explosions of recently placed bombs during planning. The
second-placed agent uses minimax search with an average search depth of only
two steps Resnick et al. (2020), an extension of this agent won the subsequent
competition held at NeurIPS 2019. Learning and planning can also be combined.
For example, Kartal et al. (2019) use model-free RL but initialize their agent
with imitation learning on samples generated by shallow MCTS with random
agents. Yang et al. combine MCTS with a learned model, they initialize their
agent with imitation learning and employ reward shaping and sophisticated
action filtering heuristics during search Yang et al. (2021).

We observe that, although they reach proficient levels of play, recent
planning-based approaches either suffer from a shallow search depth or
introduce high bias through search heuristics and reward shaping. In this
paper, we explored the feasibility of learning-based MCTS in the Pommerman
environment with opponent models, given only an environment model, a sparse
reward signal at the end of the episode, and demonstrations from other agents.

##  6\. Conclusion

With this work, we proposed two methods based on MCTS that make use of
deterministic opponent models and reduce competitive multiplayer games to
single- and two-player games. This greatly reduces the complexity of the
search space and makes MCTS applicable to complex environments with time
constraints. We evaluated our approach in the game Pommerman without custom
reward shaping. We found that both methods load to high improvements in terms
of win rate against baseline agent heuristics, both when using an
uninitialized model and a model trained on demonstrations. Our two-player
search outperforms the single-player search, but requires more simulations and
a good initial model. While the application of RL based on the samples
generated by the search leads to improved win rates in most cases, we found
that the agents develop a passive playing style. We think that intermediate
rewards might be necessary to learn a more active policy in a RL setup.

Future work could investigate how our approaches perform if demonstrations
from better agents are used to train the initial models. To further explore
the RL setup, the next step would be to integrate reward shaping. It would
also be interesting to expand upon the opponent selection in our two-player
search, e.g. by predicting the most dangerous opponent in each step. Another
promising direction would be to consider MCTS with stochastic opponent models.
To extend our approach to the team and radio modes, the combination of MCTS
with recurrent neural networks and learned communication between agents could
be explored further.

The authors thank Jonas Ringsdorf for assisting with the implementation and
evaluation, Adrian Alic for the development of pomcpp, and Quentin Delfosse as
well as Jannis Blüml for valuable feedback. This work benefited from the
Hessian Ministry of Science and the Arts (HMWK) project ‘The Third Wave of AI’
and has been co-funded by the German Research Foundation (DFG) in the
Collaborative Research Center (CRC) 1053 MAKI.

## References

  * (1)
  * Anthony et al. (2017) Thomas Anthony, Zheng Tian, and David Barber. 2017\.  Thinking Fast and Slow with Deep Learning and Tree Search. In _Advances in Neural Information Processing Systems 30_. 5360–5370.
  * Baier and Kaisers (2020a) Hendrik Baier and Michael Kaisers. 2020a.  Guiding Multiplayer MCTS by Focusing on Yourself. In _IEEE Conference on Games_. 550–557.
  * Baier and Kaisers (2020b) Hendrik Baier and Michael Kaisers. 2020b.  Opponent-Pruning Paranoid Search. In _Proceedings of the 15th International Conference on the Foundations of Digital Games_. ACM, 10:1–10:7.
  * Czech et al. (2021) Johannes Czech, Patrick Korus, and Kristian Kersting. 2021\.  Improving AlphaZero Using Monte-Carlo Graph Search. In _Proceedings of the International Conference on Automated Planning and Scheduling_ , Vol. 31. 103–111.
  * Czech et al. (2020) Johannes Czech, Moritz Willig, Alena Beyer, Kristian Kersting, and Johannes Fürnkranz. 2020\.  Learning to Play the Chess Variant Crazyhouse Above World Champion Level With Deep Neural Networks and Human Data.  _Frontiers in Artificial Intelligence_ 3 (2020).
  * Esser et al. (2013) Markus Esser, Michael Gras, Mark H. M. Winands, Maarten P. D. Schadd, and Marc Lanctot. 2013\.  Improving Best-Reply Search. In _Proceedings of the 8th International Conference on Computers and Games_ _(Lecture Notes in Computer Science, Vol. 8427)_. Springer, 125–137.
  * Foerster et al. (2018) Jakob N. Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. 2018.  Learning with Opponent-Learning Awareness. In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_. 122–130.
  * Gao et al. (2019a) Chao Gao, Pablo Hernandez-Leal, Bilal Kartal, and Matthew E. Taylor. 2019a.  Skynet: A Top Deep RL Agent in the Inaugural Pommerman Team Competition.  (2019).  arXiv:1905.01360 [cs.MA]
  * Gao et al. (2019b) Chao Gao, Bilal Kartal, Pablo Hernandez-Leal, and Matthew E. Taylor. 2019b.  On Hard Exploration for Reinforcement Learning: A Case Study in Pommerman. In _Proceedings of the 15th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_. AAAI Press, 24–30.
  * Kartal et al. (2019) Bilal Kartal, Pablo Hernandez-Leal, Chao Gao, and Matthew E. Taylor. 2019.  Safer Deep RL with Shallow MCTS: A Case Study in Pommerman.  (2019).  arXiv:1904.05759 [cs.LG]
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled Weight Decay Regularization. In _Proceedings of the 7th International Conference on Learning Representations_.
  * Luckhart and Irani (1986) Carol Luckhart and Keki B. Irani. 1986.  An Algorithmic Solution of N-Person Games. In _Proceedings of the 5th National Conference on Artificial Intelligence_. Morgan Kaufmann, 158–162.
  * Nijssen (2013) Joseph Antonius Maria Nijssen. 2013\.  _Monte-Carlo Tree Search for Multi-Player Games_.  Ph.D. Dissertation.
  * Nijssen and Winands (2011) J. (Pim) A. M. Nijssen and Mark H. M. Winands. 2011.  Playout Search for Monte-Carlo Tree Search in Multi-player Games. In _Proceedings of the 13th International Conference on Advances in Computer Games_ _(Lecture Notes in Computer Science, Vol. 7168)_. Springer, 72–83.
  * Osogami and Takahashi (2019) Takayuki Osogami and Toshihiro Takahashi. 2019.  Real-time tree search with pessimistic scenarios: Winning the NeurIPS 2018 Pommerman Competition. In _Proceedings of the 11th Asian Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 101)_. PMLR, 583–598.
  * Ozair et al. (2021) Sherjil Ozair, Yazhe Li, Ali Razavi, Ioannis Antonoglou, Aaron Van Den Oord, and Oriol Vinyals. 2021\.  Vector Quantized Models for Planning. In _Proceedings of the 38th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 139)_. PMLR, 8302–8313.
  * Peng et al. (2018) Peng Peng, Liang Pang, Yufeng Yuan, and Chao Gao. 2018\.  Continual Match Based Training in Pommerman: Technical Report.  (2018).  arXiv:1812.07297 [cs.AI]
  * Petosa and Balch (2019) Nick Petosa and Tucker Balch. 2019.  Multiplayer AlphaZero.  (2019).  arXiv:1910.13012 [cs.AI]
  * Resnick et al. (2018a) Cinjon Resnick, Wes Eldridge, David Ha, Denny Britz, Jakob N. Foerster, Julian Togelius, Kyunghyun Cho, and Joan Bruna. 2018a.  Pommerman: A Multi-Agent Playground. In _Joint Proceedings of the Workshops co-located with the 14th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ _(CEUR Workshop Proceedings, Vol. 2282)_.  CEUR-WS.org/Vol-2282/MARLO_104.pdf
  * Resnick et al. (2020) Cinjon Resnick, Chao Gao, Görög Márton, Takayuki Osogami, Liang Pang, and Toshihiro Takahashi. 2020.  Pommerman & NeurIPS 2018. In _The NeurIPS ’18 Competition_ , Sergio Escalera and Ralf Herbrich (Eds.). Springer International Publishing, Cham, 11–36.
  * Resnick et al. (2018b) Cinjon Resnick, Roberta Raileanu, Sanyam Kapoor, Alexander Peysakhovich, Kyunghyun Cho, and Joan Bruna. 2018b.  Backplay: ”Man muss immer umkehren”.  (2018).  arXiv:1807.06919 [cs.LG]
  * Rosin (2011) Christopher D Rosin. 2011\.  Multi-armed bandits with episode context.  _Annals of Mathematics and Artificial Intelligence_ 61, 3 (2011), 203–230.
  * Schadd and Winands (2011) Maarten P. D. Schadd and Mark H. M. Winands. 2011.  Best Reply Search for Multiplayer Games.  _IEEE Transactions on Computational Intelligence and AI in Games_ 3, 1 (2011), 57–66.
  * Schrittwieser et al. (2020) Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. 2020\.  Mastering atari, go, chess and shogi by planning with a learned model.  _Nature_ 588, 7839 (2020), 604–609.
  * Silver et al. (2018) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. 2018\.  A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.  _Science_ 362, 6419 (2018), 1140–1144.
  * Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. 2017\.  Mastering the game of go without human knowledge.  _Nature_ 550, 7676 (2017), 354–359.
  * Sturtevant and Korf (2000) Nathan R. Sturtevant and Richard E. Korf. 2000.  On Pruning Techniques for Multi-Player Games. In _Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence_. AAAI Press / The MIT Press, 201–207.
  * Świechowski et al. (2023) Maciej Świechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Mańdziuk. 2023.  Monte Carlo Tree Search: a review of recent modifications and applications.  _Artificial Intelligence Review_ 56 (2023), 2497–2562.
  * Szita et al. (2009) István Szita, Guillaume Chaslot, and Pieter Spronck. 2009\.  Monte-Carlo Tree Search in Settlers of Catan. In _Advances in Computer Games_. Springer, 21–32.
  * Weil and Alic (2021) Jannis Weil and Adrian Alic. 2021.  pomcpp2: Pommerman Environment in C++.  https://github.com/jw3il/pomcpp2.
  * Wu (2019) David J Wu. 2019\.  Accelerating Self-Play Learning in Go.  (2019).  arXiv:1902.10565 [cs.LG]
  * Yang et al. (2021) H. Yang, S. Li, X. Xu, X. Liu, Z. Meng, and Y. Zhang. 2021\.  Efficient Searching With MCTS and Imitation Learning: A Case Study in Pommerman.  _IEEE Access_ 9 (2021), 48851–48859.

  *[MCTS]: Monte-Carlo Tree Search
  *[RL]: Reinforcement Learning
  *[FFA]: Free For All
  *[PUCT]: Predictor Upper Confidence Bounds
  *[BRS]: Best Reply Search
  *[SL]: Supervised Learning