Radical idea to get rid of cpuct and softmax temperature, and put an end to the endless cpuct tests.

[Videodr0me]

Why not get rid of the softmax normalization and cpuct altogether. The idea is that if policy is learned and NOT normalized the NN would automatically learn best cpuct indirectly via policy. Policy is currently multiplied by cpuct, so if the NN can adjust policy more freely (without the imposed sum-to-one constraint) it can indirectly choose which cpuct to use. An added bonus is that the NN would learn how to adapt this per position. If for a position a cpuct of 3.0 would be optimal the NN would just output a policy three times as high.

I don't know if this has already been tried and/or discussed. Also it might or might not entail a small change to the policy output layer, as i do not know if currently any constraints are (directly or indirectly) imposed at that stage (apart from the softmax sum-to-one constraint imposed when first fetching the output). Also it might or might not make learning more (or less) difficult. Another thing that would change is that cross-entropy might have to be adapted/replaced to have a learning target that also preserves the scale of policy output.

Could this be made to work? Any ideas?

[ddobbelaere]

Interesting idea!

I have a feeling it might be unstable though. If the a priori probability P(s,a) is high initially (after reset, random weights), it might 'usurp all the nodes' (at the low nodes counts used during selfplay, namely 800) and reinforce itself (via cross-entropy term). Normalization has the benefit that at least P(s,a) is bounded by 1 (and gives the other actions a chance), even if it is crap. But maybe not...

[mooskagh]

Would learning targets for P will be N_move / N_total ?
(E.g. sum of P's for legal moves will still be trained to be 1)

[ddobbelaere]

@mooskagh You're right. The cross-entropy becomes minimal if sum of all P's corresponding to valid move is 1. Ignore my previous post.

So, for this idea to work, the cross-entropy term needs to be changed for sure.

[Videodr0me]

Yes, the main obstacle is the training target.

The following thought experiment illustrates the main problem, that we need to solve. Lets say we just let the NN output cpuct, along with policy and value. Lets also say everything else remains the same, including softmax normalization Then if a training game is won, we dont need to change anything, great. But if we loose (or draw) we need to change cpuct, but in what direction? Up or down? We do not know, and thats the problem we need to tackle.

Translating this to an unconstraint (not softmax normalized) policy learning, it just boils down to the question of what our training target is. From search we only get a distribution of moves (arbitraritly scaled by visits) and it is not clear how we scale this, to what target that is.

Thats what this issue is about, collecting some ideas on how we could do this. Its a difficult problem, not only because DM did not find a way to automatically learn cpuct, but also because its not clear if we can learn this "hyperparameter" in an efficient way.

I have some vague ideas that are interesting but all have certain drawbacks. But without nudging this discussion in a certain direction, maybe its best to first collect some ideas, arguments and general assessment of such a scheme.

[Videodr0me]

Ok let me sketch my idea in broad terms (just using a scale augmented cross-entropy, this probably could be folded into one measure more elegantly). We need a target for a scaled policy vector. If we assume that a search in a position is more efficient if it finds the best move earlier than a search with a different cpuct that finds the same move, we can contruct such a target. Lets assume that we have a (true to scale) training target pi_s (of which pi is the normalized version) for the un-normalized policy vector p. Then:

(1) We augment the loss function:
l = (z-v)^2 - pi^T log(p) + c||theta||^2
by a term that measures the differences in scale of the training target :
l = (z-v)^2 - pi^T log(p) + d(sum(p) - sum(pi_s))^2 + c||theta||^2
d just like c controls the weigth of the scale of p (essentially the weight of cpuct).

(2) we compute pi_s by searching each position three times in training using p, su and sl as policy:

    p = p
    su = p *(1+ delta_cpuct)
    sl =  p *(1- delta_cpuct)
    
    with su_c = 1+delta_cpuct,      p_c =1 and     sl_c = 1-delta_cpuct 

(3) for each (of the three) searches we store the first visit (n_1) a move became the most visited and remained the most visited when search stopped. We store the three best moves (most visits at end of search) p_m, su_m and sl_m as well as the corresponing n_1s (p_n_1 etc.) in training data (along with the three visit distributions su_pi etc. - these are normalized).

(4) Calculating training target pi_s

  if z = 1 then  
      set = (p,sl,su) for which _m = p_m
      s =argmin_in_n_1(set)
      pi    = s_pi 
      pi_s = s_pi * s_c
    else 
      pi = p_pi
      pi_s = p_pi 

The condition z = 1 is a safeguard, most likely it can be dropped as learning how to get the same search result quicker might suffice regardless of game result.

Some notes. This is a crude sketch on how to constuct a target. Some details have to be thought of - for example if we use pi_s for actually playing the move in training games (probably) or just the normal p search result. But i hope the main idea is somewhat clear.

The main caveat is that game generation rate is only 1/3 of standard. But if it works (and thats a big if) we learn cpuct (so to speak, but now in the form of unconstraint policy) per position, which potentially might be much more effective both for learning (more data and more appropriate data as it pertains to search efficiency directly) and for playing strength. Also the policy_softmax_temperature parameter would be learned along the way.

Maybe there are other ways to construct such a learning target. Any ideas, discussion welcome.....

[ddobbelaere]

Interesting!

Essentially you want to guide the effective cpuct by trying to get quicker (earlier first visit) to the move that has the most visits in the end (at least in the case that the game is won (z=1), as you then argue that it was probably the best move).

[Note that you can restate this to: try to get quicker (earlier first visit) to the move that was chosen (irrespective of number of visits). If temperature picks up a killer move (with few visits), this also adapts cpuct (to a higher value in this case).]

I have a feeling that the optimal cpuct direction of change can be deduced by using some clever maths based on one search (based on the unnormalized policy), instead of three.

I'll try to work it out if I find some time.

[amjshl]

Interesting idea. What would delta_cpuct be? Would it be a hyperparameter that will be determined by experiments but kept constant throughout the training period?

I think there may be a way to calculate cpuct by running just a single search. This can be done by keeping track of the Q value, and parent visit count for a certain fixed number of visit counts for each of the child nodes. For example, lets say root node is x and its children are x1, x2 .... xn. Then for each of the x1, x2 .... xn nodes, whenever the visit counts reaches either of these values (lets say 0, 1, 10, 30, 80, 200 , 500...) we record the following data.
Q value at that visit count
N = number of visits of the parent node at that particular point.

Lets say, to determine the value of cpuct we just fix a fixed visit count "v" for which we would have wanted to find the most visited node.

we use the equation (Q+U)("0", "1", "10", ....)(new cpuct) = (Q+U)(v)(old cpuct) to find the value of the new cpuct. Find this "new cpuct" value for each of the visit counts (0, 1, 10 .... 500) and then pick the lowest cpuct (just for stability) and multiply the normalized policy by that lowest cpuct value.

Wonder if this makes sense to anyone.

[ddobbelaere]

@amjshl I have difficulties understanding your equation. For each visit count of the best move you want to optimize it to the "ideal" visit count "v"? For 0 --> v > 0, no value of cpuct will satisfy (as it was the initial Q that led to first visit of this node in any case). For 1 --> v > 1, cpuct should definitely be increased, but for let's say 500 --> v < 500, it is possible that cpuct must be lowered.

I'm confused. Also, I don't like the arbitrary additional parameter "v".

[amjshl]

To give an example, lets say node x4 (child of x) was the most visited node after 800 playouts using an old value of cpuct (cpuct_old). And lets assume that it became the most-visited node on playout number 600. We record the value (Q+U) when it promoted from becoming the second-most visited node to the most-visited node. Now we pick a playout number (say 80) where we would have liked it to have become the most visited node. We set the (Q+U(cpuct_new))(80) = (Q + U(cpuct_old))(600). Now we arbitrarily chose the value 80 where we would have liked it to become the most visited node. We could have chosen this number to be either of the other values (ie 1,10,30,200 or 500). and would have gotten a different value for cpuct_new. My take is that we pick the minimum of those values so that cpuct does not blow up.

The training target will then be the final visit_count(normalized)*cpuct_new. My hunch is doing this for multiple iterations will sort of stabilize the value of cpuct_new towards a fixed value (which will of course depend on the complexity of the position)

Not sure if this clarifies my post.

[Videodr0me]

@amjshl I think it is not that easy, as the most visited move is determined by the relative magnitudes of Q and U of all root moves. As MCTS is sequential in nature a static change of just the best move's Q+U(cpuct new) does not imply that when restarting the search with this new cpuct that move will (a) be found at the picked playout number and (b) that it will be the best move after all. Because in the search process all other Q+U change es well.

This does not mean that some sort of such analysis is impossible, maybe it can be made to work approximately and that might very well be enough. It could somehow collect search data (not only best move Q,U etc.) and then guess if a lower or higher cpuct would have found the move faster.... This is a very viable venue for research.

But that being said, essentially I just circumvented this problem by doing the two additional searches.

In regard to the question about cpuct_delta: It is basically the learning rate for cpuct. One could start with values like 0.01 or 0.1 and lower gradually depending on learning.

[Videodr0me]

Essentially you want to guide the effective cpuct by trying to get quicker (earlier first visit) to the move that has the most visits in the end (at least in the case that the game is won (z=1), as you then argue that it was probably the best move).

Yes. Let me clarify a detail about "earlier first visit". Its probably obvious, but just to state it more accurately:
Let n be a count of visits increasing by one for each iteration of the MCTS algo. Then n_1 is the smallest n_1 >0 at which the best move became best move and remained best move for all n >= n_1.

[mooskagh]

Not getting traction, closing.