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.
2
-
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.– orlpFeb 14, 2018 at 12:27
-
Useful reference: stackoverflow.com/questions/16500739/…– StoudMay 27, 2018 at 4:18
Add a comment
|
2 Answers
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, 2018 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, 2018 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
- 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.
answered Feb 15, 2018 at 1:48
-
1These 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 :) Feb 15, 2018 at 12:18
-
@user929304 I think we should close the question as there's no way to answer correctly. I was just guessing. Feb 15, 2018 at 12:38
-
Hi SmallChess, thanks for the suggestions. I will look into them, and post when I have figured out what was wrong. Thanks, Henry– Henry HFeb 15, 2018 at 14:44
-
@HelloWorld I vote to keep it open. You may not be able to answer but others could. Feb 22, 2020 at 3:15