Leela-chess: Game result statistics

[jkiliani]

From 311 self-play games I generated so far, I counted 157 draws, 139 white wins, and 15 black wins. This strikes me as odd, considering that the first move advantage should be worth very little for a basically unskilled network, and even for a skilled one it should not be nearly this large.

Is it possible the search code has some sort of bug giving white an advantage over black?

Edit: From simply looking at the games, I would say white tends to move pawns a lot more than black, and due to the chaotic nature of the games those pawns regularly get promoted.

[amj]

I would definitely want to check this; unlike in go, where white gets points as compensation for black going first, i would expect two random chess players to be equally likely to blunder into the others king. This smells like a bad bug somewhere.

[jkiliani]

@amj I thought so too. Leela Zero had lopsided winrates in the beginning, but that was just a result of komi and black passing too early. This should not happen for chess.

@kiudee Did you look at your games, are the statistics similarly skewed?

@error323 Did you notice any irregularities between performance with black and white when evaluating the supervised net? Could the asymmetry be a result from the random policy head being filtered for legal moves and somehow creating a bias in that way?

[evalon32]

I have a theory (and some empirical confirmation):
UCTNode::link_nodelist() sorts the legal moves by policy score (descending), then by move enum (also descending):

     // Use best to worst order, so highest go first
     std::stable_sort(rbegin(nodelist), rend(nodelist));

This biases the search toward higher-numbered moves, i.e. play on the black side of the board.
I tried inverting this bias, i.e., sorting by policy score (descending), then by move enum (_ascending_):

   std::stable_sort(nodelist.begin(), nodelist.end(),
       [](const Network::scored_node& x, const Network::scored_node& y)
       { return x.first > y.first || (x.first == y.first && x.second < y.second); });

And lo and behold, black started winning more often. Out of 50 games with -p 100, the score was 27.5 : 22.5 before the change and 19.5 : 30.5 after the change.

[Error323]

Hmmm very interesting, if I understand correctly then: This implies that for a neural network fθ(s) with random weights θ and some board position s there are many legal moves with equal probability. This should not be the case, as if all probabilities have been reduced to 0 or something. I'm just speculating here, I'll investigate and come back with actual data :)

[Error323]

OK I'm back with some data. Observing the raw_netlist shows that indeed for a random initialized network all the probabilities are 0. In the case of a trained neural network (from our supervised data) the probabilities seem to be sane.

My conclusion from this would be that our method of generating random weights for the neural network is incorrect.

edit: This might even explain #5.

[jkiliani]

OK, so the supervised net shows no strange behavior regarding playing strength of white vs black? Then maybe we don't really have to change things, since as soon as the network weights are updated by reinforcement learning, the imbalance should be sorted out. Am I missing something here?

My main concern is that the value net would initially learn that white is far better than black in the starting position, so resignation should not be used until the position evaluation starts being reasonable.

[Error323]

OK, so the supervised net shows no strange behavior regarding playing strength of white vs black?

I didn't notice it, but also wasn't looking for that at the time. However, the findings above seem to explain the behavior you observed.

Then maybe we don't really have to change things, since as soon as the network weights are updated by reinforcement learning, the imbalance should be sorted out. Am I missing something here?

I think bootstrapping the trainingdata with random weights that do not produce random results on the neural network heads is very dangerous. It's hard to predict the ramifications, but I would strongly suggest that we halt the simulations, fix our random weight generator and restart from scratch, trashing all results so far.

My main concern is that the value net would initially learn that white is far better than black in the starting position, so resignation should not be used until the position evaluation starts being reasonable.

I think we should compute the resign threshold from a subset of the data similar to what AlphaGo Zero does. I'm not sure if this is already implemented, but I thought it was quite elegant.

[jkiliani]

I would strongly suggest that we halt the simulations, fix our random weight generator and restart from scratch, trashing all results so far.

Not disagreeing with you there, but this would be @glinscott's call. He seems to be currently implementing a way to evaluate networks. If there is a restart, we should also raise the move cap from 75 moves to a more sensible value like maybe 125?

Resigning should usually not be enabled at the very start. Leela Zero only had this enabled after it could count at least, and a chess AI similarly should not be allowed to resign until it has at least a basic idea on which positions are won, lost and drawn.

How are we getting the randomness for evaluation matches? You mentioned keeping Dirichlet noise active during test matches. I opened another thread about temperature implementation for the purpose of evaluation matches, maybe this could help also.

[glinscott]

@jkiliani thanks for the investigation! It looks like there is indeed some problem with the random weights. I'll take a look. And we will need to throw out all the games it looks like :(. Ah well, still in the alpha stages.

[jkiliani]

Glad to help! You can consider throwing games out, but it might not be necessary. Leela Zero had some horrific bugs in the beginning, but it turned out that reinforcement learning is very robust: Those problems just delayed progress, but didn't cause lasting damage.

I'd recommend at least trying to train one net from the current games to test whether the problem is mitigated if weights are no longer random. If that isn't the case, then maybe a restart is in order.

[glinscott]

Also, 125 moves is a lot for a normal chess game. The average human chess game is about 40 moves. Of course humans resign as well. Maybe in the beginning while the network is learning we can have a higher cap, but later I think we can move it way down.

[jkiliani]

Agreed, 125 is a lot, but for Go, @gcp decided to err on the side of caution here: A game of Go is almost never longer than 400 moves, but he set the hardcap at 723 moves. If the hardcap is reached for anything other than extreme exceptions, then the network will learn that it's not possible to win a long endgame. Also, what will the bot do when playing other engines working on FIDE rules?

[glinscott]

Yes, that's a good point. 125 seems like a good compromise.

[jjoshua2]

People looking for maximum strength against other engines will hook it up to sygyzy egtb anyway so maximum strength in endgames is less important than other places where we don't have an oracle, and where people want to see how a super ai handles openings and middlegames.
Looking at the graph here I felt 200 was a good point of diminishing returns, but 160 is almost as good and closer to the inflection point:
https://chess.stackexchange.com/questions/2506/what-is-the-average-length-of-a-game-of-chess

[evalon32]

For another data point, here's a histogram of game length in the KingBase dataset:
0-9 1.2%
10-19 7.3%
20-29 16%
30-39 26%
40-49 23%
50-59 13%
60-69 7.4%
70-79 3.2%
80-89 1.3%
90-99 0.55%
100-109 0.27%
110-119 0.13%
120-129 0.061%
130-139 0.031%
140-149 0.014%
150-159 0.009%
160-169 0.0043%
170-179 0.0017%
180-189 0.0013%
190-199 0.00049%
200-209 0.00019%
210-219 0.00024%
220-229 0.00019%
230-239 9.7e-05%

[jkiliani]

If it was only about maximum endgame strength I would agree, but the problem is that truncating a won position will impact the quality of the training data: A neural net trained on loads of such positions will think they're drawn instead. If such positions are achieved against the program with such a neural net, it will hold the "delusion" that it's only allowing a drawn position, while it's actually going to lose that endgame.

For the playing strength of an Alpha-Zero like engine, it's very important to accurately judge if positions are won, drawn or lost. Truncation means it won't learn this correctly on many positions. The game length statistics are slightly misleading here, since games between humans and Alpha-Beta engines are generally resigned when it's clearly a lost position. For a neural net based engine, it needs to see how to convert these wins at least in the beginning.

[Error323]

..., but it might not be necessary. Leela Zero had some horrific bugs in the beginning, but it turned out that reinforcement learning is very robust: Those problems just delayed progress, but didn't cause lasting damage.

I don't know man. It seems that given the bug, the first generation of games will be skewed massively towards white wins. The final solution fθ* might get stuck into some local optima because of it. _Every playout of every game played_ will sort the moves in the exact same manner. Except for every root node as that receives dirichlet noise. It will be very hard to find out.

[jkiliani]

The value head of the first generation net would definitely be skewed towards white, agreed, but Leela Zero went through several such phases as well: The Tromp-Taylor rules for Go specify that when both players pass consecutively, the game ends and is scored. In the very early nets, black used to pass randomly at times, and white could then win many games instantly by passing back (because of the first move compensation in Go). So for a while, the value net thought that white had a massive advantage.

What happened was that black learned not to pass early, while white "learned" to pass early in the hope that black would mess up and pass back. So we had a time when the net thought black had a big advantage. In the end, both players learned that passing early is bad, and the empty board evaluation got balanced as the nets got stronger.

It's highly unlikely that the final network would be in any way affected by what happens this early in the training. Local optima are only a problem if learning rates are lowered too early, and I presume you'll be using the starting reinforcement learning rates until the strength stagnates, correct?

At the moment, self-play is still early enough you could do a restart without a massive cost, so if it makes you more comfortable with the result, sure. I'm just mentioning that this most likely won't be the last major bug you'll discover, and you won't be able to restart the pipeline everytime this happens.

[Error323]

It's highly unlikely that the final network would be in any way affected by what happens this early in the training. Local optima are only a problem if learning rates are lowered too early, and I presume you'll be using the starting reinforcement learning rates until the strength stagnates, correct?

Hmmm I disagree here. This bug would severely skew the entire dataset in trainingstep 1. Which is the basis for step 2 and so on and so forth. It's not an issue that is related to the learning rate. The entire statespace is simply too big to probe fully. Having such a strong bias in the initial dataset will remain present for an unknown amount of steps and simulations. We can only hope it will ever dissolve fully.

I'd like to propose we keep trashing data until we atleast get a 50/50 winrate for black and white. This is easy to check and relatively cheap computationally.

[jkiliani]

My experience with Leela Zero is that reinforcement learning is remarkably robust, but I can see I'm not going to convince you there. If @glinscott shares your opinion and you decide on a reset, I would suggest you do it soon, so the people who contributed compute to running the client don't feel their effort is wasted. Ideally the server should be shut down asap in this case, and programmed to only accept games from the fixed client version. I stopped my client hours ago when the reset discussion first came up.

[killerducky]

I dumped the contents of Network.cpp outputs vector std::vector<float>& outputs = softmax_data;

One entry is 1.0 and all the others are 0.0. So indeed the random network initialization is not doing well.

Because the one single 1.0 will usually not be a legal move, by the time it reaches this code in UCTNode, every move has a value of zero, and this normalizing code doesn't do anything:

    // If the sum is 0 or a denormal, then don't try to normalize.
    if (legal_sum > std::numeric_limits<float>::min()) {

One quick fix would be to change this code to have an else statement that just assigns uniform probability to all moves. It should probably only happen for random nets.

Edit: Digging further, the policy_out vector has a very large range of values. Then the softmax sharpens this into 1.0 for one move and 0.0 for all others. Snippet of some policy_out values:

raw_policy -775.680298
raw_policy -942.498901
raw_policy -415.239441
raw_policy 393.050018
raw_policy -462.288116
raw_policy 92.670105
raw_policy -67.455200
raw_policy -577.989014
raw_policy 120.927155
raw_policy -494.193756
raw_policy 28.972923
raw_policy 1064.673340
raw_policy -134.970367

A quick fix for this could be set cfg_softmax_temp = 1000.0f to make the output flatter. Note the much more reasonable N: values in this debug output:

c2c4 ->       1 (V: 100.00%) (N: 8.793101%) PV: c2c4 b7b6
b2b4 ->       0 (V:  0.00%) (N: 8.405190%) PV: b2b4
f2f3 ->       0 (V:  0.00%) (N: 6.875527%) PV: f2f3
g2g3 ->       0 (V:  0.00%) (N: 6.453956%) PV: g2g3
d2d4 ->       0 (V:  0.00%) (N: 6.415429%) PV: d2d4
e2e4 ->       0 (V:  0.00%) (N: 5.559554%) PV: e2e4
h2h4 ->       0 (V:  0.00%) (N: 5.490494%) PV: h2h4
a2a4 ->       0 (V:  0.00%) (N: 5.388685%) PV: a2a4
c2c3 ->       0 (V:  0.00%) (N: 5.354068%) PV: c2c3
b1c3 ->       0 (V:  0.00%) (N: 5.001895%) PV: b1c3
h2h3 ->       0 (V:  0.00%) (N: 4.742374%) PV: h2h3
g2g4 ->       0 (V:  0.00%) (N: 4.340144%) PV: g2g4
d2d3 ->       0 (V:  0.00%) (N: 4.073405%) PV: d2d3
g1f3 ->       0 (V:  0.00%) (N: 4.049125%) PV: g1f3
e2e3 ->       0 (V:  0.00%) (N: 4.016016%) PV: e2e3
g1h3 ->       0 (V:  0.00%) (N: 3.859178%) PV: g1h3
b1a3 ->       0 (V:  0.00%) (N: 3.539085%) PV: b1a3
a2a3 ->       0 (V:  0.00%) (N: 3.263456%) PV: a2a3
f2f4 ->       0 (V:  0.00%) (N: 2.218552%) PV: f2f4
b2b3 ->       0 (V:  0.00%) (N: 2.160756%) PV: b2b3

Edit2: Of course the cfg_softmax_temp = 1000 would be only for the first few nets, it should stabilize quickly and we can go back to temp = 1.

[killerducky]

Value head has a similar problem, input to the tanh function has very large values, so winrate_sig ends up being just 0 or 1. This will make it impossible for the search to find checkmates.

As a workaround I put this in my code for now, similar to the cfg_soft_max_temp=1000 workaround:
auto winrate_sig = (1.0f + std::tanh(winrate_out[0]/100000.0f)) / 2.0f;

BTW I'm trying to test things using cutechess-cli, is this what I should be doing? If not can someone suggest how I should test things?

cutechess-cli \
-games 10 -rounds 1 -pgnout test2.pgn -debug \
-engine cmd=./lczero arg=-w arg=/home/aolsen/lcnetworks/latest.txt arg=-p arg=800 arg=--noponder arg=-n arg=-t1 arg=--randomize tc=1/30+30 proto=uci stderr=lc1.txt \
-engine cmd=./lczero arg=-w arg=/home/aolsen/lcnetworks/latest.txt arg=-p arg=800 arg=--noponder arg=-n arg=-t1 arg=--randomize tc=1/30+30 proto=uci stderr=lc2.txt \

[glinscott]

@killerducky would the value head affect things much with a random network though?

[glinscott]

I'm adding support for sending training parameters down to the client from the server, so we can set the softmax temp dynamically.

[Error323]

I think the underlying issue has todo with the default biases, means and variances during a random initialization. This fix will help, but we'd have to be careful to change the temperature back at the right time.

[jkiliani]

If this issue affects both heads, would this not have affected Leela Zero too? Or did it but we never noticed it since it was trained out early on?

[Error323]

I'm quite sure this affected leelazero too. It might even be the reason why the passing was performed so often? I wanted to test to be sure, but I was unable to find random weights for leelaz.

[jkiliani]

The very first net in the list should be random, i.e. d645af97.

[Ttl]

Here is a heatmap from random 5x32 weights:

Leela: heatmap
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   2   0   0   0   0   0   0 
  0   0   3   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0  43   0   0   0   0   0   0   0   0   0   0   0   0   0 
 13   0   0   0   0   0   0   0   0   0   0   0   0   0   0 927   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
  0   1   0   0   0   0   0   0   2   0   0   0   0   0   0   0   0   0   0 
pass: 0
winrate: 1.000000

Looks very non-uniform.

[jkiliani]

If I recall, it took quite a while until Leela Zero could reliably see ataris and capture stones, and heatmaps looking like this would certainly explain that.

[Error323]

Confirmed. The policy probabilities from my debugger:

[0] = {float} 0
[1] = {float} 0
[2] = {float} 0
[3] = {float} 0
[4] = {float} 0
[5] = {float} 0
[6] = {float} 0
[7] = {float} 0
[8] = {float} 0
[9] = {float} 0
[10] = {float} 0
[11] = {float} 0
[12] = {float} 0
[13] = {float} 0
[14] = {float} 0
[15] = {float} 0
[16] = {float} 0
[17] = {float} 0
...

edit: truncated

[brianprichardson]

I have scanned several large (CCRL 500K-1.5M games) computer v computer pgn collections and consistently the average number of move plies is pretty close to 140.

[jkiliani]

I have scanned several large (CCRL 500K-1.5M games) computer v computer pgn collections and consistently the average number of move plies is pretty close to 140.

That's good to know, and what is your conclusion from this information?

If you're trying to say a move cap of 70 would work for LCZero, I'd like to quote from the AlphaZero paper

Chess and shogi games exceeding a maximum number of steps (determined by typical
game length) were terminated and assigned a drawn outcome

"Determined by" does not mean "Set to" or "Equal to". On the contrary, it's a typical weasel word, and could be interpreted to mean "double the typical game length" or anything really. Leela Zero set this limit very conservatively at a much higher value than typical game length, and for a good reason discussed earlier here.

[killerducky]

@glinscott yes I think it's ok to leave the value head as picking 1 or 0 randomly. The RL process should quickly adjust it to be smoother. I think even leaving the policy alone the RL would fix itself but it's easy enough to use #72 for this.

Results of a tournament I ran with the workarounds to both policy and value heads.

grep Result test2.pgn | sort | uniq -c
     16 [Result "0-1"]
     13 [Result "1-0"]
     82 [Result "1/2-1/2"]

This was run with two other changes: TTable was removed, and no forced draw limit move count.
Edit: There was a third change, I disabled the OpenCL error.

I suspected TTable was the issue at first, turned out not to be the case. But I recommend removing TTable because it doesn't work well and introduces a bunch of strange behavior, especially when there is no tree reuse. LZ removed it awhile ago and replaced it with NNCache.

Here is the PlyCount of all decisive games:

[PlyCount "69"]
[PlyCount "43"]
[PlyCount "148"]
[PlyCount "16"]
[PlyCount "28"]
[PlyCount "11"]
[PlyCount "94"]
[PlyCount "80"]
[PlyCount "140"]
[PlyCount "11"]
[PlyCount "174"]
[PlyCount "252"]
[PlyCount "307"]
[PlyCount "229"]
[PlyCount "16"]
[PlyCount "43"]
[PlyCount "38"]
[PlyCount "284"]
[PlyCount "9"]
[PlyCount "8"]
[PlyCount "19"]
[PlyCount "46"]
[PlyCount "65"]
[PlyCount "20"]
[PlyCount "94"]
[PlyCount "161"]
[PlyCount "68"]
[PlyCount "351"]
[PlyCount "17"]

[jkiliani]

Surprising how few wins appeared in this tournament... I expected more decisive than drawn games, for an untrained network.

[kiudee]

[Ttl]

[jkiliani]

[kiudee]

[Error323]

[Ttl]

[jkiliani]

[Error323]

[Error323]

[Error323]

[jkiliani]

[brianprichardson]

[remdu]

[jkiliani]

[remdu]

[Error323]

[jkiliani]

[Error323]

[jkiliani]

[Error323]

[jkiliani]

[gcp]

[jkiliani]

[gcp]

[jkiliani]

[gcp]

[Ttl]

[Error323]

[Ttl]

[killerducky]

[jkiliani]

[Error323]

[jkiliani]

[glinscott]

[Error323]

[Error323]

[jkiliani]

[Error323]

[jkiliani]

[jjoshua2]

[Error323]

[jkiliani]

[jkiliani]

[Error323]

[jkiliani]

[Error323]

[jkiliani]

[Error323]

[jkiliani]

[killerducky]

[killerducky]

[jkiliani]

[killerducky]

[jkiliani]

[Error323]

[jkiliani]

[Error323]

[Error323]

[jkiliani]

[kiudee]

[jkiliani]

[Error323]

[jkiliani]

[jkiliani]

[killerducky]

[jkiliani]

[jkiliani]

[jjoshua2]

[Error323]

[kiudee]

[jkiliani]

[jkiliani]

[Error323]

[killerducky]

[Error323]

[killerducky]

[Error323]

[Error323]

[jkiliani]

[Error323]

[killerducky]

[glinscott]

[jkiliani]

[evalon32]

[jjoshua2]

[evalon32]

[jkiliani]

[jkiliani]

[jkiliani]

[jkiliani]

[Error323]

[killerducky]

[Error323]

[killerducky]

[jkiliani]

[Error323]

[jkiliani]

[Error323]

[Error323]

[jkiliani]

[Error323]

[jkiliani]

[evalon32]

[Error323]

[jkiliani]

[jkiliani]

[Error323]

[jkiliani]

[Error323]

[Error323]

[jkiliani]

[kiudee]

[Zeta36]

[glinscott]

[Error323]

[jkiliani]

[killerducky]

[Zeta36]

[Error323]

[Error323]

[jjoshua2]

[Error323]

[Error323]

[jkiliani]

[Error323]

[jkiliani]

[Dorus]

[jkiliani]

[jkiliani]

[jkiliani]

[killerducky]

[jjoshua2]

[Error323]

[glinscott]

[jjoshua2]

[jkiliani]

[jkiliani]

[Dorus]

[jkiliani]

[Error323]