5

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)

2

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.

  • Indeed CCRL ELO is not "one to one" with humans, but it is easier to measure (while coding an engine); so that is the measure I pick: "2000 ELO on CCRL 40/4". – rodrigob Aug 29 '15 at 19:26
  • Why is SSE only added "at the end"; would not that alone help remove some of the previous ingredients ? Out of the ones you mention; which one you think made the most impact ? – rodrigob Aug 29 '15 at 19:27
  • @rodrigob I think q-search, hashing and null-move are the most important. Of course, you'll need a good like iterative deepening, sorting the PV moves, good evaluation to make it work. – SmallChess Aug 30 '15 at 4:15
  • 1
    @rodrigob SSE helps, and it's easy to implement. I implemented SSE later in the development, no particular reason, just personal preference. As long as you have a reasonable evaluation, and implement the those mentioned techniques well, you should not have a problem reaching 2000. – SmallChess Aug 30 '15 at 4:17
8

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.

1

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.

  • SMP is an advanced concept... Where do you get those ELO numbers from? – SmallChess Aug 29 '15 at 15:57
  • @StudentT here are numbers about SMP - talkchess.com/forum/viewtopic.php?t=46858 – EvgeniyZh Aug 29 '15 at 16:02
  • @StudentT SMP is pretty easy to understand, and the simplest algorithms are pretty obvious – EvgeniyZh Aug 29 '15 at 16:03
  • Are you really sure SMP is the "simplest" algorithm? – SmallChess Aug 30 '15 at 4:35
  • @StudentT I said that simplest of SMP algorithms are pretty easy to understand. – EvgeniyZh Aug 30 '15 at 4:39

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.