# How Do Top Engines' Achieve Large Search Depth

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.

• 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.
– orlp
Feb 14 '18 at 12:27
• Useful reference: stackoverflow.com/questions/16500739/… May 27 '18 at 4:18

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

• Not wrong. 1:) Hard to imagine a new engine like here would have complicated evaluation. I think more likely it's too simple. Feb 19 '18 at 15:28
• 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. Feb 19 '18 at 15:30

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