how smart pruning works?

[OfekShochat]

how does smart pruning work?
thank you aot

[Ras]

how does smart pruning work?

By pruning only the moves that aren't smart: https://www.chessprogramming.org/Pruning

[OfekShochat]

um, I looked into the chessprogramming before that. its not what I needed. threre is smart pruning like leela uses.

[hgm]

Leela doesn't prune, does it? It uses MCTS. 'Pruning' is what you do in a search that would otherwise be 'brute force', i.e. search every move in every position up to a certain number of ply ahead. (Where this number of ply is then stepwise increased.) MCTS does not do that. It builds the tree node by node, not necessarily adding all daughters of one level before it starts adding daughters to a much deeper one. So it is highly selective extension, rather than pruning.

[OfekShochat]

I think leela does prune. thats what they call "edges". the ones they prune. uct in its pure form doesn't prune. and so does alpha beta in its pure form (minimax).
there is the policy net that points leela in the direction. maybe its the lowest policy values?

[hgm]

OK, I didn't know that. I thought that Leela was just an AlphaZero implementation.

I suppose there are two criteria that could be used for pruning. One is the policy network, suggesting the move is no good at all. It seems to me that pruning such moves would do more harm than good. The policy network should have discouraged their search enough to only provide a marginal advantage for not searching it at all. And it would then 'absolutize' any errors in the judgement of the policy head. While an unjustly discouraged move that is still explored at some very low level would allow one to discover it is actually good, and then overturn the policy decision.

A second criterion could be alpha-beta like; if a node already has one move that seems a solid refutation of what went on before, there is no need to explore alternative moves to see if they happen to be better. Pure UCT is very stupid in this respect.

[yurikvelo]

https://github.com/glinscott/leela-chess/issues/333
lc0 "smart pruning" = time management


https://lczero.org/dev/docs/timemgr/
search time budget = target search time ÷ smartpruning timeuse factor .
The estimated nps value is also passed to a smart pruning stopper for better protection against insta-moves.

Initially smartpruning timeuse factor is taken from init-timeuse parameter (default: 0.7)
It’s updated every move based on actual timeuse factor using exponential decay with a step of timeuse-update-rate of average moves (default: 10.0)
If it goes below min-timeuse (default: 0.3), it’s limited by this value.

LC0 instead uses Monte Carlo Tree Search (MCTS). To backup a little: A Monte Carlo method, in its pure form, would expand the root node using valid moves (i.e. create child nodes) and then perform many (say 10M) rollouts from each one using random (but valid) moves until a win, draw or loss is obtained. Say each rollout consists of an average of 60 moves, that is 600M moves per child node! The ”value” of each of those child nodes would be the average score over those 10M rollouts. The child with the highest ”value” (average score) is then chosen.

Anyone aware of the immense state space of a chess game realises that this still only samples a minuscule part of the full tree (so pretty useless). Still, rollouts using good chess engines with a slightly randomised move ordering / eval() are useful game analysis tools. Anyways, the MCTS improves on this by implementing a tree search algorithm and balancing the tree between exploitation (digging deeper) and exploration (look at new lines). This balance is achieved by the UCB formula which selects the next node to explore. The random rollouts and averaging of scores are, however, still present in the algorithm.

Although an MCTS implementation (such as LZ0) understands what depth it is currently at, it makes no sense at all to say that LZ0 searches to depth 32 for example. MCTS traverses a search space tree in a highly asymmetric fashion and is not at all guided by any depth limit (only ”Interesting, I’ll look deeper” or ”Hey, haven’t seen this, I’ll check it out”).

You may have noticed that so far no move ordering or eval() function is needed, and this is true but also the reason Dietrich suggested I remove the text ”Monte Carlo” from my previous answer since LZ0 does not use random rollouts as the MCTS calls for. And this is where the NN (the deeeep one) enters the picture.

Given the current board state (and 8 previous ones I believe), it feeds this data through a number of convolutional, ReLu … etc. layers until it produces 1) a policy vector which tweaks the UCB formula and therefore guides the MCTS in selecting the next node to explore, I’d say it is somewhat akin to the SF move ordering logic and 2) a value scalar that estimates the node ”value” that would have been obtained _if_ infinite bona fide rollouts had been performed, I'd say it somewhat akin to the SF eval() function … if one feels the need for a simple comparison.

[hgm]

So 'smart pruning' is basically just what we normally call 'easy move'?