Simplest chess engine to reach 2000 ELO?

Question

From what I have read coding a "vanilla chess engine" (c++ code for alpha-beta search over bitboard representation with simple hand-crafted evaluation function), will get you to 1500~1700 ELO on CCRL 40/4.

Q1: What is the minimal set of ingredients needed to reach 2000 ELO ?

Q2: What is the minimal set of ingredient needed, if no opening or closing book is allowed ?

I have found micro-max and the development log of zurichess as initial hints on how to reach ~2000 ELO. And I found jazz engine as proof that 2000+ ELO can be reach without opening/ending books. However I would like to heard the opinion of others on the matter.

Thanks a lot for your suggestions.

(ps: here "simplest" is in "how long it takes to describe the algorithm", not necessarily in lines of codes)

Answer 1

I don't think the CCRL rating list has anything to do with the FIDE rating list, so Micro-Max most likely performs weaker than a FIDE 2000 human-chess player. I have an iOS chess app for MicroMax - Chess Mini, it uses the MicroMax chess engine. That's my description: "The engine has a rating of Elo 2000 on the Computer Chess Rating Lists." While this is certainly true, I've received complains that the app is too easy for a human FIDE 2000 player. In fact, I can consistently beat the app myself and I'm a 1900-2000 rated player. I don't recall that the app has ever positionally outplayed me.

Why is that important? It implies that the CCRL rating list most likely over-estimates the performance for MicroMax (for a human player). Therefore, I don't think a vanilla chess engine such as MicroMax should be your benchmark on what a 2000 chess engine should do. Evaluation in a plain engine (e.g.: MicroMax) is too simple and too much time spent on evaluating useless branches.

Let's take a look at BikJump, it's available on Android. Despite being rated 2100 on the CCRL list, I was still able to defeat it (more than once) after a complicated struggle. I think (but not 100% sure) the FIDE 2000 line should be drawn around CCRL 2100-2200. While I don't have the source code for BikJump, I'm pretty sure it's not a pure alpha-beta engine.

From memory, I could beat my engine quite convincinly when it was only counting materials and a plain alpha-beta. As soon as I added knowledge for pawn-structure, spacing and more aggressive cutoff strategy (e.g.: null-move pruning, hashing), it was equal to me. Next, I added king safety and things like SSE, the machine was starting to beat me.

PS: We don't call "closing book", we call "tablebase". They are not needed to reach 2000.

Answer 2

I'm the author of zurichess, the engine mentioned in your post. Here are, what I think, the most important things to get your engine to play +2000ELO. If it the terminology is not clear check https://chessprogramming.wikispaces.com/ which is one of the best resources available.

• Write a move generator. Make sure it's correct and passes all perft tests. Don't worry about the speed.
• Start with an alpha beta and a basic eval such as piece counting.
• Add aspiration window.
• Improve move ordering: add killer move heuristic and order moves by mvv/lva. Alpha-beta works best when best moves are searched first.
• Add quiescence search which solves the captures at the end of the search. This stabilizes the evaluation quiet a bit and removes much of the horizon effect issues.
• Add null-move pruning (i.e. if I don't do anything can my opponent improve?). This effectively gives you +100ELO because you now cut huge parts of the tree.
• Begin to add basic evaluation features such as: mobility, pawn position, king position, passed pawns.
• Add transposition tables. Don't generate the moves if you already have a hash move (but the score was not accepted due to low depth of the hash entry). With this, move generation speed becomes a non-issue.
• Extend search on check to avoid cases when the danger is pushed over the horizon. Don't extend everything, test several conditions.

By now your new engine should be over 2000. However, if you look at top engines such as crafty/stockfish/komodo, they all have something in common which most weaker engines do not: cluster testing.

Once your engine passes the 1500 ELO mark chances are that your changes are losing on average more ELO than they are gaining. You need to build a serious testing framework with a good stopping criteria (LOS 99% works until 2000ELO, after that you need SPRT). I invested about 700$ and bought 6 ODROID U3 (each with 4 32bit cores) and build a cluster to test all of my patches that could affect search. If you look into the commit log of zurichess you'll see the gains for each patch. A month ago hardkernel released ODROID XU4, which is slightly more expensive than U3 but has 8 64bit cores.

Answer 3

Well concurrency can give you some 80-100 ELO on 4 cores. Lazy SMP is eazy both for explain and write. Other features are harder to measure, it depends on engine too. Null-move is very simple feature, so add Adaptive Null-move pruning. Add endgame tablebases - that was measured to be about 30 ELO. PVS search is a bit more complicated, but is very important.

Add transposition tables - hash should give a decent speedup.

Tune evaluation: piece-square tables, backward, isolated, passed, doubled pawns, bishop pair, rook on open file.

That are easiest concepts I can recall, not sure what ELO it will give in result.