MCTS for non-deterministic games with very high branching factor for chance nodes

Question

I'm trying to use a Monte Carlo Tree Search for a non-deterministic game. Apparently, one of the standard approaches is to model non-determinism using chance nodes. The problem for this game is that it has a very high min-entropy for the random events (imagine the shuffle of a deck of cards), and consequently a very large branching factor ($\approx 2^{32}$) if I were to model this as a chance node.

Despite this issue, there are a few things that likely make the search more tractable:

1. Chance nodes only occur a few times per game, not after every move.
2. The chance events do not depend on player actions.
3. Even if two random outcomes are distinct, they might be "similar to each other", and that would lead to game outcomes that are also similar.

So far all approaches that I've found to MCTS for non-deterministic games use UCT-like policies (e.g. chapter 4 of A Monte-Carlo AIXI Approximation) to select chance nodes, which weight unexplored nodes maximally. In my case, I think this will lead to fully random playouts since any chance node won't ever be repeated in the selection phase.

What is the best way to approach this problem? Has research been done on this? Naively, I was thinking of a policy that favors repeating chance nodes more over always exploring new ones.

Answer 1

You can try using an "Open-Loop" MCTS approach, instead of the standard "closed-loop" one, and eliminate chance nodes altogether. See, for example, Open Loop Search for General Video Game Playing.

In a "standard" (closed-loop) implementation, you would store a game state in every normal (non-chance) node. Whenever there is a chance event, you would stochastically traverse to one of its children, and then have a normal node with a "deterministic" game state again.

In an open-loop approach, you do not store game states in any node (except possibly the root nodes), because nodes no longer deterministically correspond to specific game states. Every node in an open-loop MCTS approach only corresponds to the sequence of actions that leads to it from the root node. This completely eliminates the need for chance nodes, and results in a significantly smaller tree because you only need a single path in your tree for every possible unique sequence of actions. A single sequence of actions may, depending on stochastic events, lead to a distribution over possible game states.

In every separate MCTS iteration, you would re-generate game states again by applying moves "along the edges" as you traverse through the tree. You also "roll the dice" again for any stochastic events. If your MCTS iteration traverses a certain path of the tree often enough, it will still be able to observe all the possible stochastic events through sampling.

Note that, given an infinite amount of time, the closed-loop approach with explicit chance nodes will likely perform much better. But when you have a small amount of time (as is the case in the real-time video game setting considered in the paper I linked above), an open-loop approach without explicit chance nodes may perform better.

---

Alternatively, if you prefer the closed-loop approach with explicit chance nodes, you could try some mix of:

• Allowing MCTS to prioritise promising parts of the search tree over parts that have not been visited at all (i.e. do not automatically prioritise nodes with $0$ visits). For example, instead of giving unvisited node a value estimate of $\infty$ (this is how you could interpret the automatic selection of them), you could give them a value estimate equal to the value estimate of the parent node, and just apply the UCB1 equation directly.
• Use AMAF value estimates / RAVE / GRAVE in your selection phase. This allows you to very quickly learn some crude value estimates for moves that you have never selected in the Selection phase yet, by generalising from observations of playing them in the Play-out phase. I have noticed that the "standard" implementation of RAVE / GRAVE, without an explicit UCB-like exploration term, does not mix well with my previous suggestion of using a non-infinite value estimate for unvisited children. It may be good to consider a UCB-like variant with an explicit exploration term instead.

Answer 2

I would have a look at progressive widening, which was created to address the problem of applying MCTS to continuous stochastic environments. That is, where the probability of encountering the same state twice in simulating a chance node is $0$.

The original paper for DPW (Double Progressive Widening) can be found here https://hal.science/hal-00542673v2/file/c0mcts.pdf. DPW addresses the case where both action and state spaces are continuous, but you can ablate it if you only have or the other.

The main idea is that you expand the chance node a few times and then revisit those expansions. When you've saturated existing outcomes according to some hyperparameter, you then randomly sample the chance node.

It has a few limitations, for example the rate at which you sample new nodes is fixed and has to be determined experimentally. In some environments, the optimal rate is dependent on the state itself which leads to more complex techniques. For your problem though, it sounds like it may be a good fit.

Answer 3

If you have that sort of a priori knowledge about your environment it, as you said, will simplify the problem substantially. From what I gather you have done a good amount of background research and simply want to apply UTC MCTS(or similar) to the environment. You mention that "chance nodes won't ever be repeated in the selection phase".

If I understand what you are asking correctly, you can simply use what you know to alter the way you search nodes of the tree. I.e you can essentially act greedily wrt the initial chance nodes and then slowly decay that search strategy as the training progresses(to avoid convergence to local maxima).

I encourage you to dig a bit deeper into the methods around exploration vs. exploitation as there may be an elegant solution to this problem in particular.