summaries: The 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. 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. 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. 
abstractText: 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 the chance player 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.
references.authors: Bruce W. Ballard
references.title: The *-minimax search procedure for trees containing chance nodes
references.venue: Artificial Intelligence,
references.authors: Richard Bellman
references.title: A markovian decision process
references.venue: Indiana Univ. Math. J.,
references.authors: C.B. Browne E. Powley D. Whitehouse S.M. Lucas P.I. Cowling P. Rohlfshagen S. Tavener D. Perez S. Samothrakis S. Colton
references.title: A survey of monte carlo tree search methods
references.venue: IEEE Transactions on Computational Intelligence and AI in Games,
references.authors: Rémi Coulom
references.title: Efficient selectivity and backup operators in monte-carlo tree search
references.venue: Proceedings Computers and Games 2006. Springer-Verlag,
references.authors: C. Hsueh I. Wu J. Chen T. Hsu
references.title: Alphazero for a non-deterministic game
references.venue: In 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI),
references.authors: Donald E. Knuth Ronald W. Moore
references.title: An analysis of alpha-beta pruning
references.venue: Artificial Intelligence,
references.authors: Levente Kocsis Csaba Szepesvári
references.title: Bandit based monte-carlo planning
references.authors: D. Mitchie
references.title: Game-playing and game-learning automata
references.authors: 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 Demis Hassabis
references.title: Human-level control through deep reinforcement learning
references.venue: Nature, 518:529–33,
references.authors: J. Pollack A. Blair
references.title: Why did td-gammon work
references.venue: In NIPS,
references.authors: Jordan B. Pollack
references.title: Nannon: A nano backgammon for machine learning research
references.venue: In CIG,
references.authors: Christopher D. Rosin
references.title: PUCT) multi-armed bandits with episode context
references.venue: doi: 10.1007/s10472-011-9258-6. URL https://doi.org/10.1007/
references.authors: Julian Schrittwieser Ioannis Antonoglou Thomas Hubert Karen Simonyan Laurent Sifre Simon Schmitt Arthur Guez Edward Lockhart Demis Hassabis Thore Graepel Timothy Lillicrap David Silver
references.title: Mastering atari, go, chess and shogi by planning with a learned model, 2019
references.authors: David Silver Aja Huang Chris J. Maddison Arthur Guez Laurent Sifre George van den Driessche Julian Schrittwieser Ioannis Antonoglou Veda Panneershelvam Marc Lanctot Sander Dieleman Dominik Grewe John Nham Nal Kalchbrenner Ilya Sutskever Timothy Lillicrap Madeleine Leach Koray Kavukcuoglu Thore Graepel Demis Hassabis
references.title: Mastering the game of go with deep neural networks and tree search
references.authors: Richard S. Sutton Andrew G. Barto
references.title: Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
references.venue: URL http://incompleteideas.net/book/the-book-2nd. html
references.authors: G. Tesauro
references.title: Temporal difference learning and td-gammon
references.venue: J. Int. Comput. Games Assoc.,
references.authors: François Van Lishout Guillaume Chaslot Jos WHM Uiterwijk. Monte carlo tree search in backgammon.
references.title: Online
references.venue: Available: http://hdl.handle.net/2268/28469 (current 2007).
references.authors: Shi-Jim Yen Cheng-Wei Chou Jr-Chang Chen I-Chen Wu Kuo-Yuan Kao
references.title: Design and implementation of chinese dark chess programs
references.venue: IEEE Transactions on Computational Intelligence and AI in Games, 7:1–1,
references.authors: S. Çalışır M.K. Pehlivanoğlu
references.title: Model-free reinforcement learning algorithms: A survey
references.venue: 27th Signal Processing and Communications Applications Conference (SIU),
sections.heading: 1 INTRODUCTION
sections.text: While the AlphaZero algorithm achieved superhuman performance in a variety of challenging domains, it relies upon a perfect simulation of the environment dynamics to perform precision planning. MuZero, the newest member of the AlphaZero family, combines the advantages of planning with a learned model of its environment, allowing it to tackle problems such as the Atari suite without the advantage of a simulator. This paper presents Nondeterministic MuZero (NDMZ), an extension of MuZero to stochastic, two-player, zero-sum games of perfect information. In it, we formalize the element of chance as a player in the game, determine a policy for the chance player via interaction with the environment, and augment the tree search to allow for chance actions.
  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 assumption of perfect information, we change the MuZero architecture to allow agents to determine whose turn it is to move and when a chance action should occur. The agent learns the fixed distribution of chance actions for any given state, allowing it to 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 a 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.
sections.heading: 2 PRIOR WORK
sections.heading: 2.1 EARLY TREE SEARCH
sections.text: 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 a 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 or min. Chance nodes, min nodes, and max nodes are interleaved depending on the game being played. The *-minimax algorithm extends the alpha-beta tree pruning strategy to games with chance nodes (Ballard, 1983; Knuth & Moore, 1975).
sections.heading: 2.2 MODEL-FREE REINFORCEMENT LEARNING
sections.text: A notable success of model-free reinforcement learning for nondeterministic 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 it is time to make a move, each legal move is used to produce a 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).
sections.heading: 2.3 MONTE CARLO TREE SEARCH
sections.text: 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., 2012). A version of MCTS by Van Lishout et al. (2007) called called McGammon (Monte Carlo Backgammon) was capable of finding expert moves in a simplified backgammon game. At a chance node, the next move is always chosen randomly; at choice nodes, the Upper Confidence bound applied to Trees (UCT) algorithm is used in the selection phase to choose player actions (Kocsis & Szepesvári, 2006).
  The McGammon approach was 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 a 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, in 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 at chance nodes are unlikely to ever be resampled. These include Double Progressive Widening and Monte Carlo *-Minimax Search (Chaslot et al.; Lanctot et al., 2013). In this paper, however, we are concerned with games that are not densely stochastic.
sections.heading: 2.4 ALPHAZERO AND MUZERO
sections.text: 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 et al., 2016; b;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 a simplified, solved version of the nondeterministic game of Chinese Dark Chess, finding that AlphaZero is capable of attaining optimal play in a stochastic setting.
  A notable limitation of AlphaZero is that the agent relies upon a perfect simulator in order to perform its lookahead search. The MuZero algorithm frees AlphaZero of this restriction, creating a model of environmental dynamics as 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 approaches such as Q-learning and the family of algorithms that followed (Mnih et al., 2015; Çalışır & Pehlivanoğlu, 2019). Despite the burden of learning enviornmental dynamics, MuZero leverages its precision-planning capabilities to achieve an extremely strong degree of performance on these problems.
  Given parameters θ and a state representation at timestep k, AlphaZero employs a single neural network fθ with a policy head and a value head: pk, vk = fθ(sk). In contrast, the MuZero model employs three networks for representation, prediction, and dynamics. A set of observations is passed into the representation function hθ to produce the initial hidden state: s0 = hθ((o1, . . . , ot)). The dynamics function recurrently takes a previous hidden state and an action image to produce an
  immediate reward and the next hidden state: rk, sk = gθ(sk−1, ak). Any hidden state produced in such fashion may be passed into the prediction function fθ to produce a policy vector and scalar value: pk, vk = fθ(sk).
  With this model, the agent may search over future trajectories a1, ..., ak using past observations o1, ..., ot; in principle any MDP planning algorithm may be used given the rewards and states produced by the dynamics function. MuZero uses a MCTS algorithm similar to AlphaZero’s search, wherein the representation function is used to generate the hidden state for the root node. Each child 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 to select an action at+1 ∼ πt via PUCT.
sections.heading: 3 NONDETERMINISTIC MUZERO
sections.heading: 3.1 DEFINITIONS
sections.text: We consider here an extension of the MuZero algorithm for two-player, zero-sum games of perfect information with chance events. Following Lanctot et al. (2019), we will characterize such games as extensive-form games with the tuple 〈N,A,H,Z, u, ι, S〉, wherein
  • N = {1, 2, c} includes the two rival players as well as the special chance player c; • A is the finite set of actions that players may take; • H is the set of histories, or sequence of actions taken from the start of the game; • Z ⊆ H is the subset of terminal histories; • u : Z → ∆nu ⊆ Rn, where ∆u = [umin, umax], is the utility function assigning each
  player a utility at terminal states;
  • ι : H → N is the player identity function, such that ι(h) identifies the player to act at history h;
  • S is the set of states, in which S is a partition of H such that each state s ∈ S contains histories h ∈ s that cannot be distinguished by ι(s) = ι(h) where h ∈ s.
  • The legal actions available at state s are denoted as A(s) ⊆ A; • Zero-sum games are characterized such that ∀z ∈ Z, ∑ i∈N ui(z) = 0; and
  • A game of perfect information is one with only one history per state: ∀s ∈ S, |s| = 1.
  A chance node (or chance event) is a history h such that ι(h) = c. A policy π : S → ∆(A(s)), where ∆(X) represents the set of probability distributions over X, describes agent behavior. An agent acts by sampling an action from its policy: a ∼ π. A deterministic policy is one where the distribution over actions has probability 1 on one action and zero on others. A policy that is not necessarily deterministic is called stochastic. The chance player always plays with a fixed, stochastic policy πchance.
  A transition function T : S × A → ∆(S) defines a probability distribution over successor states s′ when choosing action a from state s. Because states are simply sequences of previous actions, a transition function can equivalently be represented using intermediate chance nodes between the histories of the predecessor and successor states h ∈ s and h′ ∈ s′. The transition function is then determined by πchance.
  As we are concerned with perfect information games, we shall use s interchangeably with h throughout this text, such that s may refer to the single history h contained within it. For ease of notation we refer to the chance policy πchance as ψ.
sections.heading: 3.2 MODIFICATIONS
sections.text: First, we shall extend N such that N = {1, 2, c, d} includes the new terminal player d. The terminal player is to act when a terminal state is reached, such that ∀z ∈ Z, ι(z) = d. We shall refer to nonchance, nonterminal players as choice players. Let us characterize the full action set A as the
  union of the choice player action set Aπ , the chance player action set Aψ , and the terminal player action set Ad as follows: A = Aπ ∪ Aψ ∪ Ad. Let us introduce the special no-op action, which is produced when it is not a player’s turn to move, such that ∀n ∈ N and ∀s ∈ S,An(s) = {no-op} when ι(s) 6= 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, end}. We can see 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: ∀s ∈ S,Aψ(s) ⊆ A, and ∀s ∈ S,Aπ(s) ⊆ A.
  To provide input sk−1, ak to the dynamics function gθ, 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 ∈ Aψ taken from ψ(s) as an image and stack it with a previous hidden state to produce input for gθ.
  For an agent to 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 θ, must predict: the chance policy ck ≈ ψt+k and the player identity policy ik ≈ ιt+k in addition to the quantities already present in MuZero: the policy pk ≈ πt+k (which we now term the choice policy), value vk ≈ zt+k, and reward rk ≈ ut+k. Two modifications are made to the MuZero network architecture. The prediction function now produces the choice policy, chance policy, and value: pk, ck, vk = fθ(sk), while the dynamics function now produces the reward, next hidden state, and player identity policy: rk, sk, ik = gθ(sk−1, a), where the length of ik = |N|. We use the no-op action as a training target for the choice policy and chance policy when it is not that player’s turn to move.
  Adding the L2 regularization term, we define our loss function as follows:
  lt(θ) = K∑ k=0 lr(ut+k, r k t ) + l v(zt+k, v k t ) + l p(πt+k,p k t ) + l c(ψt+k, c k t ) + l i(ιt+k, i k t ) + c||θ||2 (1)
sections.heading: 3.3 TREE SEARCH
sections.text: 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 is to play before either making a player action, making a chance action, or terminating the search. We introduce the identity layer, a 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 s0 is generated by passing observations into the representation function such that s0 = hθ((o1, . . . , ot)). We then derive the priors of the root node’s children by feeding the root hidden state into the prediction function: p0, , = fθ(s0); 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, Aπ(st), 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 sk, and identity policy ik of an identity node is generated by applying the dynamics function to the hidden state of its parent sk−1 along with the image of its action: rk, sk, ik = gθ(sk−1, a). The prediction function is then applied to the next hidden state sk, yielding the choice policy, chance policy, and value: pk, ck, vk = fθ(sk). 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 ik. The children from the choice player edges {1, 2} become choice nodes, the child from the chance edge c becomes a chance node, and the child from the terminal edge d becomes a terminal node.
  Each chance node and nonroot choice node inherits the hidden state sk from its parent identity node and has a number of children equal to |A|. (We do not assume prior knowledge of |Aπ| or |Aψ|; so long as we begin with |A|, these are learned and approximated through training.) A choice node also inherits from its parent the value vk, and its children take their priors from the choice policy pk. A chance node inherits the chance policy ck from its parent and uses this to generate the priors of its
  children; during search, the child of a 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 a choice node or a terminal node. First, let us consider the case when the leaf node is a choice node. We will refer to identity nodes with a 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 or subtract the value obtained from the leaf node to the result nodes found in the visit path. If the edge leading to the leaf node is the same as 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 a terminal node, we 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.
sections.heading: 4 EXPERIMENTS
sections.heading: 4.1 NANNON
sections.text: 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 parameterized 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. It 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:
  k∑ i=0 k∑ j=0 ( n i )( n− i j ) (k + 1− i)(k + 1− j) (2)
  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 on 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 a 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 a more objective estimate of their performance.
sections.heading: 4.2 EXECUTION AND HYPERPARAMETERS
sections.text: 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 fθ, gθ, and hθ 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 performs one hundred simulations per move. The 6-3-6 run used a 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 a K value of six is used, where K is the number of hypothetical steps in which the network is unrolled and trained via backpropagation 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 1K or 1 2 . For the first twenty rounds of the trial, five epochs of training are performed; afterwards, 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, we ran the TD-Lambda algorithm on the same Nannon configurations. Three hundred games of self-play are performed per round, while training occurs with a learning rate of 0.001, λ = 0.7, and γ = 1.0.
sections.heading: 4.3 DYNAMICS EVALUATION
sections.text: Tests were designed to 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 pt of fθ is compared with the actual legal moves for that position: Aπ(stenv). 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 gθ along with the move actually played to produce a new hidden state that is fed into fθ, obtaining pt+k for each k in 1, . . . ,K. The actual legal moves for these future states st+1, . . . , st+K are compared with the recurrently produced policies, and the results for all positions are averaged. We call this the top move dynamics test.
  The second test proceeds along similar lines as the first; however, the position is marked a failure if any illegal move is given greater than uniform probability. For example, if pt has length 4 and an illegal move has probability > 0.25, the test for that position is a failure; otherwise it is a 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.
sections.heading: 4.4 RESULTS AND CONCLUSION
sections.text: We observe in Figure 2 that, for both configurations, AlphaZero experiences a very sharp and immediate increase in performance against the random player; the performance of NDMZ, on the other hand, exhibits a gradual curve before reaching a plateau of near-convergence with the AlphaZero agent. This is similar to some of the results shown in Figure 2 of Schrittwieser et al. (2019), where we see that the Elo performance of the MuZero agent eventually converges with that of the AlphaZero agent in the domains of chess and shogi. Moreover, we see that both AlphaZero and NDMZ exceed the performance of the TD-Lambda agent by a 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 even several moves deep in the search. By comparing the two graphs, we also observe that the performance of the agent improves as it better learns to model its environment.
  From these results, we may conclude that NDMZ is capable of learning effective strategies and a useful model of the game. Future work could entail testing NDMZ on games with more unorthodox chance node interleavings, such as Chinese Dark Chess, and extending the algorithm to accommodate more complex single-player environments such as the Atari suite.
sections.heading: A APPENDIX
sections.text: Algorithm Nondeterministic MuZero Tree Search 1: function NDMZSEARCH(senv) . senv is the raw environment state 2: create root node w0 3: EXPANDROOT(w0, senv) . adds children and hidden state to root 4: while within computational budget do 5: wL ← TREESELECT(w0) . returns a leaf node 6: if K(wL) = choice or K(wL) = terminal then . K is the kind of node 7: BACKUP(wL, v) 8: W← children of w0 . N is the number of visits 9: w1 ← sample a child w′ from W proportional to N(w
  ′)1/τ∑ b∈WN(b) 1/τ . τ : temperature param
  10: return A(w1) 11: 12: function EXPANDROOT(w0, senv) 13: S(w0)← hθ(senv) . representation network assigns hidden state S to root. 14: K(w0)← choice . root is choice node 15: p, , ← fθ(S(w0)) . prediction network: choice policy logits 16: p← masked softmax of (p,Aπ(senv)) . scale for legal actions only 17: for e ∈ Aπ(senv) do . for each edge e taken from the set of legal actions 18: add child w′ with . N : visit count; W : total value; 19: N(w′)← 0;W (w′)← 0;Q(w′)← 0; . Q: mean value; P : prior probability; 20: and P (w′)← pa;E(w′)← e . E: edge leading to node 21: 22: function BACKUP(w) 23: if K(w) = terminal then . if w is a terminal node 24: n← w 25: while K(n) 6= choice do 26: n← parent of n . search up the tree until we find the closest choice node 27: e← E(n) . player identity of the choice node 28: v ← V (n) . value from the choice node 29: else 30: e← E(w) . player identity of the leaf node 31: v ← V (w) . value from leaf node 32: while w is not none do 33: j ← parent of w 34: if K(w) = identity and K(j) = choice then . if w is a result node 35: if E(j) = e then . if the edge leading to j is the same 36: W (w)←W (w) + v . add to total value 37: else 38: W (w)←W (w)− v . subtract from total value 39: N(w)← N(w) + 1 . increment visit count 40: Q(w)← W (w)N(w) . adjust mean value 41: w ← parent of w
  42: function TREESELECT(w) 43: while K(w) is not terminal do 44: if w not expanded then . w is a leaf node 45: return EXPAND(w) . adds child nodes, hidden state, and value 46: W← children of w 47: if K(w) = chance or K(w) = identity then . chance or identity node 48: w ← sample w′ from W weighted by P (w′) . roulette wheel selection 49: else if K(w) = choice then . choice node
  50: w ← arg max w′∈W
  ( Q(w′) + cpuctP (w ′) √∑ b∈W N(b)
  1+N(w′)
  ) . PUCT
  51: return w 52: 53: function EXPAND(w) 54: j ← parent of w 55: if K(j) = choice or K(j) = chance then . if w is the child of a choice or chance node 56: K(w)← identity . w is an identity node 57: , S(w),p← gθ(S(j), A(w)) . for board games, we ignore the reward 58: O(w), C(w), V (w)← fθ(S(w)) . choice policy, chance policy, and value 59: C← N . C is the set of child edges 60: else if K(j) = identity then . if w is the child of an identity node 61: S(w)← S(j) . w always inherits the hidden state of its parent 62: if A(w) = c then . if the edge leading to w is the chance edge c 63: K(w)← chance . w is a chance node 64: p← C(j) . p is the chance policy vector 65: C← A . A is the full action set 66: else if A(w) = d then . if the edge leading to w is the terminal edge d 67: K(w)← terminal . w is a terminal node 68: C← {} . terminal nodes have no children 69: else 70: K(w)← choice . w is a choice node 71: p← O(j) . p is the choice policy vector 72: V (w)← V (j) . w inherits value from parent 73: C← A 74: for e ∈ C do . for each edge in the set of child edges 75: add child w′ with 76: N(w′)← 0;W (w′)← 0;Q(w′)← 0; 77: and P (w′)← pe;E(w′)← e . assign prior to child from p along with edge e 78: return w