Our great sponsors
-
-
ChessPositionRanking
Software suite for ranking chess positions and accurately estimating the number of legal chess positions
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
-
parallel-hashmap
A family of header-only, very fast and memory-friendly hashmap and btree containers.
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
I recommend anyone who's interested in this topic, or in data structures and optimisation, to pick apart Stockfish' transposition table implementation[0,1]. It's essentially a highly customised hash table. It has to handle multiple threads reading and replacing entries, with no locking. It can't grow dynamically, and so it has to "age out" entries.
Think of it like hash table implementation with the difficulty set to brutal. You can't grow dynamically(too many entries). You can't store the key, since it'll almost double the size of each entry. You can't use locks. Lookup times need to be practically constant time.
[0]: https://github.com/official-stockfish/Stockfish/blob/master/...
Shannon's estimate was based on very primitive methods; by generating random positions and using fairly advanced methods to see whether they are legal or not (ie., can you construct a proof game for it, or prove that it could never happen), you will get much closer. A group of people have been working on this, and their current best estimate is (4.822 +- 0.028) * 10^44, or a bit over 148 bits. (Amazingly enough, Shannon wasn't all that far off on this account! His estimated number of legal games seems much more dodgy, though.)
http://talkchess.com/forum3/viewtopic.php?f=7&t=77685&sid=e3...
Practically speaking, https://github.com/tromp/ChessPositionRanking gives a number between 0 and approx. 8.7 * 10^45 for any legal position, so it's only a couple of bits away from optimality.
https://boristrapsky.com (https://lichess.org/@/Boris-Trapsky) plays against a typical, rather than perfect-playing, opponent but I could not find any source code.
It doesn't use transposition tables or quiescence search. Instead of that, I simply search only to depth=1 and then even depths after that, which tends to limit the horizon effect. I usually lose against it, but it's fun when I pull off a win.
I even tried porting it to web assembly [2]. It mostly works, but the display code still has a bug where the interface disappears sometimes, and I'm still trying to figure out why.
Then they should really try https://github.com/greg7mdp/parallel-hashmap, the current state of the art.