Answers.Body: <p>I am not a specialist about programming chess engines, but the notions of depth is a little bit misinterpreted. "Depth" is somehow the maximal value reached by the engine during his search but the engine is absolutely not searching in every position with a depth of 20 moves. Modern engine uses heuristics to determine line of play and reducing the number of positions to analyse.</p>
  
  <p>I don't precise way to do so but I can imagine that line of play with too much imbalance are not completely analysed by the engine, for example.</p>
  
  <p>One point as well is about the evaluation function of your algorithm, if the function is too time-consuming then the algorithm would run longer as well.</p>
  
  <p>One thing is about the transposition table (TT), you need to check if the TT is not becoming too large which would result into some memory issues.</p>
  
  <p>I really believe that the number of positions to analyse at each step is strongly bound by the way of choosing which position to analyse or not.</p>
  
  <p>I think you know the chessprogramming wiki, but there is a lot about improving searching on <a href="http://chessprogramming.wikispaces.com/Search" rel="nofollow noreferrer">http://chessprogramming.wikispaces.com/Search</a>.</p>
  
  <p>I hope I've helped you :)</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-19T15:28:47.133Z
Answers.Text: Not wrong. 1:) Hard to imagine a new engine like here would have complicated evaluation. I think more likely it's too simple.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-19T15:30:14.857Z
Answers.Text: 2:) Of course TT must be kept in the memory and no disc access. We might take advantage of word size while reading data from the table.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-19T14:46:04.310Z
Answers.LastActivityDate: 2018-02-19T14:46:04.310Z
Answers.UserDisplayName: Sylvain Julmy
Answers.Body: <p>It's hard to answer (I voted to close for "too broad"), you'll need to do some research. Some possibilities:</p>
  
  <ul>
  <li>Your TT table implementation is slow</li>
  <li>You're not saving positions properly to the TT</li>
  <li>How you make the hash key for TT table is very slow</li>
  <li>You might want to try null-move pruning</li>
  <li>You made a debug build for your engine</li>
  <li>Your evaluation function is too <strong>simple</strong> for effective pruning. Are you just counting materials?</li>
  <li>You're not sorting the moves</li>
  <li>When a top engine says 20+ deep, it doesn't mean it searches everything up to 20+ deep. It could mean quiescence search or something else. In any case, most of the search tree would be discarded.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-15T12:18:24.320Z
Answers.Text: These are great guesses/pointers, +1. I'd say don't close the post, it's a pity now that it's received a good answer :)
Answers.UserDisplayName: user929304
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-15T12:38:59.187Z
Answers.Text: @user929304 I think we should close the question as there's no way to answer correctly. I was just guessing.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-15T14:44:38.970Z
Answers.Text: Hi SmallChess, thanks for the suggestions. I will look into them, and post when I have figured out what was wrong. Thanks,  Henry
Answers.UserDisplayName: Henry H
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-22T03:15:34.003Z
Answers.Text: @HelloWorld   I vote to keep it open.  You may not be able to answer but others could.
Answers.UserDisplayName: edwina oliver
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-15T01:48:55.823Z
Answers.LastActivityDate: 2018-02-15T01:48:55.823Z
Answers.UserDisplayName: SmallChess
Body: <p>Im new to programming chess engines. I have implemented a transposition table, search tree, and alpha-beta pruning, an can analyze ~80000 boards per second. However, even with alpha-beta search, when I increase the depth of the search by 1, it analyzes approximately 20 times as many boards and takes 20 times as long. Therefore I can only search 5 to 6 moves deep, which is clearly terrible. How is it that top engines can analyze 20+ plays deep? Even if I could analyze 100x as many boards each second, that would still only get me 1.5 more plays deep, so I don't think my board analysis speed is that big a factor.
  Also, are there any books that you would suggest for a good introduction to chess programming?
  Thanks in advance.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-14T12:27:29.180Z
Comments.Text: I don't have the experience to give you a full answer, but I can already tell you that the answer will be heuristics and monte carlo tree search to explore the most promising lines more than others.
Comments.UserDisplayName: orlp
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-05-27T04:18:14.403Z
Comments.Text: Useful reference: https://stackoverflow.com/questions/16500739/chess-high-branching-factor/16642804#16642804
Comments.UserDisplayName: Stoud
Tags: <engines><beginner>
Title: How Do Top Engines' Achieve Large Search Depth
ThreadText: # How Do Top Engines' Achieve Large Search Depth
  
  (Asked by: username_0 on 2018-02-14)
  
  Im new to programming chess engines. I have implemented a transposition table, search tree, and alpha-beta pruning, an can analyze ~80000 boards per second. However, even with alpha-beta search, when I increase the depth of the search by 1, it analyzes approximately 20 times as many boards and takes 20 times as long. Therefore I can only search 5 to 6 moves deep, which is clearly terrible. How is it that top engines can analyze 20+ plays deep? Even if I could analyze 100x as many boards each second, that would still only get me 1.5 more plays deep, so I don't think my board analysis speed is that big a factor.
  Also, are there any books that you would suggest for a good introduction to chess programming?
  Thanks in advance.
  
  **Tags:** engines, beginner
  
  > **Comments:**
  > **username_1**: I don't have the experience to give you a full answer, but I can already tell you that the answer will be heuristics and monte carlo tree search to explore the most promising lines more than others.  
  > **username_2**: Useful reference: https://stackoverflow.com/questions/16500739/chess-high-branching-factor/16642804#16642804  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2018-02-19. Score: 2
  
  I am not a specialist about programming chess engines, but the notions of depth is a little bit misinterpreted. "Depth" is somehow the maximal value reached by the engine during his search but the engine is absolutely not searching in every position with a depth of 20 moves. Modern engine uses heuristics to determine line of play and reducing the number of positions to analyse.
  
  I don't precise way to do so but I can imagine that line of play with too much imbalance are not completely analysed by the engine, for example.
  
  One point as well is about the evaluation function of your algorithm, if the function is too time-consuming then the algorithm would run longer as well.
  
  One thing is about the transposition table (TT), you need to check if the TT is not becoming too large which would result into some memory issues.
  
  I really believe that the number of positions to analyse at each step is strongly bound by the way of choosing which position to analyse or not.
  
  I think you know the chessprogramming wiki, but there is a lot about improving searching on <http://chessprogramming.wikispaces.com/Search>.
  
  I hope I've helped you :)
  
  > **Comments:**
  > **username_4**: Not wrong. 1:) Hard to imagine a new engine like here would have complicated evaluation. I think more likely it's too simple.  
  > **username_4**: 2:) Of course TT must be kept in the memory and no disc access. We might take advantage of word size while reading data from the table.  
  
  ---
  
  ### Answer by username_4 on 2018-02-15. Score: 1
  
  It's hard to answer (I voted to close for "too broad"), you'll need to do some research. Some possibilities:
  
  * Your TT table implementation is slow
  * You're not saving positions properly to the TT
  * How you make the hash key for TT table is very slow
  * You might want to try null-move pruning
  * You made a debug build for your engine
  * Your evaluation function is too **simple** for effective pruning. Are you just counting materials?
  * You're not sorting the moves
  * When a top engine says 20+ deep, it doesn't mean it searches everything up to 20+ deep. It could mean quiescence search or something else. In any case, most of the search tree would be discarded.
  
  > **Comments:**
  > **username_5**: These are great guesses/pointers, +1. I'd say don't close the post, it's a pity now that it's received a good answer :)  
  > **username_4**: @username_5 I think we should close the question as there's no way to answer correctly. I was just guessing.  
  > **username_0**: Hi username_4, thanks for the suggestions. I will look into them, and post when I have figured out what was wrong. Thanks,  username_0  
  > **username_6**: @HelloWorld   I vote to keep it open.  You may not be able to answer but others could.  
  
  ---
  
  