Playing Nondeterministic Games through Planning with a Learned Model
Authors: Thomas Willkens
Jordan Pollack
Venue:  (2021)
Keywords: reinforcement learning
alphazero
muzero
mcts
planning
search

Abstract: The MuZero algorithm is known for achieving high-level performance on traditional zero-sum two-player games of perfect information such as chess, Go, and shogi, as well as visual, non-zero sum, single-player environments such as the Atari suite. Despite lacking a perfect simulator and employing a learned model of environmental dynamics,  MuZero produces game-playing agents comparable to its predecessor AlphaZero. However, the current implementation of MuZero is restricted only to deterministic environments. This paper presents Nondeterministic MuZero (NDMZ), an extension of MuZero for nondeterministic, two-player, zero-sum games of perfect information. Borrowing from Nondeterministic Monte Carlo Tree Search and the theory of extensive-form games, NDMZ formalizes chance as a player in the game and incorporates it into the MuZero network architecture and tree search. Experiments show that NDMZ is capable of learning effective strategies and an accurate model of the game.

Under review as a conference paper at ICLR 2021
PLAYING NONDETERMINISTIC GAMES
THROUGH
PLANNING WITH A LEARNED MODEL
Anonymous authors Paper under double-blind review
ABSTRACT
The MuZero algorithm is known for achieving high-level performance on tradi- tional zero-sum two-player games of perfect information such chess, Go, and shogi, as well as visual, non-zero sum, single-player environments such as the Atari suite. Despite lacking perfect simulator and employing learned model of environmental dynamics, MuZero produces game-playing agents comparable to its predecessor, AlphaZero. However, the current implementation of MuZero is restricted only to deterministic environments. This paper presents Nondetermin- istic MuZero (NDMZ), an extension of MuZero for nondeterministic, two-player, zero-sum games of perfect information. Borrowing from Nondeterministic Monte Carlo Tree Search and the theory of extensive-fome games, NDMZ formalizes chance as player in the game and incorporates the chance player into the MuZero network architecture and tree search. Experiments show that NDMZ is capable learning effective strategies and accurate model of the game.
INTRODUCTION
While the AlphaZero algorithm achieved superhuman performance in a variety of challenging do- mains, it relies upon a perfect simulation of the environment dynamics perform precision plan- ning. MuZero, the newest member of the AlphaZero family, combines the advantages of planning with a learned model of its environment, allowing it tackle problems such as the Atari suite without the advantage of simulator. This paper presents Nondeterministic MuZero (NDMZ), an extension of MuZero to stochastic, two-player, zero-sum games of perfect information. formalize the element of chance as player in the game, determine policy for the chance player via interaction with the environment, and augment the tree search to allow for chance actions.
it, we
As with MuZero, NDMZ is trained end-to-end in terms of policy and value. However, NDMZ aims to learn two additional quantities: the player identity policy and the chance player policy. With the change the MuZero architecture allow agents determine
assumption of perfect information, whose turn it to move and when a chance action should occur. The agent learns the fixed distri- bution of chance actions for any given state, allowing model the effects of chance in the larger context of environmental dynamics. Finally, we introduce new node classes to the Monte Carlo Tree Search, allowing the search to accommodate chance in flexible manner. Our experiments using Nannon, a simplified variant of backgammon, show that NDMZ approaches AlphaZero in terms of performance and attains a high degree of dynamics accuracy.
PRIOR WORK
2.1
EARLY TREE SEARCH
The classic search algorithm for perfect information games with chance events is expectiminimax, which augments the well-known minimax algorithm with the addition of of chance nodes (Mitchie) 1966 Maschler et al.] 2013). Chance nodes assume the expected value of random event taking place, taking a weighted average of each of its children, based on the probability of reaching the child, rather than the max min. Chance nodes, min nodes, and max nodes are interleaved de- pending on the game being played. The *-minimxx algorithm extends the alpha-beta tree pruning strategy games with chance nodes (Ballard 1983. Knuth & Moore 1975.

---

Under review as a conference paper at ICLR 2021
2.2 MODEL-FREE REINFORCEMENT LEARNING
A notable success of model-free reinforcement learning for nondeterninistic games is TD-Gammon, an adaptation of [Sutton & Barto (2018)'s TD-Lambda algorithm to the domain of backgammon [Tesauro 1995). Using temporal difference learning, a network is trained to produce the estimated value of a state. When is time to make move, each legal move is used to produce successor state, and the move with the maximum expected outcome is chosen. Agents produced by TD-Gammon were able to compete with world-champion backgammon players, although it was argued that the stochastic nature of backgammon assisted the learning process (Pollack & Blair 1996).
2.3 MONTE CARLO TREE SEARCH
The Monte Carlo Tree Search (MCTS) algorithm attracted interest after its success with challenging deterministic problems such as the game Go. and it has been adapted for stochastic games in an number of different ways (Coulom 2006, Browne et al. (0022) version of MCTS by Van Lishout al. (2077) called called McGammon (Monte Carlo Backgammon) was capable of finding expert moves in a simplified backgammon game, At a chance node, the next move always chosen ran- domly; at choice nodes, the Upper Confidence bound applied to Trees (UCT) algorithm is used in the selection phase to choose player actions (Koesis & Szepesvári 2006).
The McGammon approach adapted by Yen et al. (2014) to the game of Chinese Dark Chess and formalized as Nondeterministic Monte Carlo Tree Search (NMCTS). There are two node types in NMCTS: deterministic state nodes and nondeterministic state nodes. Nondeterministic state nodes contain at least one inner node; each inner node has its own visit count, win count, and subtree. Upon reaching nondeterministic state node, an inner node is chosen using "roulette wheel selection" based on the probability distribution of possible resulting states. NMCTS was designed to suit the nature of Chinese Dark Chess, which both types of state nodes may exist on the same level of the search tree; this is in contrast to backgammon, in which homogeneous layers of chance nodes and choice nodes are predictably interleaved.
Alternative MCTS approaches have been adapted for densely stochastic games, wherein the the branching factor at chance nodes is so great that successor states chance nodes are unlikely to ever be resampled. These include Double Progressive Widening and Monte Carlo *-Minimax Search (Chaslot et al. [aactot et al., 2013). In this paper, however, we are concerned with games that are not densely stochastic.
2.4
ALPHAZERO AND MUZERO
MCTS served as the foundation of the AlphaGo and AlphaZero algorithms, the latter of which attained superhuman performance in the deterministic domains of chess, Go. and shogi (Silver al.) 2016 a). AlphaZero substitutes neural network activations for random rollouts to produce policy and value evaluations, employs the Polynomial Upper Confidence Trees (PUCT) algorithm during search, and trains solely via self-play reinforcement learning (Rosin 2011). Hsueh et al. (2018) adapted AlphaZero for simplified, solved version of the nondeterministic game of Chinese Dark Chess, finding that AlphaZero is capable of attaining optimal play in a stochastic setting.
notable limitation of AlphaZero is that the agent relies upon a perfect simulator in order to per- form its lookahead search. The MuZero algorithm frees AlphaZero of this restriction, creating model of environmental dynamics well as game-playing strategies through interactions with the environment and self-play (Schrittwieser et al.) 2019). Until recently, the state of the art in complex single-player domains such as Atari games involved model-free reinforcement learning ap- proaches such as Q-learning and the family of algorithms that followed (Mnih et al. [015] Calışir & Pehlivanoglu 2019). Despite the burden of learning enviornmental dynamics, MuZero leverages its precision-plannanee planning capabilities to achieve extremely strong degree of performance on these problems.
Given parameters 0 and a state representation timestep k AlphaZero employs single neural network fo with a policy head and a value head: p², u* = fo(s²). In contrast, the MuZero model employs three networks for representation, prediction, and dynamics. A set of observations is passed into the representation function hg to produce the initial hidden state: S = hp((o)...., ot)). The dynamics function recurrently takes a previous hidden state and an action image to produce an
2

---

A(A(s)), Under review as a conference paper at ICLR 2021
immediate reward and the next hidden state: rh r² 100 _a²). Any hidden state produced in such fashion may be passed into the prediction function fo to produce a policy vector and scalar value: p", et = fo(s".
With this model, the agent may search over future trajectories a'..... a using past observations 01,-.., og; in principle any MDP planning algorithm may be used given the rewards and states pro- duced by the dynamics function. MuZero uses a MCTS algorithm similar to AlphaZero's search, wherein the representation function is used generate the hidden state for the node then has its own hidden state, produced by the dynamics function, and prior probability and value, produced by the prediction function. These values are used in the tree search select an action a++1 Te via PUCT.
node. Each child
NONDETERMINISTIC MUZERO
3.1 DEFINITIONS
We consider here an extension of the MuZero algorithm for two-player, zero-sum games of perfect information with chance events. Following Lanctol al. (2019), we will characterize such games as extensive-form games with the tuple (N, A. H, Σ, u, 1, S). wherein
N {1, c} includes the two rival players as well as the special chance player e;
A is the finite set of actions that players may take;
is the set of histories, or sequence of actions taken from the start of the game;
Z $ Hi is the subset of terminal histories;
u Z - A S R", where A, = [umin Umaal, is the utility function assigning each
player utility at terminal states;
H N is the player identity function, such that ((h) identifies the player to act history h;
S is the set of states, in which S is a partition of H such that each state s E contains histories h that cannot be distinguished by ((s) = (h) where h E s.
The legal actions available at state are denoted A(s) S A;
Zero-sum games characterized such that V2 Z. EieN ux(2) 0; and
game of perfect information is one with only one history per state: Vs E &,,18/
chance node (or chance event) history h such that <(h) c. A policy क where A(X) represents the set of probability distributions over X, describes agent behavior. An agent acts by sampling an action from its policy: the distribution over actions has probability on one action and zero others. A policy that is not necessarily deterministic called stochastic. The chance player always plays with fixed, stochastic policy Tehance.
R. A deterministic policy one where
transition function A + (SS) defines a probability distribution over successor states s' when choosing action from state Because states are simply sequences of previous actions, a transition function can cquivalently be represented using intermediate chance nodes between the histories of the predecessor and successor states h and h' s'. The transition function is then determined by Tchunce-
As concerned with perfect information games, we shall use interchangeably with h through- out this text, such that s may refer to the single history h contained within it. For ease notation refer to the chance policy Tehance as
3.2 MODIFICATIONS
First, shall extend N such that N = 2, c. includes the new terminal player d. The terminal player to act when a terminal state is reached, such that Yz E Z, (()) = d. We shall refer to nonchance, nonterminal players as choice players. Let us characterize the full action set A as the
3

---

Under review as a conference paper at ICLR 2021
union of the choice player action set An, the chance player action set Ay, and the terminal player action set Ad as follows: A = Ax U As U Ag. Let us introduce the special no-op action, which is produced when it is not a player's turn to move, such that An E N and Vs E S, (s) when <(s) o n. The action set Ad of the terminal player contains the no-op action as well as the end action, which represents ending the game: Ad (no-op,endl We can that for any given state, the set of legal chance actions and the set of legal choice actions are both subsets of the set of all actions: Vs E S, (s) S A, and Vs E S, Am (s) C A.
{no-op}
To provide input sk-1, a the dynamics function go, the original MuZero encodes the action performed as an image and stacks it with the current hidden state. As with any choice player action, we may then encode any chance action a E Ay taken from (b)) as an image and stack it with a previous hidden state to produce input for ge-
For an agent properly model a stochastic environment, it must determine when chance events occur as well as the distributions of their effects. The problem then is to learn an approximation of the player identity function ((s) as well as the chance player policy (s). We then add two quantities that our model, conditioned by parameters 0 must predict: the chance policy ct s th++R and the player identity policy j x 4++ in addition to the quantities already present in MuZero: the policy p RJ Te+k (which we now term the choice policy), value ot Re Zttk, and reward r ~ Ur+k-
Two modifications are made to the MuZero network architecture. The prediction function now pro- duces the choice policy, chance policy, and value: p", c², v² = fs()*), while the dynamics function now produces the reward, next hidden state, and player identity policy: rk s 2 = go(s*=1 a), where the length of it [N] We use the no-op action as training target for the choice policy and chance policy when it is not that player's 's turn to move.
Adding the L2 regularization term, we define our loss function as follows:
K
1((0)
Il (144,,7) + +1 (2LL,, vf) + +1 (TT... p.) + +1 (W et) + 1' (114, ab) + cc100
(1)
3.3 TREE SEARCH
Equipped with these new quantities, we wish to modify our MCTS to accommodate chance nodes. To flexibly capture the dynamics of stochastic games, the model must determine who to play be- fore either making a player action, making a chance action, or terminating the search. We introduce the identity layer, layer of nodes that we interleave with action layers. The identity layer employs our approximation to determine the direction of the search.
Let us declare the root node to be a choice node. As in MuZero, the root hidden state s is generated by passing observations into the representation function such that s" = ha ((o),.... oz)). We then derive the priors of the root node's children by feeding the root hidden state into the prediction function: p", , fe (s)); here, the chance policy and value may be ignored. Following MuZero, the children of the root node are taken from the set of legal actions derived from the true environment state, Ax (s'), ), and assigned edges corresponding to those actions; likewise, we select among the children of a choice node with PUCT during tree search.
The children of choice nodes are identity nodes. Upon expansion, the reward rK next hidden state s and identity policy j of an identity node is generated by applying the dynamics function to the hidden state of its parent s along with the image of its action: n² s i (0= ,a). The prediction function is then applied to the next hidden state s², yielding the choice policy, chance policy, and value: p" c² n () An identity node has a number of children equal to [N]; thus, in our example each identity node has four children corresponding to (1, 2. c, d). A child is selected from an identity node using roulette wheel selection proportional to #t The children from the choice player edges {1, 2} become choice nodes, the child from the chance edge becomes chance node, and the child from the terminal edge becomes a terminal node.
Each chance node and nonroot choice node inherits the hidden state * from its parent identity node and has a number of children equal to |A]. (We do not assume prior knowledge of | or |Ap]; so long as we begin with [A], these are learned and approximated through training.) A choice node also inherits from its parent the value ot and its children take their priors from the choice policy p*. A chance node inherits the chance policy e from its parent and uses this to generate the priors of its
4

---

Under review as a conference paper at ICLR 2021
h
Choice1 s p
vo
r.st 1'
Identity s'.
p'.c'.v v'
Identity
e²
Chance s'. c²
Choice1
Choice2
Terminal
P. s?,
Identity st. i
Identity
f p¹.c'.v'
Choice2 st, p'..v v²
Choice1
Chance
Terminal
Figure 1: Illustration of NDMZ tree search. e represents the edge between nodes.
children; during search, the child of chance node is also chosen using roulette wheel selection. All children of chance nodes and nonroot choice nodes are identity nodes.
In contrast with MuZero, backup is only performed when the leaf node is either choice node or a terminal node. First, let us consider the case when the leaf node is choice node. We will refer identity nodes with choice node parent as result nodes. We only employ PUCT during search when selecting among result nodes and use roulette wheel selection otherwise. Because of this, we only need add subtract the value obtained from the leaf node the result nodes found in the visit path. If the edge leading the leaf node is the same the edge leading to the parent of the result node, we add the value of the leaf node to the total value of the result node; otherwise, we subtract. If the leaf node is terminal node, start with the parent of the leaf node and search up the tree until we find the most recent choice node. We note the value and the edge leading to this most recent choice node, return to the leaf node, and proceed with backup as described above.
Pseudocode for a version of the algorithm applicable to board games lacking immediate rewards is given in full in Appendix A

---

Under review as a conference paper at ICLR 2021
4 EXPERIMENTS
4.1 NANNON
For testing, benchmarking, and evaluation, we used Nannon, a simplified variant of backgammon that is solvable through value iteration (Pollack) 2005). Nannon is properly considered as a param- eterized set of games, such that the number of board points, checkers per player, and sides of dice may be changed, influencing the complexity of the game. is played by rolling a single die. There is no stacking, and only one checker per point is allowed; however, two adjacent pieces of the same color form a block. The number of possible board states may be found with the following equation, where n is the number of points on the board and k is the number of checkers per player:
n - ( +1- +1-)
We chose two game configurations, both with a six-sided die: six points on the board with three checkers per player (6-3-6) and twelve points the board with five checkers per player (12-5-6). 6- 3-6 Nannon has 2,530 states, and 12-5-6 Nannon has 1,780,776 states. The first game configuration has some surprising subtleties despite the small number of total states; the second, while much more complex, is still far more tractable than backgammon. Each configuration was solved using value iteration, yielding lookup table with which the optimal policy could be derived (Bellman 1957). This policy is used to guide the actions of the optimal player; by pitting agents produced by AlphaZero and NDMZ against the optimal player, we obtain more objective estimate of their performance.
4.2 EXECUTION AND HYPERPARAMETERS
The NDMZ algorithm was executed as follows. The Nannon game engine code was written in C++ using the OpenSpiel framework, while the algorithm was written in Python using Tensorflow 2.4. Dense multi-layer perceptrons were used instead of convolutional resnets. Models for fo, 9o. and he were initialized with two hidden layers each of 256 weights, using SELU activation and LeCun Normal initialization (Klambauer et al. 2017). Experiments were carried out on a Kubernetes cluster with Ray using 500 CPU workers for evaluation and 300 CPU workers for self-play; a single T4 GPU was used for training.
One hundred rounds of self-play, training, and evaluation were performed. For both AlphaZero and NDMZ, the models run for three hundred games of self-play per round, while the tree search per- forms one hundred simulations per move. The 6-3-6 used replay buffer limit of 4,000 games, while the 12-5-6 run used a limit of 1,000, as games on the larger board are roughly four times longer; for both configurations, the replay buffer carries about 100,000 examples total. For MuZero, samples are pulled at random from randomly chosen games, and K value of six is used, where K the number of hypothetical steps in which the network is unrolled and trained via backpropaga- tion through time. Around 600,000 examples are then seen per epoch for NDMZ and 100,000 for AlphaZero.
Training for both algorithms employs an Adam optimizer with a learning rate of 0.001 and a batch size of 512. We did not scale the hidden states to the same range as the action input, nor did we scale the loss by or 2. For the first twenty rounds of the trial, five epochs of training are performed; af- terwards, only a single epoch is done. Evaluation of the AlphaZero and NDMZ agents is performed once before training begins and after every training iteration, consisting of 1,000 rounds of play versus the optimal player and 1,000 rounds of play versus an agent that makes moves at random (500 games of each color). For comparison with model-free algorithms, algorithm on the same Nannon configurations. Three hundred games of self-play are performed per round, while training occurs with learning rate of 0.001, X 0.7, and 7 1.0.
ran the TD-Lambda

---

Under review as a conference paper at ICLR 2021
Parcenaae
Wia Pacennng
0.5
randoen
NDMZ vs. random optimal va. optimal
0.3
optimal vs. madom
0.8
10
20
40
70
90
100
10
30
60
90
Training Round
Trinnig
(a) 6-3-6 Nannon Performance
(b) 12-5-6 Nannon Performance
Figure 2: Performance evaluation results of agents produced by the NDMZ and AlphaZero (AZ) algorithms in the game of Nannon throughout the duration of training run, compared with the average results of a trained TD-Lambda agent.
4.3 DYNAMICS EVALUATION
Tests were designed provide more practical insight into the ability of the networks to capture the dynamics of the game. After each training iteration, five hundred games are played with random moves and two tests are performed.
For the first test, the game trajectories are analyzed in the following manner: For every position at timestep t reached in every game, the choice policy output p' of fe is compared with the actual legal moves for that position: (s..). If the choice policy ranks any illegal move with greater probability than a legal move, the position is marked a failure; otherwise, it is a success. This proceeds recurrently for K times, using the dynamics network go along with the played to produce a new hidden state that is fed into fo. obtaining p*+* for each & in 1,....4 K. The actual legal moves for these future states g++ ..... policies, and the results for all positions are averaged. We call this the top move dynamics test.
actually
g+ are compared with the recurrently produced
The second test proceeds along similar lines the first; however, the position marked failure any illegal move is given greater than uniform probability, For example, if p' has length 4 and an illegal move has probability 0.25, the test for that position is failure; otherwise success. This we call the uniform dynamics test. Each test evaluates around 60,000 positions for 6-3-6 Nannon and 240,000 positions for 12-5-6 Nannon.
0.9
0.8
Dyuunics Assuacy
0.5
0.4
0.3
6:3-6
6-3-6
12-5-6
12-54
20
100
30
80
Trnining
Training Round
(a) Top Move Dynamics Test Results
(b) Uniform Dynamics Test Results
Figure 3: Results of dynamics tests as described in Section 4.3

---

Under review as a conference paper at ICLR 2021
4.4 RESULTS AND CONCLUSION
We observe in Figure that, for both configurations, AlphaZero experiences a very sharp and imme- diate increase performance against the random player; the performance of NDMZ. on the other hand, exhibits gradual curve before reaching plateau of near convergence with the AlphaZero agent. This is similar to some of the results shown in Figure 2 of Schritttweeee et al. (2019). where we see that the Elo performance of the MuZero agent eventually converges with that of the Alp- haZero agent in the domains of chess and shogi. Moreover, we see that both AlphaZero and NDMZ exceed the performance of the TD-Lambde agent by significant margin in the 12-5-6 configuration. The dynamics experiments in Figure 3 show that NDMZ agents can predict valid moves with a high degree of accuracy several moves deep in the search. By comparing the two graphs, also observe that the performance of the agent improves as it better learns to model its environment.
From these results, may conclude that NDMZ is capable of learning effective strategies and useful model of the game. Future work could entail testing NDMZ on games with more unorthodox chance node interleavings, such Chinese Dark Chess, and extending the algorithm accommo- date more complex single-player environments such as the Atari suite.
REFERENCES
Bruce W. Ballard. The *-minimax search procedure for trees containing chance nodes. Ar- tificial Intelligence, 21(3):327 - 350, 1983. ISSN 0004-3702. doi: https://doi.op/:
1016500000-330222338800555555
URL http::/wwer sci eecedieceiiicc rect. www.coooccc...... encee
arricle/s1//5000377888888
Richard Bellman. A markovian decision process. Indiana Univ. Math. J., 6:679-684, 1957. ISSN 0022-2518.
C. B. Browne, Powley, D. Whitehouse, M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4(1):1-43, 2012.
Guillaume Chaslot, Mark Winands, H. Herik, Jos Uiterwijk, and Bruno Bouzy. (DPW) progressive strategies for monte-carlo tree search. 04:343-357. doi: 10.1 |
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In In: Pro- ceedings Computers and Games 2006. Springer-Verkle 2006.
C. Hsuch, I. Wu, J. Chen, and T. Hsu. Alphazero for non-deterministic game. In 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI), pp. 116-121, 2018.
G. Klambauer, Thomas Unterthiner, Andreas Mayr, and S. Hochreiter. Self-normalizing neural networks. ArXiv, abs/1706.02515, 2017.
Donald E. Knuth and Ronald W. Moore. An analysis of alpha-beta pruning. Ar- tificial Intelligence, 6(4):293 326, 1975. ISSN 0004-3702. 10.001600044-70025599001133 URL http://ww.scienediiree. wttp://iiiirtcccccccceoeeeeooeee scinnece atticcle/p11/00447777750000
doi: http://doi.org/
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. volume 2006, pp. 282- 293, 09 2006. doi: 10.1007/11871842..22
Mare Lanctot, Abdallah Saffidine, Joel Veness, Christopher Archibald, and Mark Winands, Monte carlo *-minimxx search. 08 2013.
Mare Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Stiram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei. Daniel Hennes, Dustin Morrill, Paul Muller, Timo Ewalds, Ryan Faulkner, János Kramár, Bart De Vylder, Brennan Saeta, James Bradbury, David Ding, Sebastian Borgeaud, Matthew Lai, Julian Schrittwieser, Thomas Anthony, Edward Hughes, Ivo Danihelka, and Jonah Ryan-Dave Open- spiel: A framework for reinforcement learning in games, 2019.
8

---

Under review as a conference paper at ICLR 2021
M. Maschler, E. Solan, S. Zamir, Z. Hellman, and M. Borns. Game theory. Cambridge University Press, Cambridge, 2013.
D. Mitchie. Game-playing and game-learning automata. L. Fox (ed.), Advances in Programming and Non-Numerical Computation, volume 3 of Proceedings of Summer Schools, pp. 183-200. Pergamon, 1966.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Marc Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-33, 02 2015. doi: 10.1038/nature14236
J. Pollack and A. Blair. Why did td id-gammon work? In NIPS, 1996.
Jordan B. Pollack. Nannon: nano backgammon for machine learning research. In CIG, 2005.
Christopher D. Rosin, (PUCT) multi-armed bandits with episode context. 61(3):203-230, 2011. ISSN 1573-7470. doi: 10. 10.10007/114422-01--9555 5 011472201--288--1
URL https://dot .tgg/10.100000
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model, 2019.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Si- monyan, and Demis Hassabis. (AlphaZero chess) mastering chess and shogi by self-play with general reinforcement learning algorithm. a. URL /tttt:://axiv....
abs/ / 1722.1120 01815
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. (Al- phaZero go) mastering the game of go without human knowledge. 350(7676;354-359, b. ISSN 0028-0836, 1476-4687. doi: 10. 00.00///aurr222200. URL http: www. na aatuee........... com/ articles/nature222
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Joannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 -89. Jan 2016. ISSN 1476-4687. doi: 10. 10.1038/nature1660 16961.
org 1038/naturee6338
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL
net.:..eet/ooooo htt.://ws...etttooo/e/eeeeeeeeee 2nd.
html
G. Tesauro. Temporal difference learning and td-gammon. Int. Comput. Games Assoc., 18:88, 1995.
François Van Lishout, Guillaume Chaslot, and Jos WHM Uiterwijk. Monte carlo tree search in (current 2007).
backgammon. 2007. [Online]. Available: http://hd..aandlc.ee///2//
Shi-Jim Yen, Cheng- Wei Chou, Jr-Chang Chen, I-Chen Wu, and Kuo-Yuan Kao. Design and im- plementation of chinese dark chess programs. IEEE Transactions on Computational Intelligence and Al in Games, 7:1-1, 01 2014. doi: 10.
S. Çahşr and M. K. Pehlivanoglu. Model-free reinforcement learning algorithms: A survey. In 2019 27th Signal Processing and Communications Applications Conference (SIU), pp. 1-4, 2019.

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
Algorithm Nondeterministic MuZero Tree Search
1: function NDMZSEARCC((
genx is the environment state adds children and hidden state to root
2: create root node Wi
3: EXPANDROOT( s
4: while within computational budget do
5: WL t (REESELECT(WN))
returns a leaf node D K' is the kind of node
6: if (wL) = choice or K ((WL)= = terminal then BACKUP(WZ,,))
7:
8:
W + children of wo
N is the number of visits
N(w')/e Lvew N(b)
9: W1 < sample a child w/ from W proportional to
T: temperature param
10: return A(w1)
11:
12: function EXPAND sem))
13:
S(wo) -- (TT)
> representation network assigns hidden state S to root. root is choice node > prediction network: choice policy logits scale for legal actions only b for each edge taken from the set of legal actions b N: visit count; W; total value; Q: mean value; P: prior probability; E: edge leading to node
14:
K(wx) choice
15:
P. + (o(((w)))
16: p masked softmax of (p, Ax (s
17: for E An (s do
add child w' with
19:
Nww") & 0; (w') t- 0: Q(w") + 0;
and P(w") + Pai E(w') +
21:
function BACKUP(w) if K (w) terminal then
23:
D if w is a terminal node
25:
while (nn # choice do
n - parent
search up the tree until we find the closest choice node player identity of the choice node value from the choice node
27:
e E(n) V(n)
28:
29:
else
c E(w)
player identity of the leaf node D value from leaf node
31:
U U V(w)
32:
while w is not none do
33:
j 4- parent of w
34:
if ((w) identity and K(j) choice then
if w is result node > if the edge leading to is the same add to total value
35:
if E()) = then
W(w) + W (w) +
37:
else
((w) + W(w)
b subtract from total value
39:
N(w) < N(w) +1
b increment visit count
40:
(ww) ((r)
W(w)
adjust mean value
w parent of
10

---

Under review as a conference paper at ICLR 2021
42:
function TREESELECT(")
43:
while (ww) not terminal do
44:
if not expanded then
is a leaf node D adds child nodes, hidden state, and value
45:
return EXPAND(w)
46:
W <- children of w K (w) = chance or ((w) identity then
47:
chance or identity node > roulette wheel selection b choice node
48:
sample w/ from W weighted by P(w')
49:
else ((w) = choice then
arg max (Q(w") Spuct P(w') V Vbew N(b) I+N(w²)
PUCT
51:
return
52:
53:
function EXPAND(W)
54:
parent of w if i(j) choice or K(j) chance then
if is the child of choice or chance node D w is an identity node D for board games, we ignore the reward choice policy, chance policy, and value C is the set of child edges if w is the child of an identity node b w always inherits the hidden state its parent if the edge leading is the chance edge D w is a chance node p is the chance policy vector A is the full action set the edge leading the terminal edge w is a terminal node terminal nodes have no children
56:
K(w) t- identity
.S(w).p++ go [(j), A(w))
58:
Oww), ((w), (w) + fe(S(w))
59:
C+ N
60:
else if K(j) identity then
61:
5(w) + S(j)
62:
if A(w) then
63:
((w) < chance
64:
p <- C(j)
65:
+ A
else A(w) then
67:
K(w) t- terminal
C 0
69:
else
70:
K ((w) f choice
w choice node p is the choice policy vector >> w inherits value from parent
71:
- O(j)
72:
V(w) + V(j)
73:
C 6 A
74:
for E C do
D for each edge in the set of child edges
75:
add child w/ with
76:
Nww') + 0; W (w') t 0; Q(Q())) +0;
77:
and P(w') + pe; E(w') t
assign prior child from p along with edge
78:
return w
11


Reviews:
[{"review_id": "wKE8jZRintM", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces NDMZ, short for nondeterministic MuZero, a deep reinforcement learning algorithm for model-based RL that doesn't use the rules of the game to perform search. The paper's contribution is mostly focused on describing how to construct the algorithm, and experimental results are provided at the end. A good analogy is that of a player that must play a (physical) board game by not only making decisions, but also acting out the game: producing random events, such as die rolls, and moving pieces on the board. \n\nOverall, I enjoyed this paper and thought it was quite clear, but it does not feel substantial enough for a conference publication. The main contribution is the detail of how to implement stochasticity in a MuZero architecture. While interesting, there's relatively little discussion of why these are the right choices, why this is particularly challenging, or in fact what value it adds compared to existing algorithms.\n\nMy main concern with the paper can be summarized as: What is this work's impact? What is the key premise that makes it a reasonable line of work? It seems that AlphaZero is just as well equipped to deal with games (where a simulator *is* available; the restriction imposed here is artificial). Demonstrating that a deep learning system can model stochastic events isn't too surprising either. I would have liked to see more discussion and empirical support arguing why this particular work brings new insights to deep RL. The easiest way to do so is to demonstrate a problem where NDMZ or MZ outperforms AlphaZero, or where a model isn't available, or is too cumbersome to be used.\n\nA minor issue also concerns the presentation. The algorithm is described in terms of 'chance policy' and 'identity policy', but I would call these just a transition model. To present them as additional players is a little surprising.\n\nMinor points:\n- PUCT: spell out the name \n- Why did you omit the L2 term in Eqn 1?\n- Why is the root node necessarily a choice node?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RDnIOc8CGx5", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper presents NDMZ, an extension of the MuZero algorithm to handle games with chance moves. In order to do this, chance nodes are added to MCTS, and add a few additional prediction targets for the network, such as predicting when a chance event will occur, so that it can be simulated in MCTS.\n\nReasons for score:\n\nI am split on this paper, on the one hand I think this is an interesting direction, and the results, even in a toy domain like Annon, show promising results. Specially Figure 3, where we can see that the learned forward model gets more and more accurate over time, which is encouraging. On the other hand, I felt that some of the new formalization is a bit clumsy. The paper could also use some work on making the descriptions more formal, clear and concise (specially Section 3.3, which includes many vague and lengthy descriptions that can be made shorter and more concise with a few definitions).\n\n\n\nAdditional feedback:\n\n- page 3: on the definition of state, you mention that histories belonging to a state cannot be distinguished by which player is next. But probably another constraint is that they cannot be distinguished either by the set of available actions, right?\n- pages 3-4: I find the addition of player \"d\" and the no-op action unnecessary, and just making the formalization clumsy. This is not needed any most other formalization of games with chance events. I do not see they extending the expressiveness of the formalization in any way, and just add unnecessary complexity. Why do you even need to train the policy of an agent when it's not its turn to move? Can't you simply skip its update, rather than making it learn to predict an arbitrary \"no-op\" value that will never be used, but will affect the network weights?", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q_EAkaGLa2G", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents an algorithm NDMZ that extends MuZero to non-deterministic, two-player, zero-sum games of perfect information. The new algorithm borrows the idea from non-deterministic MCTS and the theory of extensive-form games. The empirical studies show a competitive performance of MuZero agains AlphaGoZero, despite MuZero lacks a perfect simulator the game.\n\nComments:\n\nThis paper is generally well-written and clear. The empirical results demonstrate that NDMZ can achieve a similar performance as AlphaGoZero, which is very interesting provided that MuZero does not get access to a perfect game simulator.\n\n1. In Fig 2. with 12-5-6 Nannon, it shows that it takes AlphaGoZero a few rounds to learn and after 100 rounds of training, it does not perform well against the optimal policy (with a winning rate about 30%), which implies that AlphaGoZero does not converge to an optimal policy. The reviewer is not familiar with AlphaGoZero's performance in these games and is wondering whether this is expected.", "extra_scores": {}, "extra_text": {}}, {"review_id": "OZsykQ7G1gM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe paper extends MuZero for nondeterministic domains (NDMZ). Compared to MuZero NDMZ also learns a function that determines who is to act (player 1,2 or chance) and a distribution of chance outcomes. This makes it possible to employ MCTS search adjusted to handle nondeterministic nodes on top of a tree constructed by NDMZ's neural nets.\n\n\nStrong points\n* NDMZ is a straightforward extension of MuZero, therefore it might be interesting to a broad audience.\n* The model is clearly described.\n\nWeak points\n* Empirical evaluation could provide more insights about the usefulness of NDMZ.\n\n\nRecommendation\n\nI recommend rejecting the paper on the basis of insufficient empirical evaluation.\n\n\nQuestions\n\n* Could you provide broader context for the presented results? How do other learning approaches perform on the selected games? \n\n* While Nannon 12-5-6 is still a relatively small game there is a significant gap in win rate of NDMZ against optimal player. Is this a good result? \n\n\nPossible improvements\n\n* Discussion of results is very brief.\n\n* The most important question not answered by current evaluation is: \"Does proposed search help over model free methods with similar number of trainable parameters?\" e.g. how far from optimum would DQN (or something similar) be in these games? \n\n* Second important missing experiment is: \"Does more search help? How does performance scale with more MCTS iterations?\" One of promises of search based systems is that they can make use of more \"thinking\" time during play. It should be easy to test whether NDMZ has this property too.\n\n* Final (obvious) improvement would be to test NDMZ on an environment that is large enough that it can't be strongly solved (e.g. Backgammon) and show the importance of search compared to model free approaches there. While scaling up might be nontrivial it would significantly improve the message of the paper. \n\n\nMinor\n\n* For MuZero, a K value of six is used, and samples are pulled at random from randomly chosen games before being unrolled K times and trained via backpropagation through time. ... It is strange to refer to K before explaining what it is.\n\n* I assume that in Section 4 AZ refers to AZ run with the exact search tree from Sec 3.3 however I believe that it isn't explicitly stated.\n\n* called called -> called \n\n\n\n===== Post rebuttal update =====\n\nI like the addition of TD Gammon like baseline and as a result of that I slightly increased my score. However please add more details about that baseline (e.g. did it have a comparable number of parameters to NDMZ?). You can also use performance of just the policy head (as a model free agent) to show what is the contribution of search.\nAlso showing how performance scales with search would still be a valuable experiment.", "extra_scores": {}, "extra_text": {}}, {"review_id": "NvD3b4cPkZ5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes NDMZ, which extends the previous MuZero algorithm to stochastic two-layer zero-sum games of perfect information. NDMZ formalize chance as a player (chance player) and introduces two additional quantities: the player identity policy and the chance player policy. NDMZ also introduce new node classes to MCTS, which allows it to accommodate chance.\n\nOne major weakness of the paper is there is its lack of novelty/contribution. The core idea of interleaving chance nodes with choice nodes to model stochastic environment in tree search is not brand new. The main contribution of this paper is the integration of such idea into the specific MuZero tree search framework. This might be OK if the authors could present strong enough experimental results. \n\nHowever, this brings up a second main weakness of the paper, which is lack of sufficient experimental justification. The proposed NDMZ is only evaluated on Nannon, a simplified version of backgammon, which is not sufficient. I would suggest the authors to evaluate the algorithm on at least 5~10 Atari games. Although the Atari environment is known to be a deterministic, it becomes stochastic when there is only a limited horizon of past observed frames. In addition, just like MuZero, the proposed NDMZ should also be adapted to single-player tasks like Atari games. Therefore, under this setting, Atari could be used to simulate the stochastic environment for the current purpose. In addition, it would also be helpful to further evaluate it on the more complicated tasks such as Chinese Dark Chess, as suggested by the authors.\n\nFinally, the dynamic evaluation (including both top-move dynamic test and uniform dynamics test) only evaluate the accuracy of the learned dynamics by only examining the chance of selecting illegal move. This seems to be just one very restricted perspective of dynamics evaluation. I’m wondering whether there should be other more comprehensive ways to do this?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a pretty good consensus that this paper should not be accepted at ICLR. The reviewers do not seem think that extending MuZero to non-deterministic MuZero constitutes a significant advance.  Three reviewers give clear rejects with scores (3, 4, 5) all with good confidence (4).  A fourth reviewer gave a score of 6, i.e., borderline accept.  While the fifth reviewer recommends, he does not seem to be very confident and did not step in to champion the paper.  The program committee decided that the paper in its current form does not meet the acceptance bar.
Decision: Reject