MCTS UCB Score Vector

Problem

Score every MCTS child with the UCB rule.

For child i with visits n_i (at least 1 for the exploration term) the score is wins[i] / n_i + c * sqrt(ln(parent_visits + 1) / n_i). Unvisited children use n_i = 1, so they get an optimistic bonus. Return the list of scores.

Hint

The exploration bonus shrinks as a child accumulates visits.

Test cases

case 1

in: [[5,2],[10,10],20,1]

expected: [1.0517719128157417,0.7517719128157416]

case 2

in: [[0,1],[0,5],10,2]

expected: [3.097027783406775,1.5850329303806088]

case 3

in: [[3],[4],0,1]

expected: [0.75]

case 4

in: [[],[],7,1.5]

expected: []

Starter codePython

import math
def mcts_ucb_scores(wins, visits, parent_visits, c):
    # Your code here
    pass

4 test cases · run your code against them in the editor