Does Leela use some kind of quiescent search like traditional engines? If not, how are tactics handled at max depth?

[Engi Laszlo Zoltan]

Does Leela use some kind of quiescent search like traditional engines? If not, how are tactics handled at max depth?

[Jhor Vi]

I believe Leela handles tactics like normal positions that's why it's extremely weak in that department.

[Jesse Jordache]

You're getting the wrong idea if you're thinking in terms of depth.  Instead of wide, think long.  Where traditional engines have horizons, Leela has lines she just hasn't considered - for a reason, but if she wrongly decides to ignore a line as unpromising it can be hard to get her to examine it.

Btw, the "depth" that's reported by Chess GUIs is just an algorithm - they take the number of discreet positions she's looked at, a.k.a, nodes, and put it on a logarithmic scale with "depth" on the other axis.  It's there for people who are used to depth, since number of nodes doesn't really translate to anything until you're used to thinking in those terms.  But it's a total lie.

[Chris Whittington]

in practice, the strong traditional engines use SEE pruning in Qsearch, and they don't treat checks as special moves. SEE is actually inaccurate (it may overlook or generate false negatives and false positives). So, don't imagine Trad Engine Qsearch is perfect by any means. A neural network*ought* to be able (sooner or later in training) to be equivalent or better than traditional in quiescence department.

On Friday, 6 July 2018 08:53:20 UTC+2, Engi Laszlo Zoltan wrote:

Does Leela use some kind of quiescent search like traditional engines? If not, how are tactics handled at max depth?

Max depth traditionally means "out of memory if we go deeper, so don't. You presumably mean at the search leafs? Tactics are really evaluated by catching them lower down the tree. In ye olde days of engines, tactics were very much calculated at the tips. Nowadays savage pruning takes place way before the tips could be reached, and plenty of tactical stuff gets missed. It works because it works, surprisingly enough.

[Jhor Vi]

Does Monte Carlo have a tendency to terminate a search in the middle some capture sequence? If true then it doesn't sound good.

[Engi Laszlo Zoltan]

Yes, i was thinking QSearch in search leafs in order to avoid the horizon effect.

[Jhor Vi]

Can you enlighten us how Monte Carlo is horizon proof if it indeed terminate a search in the middle of some capture sequence?

[Chris Whittington]

from the questions you are asking, I am getting the impression you don't understand "search" in chess programs, MCTS nor minimax. Which makes me think, there's not a lot of point to reply. But, for others:

qsearch is inherently a minimax concept which doesn't sit well within an MCTS engine. In particular one that is designed to contain (eventually) a full on evaluator of all situations, terminal, mid tree, quiet or not quiet. It (LCZERO) doesn't have a "how quiet is this?" evaluator function, it doesn't have an algorithm for "middle of capture sequence". Everything is different in this paradigm. One problem with new paradigms is the continual clatter from old ways of thought, why does it do this or why does it do that, or even why does doesnt it use this that or the other concept. To which the answer is: the proof will be in the pudding, does it work, or does it not work? Or even, well write something yourself and see, this is uncharted territory ........

On Friday, 6 July 2018 14:45:18 UTC+2, Jhor Vi wrote:

Can you enlighten us how Monte Carlo is horizon proof if it indeed terminate a search in the middle of some capture sequence?

that's the way it works. it's sees as far as it sees, and as wide. MCTS and neural networks don'r prove "proofs" of anything. They are statistical machines. 

[Hanamuke]

Stockfish do treat checks as moves to be searched in Qsearch, and while imperfect, SEE still take into account pinned pieces and xray attacks. Of course, Qsearch will not find tactics involving quiet moves, such as checkmate threats, which a NN might see.

[Tom Idermark]

Monte Carlo Tree Search is quite different from Alpha/Beta (Minimax with pruning) in that is does not evaluate the position at every node (except win/draw/loose at the terminal node). Instead it does many "runouts" (random moves until a terminal node is reached) and uses the win/loose ratio to determine the "expected value" of choosing a move. A highly statistical method which allows the neural network to examine a large body of alternatives (somewhat statistically sparse unless large computing power is available when training). So, Leela probably doesn't even understand the notions of "quiescent" and "max depth" - she presses on until she wins or looses and then feeds that statistics up the tree. She definitely understands the concept of a search tree though.

[Dietrich Kappe]

In the case of A0 and Leela, it does not do "playouts." Value head gives a winrate instead of having to play out simulations, policy provides guidance on which moves to select for expansion rather than picking a move randomly. You might remove "Monte Carlo" here.

[Tom Idermark]

OK, I should have been more careful in separating general MCTS methods with its implementation in LZ0. I now remember the policy network described in the Alpha Zero paper and, well my bad. I still hope the OP got some useful information out of the somewhat different concepts at play here.

[Jeremy Zucker]

Hi Tom,

In pure MCTS, it is true that the game is played through to completion, but with Leela Chess Zero, the MCTS rollout is guided by the policy network and when she reaches a leaf node that she hasn't previously explored, she simply uses her value head to score the position as win or loss, and then feeds the statistics up the search tree.  Lather, rinse, repeat for 800 nodes (during training), and then use the MCTS stats to make the next actual move.

https://www.linkedin.com/in/jeremyzucker

--
You received this message because you are subscribed to the Google Groups "LCZero" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lczero+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lczero/3bcfa151-589a-4798-83a4-91b4b34f8e3d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jesse Jordache]

Speaking of quiescence as a search concept, and how, again, it's not really relevant to how Leela does things, I always wondered if it was really all that good an idea in situations other than when a minimax engine has a more-or-less fully flexible time in which to search.  But say you're analyzing a position on your own, and you decide you've seen enough, you'll turn it off, quiescence or no.  It might be useful in engine-on-engine competitions, but even then, the clock doesn't care whether you're in the middle of resolving a position full of potential checks and capture or not.

[Chris Whittington]

well, yes and no.

Stockfish generates checks only at the root of the Q_SEARCH

    // Initialize a MovePicker object for the current position, and prepare

    // to search the moves. Because the depth is <= 0 here, only captures,

    // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will

    // be generated.

then if not InCheck

// futility prune (chucks out moves that don't look good)

// Don't search moves with negative SEE values

Stockfish SEE pruning can definitely make mistakes in the pinned piece department, it correctly calculates x-rays though (I think). However, in case Stockfish, it is ALREADY pruning away some checks and other forcing moves way before QSearch depth is reached. Just looking at the code from the point of view of a chess programmer from ten years or more ago, it is hard to believe it works, but it does, very well, and as Marco says himself, all that counts is the statistics.

SEE can be modified to allow find checks, and find mate threats. Problem though is that the QSearch node count can easily begin to explode. As it is, Qsearch is responsible for about half of all nodes, so anyone just wanting to tack it onto MCTS had better consider that too. SEE search also requires alpha and beta bounds (not available in vanilla MCTS).

[Enqwert]

Can Leela reuse a tactical pattern that she learned on a2, b2,c2 (for ex, an xray attack), if the same there pieces are on f7,g7,h7 or are they considered as two seperate pattern that needs to be learned seperately?

[Jhor Vi]

Considering how extremely weak Leela is in tactics...why not?

[Dietrich Kappe]

Weak in tactics, you say? I’ve been reviewing the games of the recent nets more. One thing that strikes me is that leela avoids messy tactical lines, probably because the winrate is hard to predict in those positions.

Take for example this game:

https://blog.lczero.org/2018/07/03/bill1/

IM William Paschall was at first surprised by 24. Rb1, expecting 24. Qb3. Upon further analysis, he discovered some messy tactics which, while probably in Leela’s favor, she did well to avoid.

In some sense she reminds me of Capablanca and Morphy. While they could play crazy tactics, they liked to keep things nice and simple and under control.

So don’t take her preference for simplicity as a sign of tactical weakness.

[Chris Whittington]

Disagree in part, sufficiently to dispute conclusion. For alpha zero I analysed way back that the combination MCTS with NN (averaging effect of evaluating) differs to alpha beta (finding one pathway) means that AZ move choice steers towards chaotic regions of the tree where AZ has many tactical shots and the opponent has few. The analysis will also apply to LC0

So, you are right about play of crazy tactics, but not right about keeping things simple. LC0 will tend to play into complexity, its just that the resolutions of the complexity will favour LC0. You can liken it to AZ taking opponent into a minefield where the mines have a much greater tendency to explode the opponent.

[Chris Whittington]

On Saturday, 7 July 2018 05:12:53 UTC+2, Jhor Vi wrote:

Considering how extremely weak Leela is in tactics...why not?

Well, do it then, and show us ......

(I can think of numerous ways to improve Leela, and tacking on QSearch comes quite low down the list, if at all,  but if you want to try it, do so ...)

[Chris Whittington]

well, ok, but we need some word to describe the search. MCTS still applies for two reasons:

1. We do have rollouts, its just that they are not going to completion, but they are single line without branching, so our "nameing" should reflect that to distinguish say from alpha-beta, where we keep trying branches, trying to find the best one.

2. Until Leela policy and value heads produce god-like results (when Alpha-God will provide us with one main line for chess), the Policy and Value necessarily introduce error and randomness (monte carlo) with the effect of the MCTS to "reduce" this error. It's still monte carlo, but the roulette wheel or the card deck, whatever, have been fixed a little.

[Galaga]

I think "weak tactical play" was a reference to reproduceable blunders leela plays, and not any kind of "preference for simplicity" or "leading the opponent into muddy waters". 

I like the idea of having compilations like "Leela's Best" or "Worst of Leela" in the wiki somewhere, though I understand that in the moment there are more urgent problems to be solved.

Blunder happens.

[Jesse Jordache]

Since Leela holds her own or wins against all but the elite of the elite, I'm finding phrases like "her extremely weak tactical play" kind of funny.  You may as well say "well, everyone knows that if it's not a capture or a checkmate, Rybka doesn't know what to do with it" or "it's only in the last few years that Stockfish managed to overcome its positional Achilles heel".  In threads that feature Leela's games with other engines, I might throw that into the conversation just to see how it lands.  "Gull seems to understand the importance of an open file.  I'm surprised".

[Dietrich Kappe]

This makes sense. I've certainly seen enough chaotic tactical situations, but Leela has her hands on the steering wheel.

[Tom Idermark]

I agree we need nomenclature and descriptions to identify the differences between a ”traditional” engine, say SF, and this new breed of engines popularised by AZ and LC0. I have had some exposure to both concepts, but not studied SF or LC0 code so I’m going to try and hope it’s not a complete disaster :-)

First: One (the) major difference is that SF is ”pre-programmed” using many, many hours of human tweaking of a lot of move ordering and board evaluation functions while LZ0 learns those concepts by self play (using even more hours?). You could call this the engine creation phase (or something more descriptive - I am at a loss right now). For SF it ends up in a tight and fast C program that a number of chess programmers fully understands, for LZ0 it ends up in a huge number of network weights that nobody knows what they really mean. Compare this to the visual cortex V1, V2 … everyone knows they work a charm but nobody can explain really how and why … Below I’m only concerned with the engine operations once created ...

Both SF and LZ0 attempts to select the ”best” move at a root node (roughly current board state) by expanding that node into valid child nodes (board states after moves), then selecting one child node (by some algorithm) and trying to determine what’s the opponents best move is from this new position, and so on. The goal for both engines is to find a line of play that is ”God-like” (either by divine knowledge or brute force) and then make the move that takes the first step into this line of play. I’m aware this is painfully obvious for everyone but I want to make the point that both engine types performs a _search_ (in a vast search space - the tree of all possible moves) to identify (by good approximation) this best line of play.

There are two main conceptual differences in SF and LC0. The first is in the search algoritm used and the second one is in how the information which guides the search is determined:

SF uses alpha-beta search (with zillions of enhancements) which is heavily dependent on the accuracy of the eval() function - handcrafted by chess experts. Move ordering is also of utmost importance to avoid searching (potentially) fruitless branches, so human knowledge together with clever techniques are employed also there. The concept of ”depth” is easily understood as this is the numbers of moves (half-moves) before the algoritm ends a line (depth-first) and starts over with the next move at the top level. If this depth happens to coincide with an exchange, check etc. a Qsearch is used to extend the depth until a stable evaluation can be fed up the tree. So, in summary: the algorithm performs a depth-first search while pruning parts of the tree that cannot improve the given players position (given by the eval() function). 

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.

The MCTS algorithm driven by the NN (policy/value) thus makes for really exciting studies! What parts of the NN lights up (high weights) at different tactical situations? I guess someone could feed LZ0 any chess problem known, look at how the network layers lights up, find interesting feature extractions and, ultimately, learn humans how to play better chess. Some day ...

So, to the OP (great) question I would say: No (and she doesn't need to), because any quiescent state is (somewhere) encoded as a feature in the NN which impacts how the policy vector and value scalar are provided to the MCTS. How ”well" it is encoded and how much it directs the search is probably impossible to answer - some research in this would be very interesting!

… and much kudos to all you guys making this possible! Anyone interested in NN’s, AI and/or chess must find this exciting times! And to kingschrusher who produces these interesting LC0 analysis videos!

PS. When I write ”move”, I really mean a half-move, but I know that you know ...