MCTS UCT Select

Problem

Select a child with the PUCT rule used by AlphaZero-style MCTS.

Return the argmax of Q[a] + c * priors[a] * sqrt(sum(visits)) / (1 + visits[a]), breaking ties toward the smallest index. If no child has been visited, return 0.

Hint

The prior keeps rarely visited but promising children in the search.

Test cases

case 1

in: [[1,1],[1,1],[0.5,0.5],1]

expected: 0

case 2

in: [[0.2,0.3],[10,1],[0.5,0.5],1]

expected: 1

case 3

in: [[5,0],[0,0],[0.5,0.5],1]

expected: 0

case 4

in: [[5,0],[5,0],[0.5,0.5],1]

expected: 0

Starter codePython

import math
def mcts_uct_select(Q, visits, priors, c):
    # Your code here
    pass

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