Initial state diversification for efficient AlphaZero-style training

Abstract

AlphaZero has achieved superhuman performance in Go, chess, and shogi with a general reinforcement learning (RL) algorithm. This achievement is remarkable because AlphaZero does not rely on any training dataset of strong players. However, AlphaZero-style training requires substantial computational resources. Gumbel AlphaZero, a recently introduced more efficient version of AlphaZero, reduces the computational cost of AlphaZero training. The goal of this study is to further improve the playing strength of Gumbel AlphaZero under a limited amount of computational resources. We focus on the diversity in training games, inspired by procedural generation and domain randomization in RL studies, and propose a novel method, initial state diversification. This method diversifies the initial states of a self-play game to encourage the RL agent to understand the game in a more general manner through diverse experiences. For example, in shogi, the initial state of each self-play game is diversified by rearranging the pieces under realistic domain constraints. Experiments demonstrated that training with initial state diversification improves the playing strength of Gumbel AlphaZero in shogi, within the same computational budget for training.

Keywords

Reinforcement learning AlphaZero Gumbel AlphaZero shogi Chess960

1. Introduction

AlphaZero (Silver et al., 2018) achieved superhuman performance in Go, chess, and shogi through self-play with a general reinforcement learning (RL) algorithm. This achievement is indeed remarkable because the algorithm does not rely on any training dataset of strong players. However, AlphaZero-style training requires substantial computational resources, especially for conducting millions of self-play games. For example, the AlphaZero experiments performed by Silver et al. (2018) used more than 5000 TPUs, and the training performed by Tian et al. (2019) of Elf Open Go used 2000 GPUs for self-play of 20 million games.

Gumbel AlphaZero (Danihelka et al., 2022), an efficient successor to AlphaZero, addresses this requirement. It can reliably learn from games produced at much less computational cost. While AlphaZero typically runs Monte Carlo tree search (MCTS) with 400 or 800 simulations per move, Gumbel AlphaZero successfully learns with 2–32 simulations per move. This reduces the computational cost of self-play training. Our research goal is to further improve the playing strength of Gumbel AlphaZero within a limited amount of computational resources.

This paper focuses on a suitable method for exploring candidate moves during self-play with a smaller number of simulations per move in Gumbel AlphaZero. A sufficient exploration or diversity of experiences is widely recognized as crucial in RL studies (Sutton and Barto, 2018). To ensure the diversity of game records, the AlphaZero RL agent was programmed to select an explorative move more frequently in the first 30 moves in self-play. The agent selects explorative moves based on a probability proportional to the number of simulations associated with the move (Danihelka et al., 2022; Silver et al., 2018,2017). Intuitively, exploration with the distribution loses granularity as the number of simulations decreases, especially when the number is less than the number of legal moves.

For exploration independent of the number of simulations, we propose a novel method initial state diversification. This method carefully diversifies the initial state of each game in self-play training to encourage the RL agent to learn diverse and general tactics of the game. As a proof of concept in shogi, we introduce two schemes for stochastic rearrangement of the pieces. This approach is inspired by procedural generation (Justesen et al., 2018; Juliani et al., 2019; Cobbe et al., 2020) and domain randomization (Tobin et al., 2017) in other RL domains.

Through experiments in shogi, we demonstrate that training with initial state diversification improves the strength of agents trained by Gumbel AlphaZero. Note that improvements in the agents’ strength within the same computational budget imply improvements in the learning efficiency as well.

Specifically, our contributions are as follows:

We introduce initial state diversification, a novel method for diversifying the initial state of each game in self-play training and thereby encouraging the agent to experience various states that are useful for obtaining a more general understanding of the game. (Section 3)

For a specific instantiation of initial state diversification in shogi, we introduce RandomStart2, a simple piece rearrangement method using two random moves, and Shogi816K, a more complex piece randomization method inspired by Chess960 (also known as Fischer Random Chess) (Section 3.2). Experiments demonstrated that the combination of RandomStart2 and Shogi816K achieves the highest playing performance among our candidates (Section 4.3).

We empirically show that an agent trained using the initial state diversification method improves the playing strength of Gumbel AlphaZero within the same amount of computational budget of self-play training (Section 4.3).

2. Background

Our method of diversifying the initial state of each game is built on top of AlphaZero and Gumbel AlphaZero, so we begin by briefly introducing them. We use RL terminology in addition to terms used in the chess and shogi programming literature. We refer to the position of a game as the state and the move of a player as an action.

2.1. AlphaZero

AlphaZero (Silver et al., 2018), a model-based RL algorithm, has outperformed state-of-the-art computer programs in chess, shogi, and the game of Go. In AlphaZero training, its neural network is trained using tens of millions of self-play games. The network has 19 residual blocks (He et al., 2016) followed by a policy head and a value head comprising a policy value network. The policy head outputs logit probabilities of actions, and the logits are converted to the probability distribution of policy with softmax function. The value head outputs a scalar value as a prediction for the outcome of the game. During the self-play games, the RL agent runs many MCTS simulations (e.g., 800 in the original AlphaZero report) for each move. After a game is finished, the game record is stored in the replay buffer. Data in the replay buffer is sampled to train the neural network.

2.2. Gumbel AlphaZero

Gumbel AlphaZero (Danihelka et al., 2022) is an improved version of AlphaZero. Although both Gumbel MuZero and Gumbel AlphaZero were built on top of MuZero and AlphaZero, respectively, we focus on Gumbel AlphaZero because it was chosen for experiments on chess (Danihelka et al., 2022, Section 7.2). Gumbel AlphaZero can reliably learn from games with few MCTS simulations (even two simulations per move according to the report), whereas the original AlphaZero reportedly fails to learn with small MCTS simulation budgets. This means that Gumbel AlphaZero enables researchers to train agents with relatively few computational resources.

Gumbel AlphaZero basically follows the original AlphaZero in the sense that it also trains the policy value network through self-play. However, Gumbel AlphaZero’s move selection algorithm is redesigned to guarantee a policy improvement (i.e., a move selected by the agent after the game tree search should be better than, or as good as, a move predicted by the policy network alone even when the simulation budget is limited), which is not guaranteed by the original AlphaZero especially when the number of simulations is small. The main difference with the original AlphaZero is in the search at the root node: The stochasticity of a candidate move is governed by the Gumbel-Top-k trick for sampling moves without replacement instead of the visit count to ensure a policy improvement. To this end, Gumbel AlphaZero introduced a two-fold search process, sequential halving (Karnin et al., 2013) at the root and MCTS among the descendants, while AlphaZero solely uses MCTS with the PUCT (predictor upper confidence for trees) algorithm (Silver et al., 2016). Sequential halving is a multi-armed bandit algorithm for simple regret minimization.

These modifications enable Gumbel AlphaZero to significantly reduce the learning time, especially with limited computational resources. Using Gumbel AlphaZero enabled us to conduct experiments in shogi with relatively few computational resources.

2.3. Exploration for quality-diverse games

Intuitively, sufficient variation of self-play games is needed for successful training, which is difficult for greedy (consequently deterministic) agents. Various methods for exploring candidate moves have been used for AlphaZero and Gumbel AlphaZero self-play.

AlphaZero introduced stochasticity in which MCTS agents follow a probability distribution induced by the visit count at the root node. This is reasonable because MCTS typically assigns more simulations to identify more effective moves. AlphaZero uses a visit-count based exploration strategy, as in AlphaGo Zero (Silver et al., 2017,2018), in which actions are selected in proportion to the root visit count for the first 30 moves of each game. In addition, for further exploration, Dirichlet noise is added to the output of the policy network at the root node (Appendix B.3).

In contrast, Gumbel AlphaZero introduced stochastic move selection, which is equivalent to a softmax policy (i.e., Boltzmann policy) if tree search is omitted. The Gumbel AlphaZero RL agent iteratively narrows down the candidate moves in a root node by sequential halving. At each halving iteration, the agent drops the less promising moves, i.e., moves with scores below the median, and performs tree search to refine the score estimates of the remaining moves. Finally, the agent selects a move with the maximum score from the remaining candidates. Formally, the move with the maximum score is defined as $\begin{matrix} (1) & A^{*} = arg max_{a \in Remaining} (g (a) + logits (a) + σ (\hat{q} (a))), \end{matrix}$ where $A^{*}$ is the action to be taken next by the agent, $Remaining$ is the set of remaining actions after the final iteration, $(g \in R^{k}) \sim Gumbel (0)$ is a k-dimensional vector of Gumbel variables sampled from the standard Gumbel distribution,1

¹
In practice, we need randomly sampled Gumbel variables, each of which is obtained as $- log (- log (u))$ , where u is a value sampled from the uniform distribution $[0, 1]$ (Murphy, 2023, Section 6.3.6).

g (a)

is a-th element of g,

logits (a)

is the logit for the probability given by the policy network,

\hat{q} (a)

is an empirical estimate of Q-values obtained by the tree search (AlphaZero’s PUCT algorithm in this paper), and σ is a monotonically increasing function. For a concrete instantiation of σ, Gumbel AlphaZero uses

\begin{matrix} (2) & σ (\hat{q} (a)) = (c_{visit} + max_{b} N (b)) c_{scale} \hat{q} (a), \end{matrix}

where

N (b)

is the visit count for action b, and both

c_{visit}

and

c_{scale}

are hyperparameters. Intuitively, equations (1) and (2) mean that moves with higher

logits (a)

and

\hat{q} (a)

are more likely to be selected, σ determines the balance between

logits (a)

and

\hat{q} (a)

, and

g (a)

introduces randomness into the action selection. The term inside

arg max

on the right side of Eq. (1) is used for selection of candidate moves in the intermediate stages of sequential halving.

While these two exploration methods are completely different, the visit-count based exploration used in AlphaZero reportedly worked well when combined with Gumbel AlphaZero in 9 × 9 Go experiments (Danihelka et al., 2022, Appendix F). However, their effectiveness was not evaluated for chess variants. Our experiments demonstrated that the proposed method works well for shogi, which is one of the chess variants.

3. Initial state diversification

Our initial state diversification method produces diverse game records that are effective for RL training. The main idea is for the initial state to be sampled from a well-designed set of diverse states. This enables the agent to experience a wider set of states and to obtain a more general understanding of the game. For a concrete instantiation in shogi, we used the proposed method to rearrange the pieces to generate a set of diverse initial positions.

After first giving an overview of our method (Section 3.1), we present the specific implementation in shogi (Section 3.2).

3.1. Rationale behind initial state diversification

In chess variants including shogi, there is a single initial state of the game, as shown in Fig. 1(a), whereas card games such as poker have various initial states. Additionally, typical AlphaZero-style training is performed through play against oneself rather than against different players. We hypothesize that this combination makes self-play games in chess variants less diverse than other games with various initial states. This hypothesis is partially based on empirical observation in shogi that AlphaZero-style agents often fail to find opening strategies frequently used by human professionals. The improvements in the diversity of opening strategies can also be observed in the frequency heatmaps for their kings and rooks (Appendix C). Inspired by these backgrounds, we propose diversifying the initial states of the games.

Our method requires only small changes to AlphaZero-style self-play training as it simply diversifies the initial state at the beginning of a game. In self-play training, each game starts with an initial state uniformly sampled from a set of diverse initial states. Except for the variety of starting states, self-play games are played following the original game rules. The rest of the training procedure is the same as in (Gumbel) AlphaZero.

Fig. 1.

Initial state diversification for shogi. Highlighted squares denote rearranged pieces.

Algorithm 1 provides an overview of our proposed training procedure. The modifications due to initial state diversification are italicized.

Algorithm 1

Self-play with initial state diversification

3.2. Initial state diversification in shogi

For a concrete instantiation in shogi, we devised two diversification schemes, namely, RandomStart2 and Shogi816K (Fig. 1).

3.2.1. RandomStart2

RandomStart2 (Fig. 1(b)) provides simple and intuitive diversification. The initial state set consists of states in which one legal move is made for each player from the original initial position. In shogi, the legal moves are independent of the opponent’s move for the two initial moves. From that point, a set of 900 unique initial states can be obtained. Note that there are 30 legal moves each for the first and second moves in shogi, so there are 900 reachable states after the first two moves. The reason for using two moves instead of four or more moves is based on our observation that four or more random moves often produced unbalanced and/or urgent states incurring checks or threats (Appendix A). Compared with Shogi816K, RandomStart2 is conservative in the sense that piece locations are closer to those in the original initial state.

3.2.2. Shogi816K

Shogi816K (Fig. 1(c)) was inspired by Chess960 (also known as Fischer Random Chess), a chess variant with 960 unique initial positions (FIDE, 2023). Chess960 is an interesting variation of chess, originally invented for human players interested in fresh opening positions. Chess960 itself is not originally intended for use in machine learning.2

²
To the best of our knowledge, whether training with Chess960 helps the RL agent to improve the strength for the original chess has not been published yet, while an AlphaZero-style chess engine Leela Chess Zero (Lc0) supports training with Chess960 game records. https://lczero.org/blog/2020/05/lc0-v0.25-has-been-released/.

In contrast, we have devised Shogi816K to improve reinforcement learning. Shogi816K contains a total of 1,632,960 initial positions. We named it Shogi816K because the number of initial positions without counting the mirror-symmetric ones is 816,480. As in Chess960, Shogi816K rearranges the initial positions of pieces in a row with the following restrictions:

Pawns remain untouched.

The “black” rook and bishop are randomly placed in the 8th rank (the 8th row in Fig. 1(c)). Note that the top (bottom) row is referred to as the 1st (9th) rank in shogi, that all shogi pieces have the same color, and that the player making the first move is referred to as the “black player” and the opponent is referred to as the “white player” by convention.

The remaining black pieces (lances, knights, silver generals, gold generals, and king) are randomly placed on the 9th rank.

The white pieces (the pieces in the 1st–3rd ranks from the top in Fig. 1(c)) are arranged in a rotation-symmetric configuration compared with the black pieces (the pieces in the 7th–9th ranks).3

In addition to rotation-symmetric configuration, line-symmetric configuration is another interesting option if one wants to optimize the agent for some openings like “static rook vs ranging rook” (both the black rook and the white rook are placed on the same horizontal side). In our small preliminary experiments, line-symmetric configuration showed better playing strength for “static rook vs ranging rook” openings at the expense of sub-optimal performance for the other openings.

We introduced these restrictions to keep Shogi816K and Chess960 as similar as possible except in cases where the original game rules differ (e.g., rotation-symmetric vs mirror-symmetric). Note that in Shogi816K there is no provision for castling because shogi does not have one.

Compared with RandomStart2, the opening states produced by Shogi816K are diversified aggressively in the sense that piece locations differ greatly from the original ones. On the one hand, this difference may negatively affect the learning of opening strategies. On the other hand, it may contribute to a general understanding of middlegame and/or endgame tactics due to a wider variety of experiences. There is thus a trade-off between the diversity of initial states and the similarity to the original state.

3.3. Pre-training and fine-tuning

To utilize the benefits of these two diversification schemes, we propose combining them: pre-training with Shogi816K and fine-tuning with RandomStart2. In AlphaZero-style RL, an agent’s neural network gradually improves with the number, typically millions, of self-play games. Therefore, it is intuitive to first train the agent by using Shogi816K to give it a general understanding of the game and then by using RandomStart2 to enable it to better establish an opening strategy starting from the original state. This approach is inspired by the pre-training and fine-tuning approach in computer vision research (Krizhevsky et al., 2012).

Table 1
Six variations of Gumbel AlphaZero used in comparison experiments

Name Initial state diversification Exploration by visit count

Base – –

RandomStart2 RandomStart2 –

Shogi816K Shogi816K –

Shogi816K+RandomStart2 Shogi816K (pre-training) + RandomStart2 (fine-tuning) –

Exploration (sequential halving) – Sequential halving

Exploration (PUCT) – PUCT

Name	Initial state diversification	Exploration by visit count
Base	–	–
RandomStart2	RandomStart2	–
Shogi816K	Shogi816K	–
Shogi816K+RandomStart2	Shogi816K (pre-training) + RandomStart2 (fine-tuning)	–
Exploration (sequential halving)	–	Sequential halving
Exploration (PUCT)	–	PUCT

4. Experiments

We experimentally evaluated how the proposed diversification improves an agent’s playing strength by comparing six variations of Gumbel AlphaZero training in shogi. They consist of a baseline, the two diversification schemes, their combination (the proposed method), and two alternatives with visit-count exploration, as summarized in Table 1.

Base: Gumbel AlphaZero without diversification and without explorative actions proportional to the visit count. The agent still selects the move stochastically thanks to the Gumbel variables in Eq. (1) even without additional exploration. This is common to the following three diversification agents for all moves and two exploration agents after the first 30 moves.

Diversification (RandomStart2): Gumbel AlphaZero with initial state diversification using RandomStart2 (Section 3.2.1).

Diversification (Shogi816K): Gumbel AlphaZero with initial state diversification using Shogi816K (Section 3.2.2).

Diversification (Shogi816K+RandomStart2): Gumbel AlphaZero with initial state diversification using both Shogi816K and RandomStart2. In training, Shogi816K is used for the first 60% of self-play games. RandomStart2 is then used for the last 40%. The 60/40 ratio is based on the results of preliminary experiments.

Exploration (sequential halving): Gumbel AlphaZero with explorative actions based on visit count obtained by sequential halving. For the first 30 moves, the agent selects explorative actions in proportion to the root visit count obtained by sequential halving. For the remaining moves, it follows Gumbel AlphaZero as in the other variations. The same hyperparameters are used for sequential halving as in Gumbel AlphaZero.

Exploration (PUCT): Gumbel AlphaZero with explorative actions proportional to the PUCT visit count. For the first 30 moves, the agent selects a move in the same manner as in AlphaZero (Silver et al., 2018) or AlphaGo Zero (Silver et al., 2017). For the remaining moves, it follows Gumbel AlphaZero as in the other variations. The same hyperparameters are used for PUCT as in AlphaZero.

4.1. Training procedure

We trained each of the six agents through self-play in shogi with the Gumbel AlphaZero algorithm. Each agent was trained using 10 million self-play games. The number of simulations per move (n) is set to 64. The maximum number of moves considered at the root node (m) is 16, as in Gumbel AlphaZero. Whereas the original AlphaZero experiment used 24 million self-play games and 800 simulations per move, we used fewer games and simulations due to limited computational resources. In addition, the original AlphaZero experiment demonstrated that training using 10 million games resulted in performance close to that of the then state-of-the-art computer shogi program.

Since the training process was still time-consuming with our limited computational resources, we introduced domain-specific enhancements to the input features to speed up the training (Appendix B). With our implementation, it took about two weeks to train the six agents twice each on a maximum of 20 GPUs (Appendix F).

4.2. Evaluation procedure

We evaluated the playing strength of the agents against that of a reference player, Suisho4

⁴
Suisho5-YaneuraOu-v7.6.1. Available from https://github.com/yaneurao/YaneuraOu.

(Sugimura, 2020), with 20K search nodes per move. Suisho is a state-of-the-art shogi program that won the 2020 World Computer Shogi Online Championship (Appendix G). Suisho is publicly available with an excellent evaluation function based on an efficiently updatable neural network (NNUE) (Nasu, 2018) and runs on YaneuraOu (Isozaki, 2024) empowered by a sophisticated game tree search similar to that of Stockfish5

⁵

https://github.com/official-stockfish/Stockfish.

in chess.

The evaluation games were played under the following conditions:

The agents selected an action using sequential halving. The number of simulations per move is set to 800, following the 9 × 9 Go experiments in Gumbel AlphaZero (Danihelka et al., 2022, Section 7.1).

Diversification and exploration were disabled.

Each evaluation game is started from the opening positions randomly sampled from a game dataset consisting of games played by professional human players (The details about the dataset are described in Appendix E). For each game, one game record was sampled from the dataset, and the first 30 moves were played following the record.6

⁶

The hyperparameter “30 moves” was chosen because AlphaZero selects explorative moves for the first 30 moves of each game.

Each player’s internal book was disabled in advance. Note that it is a common practice to evaluate shogi agents with opening suites.7

⁷

Also in chess, human opening positions and TCEC (Top Chess Engine Championship) opening positions are used in the AlphaZero experiments (Silver et al., 2018, “Match conditions” section in the supplementary material).

(We have supplementary evaluation results with computer generated openings for Fairly-Stockfish in Appendix D.1, or without using shared opening suites in Appendix D.2.)

For fairness and reproducibility, parallel MCTS search (e.g., parallel MCTS with virtual loss (Segal, 2011) used in AlphaGo (Silver et al., 2016)) was disabled in the agent. The reference opponent also did not use parallel search.

4.3. Experimental results

4.3.1. Effect of training on Elo rating

We used the Elo rating system, a method for calculating the relative skill levels of players in zero-sum games, as the performance metric. The improvement in playing strength with the number of training games for the six agents is plotted in Fig. 2. The playing strength (y-axis) is the Elo rating relative to the reference player.8

⁸
The winning probability corresponding to the Elo rating difference is given by $P = \frac{1}{1 + 10^{- EloDifference / 400}}$ (Wikipedia, 2024). Draws were not used to estimate the Elo rating.

For instance, a 100 Elo rating difference means that the player with the higher rating has a 64% chance of winning against the player with the lower one. In the experiments, the Elo rating was calibrated so that Suisho (the reference player) with 20K search nodes per move had a rating of

\pm 0

. The number of Suisho’s search nodes is set to 20K in order to adjust Suisho’s strength roughly to the same level of six agents.9

⁹

We followed the configuration in Gumbel AlphaZero’s experiments for the 9 × 9 Go (Danihelka et al., 2022, Section 7.1), where agents used 800 simulations per move and the reference player, Pachi, used 10K simulations.

The rating of the agent was estimated on the basis of 2000 evaluation games against the reference player for every one million self-play games during training. The shading in Fig. 2 denotes the standard errors from two independent training runs with different random seeds.

As the blue curve indicates, the proposed method (Shogi816K+RandomStart2) achieved the highest average performance among the ablated agents (Shogi816K and RandomStart2) and others (Exploration (PUCT), Exploration (Sequential halving), Base) after the same 10 million training games (Fig. 2). It performed better than Shogi816K alone (more aggressive diversification) and RandomStart2 alone (more conservative diversification). Note that the ratings generally improved more rapidly immediately after the six millionth game, when the diversification method was switched from Shogi816K to RandomStart2. This indicates that the instance implementation inspired by the concept of pre-training and fine-tuning works well in shogi. It is shown that the proposed method is an efficient training method in the sense that the method improves the playing strength within the same computational budget.

Fig. 2.

Relative Elo rating for shogi against number of self-play training games. Relative Elo rating is computed so that the reference player (Suisho with 20K search nodes per move) has a rating of $\pm 0$ (black horizontal line). All the six agents use $n = 800$ simulations per move in evaluation. Shading denotes standard errors from two independent training runs with different random seeds. The proposed method (Shogi816K+RandomStart2) (blue) performed the best after the same 10 million training games.

None of the other five agents reached the performance of the proposed method. Among four agents trained with a single diversification or exploration method, RandomStart2 performed as well as or better than Exploration (PUCT), in which the agent took explorative actions proportional to the PUCT visit count. This demonstrates the effectiveness of initial state diversification. Both RandomStart2 and Shogi816K+RandomStart2 did not use explorative actions proportional to the visit count. This suggests that initial state diversification can be used as an alternative to explorative actions.

Moreover, exploration with sequential halving and visit count did not work well, while exploration with PUCT and visit count improved agent performance compared with the performance of the base agent to some extent. We hypothesize that this is because sequential halving gives almost equal visit counts to both the best move and the second-best move. This means the best move and the second-best move would be selected with almost equal probabilities. This can degrade the accuracy of the game outcome estimation, especially in states with only one effective move (e.g., recapturing major pieces).

4.3.2. Win rate for various shogi openings

We evaluate the playing strength in various opening strategies. It is important for shogi engines to be robust enough to play various shogi opening strategies well. If the engine has a weakness in a certain opening, the strong opponents often try to attack the weakness. In addition, since most human users of shogi engines are interested in various openings, it is preferable for the engine to be able to provide analyses with consistent quality.

We evaluated playing performance separately for nine opening strategies popular among human players. Figure 3 plots the win rates against the reference opponent for the nine strategies after training using 10 million self-play games. The agents were evaluated through 2000 games against the reference opponent for each opening strategy. The nine openings are the nine most frequent strategies in the dataset (Appendix E), each of which appeared more than 2000 times in the records. The openings from (1) to (4) are categorized as “static rook” and the openings from (5) to (9) are categorized as “ranging rook.”

Overall, Fig. 3 demonstrates that the proposed method (diversification with Shogi816K+RandomStart2) (blue) achieved the highest performance for all nine openings among the six agents. This indicates that the proposed method improves the robustness of agents in the sense that the proposed method does not have major weakness for all nine opening strategies.

Fig. 3.

Win rate against reference player for nine shogi openings. Error bars denote standard errors from two independent training runs with different random seeds. The proposed method (diversification with Shogi816K+RandomStart2) (blue) consistently performed the best in all the nine opening strategies.

In more detail, Shogi816K showed relatively good performance for (7) third file rook and (9) double ranging rook, both of which are categorized as “ranging rook” openings (a strategy of moving the rook to the left (for the black player) or to the right (for the white player) in the openings). In contrast, RandomStart2 performed relatively well for (1) fortress, (2) double wing attack, and (4) bishop exchange, all of which are categorized as “static rook” openings (a strategy of placing the rook on the starting square). Shogi816K+RandomStart2 benefited from the combination of pre-training with Shogi816K and fine-tuning with RandomStart2.

In addition, Fig. 3 demonstrates that performance against the reference opponent depended on the opening strategy. For example, all the agents tended to achieve higher win rates (approximately 70–85%) for (2) double wing attack opening and lower win rates (approximately 50–70%) for (7) third file rook opening. This indicates that some openings may be more difficult to learn than others, suggesting that there is room for further improvement in the diversification and exploration algorithms.

5. Related work

5.1. Accelerating AlphaZero training

Many studies have focused on accelerating the self-play training of AlphaZero. Promising ideas have been proposed, including improving the neural network architecture, enhancing the MCTS, using a variable MCTS budget, and setting learning targets. Some of the improvements are introduced below.

We share the research goals of these studies, although the approach differs. We expect that some studies may work well in combination with our method to yield further improved agents, depending on the games or the detailed conditions.

Neural network architecture: While vanilla AlphaZero uses residual blocks (He et al., 2016) for its trunk in the policy and value network, improvements in network architectures have been proposed. In KataGo (Wu, 2020), a state-of-the-art Go program, global pooling layers were added to the network to take into account global context information. In Gumbel AlphaZero (Danihelka et al., 2022), a bottleneck residual block architecture and broadcasting layers were introduced, which accelerated the network’s inference speed in Go experiments. We adopted these improvements with a few adjustments in our experiments. Gao et al. (2018) used a three-head neural network for Hex, where the network has policy, state value, and action value heads.

Monte Carlo Tree Search: MCTS plays an important role in AlphaZero training (Grill et al., 2020). Grill et al. (2020) showed that AlphaZero’s search heuristics are an approximation to the solution of a specific regularized policy optimization problem, and proposed a variant of AlphaZero that later inspired Gumbel AlphaZero. Previous studies have attempted to enhance MCTS to accelerate AlphaZero training. AlphaZero’s MCTS is reportedly improved with MCTS Solver (Winands et al., 2008; Chen et al., 2018), checkmate solver (Nakayashiki and Kaneko, 2018), and Monte Carlo Graph Search (Czech et al., 2021).

Variable MCTS budget: In AlphaZero training, self-play is the most time-consuming process because it requires many simulations within the MCTS. To reduce the average number of simulations, Wu (2020) proposed randomly varying the number of simulations and using both fast searches with fewer simulations and full searches with more simulations. Fast searches are used for most positions while only positions with full searches are recorded for training. This reportedly improves the training of the value head because more games are played with a fixed amount of computational resources.

Learning targets: Auxiliary tasks can help the RL agent to learn more efficiently and robustly (Sutton and Barto, 2018, Chapter 17). Such applications to AlphaZero include using an auxiliary policy target to predict opponent moves (Wu, 2020), path consistency (Zhao et al., 2022), and Q-values inside the game tree (Norelli and Panconesi, 2023).

5.2. Diversity of data in RL

The diversification in initial states with the proposed method can be interpreted as domain randomization or procedural generation in RL or as data augmentation of initial states. Our method was inspired by the success of studies in these areas.

Data augmentation in pixel-based RL: Data augmentation, such as random cropping and random flipping of image data, is a well-known technique in computer vision. For example, AlexNet (Krizhevsky et al., 2012) uses data augmentation for the ImageNet image classification task to improve the model accuracy with limited labeled data. Laskin et al. (2020) applied data augmentation to pixel-based RL in which the agents are trained with randomly augmented visual observations. This contributes to data efficiency and generalization to unseen environments without modifying the underlying RL algorithm. While our method does not crop or flip states, there is a similarity in using artificially crafted data.

Procedural generation in video games: Procedural content generation is known as the algorithmic creation of game content with limited or indirect user input (Shaker et al., 2016). Recent RL studies have proposed using procedurally generated video game environments to evaluate sample efficiency and generalization. Such environments include ProcGen (Cobbe et al., 2020) and Obstacle Tower (Juliani et al., 2019). In these environments, each level consists of randomly generated content such as maps, items, and characters. This diversity prevents agents from overfitting to a fixed environment and helps them learn robust policies. It is reported that generalization performance across variations of environments can be improved with less data by manipulating the difficulty of the levels in response to the performance of the agent (Justesen et al., 2018). Similar to the procedural generation in video games, our proposed method procedurally generates initial positions in shogi and this can help the agent learn the various shogi strategies and improves average performance over various opening strategies.

Domain randomization in robotics: Learning in a simulator and transferring the knowledge to the real world is an effective manner in training robotics. However, there is a gap between a physics simulator and the real world. A simulator often suffers from unmodeled physical effects and low-fidelity sensors. To address this “reality gap,” Tobin et al. (2017) applied domain randomization to robot control in diversified environments with different lighting conditions, object positions, textures, etc.

6. Limitations and future work

The concept of initial state diversification should be useful as well for training agents for other board games. However, only the initial states are diversified, so the proposed method is effective only for domains that need diversification, i.e., those having a limited diversity in initial states or opening variations. Chess variants including shogi are such domains because there is a single and fixed initial state, and the set of legal moves for each state is a very limited subset of all possible moves among all states. In contrast, while Go also has a single fixed initial state (an empty board), the legal moves are much less constrained. Moreover, the initial states of most card games are already diversified with randomly dealt cards.

This paper followed AlphaZero in that our method is free from strong players’ resources such as game records or opening suites. This advantage is important to discuss the applications to other domains. For example, one can consider a similar method of Shogi816K for shogi variants, e.g., minishogi, while there are domains apparently inconsistent with our method such as Go. However, in terms of purely making shogi engines stronger, making use of a dataset from the strong players may become another option. For example, training from the opening positions generated by the strong computer players is an interesting choice. In addition, training from the opening positions that are sampled from the professional players is another interesting configuration.

The design of Shogi816K incorporates domain knowledge for use in rearranging the pieces to keep the resulting states balanced between the two players. Considering these limitations, we are working to devise a more general strategy that can be more easily exported to other games.

7. Conclusion

We proposed initial state diversification to improve the training of AlphaZero-style agents. The proposed method is based on some properties of shogi, but is still free from strong players’ game records. We demonstrated that initial state diversification improves the efficiency of self-play training in the sense that it improves the playing strength of the agent within the same computational budget. Moreover, experiments showed that initial state diversification improves the robustness of the agent in terms of being able to play well given a variety of opening positions in shogi.

Initial state diversification is an effective alternative to explorative actions. Our experiments demonstrated that agents trained with initial state diversification did not require explorative actions proportional to the visit count. Our approach should thus be particularly valuable when training with a small number of simulations per move.

Footnotes

Statistics on RandomStart2 and Shogi816K

To see how balanced the diversified states are, we empirically evaluated sampled states for three methods; RandomStart2, RandomStart4 (two random moves for each player), and Shogi816K. Figure 4 illustrates the first player’s advantage for the three sets of initial states. The horizontal axis is the first player’s advantage as evaluated by reference to Suisho (Sugimura, 2020) with 20K search nodes and is shown in centipawn scale. To keep the sample size identical, the distribution plots for RandomStart4 and Shogi816K were obtained from 900 random samples for each while that for RandomStart2 was obtained from all 900 states. We can see that the states are more concentrated near the peak for Shogi816K and are more widely distributed for the other two methods. Note that the mean value is slightly positive for all sets. This is consistent with our empirical property in shogi.

Table 2 shows the statistics for these three sets of initial states. The standard deviation of the first mover advantage for four random moves (219.9) is almost twice that for RandomStart2 (128.5). This is because the initial states obtained from four random moves often start with urgent situations such as checks to the king or threats to major pieces. Considering these results, we decided to use RandomStart2 instead of four or more random moves in our experiments.

In summary, Shogi816K had the smallest standard deviation and the largest number of available initial states among the alternatives. This means that Shogi816K has desirable properties, includes few states that are too advantageous or disadvantageous for one player or the other.

Experimental details

Frequency heatmaps of kings and rooks during self-play training

To provide an intuitive understanding about the variation in opening strategies (by each method), we visualize how the agents play shogi in self-play training. In this section, we focus on two important types of pieces in shogi: kings and rooks. We observe how these pieces are moved by the agents in order to evaluate the diversity of the self-play game records.

Figure 6 and 7 are the heatmaps of the kings and rooks during self-play training. Each heatmap represents the 9 × 9 squares for the shogi board. The color of each square shows the frequency of the kings or rooks placed on that square just after the 30th move of each game. We focus on the kings and rooks because these pieces are important. Kings are the most valuable pieces and are closely related to opening strategies. Rooks are the strongest attackers in shogi and play a key role in the offense. To visualize the diversity of opening games, we have collected the positions just after the 30th move for each game. Since the original AlphaZero selects explorative moves in the first 30 moves of each game, the positions just after the 30th move should represent the diversity of openings during training.

Figure 6 shows the heatmaps of the kings for both sides at 1, 5, and 10 million training games. Each row represents the agent, and each column represents the progress of self-play training. At the bottom right of the figure, we added the heatmap of the kings for human professionals (data collected from the dataset in Appendix E) for comparison. We can see that the king location in Base and Exploration (PUCT) is limited in terms of the king positions; the kings tend to go to the same square (i.e., the upper left neighbor from the initial placement) for almost all self-play games, especially after training of 10 million games. Exploration (Sequential halving) has a wider coverage of king squares, although the frequencies of the kings are concentrated around the original king square. In contrast, Shogi816K has the widest coverage of king squares among the six agents. The distribution of king frequencies for Shogi816K is almost evenly distributed from the second to the eighth file. Like Shogi816K, the proposed method (Shogi816K+RandomStart2) has diverse king distributions at 1M and 5M training games. After the proposed method switched from Shogi816K to RandomStart2 at 6M training games, both the proposed method and RandomStart2 show similar distributions at 10M games. While there is little difference between the proposed method and RandomStart2 at 10M games, they both are similar to the heatmap of professional players. Observing these heatmaps, the agents without initial state diversification prefer limited opening strategies with respect to the arrangement of the kings.

Figure 7 shows the same heatmaps of the rooks. Figure 7 demonstrates that the Base agent (no diversification and exploration) almost always used the rooks at the initial placement, especially as the training progressed. The Exploration (PUCT) agent found vertical rook movements, although it tended to stop using rooks horizontally. In contrast, the other methods, including the proposed method, move the rooks in both horizontal and vertical directions. In shogi, moving the rooks horizontally is a famous category of opening strategy called “ranging rook”. This difference would be one of the reasons why the proposed method performs better in the “ranging rook” category of openings than the Exploration (PUCT) and Base.

In addition, we plot the entropy along with the training progress for the kings (Fig. 8a) and rooks (Fig. 8b). The y-axis shows the entropy of the empirical probability distribution of the pieces after the 30th move for each game. The higher the entropy, the more diverse the piece locations. The entropy observed from the human professional dataset is shown as a horizontal line (pink) for comparison. These figures demonstrate that Base has the lowest entropy among the six candidates, which is consistent with the previous heatmaps. The entropy of Exploration (PUCT) gradually decreases as the training progresses. This would be one of the reasons for the saturation in the playing performance. In contrast, Shogi816K has the highest entropy, which is higher than that of human professionals, throughout the training. The proposed method (Shogi816K+RandomStart2), RandomStart2, and Exploration (sequential halving) maintain an entropy similar to that of human professionals. However, Exploration (sequential halving) is significantly weaker than the other two agents in Fig. 2. Therefore, we need to emphasize that these entropies give us an interesting intuition, but the entropy itself is not suitable for the objective function to be maximized in training.

Role of opening suites for engine evaluation

In this section, we examine the role of opening suites for engine evaluation in shogi. First, we conducted an additional evaluation of our six agents with computer generated opening suites instead of human opening suites (Appendix D.1). Second, we evaluate the agents without opening suites (Appendix D.2).

Data availability

We used a game dataset mostly composed of professional human players’ games15

¹⁵

Currently available on the Internet Archive. https://web.archive.org/web/20190330074233/http://www.geocities.jp/shogi_depot/2chkifu.zip.

to evaluate agent performance. There were also a few computer game records in the dataset, but they accounted for less than 1% of all games. We first chose 53,663 games out of the 62,627 games on the basis of two criteria; the game length was at least 40 moves, and there was a label for the opening strategy. Then we chose nine opening strategies for which there were more than 2,000 game records.

For the training, we did not use any dataset. As in Gumbel AlphaZero, our method is free from any dataset in the training of agents.

Computational resources

We used a maximum of 20 GPUs as listed below in the experiments. A training run took about 1–2 days depending on the available GPUs.

In each training run, one GPU was used to optimize the network parameters with PyTorch, and a subset of the other GPUs generated self-playing games in parallel. Each self-play worker asynchronously generated 20,000 games and fetched the latest network parameters before generating the next set of games.

1 x GeForce RTX 4090

2 x GeForce RTX 4070 Ti

4 x GeForce RTX 3090

2 x GeForce RTX 3080 Ti

12 x GeForce RTX 2080 Ti

Recent strong computer shogi programs

The most famous computer shogi competition is the annual World Computer Shogi Championship,16

¹⁶

http://www2.computer-shogi.org/index_e.html.

which has been held since 1990. In the 2024 championship,17

¹⁷

http://www2.computer-shogi.org/wcsc34/index_e.html.

each program is initially allowed 15 minutes, plus five seconds for each of its turns. For evaluation functions in shogi, deep neural networks (Silver et al., 2018) running on GPUs and efficiently updatable neural network (NNUE) (Nasu, 2018) running on CPUs are two major streams in the recent championships. While the former family won the 2022 and 2023 championships, the latter family won the 2020, 2021, and 2024 championships.

We used Suisho (Sugimura, 2020) as a reference player for all the evaluation experiments. Suisho is one of the state-of-the-art computer shogi programs and won the 2020 World Computer Shogi Online Championship. Suisho has an excellent evaluation function based on an efficiently updatable neural network (NNUE) (Nasu, 2018) and runs on YaneuraOu (Isozaki, 2024) empowered by an alpha-beta search. Suisho is an open source software and is available online.18

¹⁸

Available from https://github.com/yaneurao/YaneuraOu.

In 2024, another engine based on NNUE evaluation function won the 2024 championship, while this version of the engine is not open source.

Dlshogi (Yamaoka, 2024) is a strong shogi program with deep neural networks, which won the 2022 and 2023 World Computer Shogi Championships. Dlshogi has a larger neural network with 30 residual blocks and 384 channels than that of the original AlphaZero with 19 blocks and 256 channels. In addition, various enhancements are adopted in dlshogi (e.g., the network is trained not only with self-play games, but also with the games against the other strong engines). We did not use dlshogi as a reference player in this paper because the latest version of dlshogi is only available on the commercial online service.19

¹⁹

https://kishin-analytics.heroz.jp/lp/. (In Japanese).

Shogi engine developed with initial state diversification

The first author of this paper successfully combined the proposed method with some of the other improvements to develop a strong shogi engine named Gikou (Demura, 2024). Gikou won the 5th place among 45 participants in the 2024 World Computer Shogi Championship.20

²⁰

http://www2.computer-shogi.org/wcsc34/ (in Japanese).

In the 2024 championship, Gikou won the second best position among the agents with deep neural networks; only dlshogi (Yamaoka, 2024) won the better position (the 2nd place) among the agents with deep neural networks in the championship. This version of Gikou adopted an evaluation function trained by the proposed method as well as other enhancements, including an improved network architecture, a checkmate solver, etc. Since this championship version has a larger neural network and is trained by more self-play games than the version in this paper, we do not have enough computational resources to perform the detailed controlled experiments for the championship version.

References

Chen, Y.-C., Chen, C.-H. & Lin, S.-S. (2018). Exact-win strategy for overcoming AlphaZero. In Proceedings of the 2018 International Conference on Computational Intelligence and Intelligent Systems (pp. 26–31). New York, NY, USA: Association for Computing Machinery. doi:10.1145/3293475.3293486.

Cobbe, K., Hesse, C., Hilton, J. & Schulman, J. (2020). Leveraging procedural generation to benchmark reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning (Vol. 119, pp. 2048–2056). PMLR.

Czech, J., Korus, P. & Kersting, K. (2021). Improving AlphaZero using Monte-Carlo graph search. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 31, pp. 103–111).

Danihelka, I., Guez, A., Schrittwieser, J. & Silver, D. (2022). Policy improvement by planning with Gumbel. In International Conference on Learning Representations. https://openreview.net/forum?id=bERaNdoegnO .

Demura, Y. (2024). Gikou appeal document. (In Japanese). https://www.apply.computer-shogi.org/wcsc34/appeal/Gikou/gikou_appeal_detail.pdf.

FIDE (2023). FIDE Handbook/E. Miscellaneous/01. Laws of Chess. https://handbook.fide.com/chapter/E012023 .

Gao, C., Müller, M. & Hayward, R. (2018). Three-head neural network architecture for Monte Carlo tree search. In Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI-18 (pp. 3762–3768). Stockholm, Sweden: AAAI Press.

Grill, J.-B., Altché, F., Tang, Y., Hubert, T., Valko, M., Antonoglou, I. & Munos, R. (2020). Monte-Carlo tree search as regularized policy optimization. In Proceedings of the 37th International Conference on Machine Learning (pp. 3769–3778). PMLR.

Grimbergen, R. (2007). Using bitboards for move generation in Shogi. ICGA Journal, 30(1), 25–34. doi:10.3233/ICG-2007-30103.

10.

He, K., Zhang, X., Ren, S. & Sun, J. (2016). Identity mappings in deep residual networks. In Proceedings, Part IV, Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016 (Vol. 14, pp. 630–645). Springer.

11.

Isozaki, M. (2024). YaneuraOu. https://github.com/yaneurao/YaneuraOu.

12.

Juliani, A., Khalifa, A., Berges, V.-P., Harper, J., Teng, E., Henry, H., Crespi, A., Togelius, J. & Lange, D. (2019). Obstacle tower: A generalization challenge in vision, control, and planning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence. IJCAI-19 (pp. 2684–2691). China: Macao. AAAI Press.

13.

Justesen, N., Rodriguez Torrado, R., Bontrager, P., Khalifa, A., Togelius, J. & Risi, S. (2018). Illuminating Generalization in Deep Reinforcement Learning through Procedural Level Generation. In NeurIPS Workshop on Deep Reinforcement Learning.

14.

Kaneko, T., Tanaka, T., Yamaguchi, K. & Kawai, S. (2005). Df-pn with fixed-depth search at frontier nodes. In 10th Game Programming Workshop, Kanagawa, Japan (pp. 1–8). (In Japanese).

15.

Karnin, Z., Koren, T. & Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning (Vol. 28, pp. 1238–1246). PMLR.

16.

Kingma, D.P. & Ba, J. (2015). Adam: A method for stochastic optimization. In International Conference on Learning Representations. https://arxiv.org/abs/1412.6980 .

17.

Krizhevsky, A., Sutskever, I. & Hinton, G.E. (2012). ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems (Vol. 25). Curran Associates, Inc.

18.

Laskin, M., Lee, K., Stooke, A., Pinto, L., Abbeel, P. & Srinivas, A. (2020). Reinforcement learning with augmented data. In In Advances in Neural Information Processing Systems (Vol. 33, pp. 19884–19895). Curran Associates, Inc.

19.

Loshchilov, I. & Hutter, F. (2019). Decoupled weight decay regularization. In International Conference on Learning Representations. https://openreview.net/forum?id=Bkg6RiCqY7 .

20.

Murphy, K.P. (2023). Probabilistic Machine Learning: Advanced Topics. MIT Press. http://probml.github.io/book2 .

21.

Nakayashiki, T. & Kaneko, T. (2018). Learning of evaluation functions via self-play enhanced by checkmate search. In 2018 Conference on Technologies and Applications of Artificial Intelligence (pp. 126–131).

22.

Nasu, Y. (2018). Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi. The 28th World Computer Shogi Championship Appeal Document. (In Japanese), https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf.

23.

Norelli, A. & Panconesi, A. (2023). Olivaw: Mastering othello without human knowledge, nor a fortune. IEEE Transactions on Games, 15(2), 285–291. doi:10.1109/TG.2022.3157345.

24.

Schrittwieser, J., Hubert, T., Mandhane, A., Barekatain, M., Antonoglou, I. & Silver, D. (2021). Online and offline reinforcement learning by planning with a learned model. In In Advances in Neural Information Processing Systems (Vol. 34, pp. 27580–27591). Curran Associates, Inc.

25.

Segal, R.B. (2011). On the scalability of parallel UCT. In

H.J.

van den Herik ,

Iida and

Plaat (Eds.), Computers and Games. Lecture Notes in Computer Science (Vol. 6515, pp. 36–47). Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-17928-0_4.

26.

Shaker, N., Togelius, J. & Nelson, M.J. (2016). Procedural Content Generation in Games. Computational Synthesis and Creative Systems. Springer.

27.

Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T. & Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484–489. doi:10.1038/nature16961.

28.

Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K. & Hassabis, D. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419), 1140–1144. doi:10.1126/science.aar6404.

29.

Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T. & Hassabis, D. (2017). Mastering the game of Go without human knowledge. Nature, 550(7676), 354–359. doi:10.1038/nature24270.

30.

Sugimura, T. (2020). Suisho appeal document. The 30th World Computer Shogi Championship Appeal Document. (In Japanese), https://www.apply.computer-shogi.org/wcsc30/appeal/Suisho/WCSC30_appeal.pdf.

31.

Sutton, R.S. & Barto, A.G. (2018). Reinforcement Learning: An Introduction. MIT Press.

32.

Tian, Y., Ma, J., Gong, Q., Sengupta, S., Chen, Z., Pinkerton, J. & Zitnick, L. (2019). ELF OpenGo: An analysis and open reimplementation of AlphaZero. In Proceedings of the 36th International Conference on Machine Learning (Vol. 97, pp. 6244–6253). PMLR.

33.

Tobin, J., Fong, R., Ray, A., Schneider, J., Zaremba, W. & Abbeel, P. (2017). Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 23–30).

34.

Wikipedia (2024). Elo rating system. https://en.wikipedia.org/wiki/Elo_rating_system.

35.

Winands, M.H.M., Björnsson, Y. & Saito, J.-T. (2008). Monte-Carlo tree search solver. In

H.J.

van den Herik ,

Xu ,

Ma and

M.H.M.

Winands (Eds.), Computers and Games. Lecture Notes in Computer Science (Vol. 5131, pp. 25–36). Berlin, Heidelberg: Springer. doi:10.1007/978-3-540-87608-3_3.

36.

Wu, D.J. (2020). Accelerating Self-Play Learning in Go. arXiv preprint. arXiv:1902.10565.

37.

Yamaoka, T. (2024). dlshogi. https://github.com/TadaoYamaoka/DeepLearningShogi.

38.

Zhao, D., Tu, S. & Xu, L. (2022). Efficient learning for AlphaZero via path consistency. In Proceedings of the 39th International Conference on Machine Learning (Vol. 162, pp. 26971–26981). PMLR.

Initial state diversification for efficient AlphaZero-style training

Abstract

Keywords

1. Introduction

2. Background

2.1. AlphaZero

2.2. Gumbel AlphaZero

2.3. Exploration for quality-diverse games

1 In practice, we need randomly sampled Gumbel variables, each of which is obtained as − log ( − log ( u ) ) , where u is a value sampled from the uniform distribution [ 0 , 1 ] (Murphy, 2023, Section 6.3.6).

3.1. Rationale behind initial state diversification

3.2.1. RandomStart2

3.2.2. Shogi816K

4.1. Training procedure

4.2. Evaluation procedure

4 Suisho5-YaneuraOu-v7.6.1. Available from https://github.com/yaneurao/YaneuraOu.

4.3.1. Effect of training on Elo rating

8 The winning probability corresponding to the Elo rating difference is given by P = 1 1 + 10 − EloDifference / 400 (Wikipedia, 2024). Draws were not used to estimate the Elo rating.

5.1. Accelerating AlphaZero training

5.2. Diversity of data in RL

6. Limitations and future work

7. Conclusion

Footnotes

Statistics on RandomStart2 and Shogi816K

Experimental details

Frequency heatmaps of kings and rooks during self-play training

Role of opening suites for engine evaluation

Data availability

Computational resources

Recent strong computer shogi programs

Shogi engine developed with initial state diversification

References

¹
In practice, we need randomly sampled Gumbel variables, each of which is obtained as $- log (- log (u))$ , where u is a value sampled from the uniform distribution $[0, 1]$ (Murphy, 2023, Section 6.3.6).

⁴
Suisho5-YaneuraOu-v7.6.1. Available from https://github.com/yaneurao/YaneuraOu.

⁸
The winning probability corresponding to the Elo rating difference is given by $P = \frac{1}{1 + 10^{- EloDifference / 400}}$ (Wikipedia, 2024). Draws were not used to estimate the Elo rating.