Study Plan

Back Up an MCTS Simulation Path

Reinforcement Learning

Medium

Update MCTS edge statistics using a leaf evaluation. The path is a root-to-leaf list of dictionaries with keys state_id (string), action (integer), player (1 or -1), N (visit count), W (total value), Q (mean value), and P (prior probability). Each edge's statistics use the perspective of its stored player.

For edge $a$ , let $v_a$ equal leaf_value when its player matches leaf_player, or its negation otherwise. Update

N'_a=N_a+1.

W'_a=W_a+v_a.

Q'_a=\frac{W'_a}{N'_a}.

Here $N_a$ , $W_a$ , and $Q_a$ are the original statistics; primes indicate updated values. Return a deep-copied list of complete records in their original order, changing only N, W, and Q. An empty path returns an empty list.

Loading visualization...

Examples

Input: path = [{"state_id":"root","action":2,"player":1,"N":0,"W":0,"Q":0,"P":0.5},{"state_id":"child","action":1,"player":-1,"N":0,"W":0,"Q":0,"P":0.5}], leaf_value = 0.5, leaf_player = 1

Output: [{"state_id":"root","action":2,"player":1,"N":1,"W":0.5,"Q":0.5,"P":0.5},{"state_id":"child","action":1,"player":-1,"N":1,"W":-0.5,"Q":-0.5,"P":0.5}]

Explanation: The child edge belongs to the opposing player, while the root edge matches the leaf perspective.

Input: path = [{"state_id":"root","action":0,"player":1,"N":0,"W":0,"Q":0,"P":0.5},{"state_id":"bonus","action":3,"player":1,"N":0,"W":0,"Q":0,"P":0.5}], leaf_value = 0.25, leaf_player = -1

Output: [{"state_id":"root","action":0,"player":1,"N":1,"W":-0.25,"Q":-0.25,"P":0.5},{"state_id":"bonus","action":3,"player":1,"N":1,"W":-0.25,"Q":-0.25,"P":0.5}]

Input: path = [{"state_id":"r","action":4,"player":-1,"N":3,"W":0.75,"Q":0.25,"P":0.2},{"state_id":"m","action":2,"player":1,"N":2,"W":-0.4,"Q":-0.2,"P":0.6},{"state_id":"l","action":0,"player":-1,"N":1,"W":0.1,"Q":0.1,"P":0.4}], leaf_value = -0.6, leaf_player = 1

Output: [{"state_id":"r","action":4,"player":-1,"N":4,"W":1.35,"Q":0.3375,"P":0.2},{"state_id":"m","action":2,"player":1,"N":3,"W":-1,"Q":-0.333333,"P":0.6},{"state_id":"l","action":0,"player":-1,"N":2,"W":0.7,"Q":0.35,"P":0.4}]

Hint 1

copy.deepcopy can separate the returned records from the input.

Hint 2

Compare the edge player with leaf_player to determine the sign.

Hint 3

Use the updated visit count when calculating the new mean.

Requirements

Accept Python lists and dictionaries; no array conversion is needed.
Preserve the input path and all fields other than N, W, and Q.
Returned records must be independent of the input records.

Constraints

Each record contains exactly state_id, action, player, N, W, Q, and P.
State identifiers are nonempty strings; actions and visit counts are nonnegative integers.
Edge players and leaf_player are 1 or -1; leaf_value lies between -1 and 1.
W, Q, and P are finite numbers; P lies between 0 and 1.
Q is zero when N is zero, otherwise W divided by N.

Try Similar Problems

Initialize Legal MCTS Edge StatisticsEasy Select an Action with PUCTEasy Turn Root Visits into a Search PolicyMedium Compute the Policy and Value HeadsMedium Apply an AlphaGo Residual BlockMedium Implement the AlphaGo Policy-Value LossMedium Apply a Dihedral Go SymmetryMedium Score a Terminal Position with Tromp-Taylor RulesMedium Value IterationMedium Expected SARSAMedium Bradley-Terry Reward Model LossMedium RLOO (REINFORCE Leave-One-Out)Medium