| I haven't inherited it, but I've been working on an experimental fork of Stockfish as a side project. The code isn't exactly easy to understand, but that's inherent to the complexity of the domain. But there's a lot of elegance to a lot of the data structures and how well optimised they are for the problem at hand. And Stockfish' way of utilising multiple cores is simply beautiful to me. There are all sorts of algorithms for parallellisation of the Principal Variation Search algorithm at the core of Stockfish's search, to do with distributing nodes between threads and so on and so forth. If you go read Stockfish, it might seem like it's just running ncpu separate single-threaded searches. Because that really is what it's doing. Which seems crazy at first. But what it does is it has a shared, effectively constant time(technically O(n) where n is 3, the number of entries per cluster) lookup hash table for caching search results, keyed by the node. And it's even lockless. And then each thread has its own set of statistics generated through search, which then influences the order in which that thread visits nodes because they're used for move ordering heuristics. And there's some other heuristics where the thread might jump straight from searching depth n to n+2, to inject some more randomness. So there is a distribution of different nodes to different threads. It's just an emergent property of fairly simple things happening in each thread, whether they got a cache hit or miss, etc. The reason this is so elegant is that the search algorithm itself is much simpler this way because it doesn't care about what other threads are doing. It looks at the transposition table, that's all, everything past that is good old single threaded programming. Then there's a very simple bit of code at the end that does a vote for the best move, based on evaluation and various other statistics(like the number of times the thread has changed its mind on the best move). What excites me so much about this is that you could in theory do wildly different things in different threads. They only have to agree on what goes into the transposition table, what it means, and how to vote at the end. Stockfish doesn't do that, so that's one of the things I've been trying to explore in my own project. |