Neural network evaluation for a Monte Carlo Tree Search engine

[dangi12012]

The idea of tuning a NN is rather simple, and doesn't really require any advanced math. You just determine the effect of a small change in each weight on the Mean Square Error of the output. Then you change the weights in proportion to how much effect they have, to make the LSE go in the desired direction.

This!
Some things are linked here that take 40 pages to describe how NNs work.
NN math and training fits on a half napkin.

[j.t.]

NN math and training fits on a half napkin.

Sure, but writing something with the least amount of words, and teaching someone the same thing are two very different things. Especially if you consider different starting points. Maybe someone has never thought about a multivariable gradient before. Additionally, it is often much better for truly understanding a concept (and finally building new things upon it) to comprehend how people thought of it/created it in the first place.

[algerbrex]

Some things are linked here that take 40 pages to describe how NNs work.
NN math and training fits on a half napkin.

True, but the understanding and background knowledge that's required to properly understand said math doesn't really fit.

For instance, I encountered the mathematics behind neural networks a couple of years ago, and while it was all neat and self-contained, I didn't have the necessary background to understand the concepts involved. I had no clue how any of it worked. It wasn't until a couple of years later after completing my multivariable calculus course, that I could actually go back and look at the math and realize how all of the pieces of the puzzle fit together.

The idea of how to train a neural network only seems relatively straightforward now to me because of the many math courses I took the past several years before.

[RedBedHed]

There is Neural Networks For Chess by Dominik Klein:

https://github.com/asdfjkl/neural_network_chess

covers A0, Lc0, NNUE.

And there are the A0 papers:

https://www.chessprogramming.org/AlphaZero#Publications

Bon chance with your engine.

--
Srdja

Oh wow, nice! Thank you so much! I know what I am reading tonight.

[RedBedHed]

But I am a total novice when it comes to neural networks.
...
Does anyone out there know of resources that provide full technical explanations of the theory, algorithms, or data structures used for this kind of learning? Textbooks, papers, videos? Relevant types of math? Machine learning libraries that are compatible with a C++ engine? Experience with training on a budget?

I found the following series of YouTube videos very educational when I first started to learn how neural networks work:
- What is a gradient? Part 1 and part 2
- Playlist that introduces and explains neural networks, it is based on this free online book, which I can also recommend. I admittedly had to watch the videos multiple times and read the book closely before I fully grasped how everything worked. But I still think that this is probably one of the best ways to learn about neural networks.
This covers only supervised learning, but as far as I know, most other training methods are based on this and only have some way of generating the loss, which they calculate the gradient from, themselves.

If you don't already know the basics of calculus and linear algebra (or even if you do, but you want to refresh it with nice intuitive explanations) there are these YouTube playlists:
- Linear algebra
- Calculus


For C++ the go-to library is probably Pytorch, which is usually known as a neural network and tensor library for Python, but it is written in C++ and also has a nice and almost the same API for C++.
Of course, you could implement a small neural network library yourself, but unless you are satisfied with very simple networks (i.e. fully connected with simple activation functions), it will be a lot of work, and finding bugs can be very difficult, as neural networks often just perform less than optimal when you made a subtle coding mistake.

Thank you so much for these awesome resources! I'll go check them out!

[RedBedHed]

NN math and training fits on a half napkin.

Sure, but writing something with the least amount of words, and teaching someone the same thing are two very different things. Especially if you consider different starting points. Maybe someone has never thought about a multivariable gradient before. Additionally, it is often much better for truly understanding a concept (and finally building new things upon it) to comprehend how people thought of it/created it in the first place.

I agree. I first looked at Neural Networks about 3-4 years ago. But I was too afraid of the math to start playing around with them.

It wasn't until I took multivariable calculus (about 2 years ago) that the idea of minimizing loss with gradient descent actually clicked. But even after taking all of the intermediate math courses, I am still pretty scared to dive into neural networks.

I think that, at the end of the day, fear really is the biggest roadblock to understanding. And for me, studying and absorbing lots of little pieces of information about the bigger picture is how I keep from feeling overwhelmed when I see it all at once.

[Joerg Oster]

I probably should add that the engine currently uses only two threads: one for the search and one for garbage collection. I'd estimate that it expands the search tree at about 500,000-700,000 nodes per second with little-to-no search optimization at this point. In 20 seconds it allocs about 12-13,000,000 nodes, performing an evaluation with each allocation and searching as deep as 250 plies. The tree policy is pure UCT with 1.42 as the exploration constant

Below a 20 sec search of my basic UCT implementation in Stockfish.
No rollouts, NNUE eval only. No special move-ordering, no quiescence search. (C = 2.26)

Code: Select all

go movetime 20000
info string NNUE evaluation using nn-6877cd24400e.nnue enabled
info depth 1 seldepth 4 multipv 1 score cp 101 nodes 21629 nps 107074 tbhits 0 time 202 pv d2d4 d7d5 a2a3 a7a6
info depth 1 seldepth 5 multipv 1 score cp 99 nodes 42063 nps 104634 tbhits 0 time 402 pv d2d4 g8f6 e2e4 a7a6
info depth 1 seldepth 5 multipv 1 score cp 106 nodes 62440 nps 103720 tbhits 0 time 602 pv d2d4 g8f6 e2e4 a7a6
info depth 1 seldepth 5 multipv 1 score cp 112 nodes 82769 nps 103203 tbhits 0 time 802 pv d2d4 d7d5 e2e4 a7a6
info depth 1 seldepth 5 multipv 1 score cp 115 nodes 102986 nps 102780 hashfull 0 tbhits 0 time 1002 pv d2d4 c7c6 e2e4 a7a6 a2a3
info depth 1 seldepth 5 multipv 1 score cp 113 nodes 122917 nps 102260 hashfull 0 tbhits 0 time 1202 pv d2d4 c7c6 e2e4 c6c5 a2a3
info depth 1 seldepth 5 multipv 1 score cp 112 nodes 142522 nps 101656 hashfull 0 tbhits 0 time 1402 pv d2d4 c7c6 e2e4 d8a5 c2c3
info depth 1 seldepth 5 multipv 1 score cp 110 nodes 161134 nps 100583 hashfull 0 tbhits 0 time 1602 pv d2d4 c7c6 e2e4 d7d6 a2a3
info depth 1 seldepth 5 multipv 1 score cp 108 nodes 179610 nps 99672 hashfull 0 tbhits 0 time 1802 pv d2d4 c7c6 e2e4 a7a6 a2a3
info depth 1 seldepth 5 multipv 1 score cp 106 nodes 197827 nps 98814 hashfull 0 tbhits 0 time 2002 pv d2d4 c7c6 e2e4 c6c5 a2a3
info depth 1 seldepth 5 multipv 1 score cp 95 nodes 285413 nps 95074 hashfull 0 tbhits 0 time 3002 pv d2d4 c7c6 e2e4 c6c5 a2a3
info depth 1 seldepth 5 multipv 1 score cp 88 nodes 369530 nps 92336 hashfull 0 tbhits 0 time 4002 pv d2d4 c7c6 e2e4 d8a5 c2c3
info depth 1 seldepth 6 multipv 1 score cp 82 nodes 452702 nps 90504 hashfull 0 tbhits 0 time 5002 pv d2d4 c7c6 e2e4 a7a6 a2a3
info depth 1 seldepth 6 multipv 1 score cp 77 nodes 534202 nps 89003 hashfull 0 tbhits 0 time 6002 pv d2d4 c7c5 d4d5 a7a6 a2a3
info depth 1 seldepth 6 multipv 1 score cp 74 nodes 616831 nps 88093 hashfull 0 tbhits 0 time 7002 pv d2d4 c7c5 e2e4 c5d4 a2a3
info depth 1 seldepth 6 multipv 1 score cp 70 nodes 699511 nps 87417 hashfull 0 tbhits 0 time 8002 pv d2d4 c7c5 e2e4 c5d4 a2a3
info depth 1 seldepth 6 multipv 1 score cp 65 nodes 782031 nps 86873 hashfull 0 tbhits 0 time 9002 pv d2d4 d7d5 e2e4 d5e4 a2a3
info depth 1 seldepth 6 multipv 1 score cp 62 nodes 864613 nps 86444 hashfull 0 tbhits 0 time 10002 pv d2d4 d7d5 e2e4 d5e4 a2a3
info depth 1 seldepth 6 multipv 1 score cp 53 nodes 1070935 nps 85661 hashfull 0 tbhits 0 time 12502 pv d2d4 d7d5 e2e4 d5e4 a2a3
info depth 1 seldepth 6 multipv 1 score cp 42 nodes 1277827 nps 85177 hashfull 0 tbhits 0 time 15002 pv d2d4 d7d5 c2c4 e7e5 d4e5 d5d4
info depth 1 seldepth 7 multipv 1 score cp 59 nodes 1484721 nps 84831 hashfull 0 tbhits 0 time 17502 pv d2d4 d7d5 c2c4 e7e5 a2a3 e5e4
info depth 1 seldepth 7 multipv 1 score cp 93 nodes 1670277 nps 83509 hashfull 0 tbhits 0 time 20001 pv d2d4 d7d5 e2e4 d5e4 a2a3 e4e3
info string Root move:   d2d4     Visits:   457958     P:  0.529 (cp 93)
info string Root move:   g1f3     Visits:   117606     P: 0.4963 (cp -47)
info string Root move:   c2c3     Visits:   109344     P: 0.4954 (cp -50)
info string Root move:   a2a3     Visits:    96016     P: 0.4936 (cp -56)
info string Root move:   e2e4     Visits:    91820     P:  0.493 (cp -58)
info string Root move:   c2c4     Visits:    88060     P: 0.4924 (cp -59)
info string Root move:   b1c3     Visits:    79965     P: 0.4911 (cp -62)
info string Root move:   e2e3     Visits:    79221     P: 0.4909 (cp -63)
info string Root move:   g2g3     Visits:    70636     P: 0.4891 (cp -67)
info string Root move:   d2d3     Visits:    68172     P: 0.4886 (cp -68)
info string Root move:   a2a4     Visits:    61882     P: 0.4868 (cp -71)
info string Root move:   b2b3     Visits:    61256     P: 0.4868 (cp -71)
info string Root move:   h2h4     Visits:    45425     P: 0.4812 (cp -80)
info string Root move:   f2f4     Visits:    43501     P: 0.4805 (cp -81)
info string Root move:   h2h3     Visits:    42086     P: 0.4798 (cp -82)
info string Root move:   b2b4     Visits:    39584     P: 0.4783 (cp -84)
info string Root move:   b1a3     Visits:    39469     P: 0.4783 (cp -84)
info string Root move:   g1h3     Visits:    37491     P: 0.4772 (cp -86)
info string Root move:   f2f3     Visits:    26926     P: 0.4692 (cp -95)
info string Root move:   g2g4     Visits:    13881     P: 0.4488 (cp -112)
bestmove d2d4 ponder d7d5

Not even close in speed to your numbers, though.

[dangi12012]

Below a 20 sec search of my basic UCT implementation in Stockfish.

How did you implement UCB1?
Do you pick the highest scoring move or the most often visited node?

[Joerg Oster]

Below a 20 sec search of my basic UCT implementation in Stockfish.

How did you implement UCB1?
Do you pick the highest scoring move or the most often visited node?

I'm using the standard UCB1 formula.
Currently I'm choosing the Robust child (most visited root move) as best move.
Although it is not clear to me if this is always the best choice for the game of chess.

[dangi12012]

Currently I'm choosing the Robust child (most visited root move) as best move.
Although it is not clear to me if this is always the best choice for the game of chess.

Yes! Thats was the intention behind my comment. The literature says that the most often visited node should be picked.
So here is one node with 50% winrate with 5001 visites and there another with 90% winrate with 2500 visits. MCTS will play the 50% winrate move.

I was asking because - do have the means to quickly test this with cutechess?
One engine build picks the robust child. One engine picks the highest winrate.

What is the stronger engine? And how big ist the difference?
If you need compute power for cutechess I can provide it.