Question: Helping MCTS by calling the reward function on non-terminal node

[damucz]

First of all, thanks for the great library. Very clean implementation. I’m looking forward to further improvements.

Would it make sense to call the reward function for non-terminal nodes to help the algorithm prefer more promising nodes? In more complex board games, the state space is huge, and I'm usually able to evaluate to some degree how good the state is for the player at any given situation. That is, at least relative to the other states.

In the reward comment it says for a given state, but it is actually called just for terminal, unless I've read wrong.

[PaytonWebber]

Thanks for the positive feedback and the great question!

You're correct that in this implementation, the reward function is only called at terminal states to determine the final outcome of a simulated playout. However, there's definitely precedent and literature suggesting that heuristic evaluations at non-terminal states can improve MCTS performance, especially in large state spaces.

Progressive Bias / Priors

In my own experiments implementing AlphaZero, I've used "priors" predicted from a model's policy function to guide the tree search. Similarly, you could generate priors (perhaps via a softmax over heuristic scores) for each candidate child action at the expansion phase. Instead of starting each child node with a uniform value, you can bias the search using these priors. The PUCT formula when incorporating priors looks like this:

PUCT = C * P * sqrt(N_parent) / (1 + N_child)

Where:

• C is the exploration parameter.
• P is the prior probability of selecting that child (generated by your heuristic).
• N_parent is the visit count of the parent node.
• N_child is the visit count of the current child node.

Starting Reward (Heuristic Evaluations)

You could add an evaluate() method to the State trait, which would return a heuristic estimate of the expected reward. When expanding a node, you’d initialize children’s Q-values with these heuristic evaluations.

If you do try adding heuristic evaluations or priors, I’d love to hear about your experiences and any performance improvements you observe!