Creating chess engine, machine learning vs. traditional engine?

Question

I am both an avid chess player and computer programmer. I would say that playing chess and programming are the two things I spend the most time doing. Naturally, I am wanting to create my own engine and, ultimately, Lichess bot.

In wake of AlphaZero's crushing performance against Stockfish last year, I am considering whether I should create this engine with machine learning (some type of neural network, possibly using Tensorflow) or traditional, hard coded heuristics.

I am less familiar with neural networks than other kinds of hard-coding. Still, it could be a good way for me to learn to work with neural networks.

Another thing I am considering is whether it is important which language I use to code the engine. I know many chess engines use C++, which I have never used before. I have used other C-based languages which do many of the same things, with mostly varying syntax. I am most familiar with Swift and Javascript, but am also familiar with Python and feel that it could do the trick for me.

So, in terms of creating the strongest chess engine possible, should I go neural network or hard-coded?

Update: I am writing a traditional engine in C++. It is currently somewhat UCI compatible and plays at what I estimate is 1100ish ELO. But it generates legal moves and I’ll be posting updates here.

This is the link to the github repo for the engine. Feel free to fork and make PRs, or just make general suggestions/tips.

Answer 1

First step: Define your goals/reasons

I think this is the predominant factor. Which of these best fits you? (Choose only one)

1. You want to enjoy a fun, challenging coding task
2. You want to create an extremely good chess engine
3. You want to learn about how chess engines work
4. You want to learn/practice coding skills
5. You want to learn/implement computer science concepts/theory (e.g. machine learning)
6. (Other)

IMO it's fine to "toss a coin" for anything except 2. For all the others, you will meet your goal whether you choose ML or hard-coding. However you probably want a comparison between the choices to help you decide.

The case for hard-coding

Playing chess (as a human) involves logical thinking. You explore the space of possible actions you and the opponent can take. This has spawned a field called game theory which contains theoretical frameworks for analysing games in general.

If you enjoy working with details and being specific and reasoning about things then this could work well for you. In comparison, machine learning involves a lot more "black box" algorithms which are fuzzy and opaque. You don't know exactly what is going on.

Also I reckon you will have an easier time "figuring it out on your own" if you go the hard-coding route rather than machine learning. Less copy-pasting stuff you don't fully understand.

The case for machine learning

It can be exciting to give birth to a creation and watch it take on a life of its own. While hard-coding is all about precision and detail, machine learning is flexible. Take away some neurons and the result will probably be similar.

Hard-coding is about studying chess. Machine learning is about studying the creature you have created.

And machine learning is, of course, a very hot topic.

Language choice for hard-coded

I am not sure what you mean by "other C-based languages". C++ is the only mainstream language that is anything like C. The advantage of C/C++ is that they are fast. Although other languages have caught up over the years, C++ still gives them a run for their money.

C++ isn't easy. You will get great performance out of more modern compiled languages like Rust, Golang or Swift. But it shouldn't be much worse if you go for a JIT language. I.e. don't use the CPython interpreter; use IronPython or Jython, or Node, or C# or Java.

GPU programming requires a different approach and I would advise against it at this point.

Language choice for machine learning

The problem with TensorFlow is that it is very low-level. It is more about writing number-crunching algorithms (which can be farmed out to parallel hardware) than about an interface dedicated to machine learning.

Of course, it can be a great learning experience! And is certainly very worthwhile learning today. However, you may want to start with Keras or PyTorch.

Answer 2

If you're trying to make the strongest engine possible, absolutely go for NN engines.

Traditional engines are great - Stockfish is arguably still the strongest engine on the planet on consensus equal hardware - but they are hard to write. These engines didn't get where they were overnight; they took years and years of work. Stockfish for example has been steadily gaining elo for six years. If you start from scratch, you will not get anywhere near Stockfish strength quickly; in fact you are likely to stall several hundred elo from where Stockfish currently is. For comparison some of the strongest single-author engines right now are Ethereal, Laser, and Xiphos (I neglect Houdini & Fire since they aren't open source). These engines are all substantially weaker than Stockfish.

Why are they so much weaker? Two reasons:

1. At this level, developing an engine takes a lot of computational power. What you do is look through your code and identify an idea that could gain elo. An example idea is, "if we know this move is probably good, do not search branches that reverse that move" (if this doesn't make sense to you, it means there's going to be a high learning curve as well). You then write a patch that implements the idea, and test the modified engine against the previous version. At this level, it takes tens of thousands of games to get a large-enough sample size to tell if the patch is effective. Playing these games takes huge amounts of computational power. Stockfish has access to super hardware: as of time of writing, the Stockfish testing ground Fishtesting is running with 1038 cores. For comparison a typical desktop computer might have 4-8 cores.

2. The other reason is that Stockfish is backed by many brains. As of time of writing, there are 8 patches written by 5 people being tested. If you look through the patch histories you'll find many more developers who've written patches. I don't know how many active Stockfish developers there are, but it's certainly >20.

On the other hand, NN engines (relatively) easily reach a strength that's well above Ethereal/Laser/Xiphos. See for yourself in the latest Top Chess Engine Championship tournament. Ethereal/Laser/Xiphos are in League 1, which is credible enough, but the engines in the top division (Division P) are:

• Stockfish (community-backed traditional engine, runs with Fishtesting)
• Komodo (commercial traditional engine, has full-time developers)
• Komodo MCTS (commercial semi-traditional engine, has full-time developers)
• Houdini (commercial traditional engine, is a one-man effort, hasn't been updated for two years)
• Leela Chess Zero (community-backed NN engine, runs with the analog of Fishtesting aka a ton of hardware)
• AllieStein (2-man NN engine)
• Stoofvlees (NN engine)
• ScorpioNN (NN engine)

The last three engines - AllieStein, Stoofvlees and ScorpioNN - are all small collaborations by people who, as far as I know, are enthusiasts like you and not full-time developers. They've gotten to Div P strength after less than two years of trying (all these NN engines only appeared after AlphaZero). Nobody single author has ever written a traditional engine that competed successfully with Stockfish/Komodo.* For comparison, in the recent history of computer chess there has only been one person who's ever written a traditional engine that competed successfully with Stockfish & Komodo on his own (Robert Houdart, the author of Houdini).

It's true that you probably won't have the hardware to compete with Lc0, but Lc0 takes this much computational power because it's a "zero" engine - it's supposed to play chess without any kind of human knowledge except for rules. You don't need to use the same methodology. You could use e.g. the Stein methodology that uses supervised learning. It's arguably even better than going "zero" - after all it's AllieStein playing in the superfinal, not Lc0.

The upshot is: if your aim is to compete with the best engines in the world, you are far more likely to succeed with NN engines than traditional ones.

*It might look like Houdini is such an example, but Houdini is plagiarized from Stockfish.

Answer 3

So, in terms of creating the strongest chess engine possible, should I go neural network or hard-coded?

Don't choose a NN unless you have access to ridiculous(A few hundred Nvidia V100s). Training a NN to play chess takes so much hardware. See the people contributing to Lc0 to train over 200 million games. Since you will probably have trouble accessing the hardware (you could try to get some at Google Colabatory, but with only that, training will be very slow).

Edit: Using a NN With Supervised learning, you MAY get away with just Google Colab and possibly one strong GPU (2080, 2080Ti, Radeon VII).

Another thing I am considering is whether it is important which language I use to code the engine. I know many chess engines use C++, which I have never used before. I have used other C-based languages which do many of the same things, with mostly varying syntax. I am most familiar with Swift and Javascript, but am also familiar with Python and feel that it could do the trick for me.

Python and Javascript are probably too slow for a strong chess engine. I haven't used Swift but it probably won't like platforms other than macOS, so it's probably better to use C or C++. You could also possibly use Rust, but that has many safety features that get annoying and you don't really need, which can get annoying. It's also going to be harder to get good performance out of it since certain low-level optimizations are hard to make. Of course, you can always write it in assembly but that's probably going to be too much work. see https://www.chessprogramming.org/Languages/

Answer 4

I built a purely toy chess engine using: python chess it was really nice not having to code the rules of the game myself and just focus on the logic; however, the number of position I was able evaluate per second is very low. This might be a good starting point.