Entropy-guided exploration for better tactical capabilities

[kk2796]

I originally posted this idea in Google Forum and was encouraged to echo it here. That thread lays out an intuitive case that using entropy to guide exploration can yield highly efficient search strategies that cannot be realized with "success likelihood" and "visit counts" alone. For the skeptics, please feel free to peruse the original thread (or to see something a bit more concrete, skim down in this thread to COOLEST POINT OF ENTIRE POST IMO )

I'm not going to spend any more time arguing for this change; I think the strongest case for it arises from exploring how it could/should work. On that note - I've taken a bit of time to explore the math of this idea, and I'd like to lay out a plausible implementation. I do not claim this is an optimal implementation.

First, it's necessary to define entropy in the context of PUCT search. This is the context where the search is in state "s" and must choose an action "a" using probabilities that align with the various U(s,a) values of all actions. The action chosen will accord to a playout to the node associated with that action. There is already a good amount of information that's calculated and pulled together to compute U(s,a) for action a:

• Q(s,a) - the average of all value-head evaluations from prior visits to the node at a and its descendants
• cPuct - multiplier to increase the impact of exploration
• P(s,a) - the a-priori policy-head probability of action a
• N(s,b) - the number of times this state has been reached.
• N(s,a) - the number of times action a has already been chosen (always <= N(s,b)).

To this mix, I introduce the term E(s,a). E(s,a) is the entropy associated with the subtree rooted at the node of action a. The entropy of a subtree is the entropy of the distribution of probabilities of a playout from the root of that subtree reaching any particular leaf node (either an unvisited node or terminal "mate" node).
An algorithm for computing E(s,a) for subtree T:

1. Enumerate every possible leaf node that can be reached with a playout from the root node of T.
2. For each playout, computing the step-wise probability of each discrete action (that is, comparing magnitude of U(s',a') of each step to the sum of U(s',*) of all that step's sibling actions).
3. compute the product of all the playout's step-wise probabilities (from root to leaf) to attain the final probability of the playout
4. repeat 2-3 for all possible/legal playouts enumerated in (1)
5. compute entropy from this final set of probabilities, using information-theory formula for entropy of N probabilities:
   Entropy({p1, p2, p3, ... pN}) = (-1)⋅ sum[n in 1..N]{ pn ⋅ log( pn , baseN) }
6. if there is only one possible playout, e.g. the first visit to a node must visit that node, or there is only one legal response to a move, that equates to a set of a single probability {1}. Entropy is defined to be 0 in this case (in fact, {1} is the only probability set where entropy=0).

For those not familiar with the math here - this entropy calculation will always return a value between 0 and 1. The more uniform the probabilities are, the closer the entropy will be to 1; the more diverse the probabilities, the closer it will be to 0.
To illustrate, here are a few sets of 4 probabilities ("log4" indicates log base 4)

• low entropy {0.01, 0.01, 0.01, 0.97} (-1)⋅(0.01⋅log4(0.01) + 0.01⋅log4(0.01) + 0.01⋅log4(0.01) + 0.97⋅log4(0.97)) = 0.12
• moderate entropy {0.2, 0.3, 0.4, 0.1} = (-1)⋅(0.2⋅log4(0.2) + 0.3⋅log4(0.3) + 0.4⋅log4(0.4) + 0.1⋅log4(0.1)) = 0.92
• high entropy {0.25, 0.25, 0.25, 0.25} = (-1)⋅(0.25⋅log4(0.25) + 0.25⋅log4(0.25) + 0.25⋅log4(0.25) + 0.25⋅log4(0.25)) = 1.00
  Note - the final example is actually perfectly uniform and thus achieves the maximum possible entropy of exactly 1.

Before I move onto the next topic (what to do with E(s,a)) I should mention that I'm not entirely clear on a low-cost method to track entropy according to this definition. In fact, this may be the largest barrier to implementation. However, there are two reasons to think it may not be a problem:

1. as subtrees grow, the newfound bias toward exploring areas of low entropy should push the entropy values to climb faster than they would otherwise climb by chance
2. the manner in which I plan to incorporate E(s,a) into the overall U(s,a) computation will actually cause a subtree's entropy to become less influential as the number of visits to that subtree go up.

So - what do I propose we do with E(s,a)? No reason to draw it out:
Old formula without E(s,a)
U(s,a) = Q(s,a) + cPuct ⋅ P(s,a) ⋅ N(s,b)^0.5 ⋅ 1/(1+N(s,a))
New formula:
U(s,a) = Q(s,a) + cPuct ⋅ P(s,a) ⋅ N(s,b)^0.5 ⋅ 1/(1+N(s,a)⋅E(s,a))

Pausing for a quick FAQ:
Q: So, "voila" you've come up with a better search formula than Deepmind?
A: As has been the case in many other regards, I suspect Deepmind team's sole concern was to find a simple solution that was "good enough" to carry their thesis. I also suspect the benefits of entropy-bias are far higher depending on sharpness of game... so while this might've made a huge difference if A0 has looked at entropy for chess, it might have been negligible against Go and Shogi.
Q: Did... did you just shove the new E(s,a) factor onto the end and hope it would work?
A: Maybe. But hear me out: this winds up being pretty slick!
Q: Are you seriously wasting github developer's time with cheesy fake dialog? Shouldn't you get on with this?
A: Ah - yeah, good point.

So, as I alluded to in the FAQ - while this may seem arbitrary at first blush, it truly is cool how well it works:

1. It's 100% consistent with current behavior for unexplored nodes: both the number of visits N(s,a) and entropy E(s,a) have value of zero, thus N(s,a) = 0 = N(s,a)⋅E(s,a) = 0⋅0

2. It's almost identical to current behavior if distributions of probabilities are nearly uniform. In that case, E(s,a) will be very close to 1, and E(s,a)⋅N(s,a) =~= N(s,a). In other words, the math will only allow the behavior to deviate from typical PUCT search if there are areas of high entropy.

COOLEST POINT OF ENTIRE POST IMO (if you read nothing else, read this)
In one circumstance where the E(s,a) significantly impacts U(s,a) and deviates from A0/Leela results, not only does the E(s,a)-based result make more sense than the current formula, but it's so obviously more-correct that it seems the entire case for E(s,a) could stand on this example. The circumstance I'm alluding to is a chess move that corresponds to action a, for which there is just one legal response, a'.

Under the current/Leela/A0 approach to exploration, when action a is unvisited, N(s,a) = 0 and the exploration term for that action has small denominator of (1+0), giving overall exploration factor of N(s,b)^0.5 ⋅ (1/(1+0)) = N(s,b)^0.5 ⋅ 1 = N(s,b)^0.5. In other words, for as long as action a remains unvisited, as N(s,b) grows, the likelihood of this unexplored node being played will climb with sqrt of N(s,b). After the action a is visited, N(s,a') will be 1, and the exploration term will be abruptly cut in half, from factor N(s,b)^0.5 to factor of (1+N(s,b))^0.5 ⋅ (1/(1+1)) =~= (N(s,b)^0.5) / 2

Now consider what happens when E(s,a) is added to the equation. The U(s,a) value for unvisited node is the same as without entropy: N(s,b)^0.5 ⋅ (1/(1+0⋅0)) = N(s,b)^0.5 ⋅ 1 = N(s,b)^0.5. However , after action a, if we compute the entropy of the subtree obtained, we would find that the playout to root node of a' was forced to follow a 100% probability path to a single node. In other words, the subtree with a single forced move has the same E(s,a') = 0 as E(s,a) did for the unvisited node.

The effect is clear: if there is an unvisited node that leads to a forced response, visiting that node once has no diminishing effect on how good a candidate it is for a follow up visit. And IMO, nothing could be closer to what our human intuition tells us: it would be absurd to evaluate a position, see that it leaves just one legal response, and not be bothered to consider what that response would be.

This is more a continuation of point #3. Consider: what if instead of there being just one response that was legal, instead there was only one move that doesn't lose instantly. For example, perhaps the initial action corresponds to a pawn attacking a queen, with only one escape square open to the queen. In this case, the response "move queen to safety" won't have a "pure" 100% policy. But it certainly may have a policy that looks like {0.92, 0.01, 0.02, 0.01, 0.03, 0.01}. For once-visited nodes, these policies become the playout probabilities for the next visit; and in this example, the entropy of those probabilities comes out to 0.22.

For those who just read through #3, it should already be evident that this is going to yield a weaker version of what we saw in #3. Instead of the exploration term doubling, ie denominator increasing from (1+0) = 1 to (1+1) = 2, this low entropy will subdue the rise of denominator; it'll increase from 1.0 to 1.22 and a follow-up visit to this queen-attack node will only be slightly less likely than the original visit.

There's actually quite a bit more I'd like to add... For example, I have dreamed up a much simpler metric than entropy that would capture a lot of the same perks - but I'll stop here for a breath and leave those for a follow-up.

Thanks to those who read this all the way through!

[oscardssmith]

That's really cool!! My only question is if variance could achieve the same result as it would be a lot easier to back up

[ddobbelaere]

Very interesting idea.

@oscardssmith As we don't really want to increase the node structure even more, I would propose to first try it out with on-the-fly entropy calculations during each playout and see how that goes.

@kk2796 Do you want to try out to code it yourself, in which case myself or someone else can certainly give you pointers where to add/modify the code, or do you want someone else to do it?

[oscardssmith]

@ddobbelaere variance backup only requires 4 bytes (1 float) per node. On the fly entropy (or variance) will probably be pretty slow.

[kk2796]

I think it's almost self-evident that a naive "on-demand" approach (computing entropy dynamically each time it is needed) would entail an untenable performance overhead. If some form of local caching can't come to the rescue, it may be necessary to work with less expensive statistical approximations such as variance (which is more conducive to incremental aggregation vs wholesale refresh). That said, though I don't have the mathematical fortitude to prove this, I do feel the "root problem" is one deeply grounded in information theory and that entropy is the right/best metric to use in solving it. Other ideas may work, but my intuition is that their effectiveness would be limited by how close they came to approximating entropy.

@ddobbelaere I'd definitely prefer to leave the coding to others. I'm 99% data scientist and 1% developer. Downloading Leela's source (along with proper compilers and appropriate IDEs) and then personally trying to put this idea into code sounds like utter drudgery. I suspect I would need weeks, perhaps months, to produce something that was even functional. Even then, my resulting code would be deplorable, and, frankly, I would hate every minute of it.

Backing up a step though - I think there's some meaningful work that can be done before any coding changes (much less discussions of tuning/optimizations) are even on the map. Is there a way to run lc0.exe so that it performs a small fixed-node search (say, 100 nodes), and spools out some representation of the search tree after 100 playouts? That is, something which would allow me to see the tree structure (nodes and edges) as well as the value-head and policy-head outputs for each node? I know there are log options which will display statistics for a position, but as far as I know, one only sees the summary stats for moves of the root node (not the entire tree).

If I can start with that, I'd be able to run some simulations showing what the effect of entropy-bias would be on various positions. In theory, I can accomplish 3 things:

1. Verify that for wide selection of randomly positions, the E(s,a) factor has a negligible effect on U(s,a) most of the time.
2. Verify that the positions that are affected, and do experience a significant shift in U(s,a) values, are all positions where one would anticipate entropy to play a role. Furthermore, verify that the role entropy plays is to shift U(s,a) in the expected direction.
3. Run the simulation for a set of hand-selected positions where Leela is prone to blunder... these would preferably be positions that traditional engines spot the blunder with ease, but leela requires great effort to see them.

I think the first two of these would be most meaningful... however, the third would probably generate the most hype for coding up a solution that can be tested "for real", e.g. assessing ELO impact of the entropy-enabled code vs unmodified code in fixed-node competition.

I should also note that during this initial assessment phase, I could play around with other variants of incorporating E(s,a) into U(s,a) formula and/or add constants that allow the effect to be magnified or dampened.

TLDR: If there's a way to run Leela in a debug or verbose mode to print the entire search tree, including policy/value results of each node, please let me know!

[AlexGreason]

adding 4 bytes to each node (assuming it is only needed in nodes, not edges) is about a 2% increase in total RAM usage by my estimate. Not a problem.

[ddobbelaere]

I want to help you with the coding part, but after thinking for a while I found there is still an issue with the proposed formula.

For moves that have only one legal follow-up move, it holds that E(s,a) = 0. The issue is that those moves will completely usurp all the visits at some point as U(s,a) grows without bound.

This problem is so severe it needs to be sorted out first. My first naive thought would be to take E'(s,a) = E(s,a) + E0, with a fixed and yet to be determined constant E0 > 0, but I am curious if there are other, maybe more elegant solutions.

[oscardssmith]

Any chance of doing it with stdev? I think it will likely yield better results, but is also much easier to calculate and backup.

[amjshl]

Sounds like a very interesting concept, though the mathematics of it is not obvious/intuitive to me at all. Should'nt the entropy term be more coupled with Q(s,a)? Moves which are good with low entropy we would want to explore more, while moves which are bad and low entropy should be explored less and less. One way to look at it is if it is a force sequence of winning moves we want to play it while if it is a forced sequence of losing moves we would want to avoid it at all cost.

[ddobbelaere]

@oscardssmith I think that in the case of only one legal follow-up move the standard deviation is also zero (at least for every possible definition I can think of).

@kk2796 Please allow me to straighten the notation in line with the conventions in literature:

During each playout, we want to maximize the upper confidence bound Q(s,a) + U(s,a), with

Q(s,a) the mean action value of the move (expected outcome averaged over values of visited nodes).
U(s,a) = cPuct ⋅ P(s,a) ⋅ N(s,b)^0.5 ⋅ 1/(1+N(s,a)) a measure of uncertainty on Q that you propose to modify to cPuct ⋅ P(s,a) ⋅ N(s,b)^0.5 ⋅ 1/(1+N(s,a)⋅E(s,a)).

As an alternative to the original intention of the opening post, I propose to calculate the entropy (or standard deviation if you like that more) over the current visit distribution of the follow-up moves (and not over the upper confidence bound Q(s,a) + U(s,a) distribution). This is much easier to calculate on-the-fly and may be feasible (moreover, it doesn't contain recursion that is present in the original proposition, i.e., that E(s,a) depends on the entropy of the follow-up moves after that, etc.)

[kk2796]

@ddobbelaere

For moves that have only one legal follow-up move, it holds that E(s,a) = 0. The issue is that those moves will completely usurp all the visits at some point as U(s,a) grows without bound.

Yes, the most extreme effect of E(s,a) is when E(s,a) = 0. Two points I want to make:

1. The lower the value of E(s,a), the more extreme its effect will be. However, in the most extreme of all cases, E(s,a)=0, the maximum impact would be mathematically identical to considering the node as unvisited. So, while it is true that as long as a node has entropy E(s,a)=0, U(s,a) will "grow without bound", that "boundless growth" is no different from the value of U(s,a) that already occurs for as long as nodes remain unvisited, N(s,a)=0. One might object that the difference is that N(s,a) is bounded by the fact that N(s,a) is guaranteed to climb once U(s,a) grows enough to visit that node, while E(s,a) could remain at 0 even after the node is visited. That takes me to my second point...

2. A key aspect I think you've overlooked is that E(s,a) represents the entropy of the entire subtree, not just the immediate follow-up (I may start using the term "canopy entropy" to clarify this point). In the already-rare case where white makes a move and black only has one legal follow-up, white will almost certainly have multiple ways to respond to black's follow up, immediately increasing E(s,a) for the subtree to something > 0. There probably have been games that have reached positions where both a response and counter-response are limited to one move, but I suspect one would need to carefully craft any position where E(s,a) =0 after more than two visits.

Put together, 1 and 2 amount to "The most extreme effect of E(s,a)=0 is only as drastic as the effect of N(s,a)=0; and while N(s,a)=0 is guaranteed to grow to N(s,a)>0 with the first visit; E(s,a)=0 is also guaranteed to grow to E(s,a)>0, it may just take 2 or even 3 visits to do so".

I've got spotty availability this morning, but do intend to follow up on other points raised.

[kk2796]

@ddobbelaere
A quick one: I used several sources to better understand the PUCT algorithm (and, I'd hoped, to not sound like an idiot trying to express my idea). Unfortunately, I did not notice that one of those sources, from stanford (really, standford??), misrepresented the upper confidence bound formula. They also did so using a visually pleasing representation; thus their representation is what stuck in my head. However, as lovely a job as they did, I 100% concur that they got it wrong and what you wrote above is actual in line with the AlphaZero paper:

... at = argmaxa(Q(st,a) + U(st,a)) using a variant of the PUCT algorithm (47), U(s,a) = C(s)P(s,a)(N(s)/(1 + N(s,a)) ...

Thanks for pointing out the discrepancy; I'll aim to use the correct nomenclature going forward.

[oscardssmith]

One confusing thing is that the A0 puct formula is different than every other one, so they really shouldn't have called it that.

[ddobbelaere]

@oscardssmith OK, didn't know that A0 convention is actually non-standard :). As the lc0 codebase follows the A0 convention, it's probably still better to use it though. You're probably referring to the term "PUCT" and not to the fact that Q is not included in U.

@kk2796 Thanks for the clarification, it makes more sense now. Now I also understand why nobody was eager to calculate the entropy on the fly :).

I am still annoyed by one thing: Q(s,a) + U(s,a) compared to the Q(s,a') + U(s,a') of all siblings doesn't really represent the probability that a move will be played IMO (in that sense, MCTS is actually very deterministic, it will always pick the move that maximizes Q+U).

Another thing to note (but this is maybe merely a technicality arising from our lc0 convention that -1 <= Q <= 1) is that (Q(s,a) + U(s,a)) / sum(Q(s,a') + U(s,a')) is not what you want it to be (as some terms can be negative), but this can maybe be solved by considering Q+U+1 in the equations instead of Q+U I guess (although I am even less sure about the meaning in terms of probability in this case, but at least it's between 0 and 1 then).

I am still wondering if the entropy over the visit distribution doesn't also make sense. IMO it more corresponds to the probability that a move will be played. Moreover, briefly looking at the backup update equations lets me conclude they are doable (if we use visit distribution) and can be incremental (calculations at each step do not depend on the branching factor)! If we ever do this, we have to check numerical stability of course. I wonder what you or other people think about these considerations.

[ddobbelaere]

After thinking about the issue for quite some time, here are my new ideas:

1. I still think the issue E(s,a) = 0 with only one string of "one legal move only" moves has not been settled. Imagine the not-so-hypothetical case where we are winning, but there is a move where we stalemate the opponent, then E(s,a) = 0 of this move and it will be chosen at sufficiently high node counts. Also the case of a selfmate in one (where we force the opponent to mate us and he has only one move to do that), albeit less common, is an example.

2. Note that Q(s,a) of unvisited (in the sense of unexpanded) nodes is not available to us (it involves a NN query). So the original idea should read "Calculate the canopy entropy E(s,a) over all Q+Us of all visited nodes in the tree".

3. Combining ideas from @oscardssmith and @amjshl (that the entropy is more coupled with Q than with U), I propose yet another adaptation of the uncertainty term. Let S(s,a) denote the standard deviation of all the raw net eval Qs of all visited nodes in the subtree (so not only leaf nodes but also in-between nodes). Note that we can either count multiple terminal visits only once (only calculating the variance over unique nodes) or multiple time. Then I propose to include this standard deviation, which is another source of uncertainty on Q (the other one that is currently present is uncertainty because of low visit count), in the following way:

U(s,a) = cPuct ⋅ P(s,a) ⋅ N(s,b)^0.5 ⋅ 1/(1+N(s,a)) + c' ⋅ S(s,a),

with c' a scaling constant (c' = 0 reduces to the old formula). The variance S^2(s,a) can be efficiently calculated during the backup step (if we want to store both the variance and the mean in each node, for example both as float) with the numerically stable algorithm https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm, that was pointed to me by @oscardssmith in Discord chat.

Note the (imo) importance of calculating the variance of all the raw net eval Qs. On top of the more easier calculation during the backup step (compared to changing Q's of the in-between non-leaf nodes), it gives us a hint that the raw NN evals fluctuate wildly in the subtree (indicating possible tactical combinations that need to be explored more agressively).