How Leela uses history planes

[Tristrom Cooke]

The test position I am using arose after running some multi-engine tree generation code that I had written in Python to investigate the Jerome gambit. It used Main net 460 (Lczero, CPU only) as White, and Houdini 1.5 as Black.

1.e4 e5 2.Nf3 Nc6 3.Bc4 Bc5 4.Bxf7+ Kxf7 5.Nxe5+ Kxe5 6.Qh5+ Ke6 7.Qh3+ Ke7 8.Qc3 Bd6 9.d4

After this position, Houdini played Nc6, and Leela (after 2k nodes) played d5?? allowing the pin Bb4 winning the queen. However, when I ran the same Leela config in the Arena 3.0 GUI, it saw the pin and played the better move O-O. The difference between the two is that the history planes are filled in Arena, while my code was just providing the static board position. I confirmed this by setting up the board position in Arena (without the moves), and this changed the policy produced by Leela's network. I decided to investigate this a bit more closely.

Let's consider the position after 9...Nc6 10.d5
With history, Bb4 policy = 19.3%. Without history: Bb4 policy = 0.31%, which is a factor of 100x less!

So here is what I think is happening. The move 9...Bb4 is obviously not good because White can just take the undefended bishop. However the fact that Nc6 was played previously now supports the bishop move to b4, making this more likely to be a good move. Leela uses the previously played moves from the history planes to determine which squares have been recently supported, and makes moves there more likely by increasing the policy.

To check whether this is correct, I examined how Leela evaluated the Bb4 policy before and after 9...a5 10.d5 which also supported Bb4. With history, Bb4 policy = 18.4%. Without history, Bb4 policy = 0.74%. Making another move that does not support b4 does not improve the policy (e.g. 9...Ng6 10.d5 gives Bb4 policy of 0.06% with history and 0.12% without). These results are consistent with my theory.

I'm sure this isn't the only use that Leela makes of the history planes, but I haven't seen this possibility mentioned before.

--

Tristrom Cooke

[Deep Blender]

As far as I know, Leela is always trained with the history planes. This means, it has learned to make a judgment with this information. If you take it away, this important piece is missing and it hurts the judgement, because it is not used to this kind of situation. It is kind of as if someone was trained to navigate with a map, a compass and by having a look at the environment and now you are taking the compass away. This person is likely still able to navigate, but has a hard time to do so. It would for sure be easier for that person to have trained in such a situation from the very beginning and the person would have performed better.

In my opinion, that's not a fair comparison. You would need to train it from scratch without the history planes to have a fair comparison.

[Cezary Wagner]

It works like discussion context - previous words give you bias.

Whatever you can judge same situation differently if previous words are different even it does have sense to judge it - it generates superstition.

This helps to repeat move memory but It destroys thinking - since memory and thinking is opposite things.

If memory will be set by thinking it will work like cache it not it will destroy thinking.

I mean that same position can be seen differently by Leela since memory.

[Cezary Wagner]

It can be compare to relative thinking (using memory good or bad - knowledge and superstition) and absolute thinking (without superstition or false assumptions).

I think Leela is more relative thinking not absolute with memory planes (we no need any planes to judge position).

Same position can be seen by Leela in 1000 ways depend on previous moves.
All of these ways must be corrected to improve network thinking so it takes a lot of time.

Consider how much time take if you separately learn promotion of "a" and "h" pawn (it is mirror).
Or pawn promotion "a" with different king setups and moves - one rule can have 1 000 000 history moves combinations.

[Kostya M]

What if train new zero network without history planes, and see what it reaches. Would it be much faster? (because net would much smaller)?

[Stephen Frost]

On Thursday, July 19, 2018 at 12:26:36 PM UTC+1, Tristrom Cooke wrote:

So here is what I think is happening. The move 9...Bb4 is obviously not good because White can just take the undefended bishop. However the fact that Nc6 was played previously now supports the bishop move to b4, making this more likely to be a good move. Leela uses the previously played moves from the history planes to determine which squares have been recently supported, and makes moves there more likely by increasing the policy.

To check whether this is correct, I examined how Leela evaluated the Bb4 policy before and after 9...a5 10.d5 which also supported Bb4. With history, Bb4 policy = 18.4%. Without history, Bb4 policy = 0.74%. Making another move that does not support b4 does not improve the policy (e.g. 9...Ng6 10.d5 gives Bb4 policy of 0.06% with history and 0.12% without). These results are consistent with my theory.

I'm sure this isn't the only use that Leela makes of the history planes, but I haven't seen this possibility mentioned before.

I think this is a fascinating insight Tristrom.  Like you, I haven't seen this particular aspect mentioned previously.  It helps explain some of the behaviour we have all noticed from time to time. 

[Deep Blender]

The size would not be much smaller without history planes. Only the very first layer would change, because it would be trained with fewer input planes, everything else would stay exactly as is.

[Chris Whittington]

Yes. Well spotted. Confirmed quickly here on my set up too.

I've been waiting for a meta-discussion on the history planes ever since this project began, back in AZ time last year. But, unfortunately, nothing doing.

I did post way back, on several different forums, that I thought history was absolutely key to this zero approach. And tried tackling it through the "time" angle. As follows: board position alone gives us two dimensions for evaluation (and policy) to play with; basically mass (the pieces) and distance (their xy coordinates), if we parallelise to physics there's not a lot of science we can do with just "mass" and "distance", but if we introduce time, then we can start playing with many concepts (velocity, trajectory,  acceleration, energy, momentum and so on and so on, many of our fundamental equations). So, I think, at meta-level, this is what history is doing for us, it introduces the time dimension, and allows the neural net to play (how, we have no idea of course) with more concepts (of which we also have no idea). In chess, at high level, we often hear words like energy of a position, momentum and so on, so I think there is something here in this connection pieces-position-history (mass distance time).

Okay, so, what you seem to have picked up here, with your experiment, is some kind of "trajectory" concept. There's a change, in time, over the power exerted on particular squares; and you're suggesting (good suggestion imo) that the Policy is picking up this trajectory and getting interested in it. Extending the idea, that would mean, that when the search was, say, 10 moves deep, the Policy (and Eval) are picking up a trajectory theme (if the tree sequence is good, so to speak), which is almost a "plan of action", it can feel a kind of heat map flow from Pos(0) to Pos(10). I guess a smart net would be able to develop a concept of "progress" or "doing something sensible" over the entire history move sequence. Likewise an 'I am going nowhere" concept, and a "my position is falling apart" concept.

Sorry if I am leaping forward in giant steps here, but it tends to be the way my neurology works. Also I been thinking about this for a long time without any sparring partner on the same wavelength!

Leaping ahead even more, if the nets have time-history trajectory concepts of "going or not going places or staying the same", it can also begin to develop ideas about fortress positions. In fact it was the fortress positions in the AZ Stockfish games that launched me down this thinking path in the first place. How did AZ understand fortresses when not understanding fortresses is a big fatal flaw in hand crafted evals? That was the question. I'm sure "history" and thus the time dimension, is the answer. Which in turn would mean that, if time history is so important, we can think about presenting inputs in some different ways to try and accelerate the net exploiting this stuff.

I'ld be really interested in your thoughts, with apologies for jumping off into the far distance ....

[abcdan]

This surprises me that Leela uses history to evaluate a position.  A position should be evaluated the same way no matter what moves precede it.  History is irrelevant when determining the best move in any given position and Leela will eventually realize this.  (Don't we want Leela to play the same best move in any position regardless of how it got there?)  Why wait for the NN to come to the conclusion that these data points that it's getting fed are useless noise, when we can save it a step by not feeding it in the first place?

[Enqwert]

From human point of view using recent history to decide next move makes sense very well. For example if there was a capture in some square,first we automatically check if  we can recapture the piece on the same square before considering other moves or as in your example if the opponent is increasing his/her control in some squares or lines, we first check if there is a tactic related to their increased control over the square or lines or If there are new open lines, we focus our attention to that lines. So it seems history planes serve as some kind of search assistant to focus search. They will introduce some bias, but Alphazero also used them believing they benefit more than they harm. 

[Jerry Vaughan]

Something that's been bugging me, maybe someone can shine some light on why this doesn't matter: doesn't Leela need every single position from the game in its history panes? Three-fold repetition doesn't have to occur in consecutive plys. 

[Deep Blender]

AlphaZero is also using eight history planes for several of its inputs. It is not unusual to feed neural networks with auxiliary data which might help to guide the neural network. I also believe that the history planes may not be needed, but they help for sure to guide the learning process and very likely help to accelerate it.

[abcdan]

This explanation makes sense.  Thanks.

[Kevin Kirkpatrick]

I wonder if the problem is that history is being done half-way.  People want a Leela that plays chess very well, but they also want an engine that can provide insightful/accurate analysis of standalone position.  Perhaps history should be ALL for a NN that is geared for optimal game-play; and NOTHING for a NN adept at positional-analysis.  

ALL: Each position is described by the entire series of moves that led up to it.  There is no encoding of repeat positions, en pessant, castling, or 50-move-draw rules.  The NN simply learns to infer them from the moves that led to current position (so NN learns to play chess similar to how it has learned to play temporal games like Quake).  This is, IMO, a more "zero" approach, and does away with a lot of the uglier aspects of current gamestate encoding.

NOTHING: A position is described with no history.  En pessant and castling-rights specified directly; no repeat-position or 50-move-draw-rule.

If one NN is desired that is optimized for neither but does both relatively well, then training data can be split 50/50; half the time position is presented with full game history, and half the time it's presented as standalone/history-free.

[Cezary Wagner]

Not at all history for human is not need at all. If you not understand position and play from memory it is bad.

It leads to absurd like grandmaster in book talks that some GM Seirwan move is very bad at start of his book but on the end book he talk that it is excellent because it come from different move.

[Cezary Wagner]

50/50, castling, 3 repeats is part of position but not history.

Do you understand it in such way or whant explain that history is castling (but it is not).

[Cezary Wagner]

You do not understand side effect of such learning.

This learning lead to memorization not to generalization/thinking.

You can learn much faster but you will not teach thinking.

Try to memorize book about programming - you probably will be much better than me in programming knowledge (I am programming expert and play chess very good).
Whatever you will no write any complex code and I will beat you in 2 days with solving most problems :)

You will spend month on solving problem and do ugly code - what I can creatively invent in 2 days and write fast and clear code.

I call this "mindless learning" (overlearning since understand of rules) - If Leela can play 3000 ELO with mindless learning - what Leela will play with creative/thinking play 4000 ELO?

[Chris Whittington]

History is not irrelevant to the search algorithm, either policy or evaluation, when up in the tree somewhere. Read my earlier post for the reasoning.

Btw, this "discussion" posited below has been going on for at least 20 years. Some people think chess is about positions, each one to be discretely analysed and an objectively best move with an objectively accurate evaluation found. Others think that chess is a game made of many connected moves. Others think that there is no such thing as an objectively best move, nor an objectively best evaluation. I decided to stay well out of those discussions for the same reason I steer clear of is there or isnt there a god and who cares anyway discussions. 

As to the use of the history planes. The proof will be in the pudding. Which is not yet cooked, and anyway requires a control experiment against a no-history engine. Many things seem weird in AI, things work when intuition says they shouldn't and vice versa and so on.

[Chris Whittington]

The neural net doesn't flag up repetitions. This is a task for the search.

[Chris Whittington]

Leela design brief does not include "what people want". The idea was to see if the AZ approach could be repeated by a distributed effort, also partly to fill the hole created by google not revealing all data in their paper. Could an AZ really beat Stockfish given "fair" test conditions, where "fair" probably means allowing SF developers to set up the SF hardware and so on.

There's no reason why Leela should have to lose the history plane concept, especially if it works. Why not ask the GUI designers, Arena or Cutechess to modify their interface to provide some sort of frigged or null history? And leave engine designers to concentrate on engines.

[Cezary Wagner]

What is you chess ELO and chess understand my is about 1700 ...?

https://lichess.org/@/Cezary_Wagner

Every 100 points you will think differently.

Definitely chess position not depend on any chain of moves - there is not such discussion in chess.
Position in castling rules, pieces setup and 50/50 rule and previous positions (three position repeat).

No matter if 1. Nf3 e5 2. e4 Nc6 or 1. e4 Nc6 2. Nf3 e5 or 1. e4 e5 ... or 1. Nf3 Nc6 ...

Some moves matter since can be forcing other moves but after move is done - it is no matter what move is done.

50/50 rule is very rare but possible (people not plays draws since it consume brain power).

[Chris Whittington]

When I last played serious rated chess, weekend tournaments and chess leagues was in 1971, about. Ratings were national at that time, and I got mine up to 221 BCF before stopping. 221 BCF is about 2400 FIDE. A lifetime of not playing means however that my opening theory is now hopeless and a career writing and analysing chess programs has shot my chess thinking to hell, one needs to approach chess in a very different way than when playing. Programming is bad for candidate move selection and bad for tactics, mostly because one gets very lazy. So, I have good meta understanding and good positional but would probably be a tactical disaster nowadays, through sloppy overlooking things.

And yes, you are quite right that each 100 ELO points brings a new level of thinking. 200 ELO points difference can put two people on such a different level that communication doesn't work even! However chess is not as bad(?) as Go which has even more understanding levels to conquer.

I disagree with you on move history.

[Deep Blender]

Where did I claim that this may not have unwanted side effects? This is one way that is known to work very well. Even though using Monte-Carlo tree search in combination with neural networks has just recently been shown to be a viable approach for very complex problems, there have already been impressive improvements. Those improvements keep coming and may lead to solutions which could make those history planes obsolete.

According to your suggestion, the results from Leela, but also the ones from AlphaZero, were achieved through memorization and not generalization. I don't agree with you on that one.

[Enqwert]

As human we always pay more attention to the recent moves subconsciously.  It is like an heuristic to cut calculations and helpful where you dont have much time to calculate everything. It can lead to errors like not paying attention to a pawn pin that was built 20 moves ago. I am not saying it is optimal play, it is just practical in most circumstances. Leela  often search positions at speed 1/1000 of a A/B engine, so usage of some methods like history planes may be helpful to  narrow/focus calculations. As can be seen from Tristrom Cooke's example and many tactical tests, inclusion of history makes Leela's tactically stronger. However when Leela policy function becomes very strong, it  may recognize patterns very well and eliminate irrelevant moves quickly and may not require a history we will see.

On the other hand I believe Leela can learn not to use them if they are not helpful.

[Cezary Wagner]

It looks you plays very good.

You can disagree that history of moves does not impact position whatever each move is just result of position not moves before.

This not true if you plays endgame but it is very rare 50/50 more possible in three repeats.

[Tryfon Gavriel]

Chris - amazing peak rating there BTW - congrats!.

For anyone that is not aware of this outside of the UK - ECF 221 is a massive achievement in British Chess rating terms! My peak rating is 212(A) in July 2014 and it would be very difficult for me to go up from my current 206 rating because I am playing usually Board 1 for Muswell Hill which is in a super strong league - Middlesex Div 1.  

Cheers, K

[Cezary Wagner]

You talk about yourself - it is superstition - I am not looking to any recent moves - only to last move. I am play chess very good.

It is not heuristic to "cut" and not see the best moves - two, three, four, five moves impact whole position you should not skip important calculation.

Such position change mean win or loose in the most of games.

History moves helps to learn fast basic chess but not to be master.

[Cezary Wagner]

I does not apply to blitz chess which is different from classic or rapid - in blitz you play using memory only in the most positions or intuition.

[Chris Whittington]

Thanks Tryfon, just looked you up on Facebook and noticed NW London! Did you ever play at the Prompt Corner? I misspent a great deal of my youth there, but that place (and also played for the Working Men's Chess Club, I think it was called, in the leagues) was responsible for me getting gopd very fast, it was a sort of live breathe eat chess 24 hours a day. Shame it closed, because that was the end of an era, for sure.

[Chris Whittington]

Well, I disagree. I think everybody is stuck thinking with an underlying, unthought assumption. Everybody discusses this as if they are thinking about the position at the root of the tree. But that isn't what either we humans, and certainly not programs do. We think about a variation, so in reality we're thinking about a position some way down from the root. In which case HOW you got there is important. Comparing BACK TO the root position is important Did I make progress, Am I stuck? And so on . For a program, this back trajectory can be very useful to know about (although hand crafted programs don't really try to use this information in any detail). 

[Tryfon Gavriel]

Hi Chris

I didn't myself - I have played for multiple north london clubs though - Barnet, Muswell Hill, and in the past Wood green. I used to play a little blitz chess at Chequers but wouldn't do that trip across london nowadays!

Is this you in this picture I found of "Prompt corner"  by any chance :

https://www.gettyimages.co.uk/detail/news-photo/patrons-of-the-prompt-corner-cafe-in-highgate-enjoy-a-news-photo/103095306#/patrons-of-the-prompt-corner-cafe-in-highgate-enjoy-a-coffee-and-a-picture-id103095306

It indicates "Patrons of the 'Prompt Corner' cafe in Highgate enjoy a coffee and a game of chess, London circa 1970. Prompt Corner was formerly a bookshop owned by Author George Orwell (1903-1950) before it was turned into a coffee house"

Cheers, K

C

c