Detailing requirements for new and improved MCTS

[oscardssmith]

• General Goals

1. Policy should only influence behavior for nodes with few visits
2. Monotonic
3. Fewer hyper-parameters
4. FPU sort of feels like a hack. The only actual information that we have at 0 visits is the P, so the term that deals with policy shouldn't need a special case at n=0

• At Root

1. Simple regret minimization

Current best effort
At root

In tree

[AlexisOlson]

Here's where the U term is currently implemented:

lc0/src/mcts/node.h

Lines 397 to 401 in 1eb0d56

	// Returns U = numerator * p / N.
	// Passed numerator is expected to be equal to (cpuct * sqrt(N[parent])).
	float GetU(float numerator) const {
	return numerator * GetP() / (1 + GetNStarted());
	}

Here's where the passed argument is computed:

lc0/src/mcts/search.cc

Lines 1028 to 1029 in 1eb0d56

	const float puct_mult =
	cpuct * std::sqrt(std::max(node->GetChildrenVisits(), 1u));

[farmersrice]

Fewer hyper-parameters

This should probably be relaxed to fewer hyperparameters OR equal hyperparameters and decent strength gain.

Also it might be the case that pst can be removed (set to 1) with the new formulas, since changing pst = changing the sharpness of policies. In the new formula, the behavior you could get from pst is approximately the behavior you would get from changing c_1 and c_3 (policies becoming more or less important in the search).

[kiudee]

The formulas in the first post are supposed to minimize simple and cumulative regret. Can we list the corresponding scientific papers?

[oscardssmith]

Good idea. Will do.

[Naphthalin]

https://link.springer.com/content/pdf/10.1007/s10472-011-9258-6.pdf is the paper given as the source of the current PUCT formula in the original AlphaGo paper.

[kiudee]

The original PUCT formula slightly resembles the one posted above, with a few deviations:

The variable Mi here is the policy of move i.

[isty2e]

Here is a slightly modified version of the formula, whose purpose is to have a few tunable parameters and removal of if-statements, and monotonicity of the m term.

c_att is added for numerical stability for p~0 cases, but can be removed. Probably this formula can be enhanced further for low-visit cases.

[Naphthalin]

Other PRs and issues concerning the PUCT formula and policies:

#796 #818 #791 #913 #918 #746 #743 #699 #1235 #1173 #1150

[Naphthalin]

As you can see I tried to collect all issues and PRs so far which discuss similar things, some of them showing that the people who have posted here so far aren't happy with the PUCT formula for quite a while :)

@oscardssmith what do you suggest on how to proceed here?