Neural network evaluation for a Monte Carlo Tree Search engine

[RedBedHed]

Hello! Sadly, due to school and work, I haven't posted here in ages. (This summer, I've been working on software for embedded avionics of all things! It's neat... I'd just rather be learning about AI lol.)

I still haven't given up on my engine. Over the last few weeks, I've been reading lots of papers and writing a Monte Carlo Tree Search algorithm that employs instant evaluation in place of rollouts and manages memory with a simple garbage collector. The evaluation is a hodge-podge of mediocre ideas, yet the engine is capable of winning against a bot rated at 1300 on Chess.com when I give it 20 seconds of think time. For me, this is a monumental achievement, and I am very, very excited! I will probably never reach that level of skill as a casual player. But I've heard that it isn't a competitive rating.

Of course, I have read about Alpha Zero and spent some time scratching my head over Leela's search code. But I am a total novice when it comes to neural networks. I feel like training a chess neural network should be a supervised process... Give it the Stockfish evaluation of a few million positions and teach it to approximate the function... However, I know from my reading that Alpha Zero and Leela managed to learn on their own...

Additionally, I have heard that Monte Carlo Tree Search provides an ideal framework for the learning that Alpha Zero and Leela did.

So I have lots of general questions for the community!

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 have an Iris Xe on my laptop, and I'm too afraid to upgrade. I'm going to be living off of my internship savings and student loans for the next several months.

Any advice at all would be very much appreciated!

Ellie

[RedBedHed]

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

[RedBedHed]

Now that I've said it out loud, I am beginning to think that searching that deep means the exploration constant is too low... Legal games probably don't last that long.

[algerbrex]

Hello! Sadly, due to school and work, I haven't posted here in ages. (This summer, I've been working on software for embedded avionics of all things! It's neat... I'd just rather be learning about AI lol.)

I'm afraid I don't have any advice on resources, since I'm looking for some myself, but welcome back! It's always nice to see new engines and faces, and I'm interested to see what you'll come up with in your engine. I also know uni can get pretty busy. I had to take a pretty long break because of last semester, and I'll likely need to do the same this coming fall.

I have plans at some point of experimenting more with a MCTS chess engine in the future myself, so I'll report back if I find any good resources during that process.

[zamfofex]

I’m really happy to be able to know you’re coming back to making a chess engine! I wasn’t around when you were posting, but I came across your posts afterwards, and I was really inspired by your work.

I even decided to use it to complement my own bot at some point: https://github.com/zamfofex/dummyette/c ... a67cac9590
The code is still available here:

I remember looking into it at the time and finding it wonderful. It is definitely very fast, and you are very talented! I’ll be looking forward to more updates to Charon, as well as to when it eventually finally becomes the #1 best engine!

[smatovic]

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

[j.t.]

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.

[RedBedHed]

Hello! Sadly, due to school and work, I haven't posted here in ages. (This summer, I've been working on software for embedded avionics of all things! It's neat... I'd just rather be learning about AI lol.)

I'm afraid I don't have any advice on resources, since I'm looking for some myself, but welcome back! It's always nice to see new engines and faces, and I'm interested to see what you'll come up with in your engine. I also know uni can get pretty busy. I had to take a pretty long break because of last semester, and I'll likely need to do the same this coming fall.

I have plans at some point of experimenting more with a MCTS chess engine in the future myself, so I'll report back if I find any good resources during that process.

Hi! It's good to see you too Yeah uni was absolutely crazy last semester! I was personally working 60-100 weeks just to stay afloat. Theoretical computer science, in particular, almost drove me insane lol.

MCTS is absolutely beautiful. I can try to send papers on it if you'd like! Most of the good info I found was through my school's library portal. I'll let you know what I find on the neural networks as well.

School is starting back up in a few days now! May the odds be ever in our favor!

[RedBedHed]

I’m really happy to be able to know you’re coming back to making a chess engine! I wasn’t around when you were posting, but I came across your posts afterwards, and I was really inspired by your work.

I even decided to use it to complement my own bot at some point: https://github.com/zamfofex/dummyette/c ... a67cac9590
The code is still available here:

I remember looking into it at the time and finding it wonderful. It is definitely very fast, and you are very talented! I’ll be looking forward to more updates to Charon, as well as to when it eventually finally becomes the #1 best engine!

Thank you! I'm so glad it was helpful! We'll see haha...

Thanks for the links! I'll take a look

[hgm]

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.