17

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?

  • 4
    They key to the new AI engines is not so much NN as reinforcement learning. RL is a complex topic, but there are good introductory resources online like David Silver's RL lectures at UCL (slides on his website and lectures on YouTube. He worked with Deepmind and traditionally covered alphago in the last lecture. You could probably develop an interesting AI engine without NN using hard coded heuristics and RL. This is how alphago started! – asac - Reinstate Monica Oct 1 at 7:19
  • It isn't chess, but the recent book "Deep Learning and the Game Go" shows how to use NNs for a game-engine. Alpha-Go and Alpha-Zero are similar under the hood. – John Coleman Oct 1 at 10:37
  • Given your Python experience it might be worth looking at Nim – Darren H Oct 1 at 15:16
  • If you want to have a go at NN, this is interesting: arxiv.org/abs/1509.01549 There is also code on github :) – Ant Oct 1 at 17:50
  • @Ant note that Giraffe was never very strong compared to top engines. (~2800 elo) – Oscar Smith Oct 2 at 4:39
8

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.

  • 1
    This is a phenomenal response, really hits all the points I mentioned. It’s kind of hard to say why exactly I want to make an engine. Realistically, I likely won’t compete with the likes of Stockfish, Komodo, and Leela (I am only a college student after all). Still, it would be fun to see my work put up toe-to-toe against other engines and not get crushed every time. Even if my primary reasoning is to make a strong engine, I will likely learn a new programming language and improve my chess knowledge as a side product of making the engine. – David Chopin Oct 2 at 14:20
  • 1
    I think more than anything I want something I can make, nurture, and fine tune over the long term. I also want a project that will objectively tell me how good my code is (Wins/Draws/Losses, ELO, etc.). – David Chopin Oct 2 at 14:21
  • 1
    This a very interesting answer but are you seriously recommending Node over Cpython for performance concerns? – Evpok Oct 2 at 14:24
  • >"C++ is the only mainstream language that is anything like C." C#? Rust? Java? There's a lot of languages that are at least "anything like C" – Maaark Oct 2 at 14:59
  • I took "like C" to be a compiled, highly optimized, implemented-to-the-machine language with C-style syntax. C#, Java, and PHP all use virtual machines, with their code compiled down to opcodes rather than CPU-specific bytecode (and PHP's compilation is completely transparent, like Python and Bash). And Rust isn't mainstream. Only C++ is "like C" in these respects, despite sharing syntax styles with several other mainstream languages. – Ghedipunk Oct 2 at 17:35
24

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). 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.

  • 6
    Maybe mention the other side of your conclusion: If your aim is to deepen your understanding of chess while doing some programming, go for traditional. – blues Oct 1 at 11:55
  • 1
    I agree with your conclusion, but I would also recommend using a recent network from a strong engine (with permission of course) as a starting point rather than starting from scratch (but continue in a way different from "train via self-play and update weights", by either adding or removing layers, adding input features, demanding additional outputs, etc.). I can't remember if Lc0 is single head or dual head, but I believe 3 head (ijcai.org/proceedings/2018/0523.pdf) is not currently implemented by any chess engines, and could end up improving on state-of-the-art. – Steven Jackson Oct 1 at 14:38
  • I think Allie's search that makes it stronger against the weaker engines (KMCST, Stoofvlees), not the Stein network. – me' Oct 1 at 22:21
  • @blues I think programming a chess engine doesn't actually make one a better chess player - with the exception of Larry Kaufman (one of the developers of Komodo), none of the top engines have titled players as developers, or had their developers become titled players. – Allure Oct 1 at 23:31
  • @me' that's possible but Leelenstein is the Stein network using the Lc0 binary, and it's done well at chess.com's computer chess championship, so the Stein networks are at least comparable to the Lc0 networks. – Allure Oct 1 at 23:32
9

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/

  • 1
    Awesome, thanks a ton for the info! I'll probably try to create an API that takes in an FEN position and outputs the calculated move. I figure this is the best way to integrate with Lichess bots. – David Chopin Sep 30 at 22:06
  • There is github.com/careless25/lichess-bot – me' Oct 1 at 0:31
  • 1
    Is it an option to implement a different NN engine that just uses lc0's network? – RemcoGerlich Oct 1 at 8:53
  • 1
    @RemcoGerlich as I understand it, NN engines use two things: the binary, and the neural network. Writing a binary is not easy, but training a neural network is relatively easy. In this sense Lc0 derivatives already exist - Leelenstein & Deus X (aka. Fat Fritz) are such derivatives. – Allure Oct 1 at 9:14
  • @RemcoGerlich in that case that wouldn't really be a different engine, that would be the Ic0 engine with just a different wrapping/interface/whatever. – Peteris Oct 1 at 13:55
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.