PUCT Selection

Problem

Select an MCTS child with PUCT and first-play urgency.

If the total visit count is zero return 0. Otherwise return the first unvisited action if one exists, else the argmax of W[a]/N[a] + c * priors[a] * sqrt(total) / (1 + N[a]), with ties going to the smallest index.

Hint

First-play urgency forces every child to be tried once before PUCT kicks in.

Test cases

case 1

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

expected: 0

case 2

in: [[4,1],[10,2],[0.5,0.5],1]

expected: 1

case 3

in: [[1,9,2],[1,1,1],[0.2,0.3,0.5],0]

expected: 1

case 4

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

expected: 0

Starter codePython

import math
def puct_select(W, N, priors, c):
    # Your code here
    pass

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