# Learning to Play Two-Player Perfect-Information Games without Knowledge

Quentin Cohen-Solal

► To cite this version:

Quentin Cohen-Solal. Learning to Play Two-Player Perfect-Information Games without Knowledge.
2026. hal-05457184

HAL Id: hal-05457184

https://hal.science/hal-05457184v1

Preprint submitted on 14 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Learning to Play Two-Player Perfect-Information Games without Knowledge

**Quentin Cohen-Solal, Fixed-term researcher**

LAMSADE, Université Paris Dauphine - PSL, CNRS
Place de Lattre de Tassigny, Paris, 75016, France
and

CRIL, Univ. Artois and CNRS
Rue Jean Souvraz SP 18, Lens, F-62300, France
and

Normandie University, UNICAEN, CNRS, GREYC
6 Boulevard du Maréchal Juin, Caen, 14 000, France

QUENTIN.COHEN-SOLAL@DAUPHINE.PSL.EU

**Editor:** My editor

## Abstract

This paper proposes several techniques for learning game state evaluation functions by reinforcement. The first generalizes tree bootstrapping to reinforcement learning with non-linear functions, ensuring no information loss. The second modifies Unbounded Best-First Minimax by extending the best action sequences to terminal states. The third replaces the classic $+1/-1$ game outcome with reinforcement heuristics such as quick wins, slow defeats, scoring, or mobility. The fourth introduces a completion technique that leverages state resolution. The fifth defines a new distribution for action selection.

Experiments show these techniques significantly improve play strength. We combine them in a single algorithm, Athénan, and compare it to ExIt, a leading self-play reinforcement learning algorithm without prior knowledge. Results demonstrate that Athénan outperforms ExIt.

Athénan is then applied to the games Hex, Othello, and Arimaa. In all cases, it surpasses the state of the art without using domain knowledge. We also test Athénan on the single-player game Morpion Solitaire, where it again reaches state-of-the-art performance without prior knowledge.

Overall, Athénan shows that reinforcement learning can achieve cutting-edge results across a diverse set of games without relying on handcrafted heuristics or expert input.

**Keywords:** Reinforcement Learning, Learning without Human Knowledge, Minimax, Search Algorithms, Games

## 1 Introduction

One of the most difficult tasks in artificial intelligence is the sequential decision making problem (Littman, 1996), whose applications include robotics and games. As for games, the successes are numerous. Machine surpasses man for several games, such as backgammon, checkers, chess, and go (Silver, Schrittwieser, Simonyan, Antonoglou, Huang, Guez, Hubert, Baker, Lai, Bolton, et al., 2017b). A major class of games is the set of two-player games in which players play in turn, without
any chance or hidden information. This class is sometimes called two-player perfect information<fnref n="1" />
games (Mycielski, 1992) or also two-player combinatorial games. There are still many challenges
for these games. For example, at the game of Hex, computers have only been able to beat strong
humans since 2020 (Cazenave, Chen, Chen, Chen, Chiu, Dehos, Elsa, Gong, Hu, Khalidov, et al.,
2020). In the context of general game playing (Genesereth, Love, and Pell, 2005), i.e. the context of
playing a unknown game with only a short time to learn how to play well: man is always superior to
machine (even restricted to games with perfect information). In this article, we focus on two-player
zero-sum games with perfect information. Note that the algorithms we propose also apply in the
single-player case. We demonstrate this in the context of Morpion Solitaire.

The first approaches used to design a game-playing program are based on a game tree search
algorithm, such as minimax, combined with a handcrafted game state evaluation function based
on expert knowledge. A notable use of minimax with an handcrafted evaluation is the Deep Blue
chess program (Campbell, Hoane Jr, and Hsu, 2002). However, the success of Deep Blue is largely
due to the raw power of the computer, which could analyze two hundred million game states per
second. In addition, this approach is limited by having to design an evaluation function manually (at
least partially). The design of evaluation functions is a very complex task, which must, in addition,
be carried out for each different game. Several works have thus focused on automatic learning
of evaluation functions (Mandziuk, 2010). One of the first successes about learning evaluation
functions is on the Backgammon game (Tesauro, 1995). However, for many games, such as Hex or
Go, minimax-based approaches, with or without machine learning, have failed to overcome human.
Two causes have been identified (Baier and Winands, 2018). Firstly, the very large number of
possible actions at each game state prevents an exhaustive search at a significant depth (the game
can only be anticipated a few turns in advance). Secondly, for these games, no sufficiently powerful
evaluation function could be identified. An alternative approach has been proposed to solve the
two problems, called Monte Carlo tree search and denoted MCTS (Coulom, 2007; Browne, Powley,
Whitehouse, Lucas, Cowling, Rohlfshagen, Tavener, Perez, Samothrakis, and Colton, 2012). MCTS
explores the game tree non-uniformly, which is a solution to the problem of the very large number
of actions. In addition, it evaluates the game states from victory statistics of a large number of
random end-game simulations. Thus, it does not need an evaluation function. MCTS gives notably
good results to Hex and Go. However, this was not enough to go beyond the level of human players.
Several variants of Monte Carlo tree search were then proposed, using in particular knowledge to
guide the exploration of the game tree and/or random end-game simulations (Browne et al., 2012).
Recent improvements in Monte Carlo tree search have focused on the automatic learning of MCTS
knowledge and their uses. This knowledge was first generated by supervised learning (Clark and
Storkey, 2015; Gao, Hayward, and Müller, 2017; Gao, Müller, and Hayward, 2018; Cazenave,
2018; Tian and Zhu, 2015) then by supervised learning followed by reinforcement learning (Silver,
Huang, Maddison, Guez, Sifre, Van Den Driessche, Schrittwieser, Antonoglou, Panneershelvam,
Lanctot, et al., 2016), and finally by only reinforcement learning (Silver et al., 2017b; Anthony, Tian,
and Barber, 2017; Silver, Hubert, Schrittwieser, Antonoglou, Lai, Guez, Lanctot, Sifre, Kumaran,
Graepel, et al., 2018). These learning-based improvements allowed programs to reach and surpass
the level of world champion at the game of Go (Silver et al., 2016, 2017b). In particular, the
program AlphaGo Zero (Silver et al., 2017b), which only uses reinforcement learning, did not need
any knowledge to reach its level of play. This last success, however, required 29 million games

<footnote n="1">1. With some definitions, perfect information games include games with chance. This is not the case in this article</footnote>
of self-play (with 1,600 state evaluations per move). The AlphaGo Zero approach has also been
generalized and applied to chess (Silver, Hubert, Schrittwieser, Antonoglou, Lai, Guez, Lanctot,
Sifre, Kumaran, Graepel, et al., 2017a) under the name of AlphaZero. The resulting program broke
the best chess program (based on minimax). Another state-of-the-art zero-knowledge reinforcement
learning algorithm is the ExIt algorithm (Anthony et al., 2017), also based on Monte Carlo tree
search.

It is therefore questionable whether minimax is totally out of date or whether the spectacu-
lar successes of recent programs are more based on reinforcement learning than Monte Carlo tree
search. In particular, it is interesting to ask whether reinforcement learning would enhance minimax
enough to make it competitive with Monte Carlo tree search on games where it dominates minimax
so far, such as Go or Hex.

In this article<fnref n="2" />, we therefore focus on reinforcement learning within the minimax framework.
We propose and asses new techniques for reinforcement learning of evaluation functions, which we
then combine together to form the Athénan algorithm. In particular, we show that Athénan makes it
possible to go beyond the state-of-the-art of reinforcement learning without knowledge, in particular
the ExIt algorithm, and the state-of-the-art dedicated to the following games: Hex, Arimaa, Othello,
and Morpion Solitaire. Note that, we showed, in collaboration with Tristan Cazenave, in an another
article produced after this article but published before, that Athénan is more efficient and performant
than AlphaZero (Cohen-Solal and Cazenave, 2023c). This further study complements the studies
carried out within this article.

In the next section, we briefly present game algorithms and in particular *Unbounded Best-First Minimax* on which we base several of our experiments. We also present reinforcement learning in games and the games on which our experiments are performed. In the following sections, we propose different techniques aimed at improving learning performances and we expose the experiments carried out using these new techniques. In particular, in Section 3, we extends the *tree bootstrap-ping* (*tree learning*) technique to the context of reinforcement learning without knowledge based on non-linear functions. In Section 4, we present a new search algorithm, a variant of Unbounded Best-First Minimax called *Descent*, intended to be used during the learning process. In Section 6, we introduce *reinforcement heuristics*. Their usage is a simple way to use general or dedicated knowledge in reinforcement learning processes. We study several reinforcement heuristics in the context of different games. In Section 5, we introduce the *completion technique* for taking into account the resolution of states in the cases of Unbounded Minimax and Descent. Section 7 introduce a new action selection distribution.

Then, we combine previously introduced techniques into the algorithm called *Athénan* and apply
it in different contexts. In Section 9, we apply Athénan to design program-players to the game of
Hex (size 11 and 13) and compare them to Mohex 3HNN (Gao et al., 2018), the best Hex program
(before Athénan), notably champion at Hex (size 11 and 13) during the 2018 Computer Olympiad
(Gao, Takada, and Hayward, 2019). In Section 8, we compare Athénan with ExIt (Anthony et al.,
2017), the state-of-the-art reinforcement learning algorithm without knowledge at Hex. Then, in
Section 10, we apply Athénan to surpass the dedicated state-of-the-art at Othello. In Section 11, we
apply Athénan to surpass the dedicated state-of-the-art at Arimaa. In Section 17, we apply Athénan
to reach the level of the dedicated state-of-the-art at Morpion Solitaire.

<footnote n="2">2. Note that this paper is an extended, improved, and english version of (Cohen-Solal, 2019).</footnote>
Moreover, in Section 13, we present the results of Athénan during the worldwide artificial intel-
ligence competition on board games: the Computer Olympiad.

Finally, in Section 14, we conclude and expose the different research perspectives.

**2 Background and Related Work**

In this section, we briefly present game tree search algorithms, reinforcement learning in the context of games, and the games used in this paper (for more details about game algorithms, see (Yannakakis and Togelius, 2018)).

Games can be represented by their *game tree* (a node corresponds to a game state and the children of a node are the states that can be reached by an action). From this representation, we can determine the action to play using a game tree search algorithm. In order to win, each player tries to maximize his score (i.e. the value of the game state for this player at the end of the match). As we place ourselves in the context of two-player zero-sum games, to maximize the score of a player is to minimize the score of his opponent (the score of a player is the negation of the score of his opponent).

**2.1 Game Tree Search Algorithms**

The central algorithm is *minimax* which recursively determines the value of a node from the value of its children and the functions min and max, up to a limit recursion depth. With minimax, the game tree is uniformly explored. A better implementation of minimax uses *alpha-beta pruning* (Knuth and Moore, 1975; Yannakakis and Togelius, 2018) which makes it possible not to explore the sections of the game tree which are less interesting given the values of the nodes already met and the properties of min and max. Many variants and improvements of minimax have been proposed (Millington and Funge, 2009). For instance, *iterative deepening* (Slate and Atkin, 1983; Korf, 1985) allows one to use minimax with a time limit. It sequentially performs increasing depth alpha-beta searches as long as there is time. It is generally combined with the *move ordering* technique (Fink, 1982), which consists of extending the best move from the previous search first, which accelerates the new search.

Some variants perform a search with unbounded depth (that is, the depth of their search is not fixed) (Van Den Herik and Winands, 2008; Schaeffer, 1990; Berliner, 1981). Unlike minimax with or without alpha-beta pruning, the exploration of these algorithms is non-uniform. One of these algorithms is the *best-first minimax search* (Korf and Chickering, 1996)<fnref n="3" />. To avoid any confusion with some best-first approaches at fixed depth, we call this algorithm *Unbound Best-First Minimax*, or more succinctly UBFM. UBFM iteratively extends the game tree by adding the children of one of the leaves of the game tree having the same value as that of the root (minimax value). These leaves are the states obtained after having played one of the best sequences of possible actions given the current partial knowledge of the game tree. Thus, that algorithm iteratively extends the *a priori* best sequences of actions. The best sequences usually change at each extension. Thus, the game tree is non-uniformly explored by focusing on the *a priori* most interesting actions without exploring just one sequence of actions.

<footnote n="3">3. At the time of the first experiments of this article, we were not aware that the Unbounded Best-First Minimax algo-
rithm had already been proposed, so we rediscovered it independently during this work.</footnote>
In this article, we use the anytime version of UBFM (Korf and Chickering, 1996), i.e. we leave a fixed search time for UBFM to decide the action to play. We also use transposition tables (Greenblatt, Eastlake, and Crocker, 1988; Millington and Funge, 2009) with UBFM, which makes it possible not to explicitly build the game tree and to merge the nodes corresponding to the same state. (MCTS and Alpha-Beta in this paper also use transposition tables). Note that positive impact of transposition tables has been evaluated (Cohen-Solal and Cazenave, 2025b). Algorithm 1 is an implementation of UBFM<fnref n="4" />. UBFM has been improved within the algorithm called *Unbounded Minimax with Safe Decision* (Cohen-Solal, 2025), denoted UBFMₛ. This variant performs the same search in the game tree but plays a different action after performing this search. Instead of playing the action that leads to the state of best value, the action played is the one that was most selected from the current state during the search. This variant of Unbounded Minimax was originally proposed in the old, unpublished versions of this article (Cohen-Solal, 2020). It has been removed from this document to simplify it. The removed results about Unbounded Minimax with Safe Decision that appeared in the old versions of this article have been improved and detailed in the article that deals with its new introduction (Cohen-Solal, 2025).

## 2.2 Learning of Evaluation Functions

Reinforcement learning of evaluation functions can be done by different techniques (Mandziuk, 2010; Silver et al., 2017b; Anthony et al., 2017; Young, Vasan, and Hayward, 2016). The general idea of reinforcement learning of state evaluation functions is to use a game tree search algorithm and an adaptive evaluation function to play a sequence of matches (for example against oneself, which is the case in this article). Adaptive evaluation functions $f_\theta$ are usually neural networks, of parameter $\theta$. Each match generates pairs $(s, v)$ where $s$ is a game state and $v$ is the value of $s$ calculated by the chosen search algorithm using the evaluation function $f_\theta$. Such pairs are learned for updating $f_\theta$ in order to improve it. The set of states used for updating $f_\theta$ varies depending on the learning technique (Tesauro, 1995; Veness, Silver, Blair, and Uther, 2009). For example, in the case of *root bootstrapping* (technique that we call *root learning* in this article), the set of pairs learned during the learning phase is $D = \{(s, v) | s \in \mathbb{R}\}$ with $\mathbb{R}$ the set of states of the match. In the case of the *tree bootstrapping* (*tree learning*) technique (Veness et al., 2009), the set of pairs learned during the learning phase is the set of states of the partial game tree built to decide which actions to play: $D = \{(s, v) | s \in \mathcal{T}\}$ with $\mathcal{T}$ the set of states of the search trees. Note that states of the match search trees include states of the match (since the states of the match are the roots of the search trees). Thus, contrary to *root bootstrapping*, *tree bootstrapping* does not discard most of the information used to decide the actions to play. The values of the generated states can be their minimax values in the partial game tree built to decide which actions to play (Veness et al., 2009; Tesauro, 1995). Work on *tree bootstrapping* has been limited to reinforcement learning of linear functions of state features. It has not been formulated or studied in the context of reinforcement learning without knowledge and based on non-linear functions. Note that, in the case of AlphaGo Zero, the learned states are the states of the sequence of the match (as with *root learning*), but the

<footnote n="4">4. This implementation is a slight variant of Korf and Chickering algorithm. Both algorithms behave identically if the evaluation function gives a different value to each state and if transposition tables are not used. In practice, in the context of using transpositions, our variant improves win performance by a few percentage points (Cohen-Solal and Cazenave, 2025b). If the evaluation function gives a different value to each state and transpositions are not used, Korf and Chickering algorithm is slightly faster (carelessly faster in some contexts).</footnote>
<table><caption>Table 1: Index of symbols</caption><thead><tr><th>Symbols</th><th>Definition</th></tr></thead><tbody><tr><td>actions (s)</td><td>action set of the state s for the current player</td></tr><tr><td>first-player (s)</td><td>true if the current player of the state s is the first player</td></tr><tr><td>terminal (s)</td><td>true if s is an end-game state</td></tr><tr><td>a(s)</td><td>state obtained after playing the action a in the state s</td></tr><tr><td>time ()</td><td>current time in seconds</td></tr><tr><td>random ()</td><td>returns a uniformly random number from [0, 1]</td></tr><tr><td>S</td><td>keys of the transposition table T</td></tr><tr><td>T</td><td>transposition table (contains states labels as function v; depends on the used search algorithm)</td></tr><tr><td>τ</td><td>search time per action</td></tr><tr><td>t</td><td>time elapsed since the start of the reinforcement learning process</td></tr><tr><td>t<sub>max</sub></td><td>chosen total duration of the learning process</td></tr><tr><td>n(s, a)</td><td>number of times the action a is selected in state s (initially, n(s, a) = 0 for all s and a</td></tr><tr><td>v(s)</td><td>value of state s in the game tree</td></tr><tr><td>v(s, a)</td><td>value obtained after playing action a in state s</td></tr><tr><td>c(s)</td><td>completion value of state s (0 by default)</td></tr><tr><td>c(s, a)</td><td>completion value obtained after playing action a in state s</td></tr><tr><td>r(s)</td><td>resolution value of state s (0 by default)</td></tr><tr><td>r(s, a)</td><td>resolution value obtained after playing action a in state s</td></tr><tr><td>f(s)</td><td>the used evaluation function (first player point of view)</td></tr><tr><td>f<sub>θ</sub>(s)</td><td>adaptive evaluation function (of non-terminal game tree leaves; first player point of view)</td></tr><tr><td>f<sub>t</sub>(s)</td><td>evaluation of terminal states, e.g. gain game (first player point of view)</td></tr><tr><td>Gain function b<sub>t</sub>(s)</td><td>0 if s is a draw, 1 if s is winning for the first player, -1 if s is losing for the first player</td></tr><tr><td>search(s, S, T, f<sub>θ</sub>, f<sub>t</sub>)</td><td>a search algorithm (it extends the game tree from s, by adding new states in S and labeling its states, in particular, by a value v(s), stored in T, using f<sub>θ</sub> as evaluation of the non-terminal leaves and f<sub>t</sub> as evaluation of terminal states</td></tr><tr><td>action_selection(s, S, T)</td><td>decides the action to play in the state s depending on the partial game tree, i.e. on S and T</td></tr><tr><td>processing(D)</td><td>various optional data processing: data augmentation (symmetry), experience replay, ...</td></tr><tr><td>update(f<sub>θ</sub>, D)</td><td>updates the parameter θ of f<sub>θ</sub> in order for f<sub>θ</sub>(s) is closer to v for each (s, v) ∈ D</td></tr></tbody></table>
**Algorithm 1** UBFM (Unbounded Best-First Minimax) algorithm : it computes the best action to play in the generated non-uniform partial game tree (see Table 1 for the definitions of symbols ; at any time $T = \{v(s, a) | s \in S, a \in \text{actions}(s)\}$).

**Function** UBFM\_iteration (s, S, T)

if terminal (s) then

return $f(s)$

else

if $s \notin S$ then

$S \leftarrow S \cup \{s\}$

foreach $a \in \text{actions}(s)$ do

$v(s, a) \leftarrow f(a(s))$

else

$a_b \leftarrow \text{best\_action}(s)$

$v(s, a_b) \leftarrow \text{UBFM\_iteration}(a_b(s), S, T)$

$a_b \leftarrow \text{best\_action}(s)$

return $v(s, a_b)$

**Function** best_action (s, S, T)

if first\_player (s) then

return $\arg\max_{a \in \text{actions}(s)} v(s, a)$

else

return $\arg\min_{a \in \text{actions}(s)} v(s, a)$

**Function** UBFM (s, τ)

$t = \text{time}()$ while $\text{time}() - t < \tau$ do UBFM\_iteration (s, S, T)

return $\text{best\_action}(s, S, T)$
target value for each of these states is the value of the terminal state of the match (Silver et al., 2017b). We call that technique terminal learning.

Generally between two consecutive matches (between *match phases*), a *learning phase* occurs, using the pairs of the last match. Each learning phase consists in modifying $f_\theta$ so that for all pairs $(s, v) \in D$, $f_\theta(s)$ sufficiently approaches $v$ to constitute a good approximation. Note that, learning phases can also use the pairs of *several* matches. This technique is called *experience replay* (Mnih, Kavukcuoglu, Silver, Rusu, Veness, Bellemare, Graves, Riedmiller, Fidjeland, Ostrovski, et al., 2015). Note that, adaptive evaluation functions $f_\theta$ only serve to evaluate non-terminal states since we know the true value of terminal states (it is important: using the exact terminal evaluation function improves confrontation performance (Cohen-Solal and Cazenave, 2025b)).

**Remark 1.** There is another reinforcement learning technique for games: the Temporal Differences algorithm TD($\lambda$) (Tesauro, 1995). It corresponds to a root learning algorithm without search (i.e. with a search of depth 1) where the target of a state is a weighted average of the values of its successor states in the match, parameterized by the constant $\lambda$. A variant of TD($\lambda$) has also been proposed (Baxter, Tridgell, and Weaver, 2000), called TD<sub>Leaf</sub>($\lambda$), where the temporal difference technique TD($\lambda$) is modified by applying it with a minimax search (i.e. with a search of depth $d \ge 1$). A comparison between these techniques was made (Veness et al., 2009). Finally, in (Björnsson and Marsland, 2003) a method is described for automatically tuning *search-extension* parameters, to decide which branches of the game tree must be explored during the search.

## 2.3 Action Selection Distribution

One of the problems related to reinforcement learning is the *exploration-exploitation dilemma* (Mandziuk, 2010). It consists of choosing between exploring new states to learn new knowledge and exploiting the acquired knowledge. Many techniques have been proposed to deal with this dilemma (Mellor, 2014). However, most of these techniques do not scale because their application requires memorizing all the encountered states. For this reason, in the context of games with large numbers of states, some approaches use probabilistic exploration (Young et al., 2016; Silver et al., 2017b; Mandziuk, 2010; Schraudolph, Dayan, and Sejnowski, 2001). With this approach, to exploit is to play the best action and to explore is to play uniformly at random. More precisely, a parametric probability distribution is used to associate with each action its probability of being played. The parameter associated with the distribution corresponds to the exploration rate (between 0 and 1), which we denote $\epsilon$ (the exploitation rate is therefore $1 - \epsilon$, which we denote $\epsilon'$). The rate is often experimentally fixed. *Simulated annealing* (Kirkpatrick, Gelatt, and Vecchi, 1983) can, however, be applied to avoid choosing a value for the parameter. In that case, at the beginning of reinforcement learning, the parameter is 1 (we are just exploring). It gradually decreases until reaching 0 at the end of the learning process. The simplest action selection distribution is $\epsilon$-greedy (Young et al., 2016) (of parameter $\epsilon$). With the distribution $\epsilon$-greedy, the action is chosen uniformly with probability $\epsilon$ and the best action is chosen with probability $1 - \epsilon$ (see also Algorithm 2).

The $\epsilon$-greedy distribution has the disadvantage of not differentiating the actions (except the best action) in terms of probabilities. Another distribution is often used, correcting this disadvantage. This is the *softmax* distribution (Schraudolph et al., 2001; Mandziuk, 2010). It is defined by
$$P(a_i) = \frac{e^{v(s, a_i)/\tau}}{\sum_{j=1}^{n} e^{v(s, a_j)/\tau}}$$
with $n$ the number of children of the current state $s$, $P(a_i)$ the probability of playing the action $a_i$, $v(s, a_i)$ the value of the state obtained after playing $a_i$ in the current state $s$,
$i \in \{0, \dots, n-1\}$, and $\tau \in ]0, +\infty[$ a parameter called temperature ($\tau \approx 0$: exploitation, $\tau \approx +\infty$: exploration).

## 2.4 Games of Paper Experiments

We now briefly present the games on which experiments are performed in this article, namely: Hex, Arimaa, Morpion Solitaire, Othello, Surakarta, Outer Open Gomoku, Clobber, Breakthrough, Amazons, Lines of Action, and Santorini. They are all board games. All of these games are present and recurring (except Morpion Solitaire) at the Computer Olympiad, the worldwide multi-games event in which computer programs compete against each other. Moreover, all these games (and their rules) are included (and available for free) in Ludii (Piette, Soemers, Stephenson, Sironi, Winands, and Browne, 2020), a general game system.

### 2.4.1 HEX

Hex is a two-player combinatorial strategy game played on an $n \times n$ hexagonal board. Each player takes turns placing a stone of their color on an empty cell. The objective is to be the first to connect the two opposite sides of the board corresponding to their color. A common variant of Hex includes the swap rule, where the second player can choose, on their first turn, to swap roles and sides with the first player. This rule helps balance the game by mitigating the first player's advantage and is typically used in competitions. It is still used at the Computer Olympiad, and we use it in this paper.

### 2.4.2 ARIMAA

Arimaa is a game with similarities with Chess. Each player has a different set of pieces (identical between the two players): one elephant, one camel, two horses, two dogs, two cats, and eight rabbits. The pieces types are fully ordered: elephant > camel > horse > dog > cat > rabbit. A higher piece can move (push or pull) a lower piece. A piece which is orthogonally adjacent to a stronger opposing piece is frozen, unless it is also adjacent to a friendly piece. If a piece is on a trap square without being adjacent to a friendly piece, it is removed from the board. A player wins when one of its rabbits reaches the other side of the board. A player without rabbits loses. It is played on a $8 \times 8$ grid like Chess (the cases (2, 2), (2, 5), (5, 2), (5, 5) are traps). At the start, the board is empty. The first player places its pieces on its side of the board then the second player does the same. On his turn, the player can make 4 moves of one square (with one or more pieces).

**Algorithm 2** $\epsilon$-greedy algorithm with simulated annealing ($\epsilon = 1 - \frac{t}{t_{max}}$) used in the experiments of this article (see Table 1 for the definitions of symbols).

**Function** $\epsilon$-greedy ($s, v$)
    **if** random() $\le \frac{t}{t_{max}}$ **then**
        **if** first-player ($s$) **then**
            | return arg max$_{a \in \text{actions}(s)}$ $v(s, a)$
        **else**
            | return arg min$_{a \in \text{actions}(s)}$ $v(s, a)$
    **else**
        | return $a \in \text{actions}(s)$ uniformly chosen.
Pushing or pulling an opposing piece counts as two moves. Details about rules are available in
https://arimaa.com/arimaa/.

### 2.4.3 MORPION SOLITAIRE

The game is played on a grid of unlimited size. The starting configuration includes a set of points already placed on the grid in the shape of a Greek cross whose side has 4 points (the cross is made up of a total of 36 points).

A move in this game consists of two steps. First, the player places a new point on the grid so as to form an alignment of five adjacent points horizontally, vertically or diagonally (which have not already been connected by a line). Then, he connects this alignment by drawing a line. An alignment cannot be placed as an extension of a previous alignment.

The aim of the game is to place as many points as possible before reaching a situation where no new points can be placed.

### 2.4.4 OTHELLO

Othello (also called Reversi) is a territory and linear encirclement game whose goal is to have more pieces than its opponent. In his turn, a player places a piece of his color on the board (only if he can make an encirclement, otherwise he pass his turn). There is an encirclement if an opponent's line of pieces has at one of its ends the piece that the current player has just placed, and has at the other end, another piece of the current player. As a result of this encirclement, the encircled opponent's pieces are replaced by pieces from the current player.

### 2.4.5 SURAKARTA

Surakarta is a move and capture game (like draughts). The goal of the game is to take all the opposing pieces. In his turn, a player can either move a piece to an empty square at a distance of 1 or move a piece to a square occupied by an opponent's piece under certain conditions and according to a mechanism specific to Surakarta (based on a movement circuit dedicated only to capture), allowing "long distance" capture.

### 2.4.6 OUTER OPEN GOMOKU

Outer Open Gomoku is an alignment game. The goal of the game is to line up at least 5 pieces of its color. On his turn, a player places a piece of his color. In the first turn, the first player can only place a piece at a distance of 2 from the sides of the board.

### 2.4.7 CLOBBER

Clobber is a move and capture game. The goal is to be the last player to have played. A player can play if he can orthogonally move one of his pieces onto a neighboring square on which there is an opponent's piece. This movement is always a capture (the opponent's piece is removed from the board).
2.4.8 BREAKTHROUGH

Breakthrough is a move and capture game. The goal of the game is to be the first to make one of his pieces reach the other side of the board. A piece can only move by moving forward one square (straight or diagonal). A capture can only be done diagonally.

2.4.9 AMAZONS

Amazons is a move and blocking game. In turn, a player moves one of his pieces in a straight line in any direction (like the queen of the game of Chess). Then he places a neutral piece in any direction starting from the new position of the piece just moved (always in the manner of the queen of the game of Chess). Any piece (neutral or player-owned) blocks placements and movements. The goal of the game is to be the last to play.

2.4.10 LINES OF ACTION

Lines of Action is a game of movement and regrouping. On his turn, a player can move one of his pieces in one direction as many squares as there are pieces in that direction. A piece cannot move if there is an opponent's piece in its path, unless it is the square to arrive (in which case a capture is made). The goal is to have all of its pieces connected.

2.4.11 SANTORINI

Santorini is a three-dimensional building and moving game. The goal of the game is to reach the 3rd floor of a building. In his turn, a player moves one of his pieces by one square then places the first floor on an adjacent empty square or increases a pre-existing construction by one floor (on which no player's piece is located). A piece cannot move to a square having strictly more than one floor more than the square where it is located (a piece only go up one floor at a time and can descend as many floors as wanted). A move cannot be made to a square with 4 floors. A construction cannot be done on a square of 4 floors. A player who cannot play loses. The advanced mode (i.e. the use of power cards) is not used in the experiments in this article.

**3 Data Use in Game Learning**

In this section, we adapt and study tree learning (see Section 2.2) in the context of reinforcement learning and the use of non-linear adaptive evaluation functions. For this purpose, we compare it to root learning and terminal learning. We start by adapting tree learning, root learning, and terminal learning. We also define in Section 8 a variant of experience replay that we call stratified experience replay. Next, we describe the experiment protocol common to several sections of this article. Finally, we expose the comparison of tree learning with root learning and terminal learning.

**3.1 Tree Learning**

As we saw in Section 2.2, tree learning consists in learning the value of the states of the search tree. However, our tree learning technique has two main differences with classic tree learning (in addition to the generalization to reinforcement learning without knowledge). On the one hand, the learning phase is carried out only after each game (and not after each search, i.e. not after each action play). On the other hand, the data of the non-terminal leaves of the tree are not learned. Thus
learning is performed on the partial game tree obtained at the end of the game from which the non-terminal leaves have been removed. It drastically reduces the number of data to learn and avoids an overlearning effect: our version significantly changes the learning performance. As a reminder, root learning consists in learning the values of the states of the sequence of states of the match (the value of each state is its value in the search tree). Terminal learning consists in learning the values of the sequence of states of the match but the value of each state is the value of the terminal state of the match (i.e. the gain of the match). To generalize tree learning and root learning, in a manner similar to the use of terminal learning in the AlphaZero framework, data to learn after each game can be modified by some optional data processing methods, such as experience replay (which involves learning a sample of previous matches instead of just learning the entire data from the previous match). In addition, the learning phase uses a particular update method so that the adaptive evaluation function fit the chosen data. The adaptation of tree learning, root learning, and terminal learning are given respectively in Algorithm 3, Algorithm 4, and Algorithm 5. The data processing method Experience replay is described in Algorithm 6 (its parameter are the memory size $\mu$ and the sampling rate $\sigma$). In addition, we use in this article a stochastic gradient descent as update method (see Algorithm 7 ; its parameter is $B$ the batch size). Formally, in Algorithm 3, Algorithm 4, and Algorithm 5, we have: processing($D$) is experience_replay($D, \mu, \sigma$) and update($f_\theta, D$) is stochastic-gradient-descent($f_\theta, D, B$). Finally, we use $\epsilon$-greedy as default action selection method (i.e. action_selection($s, S, T$) is $\epsilon$-greedy($s, T.v$) (see Algorithm 2 ; recall that $T$ stores the children value function $v$)).

**Algorithm 3** Tree learning (tree bootstrapping) algorithm (see Table 1 for the definitions of symbols). For tree learning, $S$ is the set of states which are non-leaves or terminal.

**Function** treeLearning($t_{max}, \tau$)
    $t_0 \leftarrow time()$
    **while** time() - $t_0 < t_{max}$ **do**
        $s \leftarrow initial\_game\_state()$
        $S \leftarrow \emptyset$
        $T \leftarrow \{\}$
        **while** $\neg terminal(s)$ **do**
            $S, T \leftarrow search(s, S, T, f_\theta, f_t, \tau)$
            $a \leftarrow action\_selection(s, S, T)$
            $s \leftarrow a(s)$
            $D \leftarrow \{(s, v(s)) \mid s \in S\}$
            $D \leftarrow processing(D)$
            update($f_\theta, D$)

## 3.2 Stratified Experience Replay

In this section, we introduce the technique we call *Stratified Experience Replay*, which is a variation of Experience Replay. The targeted objective of Stratified Experience Replay is to reduce the variance of learning processes.

Stratified Experience Replay consists in performing a stratified sampling without replacement on the replay buffer of Experience Replay whose data has been grouped in relation to the matches that generated it. Stratified sampling imposes the same proportion of data for each previous match,
so we have a good level of variability during each learning phase. The absence of replacement makes that no data is unnecessarily repeated and no data is forgotten.

Stratified Experience Replay depends on two parameters: $\mu$ the number of previous matches kept in memory and $\delta$ the duplication factor: the number of times a piece of data must be learned during the learning phases. The data is stored in two datasets, the data to be learned stored in $\mu$ sets $D_i$ with $i \in \{1, \dots, \mu\}$, each corresponding to the data of the $i$-th previous match that must be learned and $\mu$ other sets $D'_i$ with $i \in \{1, \dots, \mu\}$, the archived data, which correspond to the data already learned from the $i$-th previous match. The set of data to learn for the new learning phase is

<caption>**Algorithm 4** Root learning (root bootstrapping) algorithm (see Table 1 for the definitions of symbols).</caption>

**Function** `root-learning`($t_{max}$, $\tau$)
    $t_0 \leftarrow time()$
    **while** `time()` - $t_0 < t_{max}$ **do**
        $s \leftarrow initial\_game\_state()$
        $S \leftarrow \emptyset$
        $T \leftarrow \{\}$
        $D \leftarrow \emptyset$
        **while** $\neg terminal(s)$ **do**
            $S, T \leftarrow search(s, S, T, f_\theta, f_t, \tau)$
            $a \leftarrow action\_selection(s, S, T)$
            $D \leftarrow D \cup \{(s, v(s))\}$
            $s \leftarrow a(s)$
            $D \leftarrow D \cup \{(s, v(s))\}$
            $D \leftarrow processing(D)$
            update($f_\theta, D$)

<caption>**Algorithm 5** Terminal learning algorithm (see Table 1 for the definitions of symbols).</caption>

**Function** `terminal-learning`($t_{max}$, $\tau$)
    $t_0 \leftarrow time()$
    **while** `time()` - $t_0 < t_{max}$ **do**
        $s \leftarrow initial\_game\_state()$
        $S \leftarrow \emptyset$
        $T \leftarrow \{\}$
        $G \leftarrow \{s\}$
        **while** $\neg terminal(s)$ **do**
            $S, T \leftarrow search(s, S, T, f_\theta, f_t, \tau)$
            $a \leftarrow action\_selection(s, S, T)$
            $s \leftarrow a(s)$
            $G \leftarrow G \cup \{s\}$
            $D \leftarrow \{(s', f_t(s)) \mid s' \in G\}$
            $D \leftarrow processing(D)$
            update($f_\theta, D$)
then samples of each $D_i$ of size $\lceil \frac{\delta}{\mu} (|D_i| + |D'_i|) \rceil$ (the total number of learned data is the number of generated data times the duplication factor $\delta$). The selected samples are removed from the $D_i$ and added to the $D'_i$. The selected data is then separated into minibatches, so as to preserve the stratification as much as possible (the minibatches are thus in a way also stratified) and learning is then performed on each minibatch. The formalization of Stratified Experience Replay is described in Algorithm 8.

**Remark 2.** We have not been able to evaluate the advantages or disadvantages of this variant with respect to the basic experience replay: the performances, we obtained during an experiment on this subject (not presented in this document), are so close that we would need increase the number of repetitions by 10 or maybe even 100 to be able to separate them, which is currently complicated or even impossible. We are not claiming that this algorithm is better than the classic replay experience, nor vice versa.

### 3.3 Common Experiment Protocol

The experiments of several sections share the same protocol. It is presented in this section. The protocol is used to compare different variants of reinforcement learning algorithms. A variant corresponds to a certain combination of elementary algorithms. More specifically, a combination consists of the association of a search algorithm (iterative deepening alpha-beta (with move ordering), MCTS (UCT with $c = 0.4$ as exploration constant), UBFM, ...), of an action selection method ($\epsilon$-greedy distribution (used by default), softmax distribution, ...), a terminal evaluation function $f_t$

**Algorithm 6 Experience replay (replay buffer) algorithm used in the experiments of this article.** $\mu$ is the memory size and $\sigma$ is the sampling rate. $M$ is the memory buffer (global variable initialized by an empty queue). If the number of data is less than $\sigma \cdot \mu$, then it returns all data (no sampling). Otherwise, it returns $\sigma \cdot \mu$ random elements.

**Function** experience_replay ($D, \mu, \sigma$)
    elements of $D$ are added in $M$
    **if** $|M| > \mu$ **then**
        remove the oldest items of $M$ to have $|M| = \mu$
    **if** $|M| \le \sigma \cdot \mu$ **then**
        return $M$
    return a list of random items of $M$ whose size is $\sigma \cdot \mu$

**Algorithm 7 Stochastic gradient descent algorithm used in the experiments of this article.** It is based on Adam optimization (1 epoch per update) (Kingma and Ba, 2014) and $L_2$ regularization (with $\lambda = 0.001$ as parameter) (Ng, 2004) and implemented with tensorflow. $B$ is the batch size (see Table 1 for the definitions of the other symbols)

**Function** stochasticGradientDescent ($f_\theta$, $D$, $B$)
    Split $D$ in $m$ disjoint sets, denoted $\{D_i\}_{i=1}^m$, such that $D = \cup_{i=1}^m D_i$ and $|D_i| = B$ for each $i \in \{1, \dots, m\}$
    **foreach** $i \in \{1, \dots, m\}$ **do**
        minimize $\sum_{(s,v) \in D_i} (f_\theta(s) - v)^2$ by using Adam and $L_2$ regularization
(the classic game gain (used by default), ...), and a procedure for selecting the data to be learned (root learning, tree learning, or terminal learning). The protocol consists in carrying out a reinforcement learning process of 48 hours for each variant (per repetition). At several stages of the learning process, each combination is evaluated. This evaluation consists in matches played by using the adaptive evaluation function generated by the evaluated combination. Each variant is thus characterized by a winning percentage at each stage of the reinforcement learning process. More formally, we denote by $f_{\theta_h}^c$ the evaluation generated by the combination $c$ at the hour $h$. Each combination is evaluated every hour by a winning percentage. The winning percentage of a combination $c$ at a hour $h \le 48$ is computed from matches by using the minimax search at depth 1 with $f_{\theta_h}^c$ as evaluation function confronting the following opponents: the minimax search at depth 1 with $f_{\theta_{48}}^c$ as evaluation

**Algorithm 8** Stochastic gradient descent with Stratified experience replay algorithm (B is the batch size, $\mu$ is the memory size, $\delta$ is the duplication factor, $M$ is the memory buffer: a global variable initialized by an empty queue; choice(E): uniformly randomly chooses an element of E; see Table 1 for the definitions of the other symbols)

**Function** SGD_with_stratified_experience_replay($f_\theta$, $D$, $\mu$, $\delta$, $B$)
    append $(D, \emptyset)$ in $M$
    **if** $|M| > \mu$ **then**
        remove the oldest items of $M$ to have $|M| = \mu$
        $n \leftarrow \sum \left\{ \left\lfloor \frac{\delta}{\mu} (|D| + |D'|) \right\rfloor \mid (D, D') \in M \right\}$
        $g \leftarrow \max(1, \lfloor n/B \rfloor)$
    **if** $|\lfloor n/g \rfloor - B| > |\lfloor n/(g+1) \rfloor - B|$ **then**
        $g \leftarrow g+1$
        $G \leftarrow \{1, \dots, g\}$
    **foreach** $i \in G$ **do**
        $S_i \leftarrow \emptyset$
    **foreach** $(D, D') \in M$ **do**
        $l \leftarrow \left\lfloor \frac{\delta}{\mu} (|D| + |D'|) \right\rfloor$
        **foreach** $c \in \{1, \dots, l\}$ **do**
            $(s, v) \leftarrow \text{choice}(D)$
            remove $(s, v)$ from $D$
            add $(s, v)$ in $D'$
            **if** $|D| = 0$ **then**
                $D \leftarrow D'$
                $D' \leftarrow \emptyset$
            $j \leftarrow \text{choice}(G)$
            $G \leftarrow G \setminus \{j\}$
            **if** $|G| = 0$ **then**
                $G \leftarrow \{1, \dots, g\}$
            add $(s, v)$ in $S_j$
        **foreach** $i \in \{1, \dots, g\}$ **do**
            minimize $\sum_{(s,v) \in S_i} (f_\theta(s) - v)^2$
for all studied combination $c'$ (there is one match in first player and another in second player per pair of combination).

This protocol is repeated several times for each experiment in order to reduce the statistical noise in the winning percentages obtained for each variant (the obtained percentage is the average of the percentages of repetitions). The winning percentages are then represented in a graph showing the evolution of the winning percentages during training.

In addition to the curve, the different variants are also compared in relation to their final winning percentage, i.e. at the end of the learning process. Unlike the evolution of winning percentages, in the comparison of final performances, each evaluation $f_{\theta_{48}}^c$ confronts each other evaluation $f_{\theta_{48}}^{c'}$ from all repetitions. In other words, this experiment consists in performing an all-play-all tournament with all the evaluation functions generated during the different repetitions. The presented winning percentage of a combination is still the average over the repetitions. The matches are also made by using minimax at depth 1. These percentages are shown in tables.

*Remark 3.* The used version of MCTS does not performed random simulations for evaluating the leaves. Instead, leaves are evaluated by a neural network. No policies are used (unless it is explicitly specified).

*Remark 4.* All the experiments based on this protocol involving MCTS were also performed with $c = \sqrt{2}$ as exploration constant. The results are similar.

*Remark 5.* Hardware used in the experiments in this article: a quarter of the following node: 2 Intel Cascade Lake 6248 processors (20 cores at 2.5 GHz), 192 GB of memory, with 4 Nvidia Tesla V100 SXM2 32GB GPUs.

### 3.3.1 TECHNICAL DETAILS

We now present the technical details of this protocol.

The used parameters are: search time per action $\tau = 2s$, batch size $B = 128$, memory size $\mu = 10^6$, sampling rate $\sigma = 4\%$ (see Section 3.1). Moreover, the used adaptive evaluation function for each combination is a convolutional neural network (Krizhevsky, Sutskever, and Hinton, 2012) having three convolution layers<fnref n="5" /> followed by a fully connected hidden layer. For each convolutional layer, the kernel size is 3 × 3 and the filter number is 64. The number of neurons in the fully connected layer is 100. The margin of each layer is zero. After each layer except the last one, the ReLU activation function (Glorot, Bordes, and Bengio, 2011) is used. The output layer contains a neuron. When the classical terminal evaluation is used, tanh is the output activation function. Otherwise, there is no activation function for the output.

*Remark 6.* In this paper, filter numbers and numbers of neurons are chosen in order to there are about the same number of variables in the convolution layers and in the dense layers.

## 3.4 Comparison of Learning Data Selection Algorithms

We now compare tree learning, root learning and terminal learning, using the protocol of Section 3.3. Each combination uses either tree learning, root learning, or terminal learning. Moreover, each combination uses either iterative deepening alpha-beta (denoted by ID) or MCTS. Furthermore, each combination uses $\epsilon$-greedy as action selection method (see Section 3.1) and the classical

<footnote n="5">5. There is an exception: for the game Surkarta, there is only two convolution layers.</footnote>
<table><caption>Table 2: Final winning percentages of the combinations of the experiment of Section 3.4 (ID: iterative deepening alpha-beta). Reminder: the percentage is the average over the repetitions, of the winning percentage of a combination against each other combination, in first and second player (see 3.3; 95% confidence intervals: max ±0.85%).</caption><thead><tr><th rowspan="2"></th><th colspan="2">tree learning</th><th colspan="2">root learning</th><th colspan="2">terminal learning</th></tr><tr><th>MCTS</th><th>ID</th><th>MCTS</th><th>ID</th><th>MCTS</th><th>ID</th></tr></thead><tbody><tr><td>Othello</td><td>48.8%</td><td>55.4%</td><td>51.0%</td><td>31.9%</td><td>52.9%</td><td>43.7%</td></tr><tr><td>Hex</td><td>45.1%</td><td>79.8%</td><td>79.8%</td><td>44.1%</td><td>29.8%</td><td>27.8%</td></tr><tr><td>Clobber</td><td>41.5%</td><td>62.5%</td><td>50.0%</td><td>45.5%</td><td>45.7%</td><td>49.8%</td></tr><tr><td>Outer Open Gomoku</td><td>40.3%</td><td>80.0%</td><td>87.3%</td><td>48.8%</td><td>21.6%</td><td>23.1%</td></tr><tr><td>Amazons</td><td>46.2%</td><td>58.8%</td><td>56.1%</td><td>44.5%</td><td>39.4%</td><td>46.0%</td></tr><tr><td>Breakthrough</td><td>78.1%</td><td>79.2%</td><td>45.5%</td><td>50.6%</td><td>22.3%</td><td>14.3%</td></tr><tr><td>Santorini</td><td>50.2%</td><td>73.8%</td><td>60.5%</td><td>51.3%</td><td>29.4%</td><td>36.5%</td></tr><tr><td>Surakarta</td><td>69.4%</td><td>65.2%</td><td>56.2%</td><td>20.8%</td><td>28.9%</td><td>23.6%</td></tr><tr><td>Lines of Action</td><td>58.8%</td><td>81.7%</td><td>67.7%</td><td>9.6%</td><td>6.9%</td><td>2.7%</td></tr><tr><td>mean</td><td>53.1%</td><td>70.7%</td><td>61.6%</td><td>38.5%</td><td>30.8%</td><td>29.7%</td></tr></tbody></table>

terminal evaluation (1 if the first player wins, -1 if the first player loses, and 0 in case of a draw). There are a total of 6 combinations. The experiment was repeated 32 times. The winning percentage of a combination for each game and for each evaluation step (i.e. each hour) is therefore calculated from 384 matches (recall that there is a first player match and a second player match per pair of combinations).

The winning percentage curves are shown in Figure 1. The final winning percentages are shown in Table 2. Each percentage of the table has required 12,288 matches. ID is first on all games except in Outer Open Gomoku where it is second (MCTS root learning is first) and in Surakarta (MCTS with tree learning is first). MCTS with root learning is better than MCTS with tree learning except in Breakthrough and Surakarta. At Hex and Amazons, MCTS with root learning gives better results throughout the learning process but ends up being caught up by ID with terminal learning. Terminal learning performs worse everywhere, except in a few cases where it is very slightly better. On average, ID with tree learning is better (71% win), then MCTS with root learning is second (9% lower win percentage), followed by MCTS with tree learning (18% lower to ID).

In conclusion, tree learning with ID performs much better than other combinations, although the results are very tight at Amazons, Hex, and Outer Gomoku with MCTS with root learning.

## 4 Tree Search Algorithms for Game Learning

In this section, we introduce a new tree search algorithm, that we call Descent Minimax or more succinctly Descent, dedicated to be used during the learning process. After presenting Descent, we compare it to MCTS with root learning and with tree learning, to iterative deepening alpha-beta with root learning and with tree learning and to UBFM with tree learning.
<figure><img src="image_2.png" /><figcaption>Figure 1: Evolutions of the winning percentages of the combinations of the experiment of Section 3.4, i.e. MCTS (dotted line) or iterative deepening alpha-beta (continuous line) with tree learning (blue line), root learning (red line), or terminal learning (green line). The display uses a simple moving average of 6 data.</figcaption></figure>
## 4.1 Descent: Generate Better Data

Thus, we present *Descent*. It is a modification of UBFM which builds a different, deeper, game tree, to be combined with tree learning.

*Remark 7.* Note that, combining it with root learning or terminal learning is of no interest. The reason is that Descent spend most of its time exploring a part of the game tree whose only purpose is to provide states for learning. With root or terminal learning, these states are not learned and therefore generated for nothing.

The idea of Descent is to combine UBFM with deterministic end-game simulations providing interesting values from the point of view of learning.

The *Descent* algorithm (Algorithm 9) recursively selects the best child of the current node, which becomes the new current node. It performs this recursion from the root (the current state of the game) until reaching a terminal node (an end game). It then updates the value of the selected nodes (minimax value). The *Descent* algorithm repeats this recursive operation starting from the

<caption>**Algorithm 9** Descent minimax algorithm (see Table 1 for the definitions of symbols; note: *S* is the set of states which are non-leaves or terminal and *T* = (*v*, *)).</caption>

**Function descent iteration (s, S, T, f<sub>θ</sub>, f<sub>t</sub>)**
**if** terminal (s) **then**
S ← S ∪ {s}
v(s) ← f<sub>t</sub>(s)
**else**
**if** s ∉ S **then**
S ← S ∪ {s}
**foreach** a ∈ actions (s) **do**
**if** terminal (a(s)) **then**
v(s, a) ← descent iteration (a(s), S, T, f<sub>θ</sub>, f<sub>t</sub>)
**else**
v(s, a) ← f<sub>θ</sub>(a(s))
a ← best action (s)
v(s, a) ← descent iteration (a(s), S, T, f<sub>θ</sub>, f<sub>t</sub>)
a ← best action (s)
v(s) ← v(s, a)
**return** v(s)
**Function** best action (s)
**if** first player (s) **then**
return arg max<sub>a∈actions (s)</sub> v(s, a)
**else**
return arg min<sub>a∈actions (s)</sub> v(s, a)
**Function descent (s, S, T, f<sub>θ</sub>, f<sub>t</sub>, τ)**
t = time()
**while** time() - t < τ **do** descent iteration (s, S, T, f<sub>θ</sub>, f<sub>t</sub>)
**return** S, T
root as long as there is some search time left. Descent is almost identical to UBFM. The only dif-
ference is that Descent performs an iteration until reaching a terminal state while UBFM performs
this iteration until reaching a leaf of the tree (UBFM stops the iteration much earlier). In other
words, during an iteration, UBFM just extends one of the leaves of the game tree while Descent
recursively extends the best child from this leaf until reaching the end of the game.

The Descent algorithm has the advantage of UBFM, i.e. to perform a longer search to determine
a better action to play. By learning the values of the game tree (by using for example tree learning), it
also has the advantage of a minimax search at depth 1, i.e. to raise the values of the terminal nodes
to the other nodes more quickly. In addition, the states thus generated are closer to the terminal
states. Their values are therefore better approximations.

*Remark* 8. In the experiments of this article, when there is a value tie in best_action(s), the tie is broken at random. An alternative could be to choose the subtree whose principal variation is the least deep.

## 4.2 Comparison of Search Algorithms for Game Learning

We now compare Descent with tree learning to MCTS with root learning and with tree learning, to iterative deepening alpha-beta with root learning and with tree learning, and to UBFM with tree learning, using the protocol of Section 3.3. There are a total of 6 combinations. The experiment was repeated 32 times. The winning percentage of a combination for each game and for each evaluation step (i.e. each hour) is therefore calculated from 384 matches (recall that there is a first player match and a second player match per pair of combinations).

The winning percentage curves are shown in Figure 2. The final winning percentages are shown in Table 3. Each percentage of the table has required 12, 288 matches. It is Descent which gets the best curves on all games. For two games (Surakarta and Outer Open Gomoku), the difference with UBFM is very narrow but the results remain better than the classic approaches (MCTS and alpha-beta). On each game, Descent obtains a final percentage higher than all the other combinations (except in Santorini where it is 2% lower than UBFM, the best algorithm at this game). On average over all games, Descent has 82% win and is above UBFM, the second best combination, by 18%. It is also above ID with tree learning, the third best combination, by 34%.

In conclusion, Descent is the best search algorithm for learning evaluation functions. UBFM (with tree learning) is the second best algorithm, sometimes very close to Descent performances and sometimes very far, but always superior to the other algorithms (slightly or largely depending on the game).

5 Completion

In this section, we propose a complementary technique, that we call completion, which corrects
state evaluation functions taking into account the resolution of states.

*Remark* 9. However, we do not evaluate this technique in this paper, to avoid making this paper un-
necessarily cumbersome and to focus on the learning aspects that constitute the main contributions
of this paper. The evaluation of this technique is however available in (Cohen-Solal and Cazenave,
2025b) which studies the impact of improvements of Unbounded Minimax. This study shows that
completion improves the performance of Unbounded Minimax by 6% ± 0.7%.
<figure><img src="image_3.png" /><figcaption>Figure 2: Evolutions of the winning percentages of the combinations of the experiment of Section 4.2, i.e. of Descent (dashed line), UBFM (dotted dashed line), MCTS (dotted line), and iterative deepening alpha-beta (continuous line) with tree learning (blue line) or root learning (red line). The display uses a simple moving average of 6 data.</figcaption></figure>
<table><caption>Table 3: Final winning percentages of the combinations of the experiment of Section 4.2 (ID: iterative deepening alpha-beta; see 3.3; 95% confidence intervals: max ±0.85%)</caption><thead><tr><th rowspan="2"></th><th colspan="4">tree learning</th><th colspan="2">root learning</th></tr><tr><th>Descent</th><th>UBFM</th><th>MCTS</th><th>ID</th><th>MCTS</th><th>ID</th></tr></thead><tbody><tr><th>Othello</th><td>89.4%</td><td>47.2%</td><td>37.7%</td><td>42.7%</td><td>44.9%</td><td>22.1%</td></tr><tr><th>Hex</th><td>94.9%</td><td>71.7%</td><td>20.5%</td><td>50.7%</td><td>50.2%</td><td>20.5%</td></tr><tr><th>Clobber</th><td>83.0%</td><td>56.7%</td><td>32.9%</td><td>48.9%</td><td>42.0%</td><td>35.5%</td></tr><tr><th>Outer Open Gomoku</th><td>77.6%</td><td>63.9%</td><td>18.0%</td><td>51.6%</td><td>64.7%</td><td>18.2%</td></tr><tr><th>Amazons</th><td>84.3%</td><td>55.3%</td><td>32.5%</td><td>46.3%</td><td>43.7%</td><td>31.7%</td></tr><tr><th>Breakthrough</th><td>86.5%</td><td>72.5%</td><td>45.5%</td><td>47.6%</td><td>19.2%</td><td>21.0%</td></tr><tr><th>Santorini</th><td>69.9%</td><td>71.8%</td><td>31.9%</td><td>47.6%</td><td>37.7%</td><td>40.2%</td></tr><tr><th>Surakarta</th><td>82.8%</td><td>69.7%</td><td>41.2%</td><td>42.1%</td><td>29.4%</td><td>14.5%</td></tr><tr><th>Lines of Action</th><td>73.4%</td><td>66.9%</td><td>36.1%</td><td>57.4%</td><td>39.4%</td><td>3.7%</td></tr><tr><th>mean</th><td>82.4%</td><td>64.0%</td><td>32.9%</td><td>48.3%</td><td>41.2%</td><td>23.1%</td></tr></tbody></table>

## 5.1 Completion Concept

Relying solely on the value of states calculated from the terminal evaluation function and the adaptive evaluation function can sometimes lead to certain aberrant behaviors. More precisely, if we only seek to maximize the value of states, we will then choose to play a state *s* rather than another state *s'* when *s* is of greater value than *s'* even if *s'* is a winning resolved state (a state is resolved if we know the result of the match starting from that state in which the two players play optimally). A search algorithm can resolve a state. This happens when all the leaves of the subtree starting from that state are terminal. Choosing *s* rather than *s'*, a winning resolved state, is an error<fnref n="6" /> when *s* is not resolved (or when *s* is resolved and is not winning). By choosing *s*, guarantee of winning is lost. The left graph of Figure 3 illustrates such a scenario. It is therefore necessary to take into account both the value of states and the resolution of states.

## 5.2 Completed Algorithms

The completion technique, which we propose in this section, is one way of doing it. It consists, on the one hand, in associating with each state *s* a completion value *c(s)* and a resolution value *r(s)*. The completion value *c(s)* of a leaf state *s* is 0 if the state *s* is not terminal or if it is a draw, 1 if it is a winning terminal state, and -1 if the state is a losing terminal state. The value *c(s)* of a non-leaf state *s* is computed as the minimax value of the subtree of the partial game tree starting from *s* where the leaves are evaluated by their completion value. The resolution value *r(s)* of a leaf state *s* is 0 if the state *s* is not terminal and 1 if it is terminal. The resolution value *r(s)* of a non-leaf state *s* is 1 if |*c(s)*| = 1. Otherwise, *r(s)* is the minimum of the resolution values of the children of *s*.

The completion technique consists, on the other hand, in using *c(·)* to compute *v(·)*. For this, states are compared from pairs (*c(·)*, *v(·)*), by using the lexicographic order (instead of just compare states from *v(·)*). More precisely, the value *v(s)* of a state *s* is computed in calculating (*c(s)*, *v(s)*) as the minimax value of the subtree of the partial game tree starting from *s* where

<footnote n="6">6. There is perhaps, in certain circumstances, an interest in making this error from the point of view of learning.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 3: The left graph is a game tree where maximizing does not lead to the best decision; the right graph is the left game tree with completion (nodes are labeled by a pair of values) and thus maximizing leads to the best decision (square node: first player node (max node), circle node: second player node (min node), octagon: terminal node).</figcaption></figure>

the leaves $l$ are evaluated by $(c(l), v(l))$. Thus, the value $v(s)$ of a winning state $s$ is always the value of the corresponding winning terminal leaf. The right graph of Figure 3 illustrates the use of completion.

Finally, with the completion technique, to decide which action to play during the search, we choose the best unresolved action if it exists and otherwise the best resolved action (i.e. we choose the action which maximize $(-r(s), c(s), v(s))$ in a max state and which minimize $(r(s), c(s), v(s))$ in a min state).

Without completion, algorithms such as Descent or Unbounded Minimax can get stuck in a non-optimal fixed point. The completion technique ensures that with sufficient thinking time, the optimal strategy is found (Cohen-Solal, 2021).

Moreover, the use of the resolution of states also makes it possible to stop the search in the resolved subtrees and thus to save computing time. Descent algorithm modified to use the completion and the resolution stop is described in Algorithm 10. With completion, after the search, Unbounded Minimax always chooses an action leading to a winning resolved state and never chooses, if possible, an action leading to a losing resolved state. Unbounded Minimax algorithm modified to use the completion and the resolution stop is described in Algorithm 13.

We also propose to use the resolution of states with action selections, to reduce the duration of games and therefore *a priori* the duration of the learning process: always play an action leading to a winning resolved state if it exists and never play an action leading to a losing resolved state if possible. Thus, if among the available actions we know that one of the actions is winning, we play it. If there is none, we play according to the chosen action selection method among the actions not leading to a losing resolved state (if possible). We call it *completed action selection*.
*Remark 10.* It is not clear, however, that *completed action selection* improves, in practice, performance as it prunes a portion of the game tree whose values could be useful for learning (but it would be surprising if this were not the case).

*Remark 11.* In some application cases, we will prefer to ensure the draw rather than trying to win. Algorithm 13 must then be adapted to decide the action to play. If the first player prefers to guarantee draws, it must instead maximize:

$$ (c(s, a), r(s, a), n(s, a), v(s, a)). $$

If the second player prefers to guarantee draws, it must instead minimize:

$$ (c(s, a), -r(s, a), n(s, a), v(s, a)). $$

**Algorithm 10** Descent tree search algorithm with completion and resolution stop (see Table 1 for the definitions of symbols and Algorithm 11 for the definitions of completed_best_action(s) and backup_resolve(s)). Note: $T = (v, c, r)$ and $S$ is the set of states of the partial game tree which are non-leaves or terminal.

**Function descent iteration (s, S, T, f<sub>θ</sub>, f<sub>t</sub>)**
**if** terminal (s) **then**
S ← S ∪ {s}
r(s), c(s), v(s) ← 1, b<sub>t</sub>(s), f<sub>t</sub>(s)
**else**
**if** s ∉ S **then**
S ← S ∪ {s}
**foreach** a ∈ actions (s) **do**
**if** terminal (a(s)) **then**
r(s, a), c(s, a), v(s, a) ← descent iteration (a(s), S, T, f<sub>θ</sub>, f<sub>t</sub>)
**else**
v(s, a) ← f<sub>θ</sub> (a(s))
a<sub>b</sub> ← completed best action (s, actions (s))
c(s), v(s) ← c(s, a<sub>b</sub>), v(s, a<sub>b</sub>)
r(s) ← backup resolution (s)
**if** r(s) = 0 **then**
A ← {a ∈ actions (s) | r(s, a) = 0}
a ← completed best action dual (s, A)
n(s, a) ← n(s, a) + 1
r(s, a), c(s, a), v(s, a) ← descent iteration (a(s), S, T, f<sub>θ</sub>, f<sub>t</sub>)
a ← completed best action (s, actions (s))
c(s), v(s) ← c(s, a), v(s, a)
r(s) ← backup resolution (s)
**return** r(s), c(s), v(s)

**Function completed descent (s, S, T, f<sub>θ</sub>, f<sub>t</sub>, τ)**
**while** time ()
- $t = time() - t < τ \land r(s) = 0$ **do** descent iteration (s, S, T, f<sub>θ</sub>, f<sub>t</sub>)
**return** S, T
*Remark* 12. For a game where there is no draw, the computation of the resolution value is not necessary (all necessary information is in the completion value).

*Remark* 13. For games without draw, the completion of Unbounded Minimax can be simply implemented by giving a value of $+\infty$ to winning terminal states and a value of $-\infty$ to losing terminal states (that is to say, it is sufficient to replace the terminal function by this infinite terminal function).

However, in the additional special case of adaptive evaluation functions with values in $]-1, 1[$, it is not sufficient that the terminal evaluation functions are in $\{-1, 1\}$. Indeed, in practice, with rounding errors, the adaptive evaluation function being real value will have values in $[-1, 1]$.

# 6 Reinforcement Heuristic to Improve Learning Performance

In this section, we propose the technique of *reinforcement heuristic*, which consists to replace the classical terminal evaluation function – that we denote by $b_t$, which returns 1 if the first player wins, $-1$ if the second player wins, and 0 in case of a draw (Young et al., 2016; Silver et al., 2017b; Gao et al., 2018) – by another heuristic to evaluate terminal states during the learning process. By using the reinforcement heuristic technique, non-terminal states are therefore evaluated differently, partial game trees and thus matches during the learning process are different, which can impact the learning performances. We start by defining what we call a reinforcement heuristic and we offer several reinforcement heuristics. Finally, we compare the reinforcement heuristics that we propose to the classical terminal evaluation function.

**Algorithm 11** Definition of the algorithms completed_best_action(s, A), which computes the *a priori* best action by using completion, and backup_resolve(s), which updates the resolution of s from its child states.

**Function** completed_best_action(s, A)

if firstplayer(s) then

return $\arg\max_{a \in A} (c(s, a), v(s, a), n(s, s'))$

else

return $\arg\min_{a \in A} (c(s, a), v(s, a), -n(s, s'))$

**Function** completed_best_action_dual(s, A)

if firstplayer(s) then

return $\arg\max_{a \in A} (c(s, a), v(s, a), -n(s, s'))$

else

return $\arg\min_{a \in A} (c(s, a), v(s, a), n(s, s'))$

**Function** backup_resolve(s)

if $|c(s)| = 1$ then

return 1

else

return $\min_{a \in \text{actions}(s)} r(s, a)$
**Algorithm 12 UBFM<sub>s</sub> tree search algorithm with completion and resolution stop (see Table 1 for the definitions of symbols and Algorithm 11 for the definitions of completed_best_action(s) and backup_resolve(s)).** Note: $T = (v, c, r, n)$. Note: Adding terminal states in $S$ is only useful during training with tree learning, so it should not be done during confrontations.

**Function ubfms_iteration (s, S, T, $f_θ$, $f_t$)**
**if** terminal (s) **then**
S ← S ∪ {s}
$r(s), c(s), v(s) ← 1, b_t(s), f_t(s)$
**else**
**if** $r(s) = 0$ **then**
**if** $s \notin S$ **then**
S ← S ∪ {s}
**foreach** $a \in \text{actions}(s)$ **do**
**if** terminal (a(s)) **then**
$r(s, a), c(s, a), v(s, a) ← \text{ubfms\_iteration}(a(s), S, T, $f_θ$, $f_t$)
**else**
$v(s, a) ← f_θ(a(s))$
**else**
A ← {$a \in \text{actions}(s) | r(s, a) = 0$}
$a ← \text{completed\_best\_action\_dual}(s, A)$
$n(s, a) ← n(s, a) + 1$
$r(s, a), c(s, a), v(s, a) ← \text{ubfms\_iteration}(a(s), S, T, $f_θ$, $f_t$)
$a ← \text{completed\_best\_action}(s, \text{actions}(s))$
$c(s), v(s) ← c(s, a), v(s, a)$
$r(s) ← \text{backup\_resolution}(s)$
return $r(s), c(s), v(s)$

**Function ubfms_tree_search (s, S, T, $f_θ$, $f_t$, $\tau$)**
$t = \text{time()}$
**while** $\text{time()} - t < \tau \land r(s) = 0$ **do** $\text{ubfms\_iteration}(s, S, T, $f_θ$, $f_t$)$
return $S, T$

**Algorithm 13 UBFM<sub>s</sub> action decision algorithm with completion (see Algorithm 12 for the definition of the method ubfms_tree_search() ; see Table 1 for the definitions of symbols).** Note: $T = (v, c, r, n)$ and $S$ is the set of states of the game tree which are non-leaves or terminal.

**Function safest_action (s, T)**
**if** first player (s) **then**
return $\arg\max_{a \in \text{actions}(s)} (c(s, a), n(s, a), v(s, a))$
**else**
return $\arg\min_{a \in \text{actions}(s)} (c(s, a), -n(s, a), v(s, a))$
**Function** ubfms (s, S, T, $f_θ$, $f_t$, $\tau$)
S, T ← ubfms_tree_search (s, S, T, $f_θ$, $f_t$, $\tau$)
return safest_action (s, T)
**6.1 Reinforcement Heuristic Definition**

A reinforcement heuristic is a terminal evaluation function that is more expressive than the classical
terminal function, i.e. the game gain.

**Definition 14.** Let $b_t$ the game gain function of a game (i.e. $b_t$ returns 1 if the first player wins, -1 if the second player wins, and 0 in case of a draw).

A reinforcement heuristic $h_r$ is a function that preserves the order of the game gain function:
for any two terminal states of the game $s, s', b_t(s) < b_t(s')$ implies $h_r(s) < h_r(s')$.

**6.2 Some Reinforcement Heuristics**

In the following subsections, we propose different reinforcement heuristics.

6.2.1 SCORING

Some games have a natural reinforcement heuristic: the game score. For example, in the case of the game Othello (and in the case of the game Surakarta), the game score is the number of its pieces minus the number of pieces of his opponent (the goal of the game is to have more pieces than its opponent at the end of the game). The scoring heuristic used as a reinforcement heuristic consists of evaluating the terminal states by the final score of the game. With that reinforcement heuristic, the adaptive evaluation function will seek to learn the score of states. In the context of an algorithm based on minimax, the score of a non-terminal state is the minimax value of the subtree starting from that state whose terminal leaves are evaluated by their scores. After training, the adaptive evaluation function then contains more information than just an approximation of the result of the game, it contains an approximation of the score of the game. If the game score is *intuitive*, the scoring heuristic should improve learning performances.

*Remark 15.* In the context of the game of the Amazons, the score is the size of the territory of the winning player, i.e. the squares which can be reached by a piece of the winning player. It is approximately the number of empty squares.

6.2.2 ADDITIVE AND MULTIPLICATIVE DEPTH HEURISTICS

Now we offer the following reinforcement heuristic: the *depth heuristic*. It consists in giving a better value to the winning states close to the start of the game than to the winning states far from the start. Reinforcement learning with the depth heuristic is learning the duration of matches in addition to their results. This learned information is then used to try to win as quickly as possible and try to lose as late as possible. If learning durations can be done, this should reduce the length of games and therefore speed up learning (by increasing the number of matches played in the same time but also by reducing the propagation time of end-of-game information to the start-of-game states). Seeking to lose for as long as possible helps avoid missing out on potential long-term wins (even if it makes games last longer).

We propose two realizations of the depth heuristic: the *additive depth heuristic*, that we denote by $p_t$, and the *multiplicative depth heuristic*, that we denote by $p_t'$. The evaluation function $p_t$ returns the value $l$ if the first player wins, the value $-l$ if the second player wins, and 0 in case of a draw, with $l = P - p + 1$ where $P$ is the maximum number of playable actions in a game and $p$ is the number of actions played since the beginning of the game. For the game of Hex, $l$ is the number of empty cells on the board plus 1. For the games where $P$ is very large or difficult to compute,
we can instead use $l = \max(1, \tilde{P} - p)$ with $\tilde{P}$ a constant approximating $P$ (close to the empirical maximum length of matches). The evaluation function $p_t'$ is identical except that $l$ satisfies $l = \frac{p'}{p}$, and $P'$ can be the exact or empirical average length of matches.

*Remark 16.* Note that the idea of fast victory and slow defeat has already been proposed but not used in a learning process (Cazenave, Saffidine, Schofield, and Thielscher, 2016).

### 6.2.3 CUMMULATIVE MOBILITY

The next reinforcement heuristic that we propose is *cumulative mobility*. It consists in favoring the matches where the player has more possibility of action and where his opponent has less. The implementation used in this article is as following. The value of a terminal state is $\frac{M_1}{M_2}$ if the first player wins, $-\frac{M_2}{M_1}$ if the second player wins, and 0 in case of a draw, where $M_1$ is the mean of the number of available actions in each turn of the first player since the start of the game and $M_2$ is the mean of the number of available actions in each turn of the second player since the start of the game.

### 6.2.4 PIECE COUNTING: PRESENCE

Finally, we propose as reinforcement heuristic: the *presence heuristic*. It consists in taking into account the number of pieces of each player. This heuristic is based on the principle that the more a player has pieces the more this one has an advantage. There are several implementations for the presence heuristic. We use in this article the following implementation: the heuristic value is $\max(n_1 - n_2, 1)$ if the first player wins, $\min(n_1 - n_2, -1)$ if the second player wins, and 0 in case of a draw, where $n_1$ is the number of pieces of the first player and $n_2$ is the number of pieces of the second player. Note that in the games Surakarta and Othello, the score corresponds to a presence heuristic.

## 6.3 Comparison of Reinforcement Heuristics

We now compare the different heuristics that we have proposed to the classical terminal evaluation function $b_t$ on different games, using the protocol of Section 3.3. Each combination uses Descent with completion (Algorithm 10), completed $\epsilon$-greedy (see Algorithm 2, and Section 5). Each combination uses a different terminal evaluation function. These terminal evaluations are the classical game gain evaluation function $b_t$, the additive depth heuristic, the multiplicative depth heuristic, the scoring heuristic, the cumulative mobility, and the presence heuristic. Other parameters are the same as Section 3.4. There are, at most, a total of 6 combinations per game (on some games, some heuristics are not evaluated because they are trivially of no interest or equivalent to another heuristic). The experiment was repeated 48 times. The winning percentage of a combination for each game and for each evaluation step (i.e. each hour) is therefore calculated from 288 to 576 matches.

The final winning percentages are shown in Table 4. Each percentage of the table has required between 13, 824 and 27, 648 matches. On average and for 7 of the 9 games, the classic terminal heuristic has the worst percentage (exception are Othello and Lines of Action). In scoring games, scoring is the best heuristic, as we might expect. Leaving aside the score heuristic, with the exception of Surakarta, Othello and Clobber, it is one of the two depth heuristics that has the best winning percentage. In Surakarta and Clobber, mobility is just ahead of the depth heuristics. On
<figure><img src="image_5.png" /><figcaption>Figure 4: Evolutions of the winning percentages of the combinations of the experiment of Section 6.3, i.e. the use of the following heuristics: classic (black line), score (purple line), additive depth (blue line), multiplicative depth (turquoise line), cumulative mobility (green line), and presence (red line). The display uses a simple moving average of 6 data.</figcaption></figure>

average, using the additive depth heuristic instead of using the classic evaluation increases the winning percentage by 15%, and using the best depth heuristic increases the winning percentage by 19%. The winning percentage curves are shown in Figure 4. The final percentages summarizes the curves quite well. Note that the positive impact of the additive depth heuristic compared to the other heuristics (except score) is particulary clear at Breakthrough, Amazons, Hex, and Santorini. In a similar manner, the positive impact of the multiplicative depth heuristic is particulary clear at Clobber, Hex, and Open Outer Gomoku.

In conclusion, the use of generic reinforcement heuristics has significantly improved performances and the depth heuristics are prime candidates as a powerful generic reinforcement heuristic.
<table><caption>Table 4: Final winning percentages of the combinations of the experiment of Section 6.3 (X: heuristic without interest in this experiment or for the associated game; presence coincides with score in Surakarta and Othello; 95% confidence intervals: max ±1.04%)</caption><thead><tr><th rowspan="2"></th><th colspan="6">depth</th></tr><tr><th>classic</th><th>score</th><th>additive</th><th>multiplicative</th><th>mobility</th><th>presence</th></tr></thead><tbody><tr><td>Othello</td><td>49.8%</td><td>70.6%</td><td>50.1%</td><td>48.9%</td><td>18.5%</td><td>score</td></tr><tr><td>Hex</td><td>33.3%</td><td>X</td><td>66.1%</td><td>60.4%</td><td>X</td><td>X</td></tr><tr><td>Clobber</td><td>43.7%</td><td>X</td><td>47.0%</td><td>49.8%</td><td>53.5%</td><td>X</td></tr><tr><td>Outer Open Gomoku</td><td>33.0%</td><td>X</td><td>41.4%</td><td>74.4%</td><td>X</td><td>X</td></tr><tr><td>Amazons</td><td>36.8%</td><td>67.9%</td><td>60.0%</td><td>50.7%</td><td>49.0%</td><td>X</td></tr><tr><td>Breakthrough</td><td>39.0%</td><td>X</td><td>69.5%</td><td>40.4%</td><td>43.9%</td><td>48.5%</td></tr><tr><td>Santorini</td><td>42.7%</td><td>X</td><td>59.7%</td><td>46.6%</td><td>43.3%</td><td>X</td></tr><tr><td>Surakarta</td><td>33.5%</td><td>68.9%</td><td>43.1%</td><td>35.3%</td><td>55.6%</td><td>score</td></tr><tr><td>Lines of Action</td><td>50.9%</td><td>X</td><td>57.1%</td><td>46.8%</td><td>53.7%</td><td>44.0%</td></tr><tr><td>mean</td><td>40.3%</td><td>69.1%</td><td>54.9%</td><td>50.4%</td><td>45.4%</td><td>46.3%</td></tr></tbody></table>

## 7 Ordinal Distribution

In this section, we propose another technique, a new action selection distribution. It is based on a new, alternative, probability distribution, that we call ordinal distribution.

The ordinal distribution does not depend on the value of states. However, it depends on the order of their values. On the one hand, this distribution has the advantage of providing different probability distributions for actions that are not the best, unlike $\epsilon$-greedy. On the other hand, it has a more intuitive interpretation than the softmax function. Indeed, with this distribution, we choose with probability $p$ to play the best action. If we do not choose it, we choose the second best action with probability approximately $p$. Otherwise, we choose the third action with probability approximately $p$, etc. More precisely, with this distribution, the conditional probability of playing an action knowing that we do not play a better action is a linear interpolation between the uniform distribution and the max distribution (with respect to the exploitation parameter $\epsilon'$). Its formula is:

$$P(c_i) = \left( \epsilon' + \frac{1 - \epsilon'}{n - i} \right) \cdot \left( 1 - \sum_{j=0}^{j<i} P(c_j) \right)$$

with $n$ the number of children of the root, $i \in \{0, \dots, n-1\}$, $c_i$ the $i$-th best child of the root, $P(c_i)$ the probability of playing the action leading to the child $c_i$, and $\epsilon'$ the exploitation parameter ($\epsilon' = 1 - \epsilon$). Algorithm 14 describes the action selection method resulting from the use of the ordinal distribution with an optimized calculation.

**Remark 17.** We experimentally compared the ordinal distribution to the $\epsilon$-greedy distribution and to the softmax distribution on many games. The ordinal distribution performs better on average and on the majority of games than the other two distributions (the gain is however quite slight but the results are solid). However, we do not show these results in this article. They will be the subject of another publication (this article is long enough). This additional article should normally be named: Ordinally Randomized Safe Unbounded Minimax.
$$-\sum_{a} \frac{n_{s,a}}{\sum_{a'} n_{s,a'}} \log \pi(a|s)$$

where $n_{s,a}$ is the number of times the action $a$ is selected during the search in the state $s$, and $\pi(a|s)$ is the probability of playing $a$ in $s$ according to the neural network. The modified UCT value of the MCTS part of ExIt is given by the following formula:

$$\text{UCT}_{\text{ExIt}}(s, a) = \text{UCT}(s, a) + w_a \cdot \frac{\pi(a|s)}{n_{s,a} + 1}$$

where $\text{UCT}(s, a)$ is the classical UCT term of MCTS (which manages the exploration exploitation dilemma (Coulom, 2007)) and $w_a$ is a constant.

Later during the training, the value network is learned and used in addition to the policy network. The two losses are thus added for the rest of the training. The value loss, named KL loss, used for training the value network is given by the following formula:

$$-z \cdot \log(v(s)) - (1-z) \cdot \log(1-v(s))$$

where $z$ is the result (classic gain) of the match and $v(s)$ is the value of the state $s$ according to the neural network. The modified UCT value of the MCTS part of ExIt when the value network is used is given by the following formula:

$$\text{UCT}_{\text{ExIt}}(s, a) = \text{UCT}(s, a) + w_a \cdot \frac{\pi(a|s)}{n_{s,a} + 1} + w_v \cdot \hat{Q}(s, a)$$

where $w_v$ is a constant, and $\hat{Q}(s, a)$ is the backed up average of the network value after playing $a$ in the state $s$ during the search.

**Algorithm 15 Algorithm ExIt (online Expert Iteration).**

$\hat{\pi}_0 \leftarrow \text{initial\-policy()}$ 
$\pi_0^* \leftarrow \text{build\_expert}(\hat{\pi}_0)$

foreach $i \in \{1, \dots, \max\_\text{iterations}\}$ do

$S_i \leftarrow \text{sample\_self\-play}(\hat{\pi}_{i-1})$ 
$D_i \leftarrow \{(s, \text{imitation\_learning\_target}(\pi_{i-1}^*(s))) \mid s \in S_i\}$ 
$\hat{\pi}_i \leftarrow \text{train\_policy}(\bigcup_{j \le i} D_j)$ 
$\pi_i^* \leftarrow \text{build\_expert}(\hat{\pi}_i)$

## 8.2 Algorithmic Comparison between ExIt, AlphaZero and Athénan

In this section, we compare the following algorithms with each other: Athénan, ExIt, and also AlphaZero. We perform a detailed comparison and then provide a summary.

### 8.2.1 DETAILED ALGORITHMIC COMPARISON

AlphaZero and Athénan share some commonalities that differ with ExIt. We begin by detailing these characteristics common to Athénan and AlphaZero that differ with ExIt. On the one hand,
unlike ExIt, the same neural network is kept from the start to the end of the learning process (it is
not reset before each learning phase). Experience replay is used (although, at least in the context of
Athénan, this is optional: it significantly improves learning performances but learning also works
without it). ExIt uses the *early stopping technique* and, in its best version, relearns all the data
generated from the beginning at each learning phase (performing the learning phases only with the
last data gave less good results during their experiments).

Furthermore, ExIt does a “warm-start”: it performs a pre-training by learning the data of
matches generated from base MCTS (base MCTS does not use any learned policy or value fonction:
the leaf states are evaluated only by statistics of victory of random games). Then, ExIt only uses
and learns the policy with its modified MCTS. Finally, it uses and learns the policy and the value of
states with its modified MCTS. It learns in this way more quickly at the beginning of the training.
Athénan performs a pre-training by learning the data of random terminal states. Like AlphaZero,
Athénan uses mean square error for learning (not the KL loss).

On the other hand, unlike ExIt, with Athénan and AlphaZero, a search is performed in each
state of the match to determine the move to play. Moreover, with AlphaZero and Athénan, the data
of each state of the match is used during the learning phases. On the contrary, ExIt plays matches
without search according to the policy of the neural network in order to perform more games. In
addition, ExIt performs a search for only one state of the match. It therefore uses only one data item
per match for learning.

We now describe the features that differ between Athénan and ExIt (and which are similar be-
tween ExIt and AlphaZero). During confrontations (evaluation matches), Athénan uses Unbounded
Minimax with Safe Decision: UBFM<sub>s</sub>. ExIt and AlphaZero use MCTS. Unlike AlphaZero and
ExIt, with Athénan, all pieces of data of searches, i.e. data of the partial game tree, is learned.
In other words, for learning value of states, tree learning is used instead of terminal learning (thus
(much) more than one piece of data is learned per search). Therefore, there is no need for large par-
allelization to generate a significant number of data for training (as done for ExIt and AlphaZero). In
addition, unlike ExIt, after each match there is a learning phase: learning is carried out continuously.
The acquired experience is thus immediately used to directly generate better matches.

*Remark* 19. Learning the minimax value (performed by Descent) instead of the end-game value (performed by AlphaZero and ExIt) is more informative (under the assumption that the state evaluation is of quality).

*Remark* 20. Note that in the case of our experiments with Athénan, we do not perform matches in parallel (it would however be possible to perform such parallelization). Conversely, ExIt and AlphaZero require massive parallelization of matches (which is done in the experiments in this paper). However, with Athénan, the evaluation of the child states of each state of the game tree is carried out in parallel (on a only GPU), which makes it possible to speed up searches without loss of efficiency. This lossless parallelization is not possible with ExIt and AlphaZero. More details on this parallelization, called Child Batching, in (Cohen-Solal, 2025).

8.2.2 SUMMARY

In summary, the two points that seem most important are that, on the one hand, Athénan is based
on Descent to generate matches, whereas AlphaZero uses MCTS and ExIt uses the neural network
(without search). On the other, Athénan uses tree learning whereas AlphaZero and ExIt uses termi-
nal learning and a target policy. In particular, Athénan does not use a policy, thus there is no need to
<table><caption>Table 5: Number of hidden dense neurons *N* used by ExIt and Athénan for each studied game.</caption><thead><tr><th></th><th>N</th></tr></thead><tbody><tr><td>Go 9 × 9</td><td>365</td></tr><tr><td>Go 11 × 11</td><td>228</td></tr><tr><td>Hex 11 × 11</td><td>228</td></tr><tr><td>Hex 13 × 13</td><td>155</td></tr><tr><td>Othello 8 × 8</td><td>477</td></tr><tr><td>Othello 10 × 10</td><td>286</td></tr><tr><td>Outer-Open-Gomoku</td><td>111</td></tr><tr><td>Connect6</td><td>65</td></tr><tr><td>Havannah 8</td><td>111</td></tr><tr><td>Havannah 10</td><td>65</td></tr></tbody></table>

encode actions (which poses a problem in certain contexts (Soemers, Mella, Browne, and Teytaud, 2021)). Additionally, with Athénan, learning is done after each match. Finally, for confrontations, Athénan uses Unbounded Minimax with Safe Decision but AlphaZero and ExIt use a variant of MCTS biased to use its policy-value neural network.

## 8.3 The Experimental Comparison

We perform a comparison between ExIt and Athénan. Specifically, for the training performed with Athénan, we use completed Descent (Algorithm 10) with tree learning (Algorithm 3), completed ordinal distribution (see Section 5 and Algorithm 14), the classic gain of the game as reinforcement heuristic<fnref n="7" /> (see Section 6), and the stratified experience replay (Section 8).

We test these two algorithms on the following games: Go 9 × 9, Go 11 × 11, Hex 11 × 11, Hex 13 × 13, Othello 8 × 8, Othello 10 × 10, Connect6, Outer-Open-Gomoku, Havannah 8, Havannah 10. We performed 40 repetitions per game and per algorithm. Each training process lasted 15 days.

## 8.4 Technical Details

### 8.4.1 COMMON PARAMETERS

We use the following neural network architecture for each of the training carried out (used as the adaptive evaluation function): a residual network with a convolutional layer with 132 filters, followed by 8 residual blocks (two 3 × 3 convolutions per block with 132 filters each), followed by a flat layer, and followed by two fully connected hidden layers (with each *N* neurons), followed by the final fully connected layer with 1 neuron (the output). The activation function used is the ReLU. The value *N* for each game is described in Table 5. The number of variables in each network is approximately 5 · 10⁶. The Adam parameters are $\lambda = 0.0001$, $\beta_1 = 0.9$, $\beta_2 = 0.999$ and $\epsilon = 10^{-7}$. L₂ regularization is used with 0.001 as parameter.

<footnote n="7">7. We could have used the score heuristic when available and the depth heuristic otherwise, which would have strongly increased Athénan's performance, but since it might be possible to inject such heuristics into ExIt, it is fair not to use them.</footnote>
### 8.4.2 EXIT PARAMETERS

The neural network has an additional head used to calculate the policy (parallel to the dense layers described above). It is composed of a convolutional $1 \times 1$ layer with 1 filter followed by a final dense layer with as many neurons as there are actions available (i.e. the number of neurons is the output policy size). Finally, the softmax function is applied on the output with the temperature parameter $T_{softmax}$ (provided at the end of this section).

As described in the ExIt paper, the neural networks is initialized by the data from matches of the base MCTS algorithm against itself. In this paper, that data were generated and learned during 12 hours (10 MCTS has been used in parallel by using 10 CPU). From the 3th day, the value network is learned and used, in addition to the policy network. We use the default settings of ExIt, except for the number of rollouts and the number of matches parallelization. We use 2500 rollouts for the MCTS algorithm used by ExIt instead of 10,000. Recall that the parallelization of matches is used to perform matches synchronously so that their states are evaluated simultaneously by the neural network on the graphic card. The inference batch size of this parallelization procedure has been reduced from 1024 to 500 (except for Othello $10 \times 10$ where it is reduced to 333). Based on our testings, these changes have very little impact on performance. However, the original larger values cause many memory overflows, some of which are unpredictable. Recall that ExIt has been applied in its introduction article only to Hex $9 \times 9$, which is a game with a quite small board.

For the other parameters, we thus use the default settings: UCT constant $C$ during the initialization: 0.25, UCT constant $C$ after the initialization: 0.05, learning batch size: 250, softmax temperature $T_{softmax} = 0.1$, search constants of ExIt MCTS: $w_a = 100$ and $w_v = 0.75$.

### 8.4.3 ATHÉNAN PARAMETERS

During training, search time per action is $\tau = 3s$. The stratified experience replay parameters used are: the batch size $B = 3000$, the memory size $\mu = 100$, the duplication factor $\delta = 3$. Moreover, when the children of a state are evaluated by the neural network, they are batched and thus evaluated in parallel (on the only GPU). The evaluation function has been pre-initialized by learning the values of random terminal states (of the order of 10,000,000). This pre-initialized lasted 12 hours and used only one CPU. Resolved states are kept in memory (the memory of the resolved states is emptied every 12 learning hours). No simulated annealing was used for the ordinal distribution. The parameter value of this distribution is a random number drawn uniformly from $[0,1]$ each time the ordinal distribution is used. Other parameters are the same as Section 3.3.1.

## 8.5 Results

Athénan and ExIt were evaluated against the base MCTS algorithm throughout their training. An evaluation has been performed approximately every day (for a total of 15 evaluations). The search time per action during the evaluations is 2 seconds. During an evaluation, each algorithm played 100 matches as first player and 100 more matches as second player.

The performance of an algorithm is its win rate minus its loss rate against MCTS, averaged over the 40 repetitions. The evolution during the learning process of the average performances over all games of Athénan and ExIt against MCTS are described in Table 5. The evolution curves for each game are in the following figures: Go $9 \times 9$: Table 6, Go $11 \times 11$: Table 7, Hex $11 \times 11$: Table 8, Hex $13 \times 13$: Table 9, Othello $8 \times 8$: Table 10, Othello $10 \times 10$: Table 11, Connect6: Table 13, Outer-Open-Gomoku: Table 12, Havannah $8$: Table 14, Havannah $10$: Table 15.
<figure><img src="image_6.png" /><figcaption>Figure 5: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS over all tested games (mean of performance and its stratified bootstrapping 5% confidence interval).</figcaption></figure>

The final performance improvement of Athénan compared to ExIt is as follows: +62.51% on average over all games, +162% at Go 9 × 9, +158% at Go 11 × 11, +32% at Hex 11 × 11, +47% at Hex 13 × 13, +110% at Othello 8 × 8, +89% to Othello 10 × 10, +9.5% at Outer-Open-Gomoku, +5.45% to Connect6 (but learning is at least 10 times much faster), +92% at Havannah 8, +23% at Havannah 10.

In conclusion, Athénan performs better than ExIt on all games and is strongly better on average and on the majority of games.

# 9 Application to Hex

In this section, we apply Athénan to design program-players to the game of Hex. We begin by giving details regarding Hex, its rules and its computational properties. Next, we present the algorithms from the literature playing to Hex (Section 9.2). Then, we apply Athénan to Hex with the board size 11 × 11 and we exceed the level of 3HNN, the best Hex program before Athénan (Section 9.3). Finally, we apply Athénan to Hex again but this time with the board size 13 × 13 and we still go beyond the level of 3HNN (Section 9.4).

## 9.1 Game of Hex

The game of Hex (Browne, 2000) is a two-player combinatorial strategy game. It is played on an empty $n \times n$ hexagonal board. We say that a $n \times n$ board is of size $n$. The board can be of any size, although the classic sizes are 11, 13 and 19. In turn, each player places a stone of his
<figure><img src="image_7.png" /><figcaption>Figure 6: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Go 9 × 9 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 7: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Go 11 × 11 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Figure 8: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Hex 11 × 11 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 9: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Hex 13 × 13 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 10: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Othello 8 × 8 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 11: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Othello 10 × 10 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Figure 12: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Outer-Open-Gomoku (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 13: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Connect6 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>Figure 14: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Havannah 8 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Figure 15: Evolutions over 15 training days of performances of the 40 learning repetitions of Athénan and ExIt against base MCTS for Havannah 10 (max of performance and mean of performance and its bootstrapping 5% confidence interval).</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Figure 16: A Hex end game of size 11 (white wins)</figcaption></figure>

color on an empty cell (each stone is identical). The goal of the game is to be the first to connect the two opposite sides of the board corresponding to its color. Figure 16 illustrates an end game. Although its rules are simplistic, Hex tactics and strategies are complex. The number of states and the number of actions per state are very large, similar to the game of Go. From the board size 11, the number of states is, for example, higher than that of chess (Table 6 of (Van Den Herik, Uiterwijk, and Van Rijswijck, 2002)). For any board size, the first player has a winning strategy (Berlekamp, Conway, and Guy, 2003) which is unknown, except for board sizes smaller than or equal to 10 (Pawlewicz and Hayward, 2013) (the game is weakly solved up to the size 10). In fact, resolving a particular state is PSPACE-complete (Reisch, 1981; Bonnet, Jamain, and Saffidine, 2016). There is a variant of Hex using a swap rule. With this variant, the second player can play in first action a special action, called *swap*, which swaps the color of the two players (i.e. they swap their pieces and their sides). The swap rule reduces the imbalance between the two players (without the swap rule, the first player has a very strong advantage). It is generally used in competitions. It is always used at the Computer Olympiad and in this paper.

## 9.2 Hex Programs

Many Hex player programs have been developed. For example, Mohex 1.0 (Huang, Arneson, Hayward, Müller, and Pawlewicz, 2013) is a program based on Monte Carlo tree search. It also uses many techniques dedicated to Hex, based on specific theoretical results. In particular, it is able to quickly determine a winning strategy for some states (without expanding the search tree) and to prune at each state many actions that it knows to be *inferior*. It also uses ad hoc knowledge to bias simulations of Monte Carlo tree search.

Mohex 2.0 (Huang et al., 2013) is an improvement of Mohex 1.0 that uses learned knowledge through supervised learning (namely correlations between victory and board patterns) to guide both tree exploration and simulations.

Other work then focused on predicting best actions, through supervised learning of a database of games, using a neural network (Michalski, Carbonell, and Mitchell, 2013; LeCun, Bengio, and Hinton, 2015; Goodfellow, Bengio, Courville, and Bengio, 2016). The neural network is used to
<table><caption>Table 6: Comparison of the main features of the latest Hex programs. These characteristics are respectively the board sizes on which learning is based, the used tree search algorithm, the type of learning, the type of neural network, and its use (to approximate the values of states, actions, and/or policy).</caption><thead><tr><td>Programs</td><td>Size</td><td>Search</td><td>Learning</td><td>Network</td><td>Use</td></tr></thead><tbody><tr><td>Mohex-CNN</td><td>13</td><td>MCTS</td><td>supervised</td><td>convolutional</td><td>policy</td></tr><tr><td>Mohex-3HNN</td><td>13</td><td>MCTS</td><td>supervised</td><td>residual</td><td>policy, state, action</td></tr><tr><td>NeuroHex</td><td>13</td><td>none</td><td>supervised, reinforcement</td><td>convolutional</td><td>state</td></tr><tr><td>EZO-CNN</td><td>7, 9, 11</td><td>Minimax</td><td>reinforcement</td><td>convolutional</td><td>state</td></tr><tr><td>DeepEZO</td><td>13</td><td>Minimax</td><td>reinforcement</td><td>convolutional</td><td>policy, state</td></tr><tr><td>ExIt</td><td>9</td><td>MCTS</td><td>reinforcement</td><td>convolutional</td><td>policy, state</td></tr></tbody></table>

learn a *policy*, i.e. a prior probability distribution on the actions to play. These prior probabilities are used to guide the exploration of Monte Carlo tree search. First, there is Mohex-CNN (Gao et al., 2017) which is an improvement of Mohex 2.0 using a convolutional neural network (Krizhevsky et al., 2012). A new version of Mohex was then proposed: Mohex-3HNN (Gao et al., 2018). Unlike Mohex-CNN, it is based on a residual neural network (He, Zhang, Ren, and Sun, 2016). It calculates, in addition to the policy, a value for states *and* actions. The value of states replaces the evaluation of states based on simulations of Monte Carlo tree search. Adding a value to actions allows Mohex-HNN to reduce the number of calls of the neural network, improving performance. Mohex-3HNN is the best Hex program. It wins Hex size 11 and 13 tournaments at 2018 Computer Olympiad (Gao et al., 2019).

Programs which learn the evaluation function by reinforcement have also been designed. These programs are NeuroHex (Young et al., 2016), EZO-CNN (Takada, Iizuka, and Yamamoto, 2017), DeepEzo (Takada, Iizuka, and Yamamoto, 2019), and ExIt (Anthony et al., 2017). They learn from self-play. Unlike the other three programs, NeuroHex performs supervised learning (of a common Hex heuristic) followed by reinforcement learning. NeuroHex also starts its matches with a state from a database of games. EZO-CNN and DeepEzo use knowledge to learn winning strategies in some states. DeepEzo also uses knowledge during confrontations. ExIt learns a policy in addition to the value of states and it is based on MCTS (see Section 8 for details). It is the only program to have learned to play Hex without using knowledge. That result is, however, limited to the board size 9. A comparison of the main characteristics of these different programs is presented in Table 6.

## 9.3 A Long Training for Hex 11

We now apply all the techniques that we have proposed to carry out a long self-play reinforcement learning on Hex size 11. More precisely, we use completed Descent (Algorithm 10) with tree learning (Algorithm 3), completed ordinal distribution (see Section 5 and Algorithm 14), and the additive depth heuristic (see Section 6.2.2).

### 9.3.1 TECHNICAL DETAILS

In addition, we use a classical data augmentation: the adding of symmetrical states. Symmetrical states are added in *D*, the set of pairs $(s, v)$ of the game tree (see Section 3 for details). The addition
<table><caption>Table 7: Winning percentages against Mohex 3HNN of UBFM<sub>s</sub> using the learned evaluation function of Section 9.3 (the search time per action is the same for each player; default settings are used for Mohex; there are as many matches in first as in second player).</caption><thead><tr><td>search time</td><td>Mohex 2nd</td><td>Mohex 1st</td><td>mean</td><td>95% confidence interval</td><td>total matchs</td></tr></thead><tbody><tr><td>2.5s</td><td>98%</td><td>84%</td><td>91%</td><td>2%</td><td>1000</td></tr><tr><td>10s</td><td>91%</td><td>86%</td><td>88%</td><td>2%</td><td>1600</td></tr></tbody></table>

of symmetric states is performed after the end of each match and before the application of experience replay. Formally, $D \leftarrow D \cup \{(r_{180^{\circ}}(s), v) | (s, v) \in D\}$ where $r_{180^{\circ}}(s)$ is $s$ rotated by $180^{\circ}$. More precisely, the processing($D$) method of Algorithm 3 is experience_replay(symmetry($D$), $\mu$, $\sigma$)) where symmetry($D$) adds symmetrical states in $D$ as described above and returns $D$.

The used learning parameters are: search time per action $\tau = 2s$ and batch size $B = 3000$. The experience replay parameters are: games memory size $\mu = 100^8$ and sampling rate $\sigma = 5\%$.

We use the following neural network as adaptive evaluation function: a residual network with a convolutional layer with 83 filters, followed by 4 residual blocks (2 convolutions per block with 83 filters each), and followed by a fully connected hidden layers (with 74 neurons). The activation function used is the ReLU.

The input of the neural network is a game board extended by one line at the top, bottom, right and left (in the manner of (Young et al., 2016; Anthony et al., 2017)). More precisely, each of these lines is completely filled with the stones of the player of the side where it is located. This extension is simply used to explicitly represent the sides of the board and their membership.

Moreover, when the children of a state are evaluated by the neural network, they are batched and thus evaluated in parallel (on the only GPU).

The evaluation function has been pre-initialized by learning the values of random terminal states (their number is 15, 168, 000).

The other settings are the same as those in Section 3.3.1. Resolved states are kept in memory (the memory of the resolved states is emptied every two learning day).

The reinforcement learning process lasted 34, 321 matches. Note that the number of data used during the learning process is of the order of $59 \cdot 10^7$, the number of neural network evaluations is of the order of $196 \cdot 10^6$, and the number of state evaluations is of the order of $15 \cdot 10^9$.

### 9.3.2 RESULTS

The winning percentages against Mohex 3HNN of Athénan (i.e. of UBFM<sub>s</sub> using the learned evaluation function generated by Descent) are described in Table 7. Note that the proposed techniques have made it possible to exceed the level of Mohex 3HNN on Hex size 11, and without the use of knowledge (which had not been done until then).

## 9.4 A Long Training for Hex 13

We carry out the same experiment as the previous section, but on Hex size 13.

<footnote n="8">8. A variant of replay experience was applied, it memorizes the pairs of the last 100 games and not the last 100 pairs.</footnote>
<table><caption>Table 8: Winning percentages against Mohex 3HNN of UBFM<sub>s</sub> using the learned evaluation function of Section 9.4 (the search time per action is the same for each player; default settings are used for Mohex; there are as many matches in first as in second player).</caption><thead><tr><th>search</th><th>Mohex 2nd</th><th>Mohex 1st</th><th>mean</th><th>95% confidence interval</th><th>total matchs</th></tr></thead><tbody><tr><td>2.5s</td><td>100%</td><td>100%</td><td>100%</td><td>0%</td><td>1200</td></tr><tr><td>10s</td><td>100%</td><td>100%</td><td>100%</td><td>0%</td><td>800</td></tr></tbody></table>

### 9.4.1 TECHNICAL DIFFERENCES

The architecture of the neural network is a convolutional layer with 186 filters, followed by 8 residual blocks (2 convolutions per block with 186 filters each), and followed by 2 fully connected hidden layers (with 220 neurons each). The activation function used is the ReLU. The network was not initialized by random end state values. The experience replay parameters are: games memory size $\mu = 250^9$ and sampling rate $\sigma = 2\%$. The search time per action $\tau$ is 5s. The reinforcement learning process lasted 5,288 matches. Note that the number of data used during the learning process is of the order of $16 \cdot 10^7$, the number of neural network evaluations is of the order of $64 \cdot 10^6$, and the number of state evaluations is of the order of $7 \cdot 10^9$.

### 9.4.2 RESULTS

The winning percentages against Mohex 3HNN of Athénan (i.e. of UBFM<sub>s</sub> using the learned evaluation function generated by Descent) are described in Table 8. Thus, Athénan has also exceeded the level of Mohex 3HNN at Hex size 13 (with swap). This had not been done before and was achieved without using any prior knowledge about Hex strategies.

## 10 Application at Othello

In this section, we apply Athénan on the game of Othello. After completing the reinforcement learning process without knowledge, we evaluated Athénan against the state-of-the-art at Othello: the Edax program<sup>10</sup>. We start by presenting the state-of-the-art at Othello (Section 10.1), then we describe the experiment carried out (Section 10.2) and its technical details (Section 10.3), and finally we present the results (Section 10.4).

### 10.1 Othello Related Work

Although Othello is one of the first games in which artificial intelligence has reached a super-human level, there is still research on Othello. Edax and Saio are the Othello state-of-the-art programs (Wikipedia contributors, 2022; Norelli and Panconesi, 2022; Liskowski, Jaśkowski, and Krawiec, 2018; Fédération Française d'Othello). Saio is not free and is similar to Edax. Edax is an open source highly optimized program. It is based on minimax and dedicated Othello techniques: *multi-probcut tree search, tabular value functions* (as evaluation function) generated from expert knowledge, and opening sequences (Buro, 1997).

<footnote n="9">9. A variant of replay experience was applied, it memorizes the pairs of the last 250 games and not the last 250 pairs.</footnote>

<footnote n="10">10. Edax version 4.4: https://github.com/abulmo/edax-reversi</footnote>
There are other programs at Othello.

A move predictor (Liskowski et al., 2018) was designed at Othello using a convolutional neural network learned by supervised learning. However, its level is low. In particular, it only beats Edax when Edax plans at depth 2 (which takes it on the order of $10^{-4}$ seconds), whereas Edax plans with a depth between 20 and 30 for a search time of the order of seconds.

AlphaZero has been applied recently at Othello (Norelli and Panconesi, 2022). This AlphaZero program, named Olivaw, is as strong as Edax with a search depth of 8. Their program reached a high level at Othello, and was able to beat a national champion at Othello.

See (Wikipedia contributors, 2022; Norelli and Panconesi, 2022; Liskowski et al., 2018) for a detailed Related Work about Computer Othello.

## 10.2 Experiment

We now apply Athénan to carry out a long self-play reinforcement learning at Othello. More precisely, we use completed Descent (Algorithm 10) with tree learning (Algorithm 3), completed original distribution (see Section 5 and Algorithm 14), the game score as reinforcement heuristic (see Section 6), and the stratified experience replay (Section 8).

## 10.3 Technical Details

In addition, we use a classical data augmentation: the adding of symmetrical states. Symmetrical states are added in $D$, the set of pairs $(s, v)$ of the game tree (see Section 3 for details). This addition is performed after the end of each game and before the application of experience replay. Formally, $D \leftarrow D \cup \{(\mathrm{sym}(s), v) \mid (s, v) \in D\}$ where $\mathrm{sym}(s)$ returns one of the 8 symmetric board states of $s$. In other words, the processing($D$) method of Algorithm 3 is experience replay($\mathrm{symmetry}(D)$), $\mu$, $\sigma$) where symmetry($D$) adds symmetrical states in $D$ as described above and returns $D$.

Search time per action is $\tau = 5s$. The stratified experience replay parameters used are: the batch size $B = 4000$, the memory size $\mu = 100$, the duplication factor $\delta = 3$.

We use the following neural network as adaptive evaluation function: a residual network with a convolutional layer with 373 filters, followed by 8 residual blocks (two $3 \times 3$ convolutions per block with 373 filters each following with a squeeze-and-excitation layer (Hu, Shen, and Sun, 2018) whose ratio is 16), followed by a $1 \times 1$ convolution with 4453 filters, followed by a global sum pooling (Aich and Stavness, 2018), followed by a flat layer, and followed by a fully connected hidden layers (with 4453 neurons). The activation function used is the ReLU. Number of weights of the neural network is 41, 695, 147. The Adam parameters are $\lambda = 0.0001$, $\beta_1 = 0.9$, $\beta_2 = 0.999$ and $\epsilon = 10^{-5}$. The parameter of the $L_2$ regularization is 0.99.

Moreover, when the children of a state are evaluated by the neural network, they are batched and thus evaluated in parallel (on the only GPU). The evaluation function has been pre-initialized by learning the values of random terminal states (of the order of 10, 000, 000). Resolved states are kept in memory (the memory of the resolved states is emptied every 12 learning hours). TNo simulated annealing was used for the ordinal distribution. The parameter of the ordinal distribution is a random number drawn uniformly from [0,1] each time this distribution is used. The other settings are the same as those in Section 3.3.1.

The reinforcement learning process lasted 52, 470 matches. Note that the number of data used during the learning process is of the order of $426 \cdot 10^7$, the number of neural network evaluations is of the order of $606 \cdot 10^6$, and the number of state evaluations is of the order of $3.49 \cdot 10^9$.
<table><caption>Table 9: Winning percentages against Edax of UBFM<sub>s</sub> using the learned evaluation function of Section 10.2 (the search time per action is the same for each player; there are as many matches in first as in second player).</caption><thead><tr><td>search time</td><td>win - loss</td><td>win</td><td>draw</td><td>loss</td><td>95% confidence radius</td><td>total matchs</td></tr></thead><tbody><tr><td>1.5s</td><td>20%</td><td>39.37%</td><td>41.25%</td><td>19.37%</td><td>3, 4%</td><td>800</td></tr><tr><td>15s</td><td>12.25%</td><td>25.37%</td><td>61.5%</td><td>13.12%</td><td>3, 4%</td><td>800</td></tr></tbody></table>

## 10.4 Results

The winning percentages against Edax of Athénan (i.e. of UBFM<sub>s</sub> using the learned evaluation function generated by Descent) are described in Table 9. Thus, the proposed techniques have made it possible to exceed the level of Edax at Othello. Recall that this reinforcement learning was carried out without using prior knowledge about Othello strategies.

## 11 Application at Arimaa

In this section, we apply Athénan on the game of Arimaa and we evaluate the performed process of reinforcement learning without knowledge against the state-of-the-art of Arimaa: the Sharp program (Wu, 2015). We start by presenting the state-of-the-art at Arimaa (Section 11.1), then we describe the experiment carried out (Section 11.2) and its technical details (Section 11.4), and finally we present the results (Section 11.5).

### 11.1 Arimaa Related Work

Since 2015, state-of-the-art at Arimaa is the program Sharp (Wu, 2015). Sharp combined traditional alpha-beta pruning with handcrafted heuristic functions. But it uses a lot of improvements of alpha-beta, called *killer moves*, *history heuristic*, *quiescence search*, *extensions*, *late move reduction*, (theses techniques required dedicated knowledge to be used). It also uses techniques dedicated to Arimaa: specific algorithms and knowledge used by alpha-beta and its improvements (mainly for move ordering, pruning, and state evaluating).

Alternative approaches to alpha-beta at Arimaa have been studied, notably based on Monte Carlo, but without success (Wu, 2015). There have also been some attempts to apply AlphaZero at Arimaa, but they have all failed to our knowledge (Forum, 2024).

### 11.2 Experiment

We now apply Athénan to carry out a long self-play reinforcement learning at Arimaa. More precisely, we use completed Descent (Algorithm 10) with tree learning (Algorithm 3), completed ordinal distribution (see Section 5 and Algorithm 14), the stratified experience replay (Section 8), and the Arimaa reinforcement heuristic described in the following section.
## 11.3 Arimaa Reinforcement Heuristic

The reinforcement heuristic (see Section 6) we used for Arimaa is a variation of the presence heuristic (Section 6) which takes into account the importance of the pieces which comes directly from the rules.

We use the following state evaluation function, denoted by $h_{arimaa}$, as reinforcement heuristic.

Let $s$ be a game state. Then, $h_{arimaa}(s) = \begin{cases} 69 + V(s) & \text{if first player wins} \\ -69 + V(s) & \text{if second player wins} \end{cases}$ where $P_1(s)$ (resp. $P_2(s)$) the set of pieces of the first player (resp. second player) in $s$, $V(s)$ is the difference of the values of the two players pieces:

$$V(s) = \sum_{p \in P_1(s)} v_{arimaa}(p) - \sum_{p \in P_2(s)} v_{arimaa}(p),$$

and $v_{arimaa}(p)$ is the value the piece $p$ corresponding to the importance of that piece according to the rule. The value $v_{arimaa}(p)$ is defined as follows: $v_{arimaa}$ (elephant) = 5, $v_{arimaa}$ (camel) = 4, $v_{arimaa}$ (horse) = 3, $v_{arimaa}$ (dog) = 2, $v_{arimaa}$ (cat) = 1, $v_{arimaa}$ (rabbit) = 6.

## 11.4 Technical Details

In addition, we use a classical data augmentation: the adding of symmetrical states. Symmetrical states are added in $D$, the set of pairs $(s, v)$ of the game tree (see Section 3 for details). This addition is performed after the end of each game and before the application of experience replay. Formally, $D \leftarrow D \cup \{(\text{sym}(s), v) | (s, v) \in D\}$ where $\text{sym}(s)$ returns one of the symmetric board states of $s$. In other words, the processing($D$) method of Algorithm 3 is experience_replay(symmetry($D$), $\mu$, $\sigma$)) where symmetry($D$) adds symmetrical states in $D$ as described above and returns $D$.

Search time per action is $\tau = 5s$. The stratified experience replay parameters used are: the batch size $B = 4000$, the memory size $\mu = 100$, the duplication factor $\delta = 3$.

We use the following neural network as adaptive evaluation function: a residual network with a convolutional layer with 263 filters, followed by 4 residual blocks (two $3 \times 3$ convolutions per block with 263 filters each), followed by a $1 \times 1$ convolution with 2217 filters, followed by a global sum pooling (Aich and Stavness, 2018), followed by a flat layer, and followed by a fully connected hidden layers (with 2217 neurons). The activation function used is the ReLU. Number of weights of the neural network is 10, 511, 017. The Adam parameters are $\lambda = 0.0001$, $\beta_1 = 0.9$, $\beta_2 = 0.99$ and $\epsilon = 10^{-7}$.

Moreover, when the children of a state are evaluated by the neural network, they are batched and thus evaluated in parallel (on the only GPU). The evaluation function has been pre-initialized by learning the values of random terminal states (of the order of 10, 000, 000). Resolved states are kept in memory (the memory of the resolved states is emptied every 12 learning hours). The other settings are the same as those in Section 3.3.1.

The reinforcement learning process lasted 6, 317 matches. Note that the number of data used during the learning process is of the order of $768 \cdot 10^7$, the number of neural network evaluations is of the order of $10^9$, and the number of state evaluations is of the order of $30 \cdot 10^9$.
<table><caption>Table 10: Winning percentages against Sharp of UBFM<sub>s</sub> using the learned evaluation function of Section 10.2 (the search time per action is the same for each player; there are as many matches in first as in second player).</caption><thead><tr><td>search time</td><td>win</td><td>loss</td><td>95% confidence interval</td><td>total matches</td></tr></thead><tbody><tr><td>2.5s</td><td>90.33%</td><td>9.66%</td><td>4%</td><td>600</td></tr><tr><td>10s</td><td>92.5%</td><td>7.5%</td><td>4%</td><td>600</td></tr></tbody></table>

## 11.5 Results

The winning percentages against Sharp of Athénan (i.e. of UBFM<sub>s</sub> using the learned evaluation function generated by Descent) are described in Table 10. Thus, the proposed techniques have made it possible to exceed the level of Sharp at Arimaa. Recall that this reinforcement learning was carried out without using prior knowledge about Arimaa strategies.

## 12 Application at Morpion Solitaire

In this section, we apply Athénan on the game of *Morpion Solitaire* (also called *Join Five*), a puzzle game (one-player game). We start by detailing the rules of Morpion Solitaire (Section 12.1), then presenting the state-of-the-art at Morpion Solitaire (Section 12.2). Next, we describe the experiment carried out (Section 12.3) and its technical details (Section 12.4), and finally we present our results (Section 12.5).

### 12.1 Morpion Solitaire Rules

The goal of the Morpion Solitaire is to play as long as possible. The score of the Morpion Solitaire is therefore the number of moves played since the start of the game. The Morpion Solitaire board is an infinite size square board. At the start of the game, some points are already placed in the shape of a cross. At each turn, the player places a point on the board and crosses out an alignment of 5 points not already crossed out in that direction. A point can therefore only be crossed out at most 4 times (horizontally, vertically, diagonally and antidiagonally). The 5 points must include the point just placed. A point can only be placed if it will belong to an alignment of 5 points that can be crossed out. A move includes the point placement plus the choice of the 5 aligned points and their crossing-out. As soon as the player cannot place any more points, the game is over. The initial board and the board of an example of first move are represented in Figure 17.

The Morpion Solitaire has a variant, called the *touching version* (the Morpion Solitaire, described above, is called the *disjoint version*). With the touching variant, the endpoints of an already drawn line can be used as an endpoint for a new line aligned in the same direction. This variant is not studied in this paper.

### 12.2 Morpion Solitaire Related Work

An upper bound on the maximum score at Morpion Solitaire (disjoint version) is 84 (Michalewski, Nagórko, and Pawlewicz, 2016). The human record is 68 (Wang, Preuss, Emmerich, and Plaat, 2020). The best actual record is 82. The record of 82 was obtained with *Nested Rollout Pol-
<figure><img src="image_18.png" /><figcaption>Figure 17: Initial board for Morpion Solitaire (left) ; The board of Morpion Solitaire after a first move (right).</figcaption></figure>

*icy Adaptation* (Rosin, 2011) and *Beam Nested Rollout Policy Adaptation* (Cazenave and Teytaud, 2012), which are Monte Carlo algorithms, using online learning, dedicated to one-player games.

AlphaZero has been applied with the *Ranked Reward* technique to Morpion Solitaire (Wang et al., 2020). The record obtained by this AlphaZero program is only 67.

ExIt, the reinforcement learning algorithm without knowledge, has been combined with Nested Rollout Policy Adaptation and applied to Morpion Solitaire (Doux, Negrevergne, and Cazenave, 2021). The record of this ExIt program is 73.

The touching version has also been studied. The record for this variant of Morpion Solitaire is 178 (Nagórko, 2019).

## 12.3 Experiment

We now apply Athénan to carry out a long self-play reinforcement learning without knowledge at Morpion Solitaire. More precisely, we use Descent (Algorithm 9) with tree learning (Algorithm 3), ordinal distribution (see Section 7), the stratified experience replay (Section 8), and the score heuristic as reinforcement heuristic (Section 6).

*Remark 21.* Note that completion is not used since it only concerns two-player games. However, resolved states are still used. In this context, a state is resolved only if all its children are resolved.

## 12.4 Technical Details

All endgame are draw unless the score of 84 is reached (win).

We use a classical data augmentation: the adding of symmetrical states. Symmetrical states are added in $D$, the set of pairs $(s, v)$ of the game tree (see Section 3 for details). This addition is performed after the end of each game and before the application of experience replay. Formally, $D \leftarrow D \cup \{(\mathrm{sym}(s), v) \mid (s, v) \in D\}$ where $\mathrm{sym}(s)$ returns one of the symmetric board states of $s$. In other words, the processing($D$) method of Algorithm 3 is `experience_replay(symmetry($D$), $\mu$, $\sigma$))` where `symmetry($D$)` adds symmetrical states in $D$ as described above and returns $D$.
<figure><img src="image_19.png" /><figcaption>Figure 18: Evolution of the score obtained in Morpion Solitaire using the evaluation function learned and UBFM<sub>s</sub> with 0.1 second of search per action.</figcaption></figure>

Search time per action is $\tau = 1$s. The stratified experience replay parameters used are: the batch size $B = 3000$, the memory size $\mu = 100$, the duplication factor $\delta = 3$.

We use the following neural network as adaptive evaluation function: a residual network with a convolutional layer with 186 filters, followed by 8 residual blocks (two $3 \times 3$ convolutions per block with 186 filters each, following with a squeeze-and-excitation layer (Hu et al., 2018) whose ratio is 16), followed by a flat layer, and followed by two fully connected hidden layers (with each 104 neurons). The activation function used is the ReLU. Number of weights of the neural network is 9, 989, 285. The Adam parameters are $\lambda = 0.0001$, $\beta_1 = 0.9$, $\beta_2 = 0.99$ and $\epsilon = 10^{-8}$.

Moreover, when the children of a state are evaluated by the neural network, they are batched and thus evaluated in parallel (on the only GPU). The evaluation function has been pre-initialized by learning the values of random terminal states (of the order of 10, 000, 000). Resolved states are kept in memory (the memory of the resolved states is emptied every 12 learning hours). The other settings are the same as those in Section 3.3.1.

The reinforcement learning process lasted 58, 971 matches. Note that the number of data used during the learning process is of the order of $126 \cdot 10^7$, the number of neural network evaluations is of the order of $0.19 \cdot 10^9$, and the number of state evaluations is of the order of $1.8 \cdot 10^9$.

## 12.5 Results

The evolution of the score obtained in Morpion Solitaire using Athénan (i.e. using UBFM<sub>s</sub> based on the evaluation function generated by Descent) with 0.1 second of search per action is described in Figure 18. The score of 82 is reached in the 58, 971 match.

Thus, the state-of-the-art level has been reached with a more general algorithm than the state-of-the-art techniques on this game. Recall that this result was not achieved with ExIt and AlphaZero, the two alternative algorithms of Athénan.

This result further shows that Athénan is applicable to single-player games.
<table><caption>Table 11: Athénan Computer Olympiad results (0: participation without result; 1: participation without opponent, i.e. title not contested; empty: no participation).</caption><thead><tr><th></th><th>2020</th><th>2021</th><th>2022</th><th>2023</th><th>2024</th></tr></thead><tbody><tr><td>Amazons</td><td>Gold</td><td>Gold</td><td>1</td><td>Gold</td><td>Gold</td></tr><tr><td>Breakthrough</td><td>Gold</td><td>Gold</td><td>Gold</td><td>Gold</td><td>Gold</td></tr><tr><td>Clobber</td><td>Gold</td><td>1</td><td>1</td><td>Gold</td><td>Gold</td></tr><tr><td>Surakarta</td><td>Gold</td><td>Gold</td><td>Gold</td><td>Gold</td><td>Gold</td></tr><tr><td>Othello 8x8</td><td>Silver</td><td>Gold</td><td>Silver</td><td>Bronze</td><td>1</td></tr><tr><td>Othello 10x10</td><td>Gold</td><td>1</td><td>1</td><td>Gold</td><td>1</td></tr><tr><td>Othello 16x16</td><td></td><td></td><td></td><td></td><td>Gold</td></tr><tr><td>Hex 11x11</td><td></td><td>Gold</td><td>1</td><td>Gold</td><td>Gold</td></tr><tr><td>Hex 13x13</td><td>0</td><td>Gold</td><td>1</td><td>Gold</td><td>Gold</td></tr><tr><td>Hex 19x19</td><td>0</td><td>Gold</td><td>1</td><td>Gold</td><td>1</td></tr><tr><td>Havannah 8</td><td>0</td><td>Gold</td><td>1</td><td>Gold</td><td>Gold</td></tr><tr><td>Havannah 10</td><td></td><td>Gold</td><td>1</td><td>Gold</td><td>1</td></tr><tr><td>Canadian Draughts</td><td></td><td>Gold</td><td>Gold</td><td>Gold</td><td>1</td></tr><tr><td>Brazilian Draughts</td><td></td><td>Gold</td><td>0</td><td>Silver</td><td>1</td></tr><tr><td>International Draughts</td><td></td><td>Silver</td><td>0</td><td>Silver</td><td>0</td></tr><tr><td>Connect6</td><td></td><td>Silver</td><td>Silver</td><td>Silver</td><td>0</td></tr><tr><td>Outer-Open-Gomoku</td><td></td><td>Bronze</td><td>Silver</td><td>Bronze</td><td>0</td></tr><tr><td>Ataxx</td><td></td><td></td><td>Gold</td><td>Gold</td><td>Gold</td></tr><tr><td>Santorini</td><td></td><td></td><td>Gold</td><td>Gold</td><td>0</td></tr><tr><td>Lines of Action</td><td></td><td></td><td>0</td><td>Gold</td><td>Gold</td></tr><tr><td>Xiangqi</td><td></td><td></td><td>0</td><td>Gold</td><td>1</td></tr><tr><td>Arimaa</td><td></td><td></td><td></td><td>Gold</td><td>1</td></tr><tr><td>Shobu</td><td></td><td></td><td></td><td></td><td>Gold</td></tr></tbody></table>

## 13 Computer Olympiad Results

In this section, we briefly present Athénan's results in the global board game artificial intelligence competition, namely the Computer Olympiad.

Athénan won a lot of gold medals at the Computer Olympiad: 48 in total. It won eleven gold medals in 2024 (Cohen-Solal and Cazenave, 2025a), sixteen gold medals in 2023 (Cohen-Solal and Cazenave, 2023a), five gold medals in 2022, eleven in 2021, and again five in 2020 (Cohen-Solal and Cazenave, 2021).

Moreover, Athénan is currently the defending champion on 17 games (the eleven 2024 gold medals plus 6 previous uncontested gold medals). All Athénan results are summarized in Table 11.

Note that, no other program has exceeded 5 gold medals in the same year since the beginning of this competition in 1989. In fact, reaching 5 medals so far was an exceptional achievement.
# 14 Conclusion

## 14.1 New algorithms: Athénan components

We have proposed several new techniques for reinforcement learning state evaluation functions.

Firstly, we have generalized tree bootstrapping (tree learning) in the context of reinforcement learning without knowledge based on non-linear functions. We have shown that learning the values of the game tree instead of just learning the value of the root significantly improves learning performances.

Secondly, we have introduced the Descent algorithm which explores in the manner of Unbounded Minimax, intended to be used during the learning process. Unlike Unbounded Minimax, Descent iteratively explores the sequences of best actions *up to terminal states*. Its objective is to improve the quality of the data used during the learning phases, while keeping the advantages of Unbounded Minimax. In the context of our experiments, the use of Descent gives strongly better performances than the use of Alpha-Beta, Unbounded Minimax, or MCTS.

Thirdly, we proposed the completion technique which allows to take into account the resolution of states, notably in the context of Unbounded Minimax and Descent. Note that the impact assessment of this technique was carried out in (Cohen-Solal and Cazenave, 2025b). This technique improves performance but the gain is lower than the techniques evaluated in this article.

Fourthly, we have suggested to replace the classic gain of a game (+1/-1) by different terminal evaluation functions, called reinforcement heuristics. We have propose different general terminal evaluations, such as the depth heuristic, which takes into account the duration of games in order to favor quick wins and slow defeats. Our experiments have shown that the use of a reinforcement heuristic improves performances. Our study recommends using the score heuristic when the game has one and otherwise using the depth heuristic.

Fifth, we have proposed a new action selection distribution which does not take into account the value of states but only their order.

We then combined all these techniques within Athénan, a zero-knowledge reinforcement learning algorithm, like AlphaZero or ExIt.

## 14.2 Evaluation of Athénan

In the unpublished initial version of this article (Cohen-Solal, 2020), Athénan has not been compared to the two state-of-the-art zero-knowledge reinforcement learning algorithms: AlphaZero and ExIt. In the meantime, Athénan's comparison with AlphaZero was realized in collaboration with Tristan Cazenave in another article (Cohen-Solal and Cazenave, 2023c). In this external study, Athénan with the classic game gain as reinforcement heuristic is at least 7 times faster than AlphaZero on equal hardware. It is also at least 30 times faster using the reinforcement heuristics presented in this article. Athénan with one GPU even outperforms AlphaZero with 100 GPUs on some games.

In the new version of this paper, we have therefore added the missing experience: the comparison with ExIt. In the context of the experiments conducted in this article, Athénan performs much better than ExIt. ExIt's average performance does not even reach in 15 days the performance that Athénan obtained in one day. Note that in this study, Athénan only used the classic game gain as reinforcement heuristic. Thus, we should achieve a result 4 times higher with the advanced reinforcement heuristics proposed in this article.
We also showed that Athénan arrived, without using any knowledge<sup>11</sup>, to surpass the state-of-the-art of many games, namely Hex size 11 and size 13, Othello, and Arimaa. This contrasts with the outperformed state-of-the-art programs which use dedicated knowledge.

Moreover, Athénan achieved the state-of-the-art level at Morpion Solitaire. Note that the state-of-the-art record at Morpion Solitaire was achieved using algorithms restricted to single-player games. Conversely, this result shows that in addition to being applicable to two-player games, Athénan is also applicable to single-player games. This is all the more noteworthy since attempts to achieve state-of-the-art level at Morpion Solitaire with ExIt and AlphaZero failed.

Finally, we briefly presented Athénan's results at the Computer Olympiad, the global artificial intelligence board game competition. Athénan broke all records at this competition, tripling the record of gold medals obtained in a single year (reaching 16 gold medals), winning a total of 48 gold medals in 5 years since its first participation, and being the defending champion on 17 games.

Overall, the results show that Athénan and its components constitute particularly efficient and above all effective alternatives to other approaches based on Alpha-Beta and MCTS, in the era of reinforcement learning.

*Remark 22.* Athénan has been programmed in Python. Switching to a faster performing language should reduce the learning time by a factor between two and five and will increase the winning percentages during confrontations.

## 14.3 Perspectives

We did not evaluate the ordinal distribution in this article. We will see in a future article that this techniques improves average performance. However, its significant gain is much lower than the other techniques proposed in this article (except completion).

Work is underway on the generalization of these algorithms in the following contexts: stochastic games (Cohen-Solal and Cazenave, 2023b), multiplayer games (Cohen-Solal, 2021), and usage of a policy.

A promising research perspective is the parallelization of Unbounded Minimax and Descent when learning: Unbounded Minimax determines the next action to play and Descent determines the pairs to learn (by batching evaluations on a single GPU or using two GPUs).

Another promising perspective is to perform training using Athénan with two neural networks playing against each other. This could potentially reduce numerical problems and the risks of local optimums. To avoid losing learning speed, on the one hand, each player performs a Descent search during its opponent's turn. On the other hand, the neural networks are evaluated in parallel, on the same graphics card (or on two different ones). This approach can also be generalized to a pool of neural networks performing matches in parallel. In this context, it might be more interesting to replace the ordinal distribution with the max distribution. These approaches should speed up training and increase efficiency, but they will reduce effectiveness.

The other research perspectives include the application of our contributions to General Game Playing (at first with perfect information). A yet-to-be-determined Athénan parameterization, perhaps with the use of small neural networks, could provide interesting performance in the context of General Game Playing. A modification of Athénan that could be interesting in this context is to

<footnote n="11">11. Without using any knowledge other than the rules of the game or arising trivially from the rules of the game (namely the use of board symmetry, encoding of board edge membership in Hex, order of importance of pieces for the Arimaa reinforcement heuristic).</footnote>
perform "online" learning, i.e. instead of performing the learning phase after each match, to perform
it after each search, or even after each Descent iteration, or maybe even after each updating of game
tree nodes.

The other research perspectives also include the application and adaptation of our contributions
to the contexts of hidden information.

Finally, they include the application of our contributions to optimization problems, such that the
RNA Inverse Folding problem (Cazenave and Fournier, 2020) and the conception of new algorithms,
similarly to what AlphaZero did for matrix multiplication and sorting (Mankowitz, Michi, Zhernov,
Gelmi, Selvi, Paduraru, Leurent, Iqbal, Lespiau, Ahern, et al., 2023; Fawzi, Balog, Huang, Hubert,
Romera-Paredes, Barekatain, Novikov, R Ruiz, Schrittwieser, Swirszcz, et al., 2022).

Acknowledgments and Disclosure of Funding

This work was supported in part by the French government under management of Agence Nationale
de la Recherche as part of the "Investissements d'avenir" program, benchmark ANR19-P3IA-0001
(PRAIRIE 3IA Institute). This project was provided with computer and storage resources by
GENCI at CINES and IDRIS thanks to the grants 2020-AD010114027, 2020-AD011011772, 2020-
AD011011714, 2021-AD011011461R1, 2022-AD011011461R2, 2023-AD011011461R3, 2023-A0141011461,
and 2024-A0161011461 on the supercomputers Jean Zay and Adastra (V100 and MI2050x parti-
tions).
References

Shubhra Aich and Ian Stavness. Global sum pooling: A generalization trick for object counting with small datasets of large images. *arXiv preprint arXiv:1805.11123*, 2018.

Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In *Advances in Neural Information Processing Systems*, pages 5360–5370, 2017.

Hendrik Baier and Mark HM Winands. Mcts-minimax hybrids with state evaluations. *Journal of Artificial Intelligence Research*, 62:193–231, 2018.

Jonathan Baxter, Andrew Tridgell, and Lex Weaver. Learning to play chess using temporal differences. *Machine Learning*, 40(3):243–263, 2000.

Elwyn R Berlekamp, John H Conway, and Richard K Guy. *Winning Ways for Your Mathematical Plays, Volume 3*. AK Peters/CRC Press, 2003.

Hans Berliner. The b* tree search algorithm: A best-first proof procedure. In *Readings in Artificial Intelligence*, pages 79–87. Elsevier, 1981.

Yngvi Björnsson and T Anthony Marsland. Learning extension parameters in game-tree search. *Information Sciences*, 154(3-4):95–118, 2003.

Édouard Bonnet, Florian Jamain, and Abdallah Saffidine. On the complexity of connection games. *Theoretical Computer Science*, 644:2–28, 2016.

Cameron Browne. *Hex Strategy: Making the right connections*. AK Peters Natick, MA, 2000.

Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. *Transactions on Computational Intelligence and AI in games*, 4(1):1–43, 2012.

Michael Buro. Experiments with multi-probcut and a new high-quality evaluation function for othello. *Games in AI Research*, 34(4):77–96, 1997.

Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep blue. *Artificial Intelligence*, 134 (1-2):57–83, 2002.

Tristan Cazenave. Residual networks for computer go. *Transactions on Games*, 10(1):107–110, 2018.

Tristan Cazenave and Thomas Fournier. Monte carlo inverse folding. *arXiv preprint arXiv:2005.09961*, 2020.

Tristan Cazenave and Fabien Teytaud. Beam nested rollout policy adaptation. In *ECAI*, 2012.

Tristan Cazenave, Abdallah Saffidine, Michael John Schofield, and Michael Thielscher. Nested monte carlo search for two-player games. In *The Thirtieth AAAI Conference on Artificial Intelligence*, February 12-17, 2016, Phoenix, Arizona, USA., pages 687–693, 2016.
Tristan Cazenave, Yen-Chi Chen, Guan-Wei Chen, Shi-Yu Chen, Xian-Dong Chiu, Julien Dehos, Maria Elsa, Qucheng Gong, Hengyuan Hu, Vasil Khalidov, et al. Polygames: Improved zero learning. *ICGA Journal*, (Preprint):1–13, 2020.

Christopher Clark and Amos Storkey. Training deep convolutional neural networks to play go. In *International Conference on Machine Learning*, pages 1766–1774, 2015.

Quentin Cohen-Solal. Apprendre à jouer aux jeux à deux joueurs à information parfaite sans connaissance. 2019.

Quentin Cohen-Solal. Learning to play two-player perfect-information games without knowledge. *arXiv preprint arXiv:2008.01188*, 2020.

Quentin Cohen-Solal. Completeness of unbounded best-first game algorithms. *arXiv preprint arXiv:2109.09468*, 2021.

Quentin Cohen-Solal. Study and improvement of search algorithms in two-players perfect information games. *arXiv preprint arXiv:2505.09639*, 2025.

Quentin Cohen-Solal and Tristan Cazenave. Descent wins five gold medals at the computer olympiad. *ICGA Journal*, 43(2):132–134, 2021.

Quentin Cohen-Solal and Tristan Cazenave. Athenan wins sixteen gold medals at the computer olympiad. *ICGA Journal*, 45(3), 2023a.

Quentin Cohen-Solal and Tristan Cazenave. Learning to play stochastic two-player perfect-information games without knowledge. *arXiv preprint arXiv:2302.04318*, 2023b.

Quentin Cohen-Solal and Tristan Cazenave. Minimax strikes back. *AAMAS*, 2023c.

Quentin Cohen-Solal and Tristan Cazenave. Athénan wins 11 gold medals at the 2024 computer olympiad. *ICGA Journal*, page 13896911251315102, 2025a.

Quentin Cohen-Solal and Tristan Cazenave. On some improvements to unbounded minimax. *arXiv preprint arXiv:2505.04525*, 2025b.

Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In *Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers*, pages 72–83, 2007.

Boris Doux, Benjamin Negrevergne, and Tristan Cazenave. Deep reinforcement learning for morgion solitaire. In *Advances in Computer Games*, pages 14–26. Springer, 2021.

Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Moham-adamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. *Nature*, 610(7930):47–53, 2022.

Fédération Française d'Othello. Télécharger des programmes d'othello. URL https://www.ffothello.org/informatique/telecharger-des-programmes/. [Online; accessed 26-May-2022].
William Fink. An enhancement to the iterative, alpha-beta, minimax search procedure. *ICGA Journal*, 5(1):34–35, 1982.

Arimaa Forum. Arimaa website, 2024. URL https://arimaa.com/arimaa.

Chao Gao, Ryan B Hayward, and Martin Müller. Move prediction using deep convolutional neural networks in hex. *Transactions on Games*, 2017.

Chao Gao, Martin Müller, and Ryan Hayward. Three-head neural network architecture for monte carlo tree search. In *International Joint Conference on Artificial Intelligence*, pages 3762–3768, 2018.

Chao Gao, Kei Takada, and Ryan Hayward. Hex 2018: Mohex3hnn over deepezo. *J. Int. Comput. Games Assoc.*, 41(1):39–42, 2019.

Michael Genesereth, Nathaniel Love, and Barney Pell. General game playing: Overview of the aaai competition. *AI magazine*, 26(2):62, 2005.

Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In *The Fourteenth International Conference on Artificial Intelligence and Statistics*, pages 315–323, 2011.

Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. *Deep learning*, volume 1. MIT press Cambridge, 2016.

Richard D Greenblatt, Donald E Eastlake, and Stephen D Crocker. The greenblatt chess program. In *Computer chess compendium*, pages 56–66. Springer, 1988.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In *Conference on Computer Vision and Pattern Recognition*, pages 770–778, 2016.

Jie Hu, Li Shen, and Gang Sun. Squeeze-and-excitation networks. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 7132–7141, 2018.

Shih-Chieh Huang, Broderick Arneson, Ryan B Hayward, Martin Müller, and Jakub Pawlewicz. Mohex 2.0: a pattern-based mcts hex player. In *International Conference on Computers and Games*, pages 60–71. Springer, 2013.

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. *arXiv preprint arXiv:1412.6980*, 2014.

Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. *Science*, 220(4598):671–680, 1983.

Donald E Knuth and Ronald W Moore. An analysis of alpha-beta pruning. *Artificial Intelligence*, 6 (4):293–326, 1975.

Richard E Korf. Depth-first iterative-deepening: An optimal admissible tree search. *Artificial Intelligence*, 27(1):97–109, 1985.
Richard E Korf and David Maxwell Chickering. Best-first minimax search. *Artificial intelligence*, 84(1-2):299-337, 1996.

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In *Advances in Neural Information Processing Systems*, pages 1097-1105, 2012.

Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. *Nature*, 521(7553):436, 2015.

Paweł Liskowski, Wojciech Jaśkowski, and Krzysztof Krawiec. Learning to play othello with deep neural networks. *IEEE Transactions on Games*, 10(4):354-364, 2018.

Michael Lederman Littman. *Algorithms for sequential decision making*. PhD thesis, 1996.

Jacek Mandziuk. *Knowledge-free and learning-based methods in intelligent game playing*, volume 276. Springer, 2010.

Daniel J Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Padu-raru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, et al. Faster sorting algorithms discovered using deep reinforcement learning. *Nature*, 618(7964):257-263, 2023.

Joseph Mellor. *Decision Making Using Thompson Sampling*. PhD thesis, 2014.

Henryk Michalewski, Andrzej Nagórko, and Jakub Pawlewicz. An upper bound of 84 for morpion solitaire 5d. In *CCCG*, pages 270-278, 2016.

Ryszard S Michalski, Jaime G Carbonell, and Tom M Mitchell. *Machine learning: An artificial intelligence approach*. Springer Science & Business Media, 2013.

Ian Millington and John Funge. *Artificial intelligence for games*. CRC Press, 2009.

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Belle-mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. *Nature*, 518(7540):529, 2015.

Jan Mycielski. Games with perfect information. *Handbook of game theory with economic applications*, 1:41-70, 1992.

Andrzej Nagórko. Parallel nested rollout policy adaptation. In *2019 IEEE Conference on Games (CoG)*, pages 1-7. IEEE, 2019.

Andrew Y Ng. Feature selection, 11 vs. 12 regularization, and rotational invariance. In *The twenty-first international conference on Machine learning*, page 78. ACM, 2004.

Antonio Norelli and Alessandro Panconesi. Olivaw: Mastering othello without human knowledge, nor a penny. *IEEE Transactions on Games*, 2022.

Jakub Pawlewicz and Ryan B Hayward. Scalable parallel dfpn search. In *International Conference on Computers and Games*, pages 138-150. Springer, 2013.
É. Piette, D. J. N. J. Soemers, M. Stephenson, C. F. Sironi, M. H. M. Winands, and C. Browne. Ludii – the ludemic general game system. In G. De Giacomo, A. Catala, B. Dilkina, M. Milano, S. Barro, A. Bugarín, and J. Lang, editors, *Proceedings of the 24th European Conference on Artificial Intelligence (ECAI 2020)*, volume 325 of *Frontiers in Artificial Intelligence and Applications*, pages 411–418. IOS Press, 2020.

Stefan Reisch. Hex ist pspace-vollständig. *Acta Informatica*, 15(2):167–191, 1981.

Christopher D Rosin. Nested rollout policy adaptation for monte carlo tree search. In *Twenty-Second International Joint Conference on Artificial Intelligence*, 2011.

Jonathan Schaeffer. Conspiracy numbers. *Artificial Intelligence*, 43(1):67–84, 1990.

Nicol N Schraudolph, Peter Dayan, and Terrence J Sejnowski. Learning to evaluate go positions via temporal difference methods. In *Computational Intelligence in Games*, pages 77–98. Springer, 2001.

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. *Nature*, 529(7587):484, 2016.

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. *arXiv preprint arXiv:1712.01815*, 2017a.

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. *Nature*, 550(7676):354, 2017b.

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. *Science*, 362(6419):1140–1144, 2018.

David J Slate and Lawrence R Atkin. Chess 4.5 - the northwestern university chess program. In *Chess skill in Man and Machine*, pages 82–118. Springer, 1983.

Dennis J.N.J. Soemers, Vegard Mella, Cameron Browne, and Olivier Teytaud. Deep learning for general game playing with ludii and polygames. *arXiv preprint arXiv:2101.09562*, 2021.

Kei Takada, Hiroyuki Iizuka, and Masahito Yamamoto. Reinforcement learning for creating evaluation function using convolutional neural network in hex. In *2017 Conference on Technologies and Applications of Artificial Intelligence*, pages 196–201. IEEE, 2017.

Kei Takada, Hiroyuki Iizuka, and Masahito Yamamoto. Reinforcement learning to create value and policy functions using minimax tree search in hex. *IEEE Transactions on Games*, 2019.

Gerald Tesauro. Temporal difference learning and td-gammon. *Communications of the ACM*, 38 (3):58–68, 1995.
Yuandong Tian and Yan Zhu. Better computer go player with neural network and long-term prediction. *arXiv preprint arXiv:1511.06410*, 2015.

H Jaap Van Den Herik and Mark HM Winands. Proof-number search and its variants. In *Oppositional Concepts in Computational Intelligence*, pages 91–118. Springer, 2008.

H Jaap Van Den Herik, Jos WHM Uiterwijk, and Jack Van Rijswijck. Games solved: Now and in the future. *Artificial Intelligence*, 134(1-2):277–311, 2002.

Joel Veness, David Silver, Alan Blair, and William Uther. Bootstrapping from game tree search. In *Advances in neural information processing systems*, pages 1937–1945, 2009.

Hui Wang, Mike Preuss, Michael Emmerich, and Aske Plaat. Tackling morpion solitaire with alphazero-like ranked reward reinforcement learning. In *2020 22nd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)*, pages 149–152. IEEE, 2020.

Wikipedia contributors. Computer othello, 2022. URL https://en.wikipedia.org/wiki/Computer_Othello. [Online; accessed 26-May-2022].

David J Wu. Designing a winning arimaa program. *ICGA Journal*, 38(1):19–40, 2015.

Georgios N Yannakakis and Julian Togelius. *Artificial intelligence and games*, volume 2. Springer, 2018.

Kenny Young, Gautham Vasan, and Ryan Hayward. Neurohex: A deep q-learning hex agent. In *Computer Games*, pages 3–18. Springer, 2016.