In MCTS, what to do if I do not want to simulate till the end of the game?

Question

I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS implemented in Java from here, and I noticed that it takes a long time to actually reach a terminal node in the simulation phase.

So, would it be possible to simulate games up until a specific depth?

Instead of returning the winner of the game after running until the max depth, I could return an evaluation of the board (the board game is simple enough to write an evaluation function), which then back propagates.

The issue I'm having is in handling the backpropagation. I'm not quite sure what to do here. Any help/resources/guidance is appreciated!

Answer 1

Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards:

The leaf $s'$ position is expanded and evaluated only once by the network to gene-rate both prior probabilities and evaluation, $(P(s′ , \cdot),V(s ′ )) = f_\theta(s′ )$. Each edge $(s, a)$ traversed in the simulation is updated to increment its visit count $N(s, a)$, and to update its action value to the mean evaluation over these simulations, $Q(s,a) = \frac{1}{N(s,a)}\sum_{s,a\to s'}V(s')$ , where $s, a\to s′$ indicates that a simulation eventually reached s′ after taking move a from position s.