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