Each iteration runs Browne et al. Algorithm 2: TREEPOLICY descends by BESTCHILD while fully expanded, EXPAND adds one untried action, DEFAULTPOLICY plays uniformly at random to a terminal state, and BACKUP propagates the reward. Selection uses UCT_j = Xbar_j + 2*Cp*sqrt(2*log(n)/n_j), unvisited children valued Inf. Cp = 1/sqrt(2) is the Kocsis-Szepesvari value for rewards in [0, 1]. Both survey backups are provided: "sum" (Algorithm 2) and "negamax" (Algorithm 3, two-player zero-sum). Both final-move criteria: "robust" (most-visited root child, default) and "max" (highest mean reward).
Usage
morie_mctsr(
root_state,
actions,
step,
reward,
is_terminal,
n_iter = 200,
c = 1/sqrt(2),
seed = 0,
backup = "sum",
final = "robust"
)Arguments
- root_state
Starting state.
- actions
Function(state) returning legal actions.
- step
Function(state, action) returning the next state.
- reward
Function(terminal_state) returning a numeric reward.
- is_terminal
Function(state) returning TRUE/FALSE.
- n_iter
Iterations (computational budget).
- c
Exploration constant Cp.
- seed
SplitMix64 seed (mirrors the Python arm).
- backup
"sum" (Algorithm 2) or "negamax" (Algorithm 3).
- final
"robust" (most visited) or "max" (highest mean).
Value
A list with elements action, root_visits,
child_visits, child_values, n_iter,
c, backup, final, seed,
method.
References
Browne, C. B. et al. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1-43.
Examples
# a race to 5: add 1 or 2 per move; the reward is 1 for landing exactly on 5
r <- morie_mctsr(root_state = 0, actions = function(s) c(1, 2), step = function(s, a) s + a,
reward = function(s) as.numeric(s == 5), is_terminal = function(s) s >= 5,
n_iter = 300, seed = 1)
r$action
#> [1] 2