Answers.Body: <p>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 - <a href="https://itunes.apple.com/au/app/chess-mini/id616424231?mt=8" rel="nofollow">Chess Mini</a>, it uses the MicroMax chess engine. That's my description: <em>"The engine has a rating of Elo 2000 on the Computer Chess Rating Lists."</em> 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.</p>
  
  <p>Why is that important? It implies that the CCRL rating list most likely <strong>over-estimates</strong> 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.</p>
  
  <p>Let's take a look at <a href="http://www.computerchess.org.uk/ccrl/404/cgi/engine_details.cgi?print=Details&amp;each_game=1&amp;eng=BikJump%202.01%2064-bit#BikJump_2_01_64-bit" rel="nofollow">BikJump</a>, 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.</p>
  
  <p>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 <strong>pawn-structure</strong>, <strong>spacing</strong> and more aggressive cutoff strategy (e.g.: <strong>null-move pruning</strong>, <strong>hashing</strong>), it was equal to me. Next, I added king safety and things like SSE, the machine was starting to beat me.</p>
  
  <p>PS: We don't call "closing book", we call "tablebase". They are not needed to reach 2000.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-29T19:26:36.853Z
Answers.Text: 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".
Answers.UserDisplayName: rodrigob
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-29T19:27:32.893Z
Answers.Text: 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 ?
Answers.UserDisplayName: rodrigob
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-30T04:15:24.243Z
Answers.Text: @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.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-30T04:17:29.813Z
Answers.Text: @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.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-29T14:22:51.343Z
Answers.LastActivityDate: 2015-08-29T15:58:06.017Z
Answers.LastEditDate: 2015-08-29T15:58:06.017Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>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 <a href="https://chessprogramming.wikispaces.com/" rel="nofollow">https://chessprogramming.wikispaces.com/</a> which is one of the best resources available.</p>
  
  <ul>
  <li>Write a move generator. Make sure it's correct and passes all perft tests. Don't worry about the speed.</li>
  <li>Start with an alpha beta and a basic eval such as piece counting.</li>
  <li>Add aspiration window.</li>
  <li>Improve move ordering: add killer move heuristic and order moves by mvv/lva. Alpha-beta works best when best moves are searched first.</li>
  <li>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.</li>
  <li>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.</li>
  <li>Begin to add basic evaluation features such as: mobility, pawn position, king position, passed pawns. </li>
  <li>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.</li>
  <li>Extend search on check to avoid cases when the danger is pushed over the horizon. Don't extend everything, test several conditions.</li>
  </ul>
  
  <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-09-01T20:42:25.043Z
Answers.LastActivityDate: 2015-09-15T06:49:07.837Z
Answers.LastEditDate: 2015-09-15T06:49:07.837Z
Answers.UserDisplayName: Alexandru
Answers.Body: <p>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.</p>
  
  <p>Add transposition tables - hash should give a decent speedup.</p>
  
  <p>Tune evaluation: piece-square tables, backward, isolated, passed, doubled pawns, bishop pair, rook on open file.</p>
  
  <p>That are easiest concepts I can recall, not sure what ELO it will give in result.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-29T15:57:14.433Z
Answers.Text: SMP is an advanced concept... Where do you get those ELO numbers from?
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-29T16:02:34.793Z
Answers.Text: @StudentT here are numbers about SMP - http://www.talkchess.com/forum/viewtopic.php?t=46858
Answers.UserDisplayName: EvgeniyZh
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-29T16:03:17.197Z
Answers.Text: @StudentT SMP is pretty easy to understand, and the simplest algorithms are pretty obvious
Answers.UserDisplayName: EvgeniyZh
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-30T04:35:25.970Z
Answers.Text: Are you really sure SMP is the "simplest" algorithm?
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-30T04:39:01.807Z
Answers.Text: @StudentT I said that simplest of SMP algorithms are pretty easy to understand.
Answers.UserDisplayName: EvgeniyZh
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-08-29T15:40:02.147Z
Answers.LastActivityDate: 2015-08-29T15:40:02.147Z
Answers.UserDisplayName: EvgeniyZh
Body: <p>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 <a href="http://www.computerchess.org.uk/ccrl/404/" rel="noreferrer">CCRL 40/4</a>.</p>
  
  <p>Q1: What is the minimal set of ingredients needed to reach 2000 ELO ?</p>
  
  <p>Q2: What is the minimal set of ingredient needed, if no opening or closing book is allowed ?</p>
  
  <p>I have found <a href="http://home.hccnet.nl/h.g.muller/max-src2.html" rel="noreferrer">micro-max</a> and the development log of <a href="https://bitbucket.org/zurichess/zurichess/" rel="noreferrer">zurichess</a> as initial hints on how to reach ~2000 ELO. And I found <a href="http://www.eglebbk.dds.nl/program/chess-index.html" rel="noreferrer">jazz engine</a> 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.</p>
  
  <p>Thanks a lot for your suggestions.</p>
  
  <p>(ps: here "simplest" is in "how long it takes to describe the algorithm", not necessarily in lines of codes)</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-08-29T13:06:41.323Z
Comments.Text: Similar question: http://chess.stackexchange.com/questions/8472/which-is-the-smallest-chess-engine-with-elo-at-least-2000
Comments.UserDisplayName: Dag Oskar Madsen
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-08-29T15:18:05.967Z
Comments.Text: the question here is about the features needed, not about the existence of a "few lines of code" engine (which I already cited in the question itself)
Comments.UserDisplayName: rodrigob
Tags: <engines><software><elo>
Title: Simplest chess engine to reach 2000 ELO?
ThreadText: # Simplest chess engine to reach 2000 ELO?
  
  (Asked by: username_0 on 2015-08-29)
  
  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](http://www.computerchess.org.uk/ccrl/404/).
  
  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](http://home.hccnet.nl/h.g.muller/max-src2.html) and the development log of [zurichess](https://bitbucket.org/zurichess/zurichess/) as initial hints on how to reach ~2000 ELO. And I found [jazz engine](http://www.eglebbk.dds.nl/program/chess-index.html) 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)
  
  **Tags:** engines, software, elo
  
  > **Comments:**
  > **username_1**: Similar question: http://chess.stackexchange.com/questions/8472/which-is-the-smallest-chess-engine-with-elo-at-least-2000  
  > **username_0**: the question here is about the features needed, not about the existence of a "few lines of code" engine (which I already cited in the question itself)  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2015-08-29. Score: 2 | Accepted answer
  
  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](https://itunes.apple.com/au/app/chess-mini/id616424231?mt=8), 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](http://www.computerchess.org.uk/ccrl/404/cgi/engine_details.cgi?print=Details&each_game=1&eng=BikJump%202.01%2064-bit#BikJump_2_01_64-bit), 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.
  
  > **Comments:**
  > **username_0**: 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".  
  > **username_0**: 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 ?  
  > **username_2**: @username_0 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.  
  > **username_2**: @username_0 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.  
  
  ---
  
  ### Answer by username_3 on 2015-09-01. Score: 9
  
  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 by username_4 on 2015-08-29. Score: 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.
  
  > **Comments:**
  > **username_2**: SMP is an advanced concept... Where do you get those ELO numbers from?  
  > **username_4**: @StudentT here are numbers about SMP - http://www.talkchess.com/forum/viewtopic.php?t=46858  
  > **username_4**: @StudentT SMP is pretty easy to understand, and the simplest algorithms are pretty obvious  
  > **username_2**: Are you really sure SMP is the "simplest" algorithm?  
  > **username_4**: @StudentT I said that simplest of SMP algorithms are pretty easy to understand.  
  
  ---
  
  