undefined | Better HN

0 pointsYeGoblynQueenne6y ago0 comments

Regarding MuZero- I confess to not have read the paper very carefully, but I am confused by its claim that the new system achieves superhuman performance without knowing the game rules.

Specifically, MuZero uses MCTS and MCTS needs to have at the very least a move generator in order to produce actions that can then be evaluated for their results. The trained MuZero model learns the transition function and evaluation function but I don't see in the paper where it learns what actions are legal in the domain. And I don't understand how any architecture could model the possible moves in a game without observing examples of external play (i.e. not self-play).

MuZero reuses the AlphaZero architecture so most likely the moves of the pieces for Chess, Shoggi and Go are hard-coded in the architecture, as they are in AlphaZero. There's also probably some similar hard-coding of Atari actions, which I'm probably missing in the paper.

0 comments

yazr6y ago

> but I am confused by its claim ... without knowing the game rules.

> probably some similar hard-coding of Atari actions

Nope, no hard coding.

Consider trying to MCTS on an Atari game. You have to "learn to predict" the <next frame, action> pairs. Initially this guess is very bad, but eventually your predictions are good enough that rolling out a tree of predictions improves your action selection

For Go, and chess, we twist our self into NOT using the game rules in the simulator e.g. for each move, just indicate if GAME LOSS WIN

Whether this paper worthy of a new Nature hype cycle is a separate debate

YeGoblynQueenneOP6y ago

>> You have to "learn to predict" the <next frame, action> pairs.

But where do the actions come from?

For example, if I play chess, I could pick up a piece and throw it at my opponent's head. Similarly, if I play Atari I could chuck the controller at the monitor. These are actions I can perform that are available to me because of my basic human anatomy and because of the laws of physics (I can grab and throw and a thrown object flies through the air untl it hits a target or gravity wins).

In the case of MuZero, what actions can the system perform and where do they come from? I don't see where that is described in the paper.

>> For Go, and chess, we twist our self into NOT using the game rules in the simulator e.g. for each move, just indicate if GAME LOSS WIN

Similarly - what determines "each move"?

EDIT: I can see in the MuZero paper that "Final outcomes {lose,draw,win} in board games are treated as rewards $u_t \in {-1,0,+1}$ occurring at the final step of the episode" but I also can't see where these come from, what tells the model that a loss, draw or win has occurred at the end of an episode.

I mean, if you're telling the model what actions can be performed and what end-states values are, then what game rules are you _not_ giving to the system?

yazr6y ago

As someone patiently explained to me 2 yrs ago...

For the ATARI, the "real world" is the present frame, and a fixed set of 4 buttons and 4 directions. This of course is the game pre-programmed into the ALE ROM.

You can take any action, and get the next frame. but you cant "undo" an action, and you cant restart a game from a fixed state (see the Go-Explore controversy). And you cant explore 4 different actions in an interesting frame.

So now, if you learn a network which predicts the next frame, you can enter the world of model-based learning, where we do a simulated move tree roll-out (i.e. not calling the ATARI), try a gazillions moves, and only then select an action and get the next sample.

In a formally defined synthetic domain such as chess or logic programming, it is not clear whether this is helpful. We are simply trading one cpu time (calling the environment) for other cpu time (running our own learned im-precise model of the environment)

Of course DM has a chess function which does codes the rules of the next move. It can return a LOSS if you try an illegal move. But this function is NOT called for the tree roll out.

2 more replies

gwern6y ago

> Specifically, MuZero uses MCTS and MCTS needs to have at the very least a move generator in order to produce actions that can then be evaluated for their results.

You are confusing the two phases. The MuZero training does not use MCTS, it merely observes sequences of moves/states/rewards. This can be done using observations from anywhere: human games, AG games, A0 games, random games. This is where it does the actual learning of what moves are valid and what makes moves good (because invalid moves will not be represented in the dataset of valid games). It does not need MCTS or any access to an oracle about move validity, which is Marcus's complaint. This is no more cheating than observing the real world to infer its physics.

The second phase, where new games are generated, may use MCTS. But it doesn't have to. So it can learn by simply training on a game corpus, and then generating a new game corpus by self-play using only its internal implicit tree search and something like illegal moves = instant loss. It will rapidly learn to not make illegal moves and play just as validly as a MCTS-structured tree search, and then its implicit learned tree search achieves the same or greater playing strength.

YeGoblynQueenneOP6y ago

>> The MuZero training does not use MCTS, it merely observes sequences of moves/states/rewards.

I'm sorry, I read the paper a bit more carefully since we're discussing it and I don't think this is right. It's true that it's a while since I read the AlphaZero paper and the details are a bit fuzzy in my memory, but in the MuZero paper it's clear that MCTS is used to generate a policy and estimated value for a current hidden state, and to select an action to take at the current real game state (the "environment"), then the observed state and reward are later reused as past observations to train the model, together with future actions, also selected by MCTS. So it seems to me that MCTS is pretty central to the training process.

The paper does say that any MDP could be used in place of MCTS but I don't think anyone seriously plans on using something else than MCTS for board games in the foreseeable future.

I'm confused by your use of the term "implicit tree search". Could you clarify?

j / k navigate · click thread line to collapse

0 comments

yazr6y ago

> but I am confused by its claim ... without knowing the game rules.

> probably some similar hard-coding of Atari actions

Nope, no hard coding.

For Go, and chess, we twist our self into NOT using the game rules in the simulator e.g. for each move, just indicate if GAME LOSS WIN

Whether this paper worthy of a new Nature hype cycle is a separate debate

YeGoblynQueenneOP6y ago

>> You have to "learn to predict" the <next frame, action> pairs.

But where do the actions come from?

In the case of MuZero, what actions can the system perform and where do they come from? I don't see where that is described in the paper.

>> For Go, and chess, we twist our self into NOT using the game rules in the simulator e.g. for each move, just indicate if GAME LOSS WIN

Similarly - what determines "each move"?

I mean, if you're telling the model what actions can be performed and what end-states values are, then what game rules are you _not_ giving to the system?

yazr6y ago

As someone patiently explained to me 2 yrs ago...

For the ATARI, the "real world" is the present frame, and a fixed set of 4 buttons and 4 directions. This of course is the game pre-programmed into the ALE ROM.

Of course DM has a chess function which does codes the rules of the next move. It can return a LOSS if you try an illegal move. But this function is NOT called for the tree roll out.

2 more replies

gwern6y ago

> Specifically, MuZero uses MCTS and MCTS needs to have at the very least a move generator in order to produce actions that can then be evaluated for their results.

YeGoblynQueenneOP6y ago

>> The MuZero training does not use MCTS, it merely observes sequences of moves/states/rewards.

The paper does say that any MDP could be used in place of MCTS but I don't think anyone seriously plans on using something else than MCTS for board games in the foreseeable future.

I'm confused by your use of the term "implicit tree search". Could you clarify?

j / k navigate · click thread line to collapse