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.
True, although I'd say transposition tables are much, much easier in a crucial aspect – you deal with hash collisions by simply overwriting the current entry or nop'ing. There's no linear probing, no cuckoo hashing, &c; when you want to update an entry, you check whether you'd rather store the new thing or keep the old, and that's it.
That's true in theory, but in the actual Stockfish implementation, a sort of mixed strategy is employed where entries are kept in clusters of 3. So there's a type of limited linear probing there too. Additionally, there's a lot of cleverness employed in how a position's hash is mapped to an individual cluster, and how collisions are avoided without storing a copy of the position or the full key(see the first_entry method in the header and the key16 field in the entry struct).
But indeed, it's not a large amount of code. But there's a lot of thought put into every aspect of how the data is laid out, and how the table is probed. It's a nice case study in domain specific optimisation.
That's not linear probing, though; that's having a 3-way associative cache.
Maybe that's how I should have phrased my comment: a transposition table is a cache, not a hash map,* because entries can be lost (overwritten). Furthermore, insertions may not succeed.
I know you know this; I mentioned it because I didn't want anyone to read Stockfish's source expecting an implementation of a hash map and then get confused.
Stockfish's source is well-written and incidentally didactic, so I'd definitely second the recommendation to read it.
*Or hash table, or dictionary; these are all synonyms, I just prefer "map" myself.
At a cursory glance, this a good example of a much simpler approach than the Stockfish one. It is far less optimized though. But that's reasonable given the age of that code.
This implementation isn't actually race free per-se. It can happen that reads and writes overlap resulting in bad entries, but they are generally rare, since Stockfish utilises various heuristics to ensure that different threads are searching non-overlapping parts of the search tree most of the time. Erroneous information at a single node doesn't usually have a huge effect since ultimately the best move is chosen through a vote between the different threads. So it sort of cheats by avoiding most races and collisions, and then having ways of spotting bad entries, ignoring and overwriting them.
This is all a bit hand-wavey, but there you have it. You could do this with atomics by shaving down the size of an entry to 64 bits(Stockfish uses 10 bytes), I suppose.
Stockfish is the state of the art for its particular use case. General-purpose hash table are completely irrelevant, they'll never be able to compete on performance. Specific things Stockfish can assume:
* The table doesn't need to dynamically grow.
* Entries are allowed to be lost, but inserts can also simply fail
* Key collisions are considered acceptable, and because of this, Stockfish doesn't store the key in the table, only its hash. Even artificially high collision rates have been shown to not significantly impact playing strength.
* Bogus data due to race conditions is considered acceptable, same as above.
Several years ago I built a chess engine in C, based on various ideas gleaned from the chessprogramming wiki [1]. I haven't looked at in a while, but that wiki was an extraordinarily useful resource.
I didn't write a better stockfish or anything, but I was surprised that it didn't take too long to write a chess engine that could routinely beat me at chess.
I'll also note that chess protocals are very standardized, and it was straightforward to attach the engine to one of the many chess GUIs out there (I used Chess Arena and scid). This was a great project and I highly recommend it.
For sure, ChessProgramming.org is one of the best resources out there.
Wrote this just trying to be a bit more of a straightforward guide to how to really get started - hard to sort through how many strategies there are out there when building an engine :)
I think chess engines are an amazing thing to study. So much fundamental computer science is covered, from extremely low level CPU instructions to high level data structures and algorithms. There's no surprise to me that many of the greats have turned their eye to representing and solving chess, from Turing to Knuth. I strongly suspect you could teach an entire CS degree never stepping outside of chess.
Even now there are so many rich directions you could go in. For example, many people are working on explainability in machine learning, but I think in many applications you want to go even further and actually optimise a model to _teach humans_ not just explain its predictions. This is especially relevant to engines when making strategic moves rather than calculating short term tactics.
I also think engines as tools for match preparation could be much better. What if you could more easily set an engine to find forced draws in certain lines, or tailor an engine to find tricky lines that a particular opponent is less likely to follow correctly, or find and optimise for certain endgame structures an opponent is weak at? Doing this in ChessBase (a truly awful but necessary piece of software) is quite painful.
This is a wonderful article and I really enjoyed the graphs and the clear explanations.
I wrote a simple chess engine in C and then ported it to C++ [1]. It doesn't use transposition tables or quiescence search. Instead of that, I simply search only to depth=1 and then even depths (2, 4, 6...) after that, which tends to limit the horizon effect. It's not that sophisticated, but I usually lose against it. Even so, 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. Also it doesn't work on mobile browsers I've tried.
Chess programming is fascinating but it seems for me that it has somewhat stalled in creativity in terms of classical (non DNN) engines. They all seem to use improved versions of min-max/alpha-beta. Which results in computer players that are extremely powerful but also quite dull. This is because they assume that the opponent will play perfect game and will do it at the full strength of the engine.
Basically there is no point playing against the engines at full strength as a human, since it will beat almost any human beyond grandmaster level. And that’s for weaker engines – the medium tier ones will regularly beat grandmasters and the top ones around the stockfish tier will probably not loose 1 game in 100 plays.
That considered I’ve wondered what’s possible dropping the assumptions about perfect play of the opponent. Some probabilistic models of opponent or different way of rating whole tree of moves in the context, instead of position only. For example considering the alternative moves and how difficult it would be to play perfect game for the opponent, it might be better to play combination with a lot of traps with possibility of loosing some position if the opponent plays perfectly. Current engines wouldn’t play such kind of move because they’d assume (via min-max/alpha-beta) that opponent will have perfect answer. Of course, if the opponent is an engine it will, but against humans it would make things much more interesting.
chessprogramming.org is a treasure trove of knowledge on building chess engines. With its help, I wrote one in C++ a few years ago that got quite good (2100+ rating on FICS but that's nowhere close to the likes of Stockfish). In fact, writing a reasonably strong chess engine is straightforward (and incredibly fun) but at the top end of strength, there's immense depth, and after a point making improvements gets increasingly resource intensive (tuning params, running experiments to verify strength gain all takes a lot of compute).
Chess programming is also extremely addictive. On forums like talkchess.com, you see folks hanging out who have been doing it for decades (most of them are also super helpful to newbies).
> running experiments to verify strength gain all takes a lot of compute
Fun fact, in my master thesis I proved that quantum computers can verify this using quadratically fewer iterations than on a classical computer. That is, if it takes a classical computer c*n iterations to say with 99% certainty that agent A is stronger than agent B, a quantum computer can do it in d*sqrt(n) iterations, where c and d are agent-independent constants (obviously n is not agent-independent as two closely matched agents are harder to distinguish than a steamroll).
The number of qubits needed put this into the far future of quantum computing, but it's neat nonetheless.
One day I'd like to write a rubbish Chess Engine purely for personal use, so that I can play chess against the computer and actually have a good probability of winning, instead of getting thrashed even on the 'easy' setting.
The way my brain works, the act of writing the engine would probably also level up my chess playing skills as a side benefit.
The hard part is writing an engine that you can barely beat, which is what would give most people the most enjoyable experience.
Usually what ends up happening is that you either get an engine you can easily trounce, or you get an engine that thoroughly outplays you on most moves but occasionally throws in a massive blunder.
Can highly recommend this article. I wrote a small chess engine for fun, mostly during a long plane flight back in 2018 when I had no internet access.
My process for writing the engine followed almost exactly the series of steps laid out in this article. The key improvement that I made was to add quiescence search with null move pruning. After I added that, it became quite tricky to beat (for my ~1450 lichess rated self). It definitely results in an engine that is extremely greedy, and almost anti-positional, but very tricky to prove wrong.
It works but it completely breaks standard behavior.
Arrow keys can work normally, or select paragraph, or do nothing, or behave erratically.
Page-up/down make work or may not work, and may have some weird interaction with the arrow keys.
The scrollbar is nonstandard on Chrome. It is not completely broken but the mouse pointer is wrong.
Mouse-based scrolling works, it is the only thing that seems to work as expected.
Reader mode doesn't work.
I don't understand why websites go out of their way to reimplement perfectly good browser behavior. I am sure it is a lot of hard work, and it is almost always done poorly, in fact, I am not sure there is a way of doing it correctly.
It cannot(at least not efficiently). There's 64 squares which could contain any one of 6 pieces or nothing. So you would need multiple u64s. In addition you need to store things like castling rights since they depend on previous moves.
Engines these days tend to use bitboards, which is just keeping multiple u64s each corresponding to a board with all the white/black knights, kings, pawns, etc. This is then manipulated using various bitwise operations.
Edit: It's also worth noting that compactness is not the most important thing for board representation. Stockfish for instance only stores one copy of the position per thread, so the effect of any overhead there is negligible. It's much more important that querying and mutating the board state is fast.
I don't agree with the reasoning in either of the other two answers you've been given, but Shannon (1950) gave the number of chess positions as somewhere around 10^43, so 150+ bits. The position accounts for almost all of the state.
You could do better with variable-length encodings and perhaps represent all "interesting" "plausible" positions in 64 bits, but as others said, compactness is really not a top priority in representations for chess engines, it's much more important to be able to query and update the representation.
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.)
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.
> The position accounts for almost all of the state.
I would argue that a complete game state depends on previous game states for the sake of repitition stalemates. The current state must include a set of previous positions that can possibly reoccur.
Having nerded out on this question in the past, I found that Wikipedia had one of the better discussions, with a Huffman encoding scheme that seemed like it should be near optimal. Someone has since deleted it but it can be found in the history
A) fixed list of piece coordinates: 32 pieces × (3 bits for row + 3 bits for column + 1 bit for whether it's alive) = 224 bits
B) list of live pieces: (3 bit row + 3 bit column + 1 bit for color + 3 bits for which piece) × up to 32 pieces = up to 320 bits
C) 8x8 array of the board: 64 squares × (1 bit for color + 3 bits for which piece) = 256 bits
Then there's the gamestate that isn't directly visible on the board:
- whose turn it is: 1 bit.
- castling rights: A needs 2 bits. B and C can pack it in with the 3 bits for pieces. there's 6 pieces so there's room for two more, one of which is a rook that's eligible to castle with.
- en passant: A needs a flag for each pawn so 16 bits. B and C can also pack in with the other spare piece being a pawn that just advanced two spaces.
- promotion: B and C get it free. A needs another 3 bits per pawn to indicate if and what it's promoted to (so 48 bits max)
- 50 moves without capture/pawn move optional stalemate: 6 bit counter from 0 to 50.
- 75 moves without capture/pawn move forced stalemate: make that 7 bits
- repitition stalemates: don't see a way around needing to know the previous board states. you need a copy of everything except the 50 move counter for previous turns. you can prune states that are impossible to return to.
A: 301 + (294 × #repeatable_states) bits
B: 328 + (321 × #repeatable_states) bits
C: 264 + (257 × #repeatable_states) bits
I'm sure there's savings to be made further compressing any of these with variable length encodings though (see links in other replies). I especially like the idea of encoding information as illegal states.
edit: originally said 4 bits for row and column but it's 3.
By "chess engine" the author refers to the AI/Machine Player, not the base of how to position the pieces, valid moves, turn taking, etc. which is what I thought "engine" would mean here (my thought was similar to a game engine vs AI/characters). For the "game engine" they're importing Chess.js. Totally fine, just a heads up since I did expect to see a truly from-0 since it says "how to build a Chess engine from scratch" and was confused when they imported a fully working "engine".
Maybe "How to build a Chess Automaton/AI Player" would be a better title? Unless in the Chess industry the "chess engine" refers to the machine player, which I do not know.
PS, this website also hijacks the "down key" and the "space key", making keyboard navigation harsh...
> Unless in the Chess industry the "chess engine" refers to the machine player, which I do not know.
"Chess engine" definitely means[0] what is the article about (I won't even repeat your words for it).
chess.js[1], ffish.js[2] or such are called chess libraries.
There is no ambiguity or confusion in these terms. If you happen to have one, pls update your terms, and don't bring it up again (so it can stay this way).
Exactly, that's why I noted "Unless in the Chess industry ...", the details of which I don't know. I only know a bit about general game making (I've tried Godot and GameMaker, some friends make games and we talk) so this was my opinion from a more general game point of view.
But still, from that Wikipedia description "a chess engine is a computer program that analyzes chess or chess variant positions, and generates a move or list of moves that it regards as strongest" that's what I mean, the chess.js package does all of this except the last step (analyzing the strongest). So it seems in the industry it's a mix between the "logic gameplay" and "AI", and this article is still only about the "AI/Automaton".
Chess Engine - is a well established term in the field. Position estimation and move generation is the hardest and most important aspect of a chess engine. In this sense chess.js may do many useful things, except the thing that would make it an "engine".
> Maybe "How to build a Chess Automaton/AI Player" would be a better title? Unless in the Chess industry the "chess engine" refers to the machine player, which I do not know.
I find this somewhat presumptuous. You wouldn't go to a different country and warn others that a particular word should mean something different based on your own (foreign language) experience, and propose a different word, with the caveat: "Unless in your country you do things differently".
If you think that your experience is common enough that a warning to fellow game-developers is warranted, do some research, find out that "Chess Engine" is a term that is contextually synonymous to "AI Player" and then inform others.
Yes, I said it because if it got me by surprise, I guessed it'd get a lot of people by surprise in HN as well. Agreed with that country analogy, but I believe this being a "Hacker News forum" and not "Chess news" the analogy would be more like if a foreigner came to my country and used a word, that has a meaning in their own country, but has a different meaning in my language. I would suggest them to adapt it to the local language, or explain to my friends what he's trying to say so there's no misunderstanding.
As another commenter said "FWIW I think that without having encountered the term ('chess engine') before, connecting chess ~ game and so chess engine ~> chess game engine is a pretty reasonable path to take in interpreting unfamiliar jargon."
I think your personal experience with games and game development may predispose you to believe that the majority of HN users share your experience and cultural vocabulary. But judging by the variety of topics discussed here weekly, I think the HN community is much more diverse in its interests than you are aware of. I think we all tend to be unaware of possibilities other than the ones we're accustomed to. (I couldn't have imagined that someone would think "Game Engine" when encountering the term "Chess Engine". For me it's clearly something much closer to the concept of a "Search Engine".)
As you can also see from several replies, there are many people who are familiar with the term. Extending the previous analogy of the foreign country, it's not immediately obvious who here is the native and who is the foreigner.
> As another commenter said "FWIW I think that without having encountered the term ('chess engine') before, connecting chess ~ game and so chess engine ~> chess game engine is a pretty reasonable path to take in interpreting unfamiliar jargon."
I see the following scenario on HN very often: There is some topic, in a less mainstream field, that reaches the front page, and inevitably one of the commenters is annoyed that some term in the headline, a term that happens to be well established in the field, doesn't correspond to their expectations. It's fine to try and interpret unfamiliar jargon, but when the result doesn't match your expectations, why not inform yourself and thus expand your domain of knowledge, instead of proposing an alternative syntax, which will only cause confusion: it will confuse field experts (arguably the target audience), it will confuse newcomers to the field, and it probably won't help the general audience, since we know that naming things is hard, and what may seem clear to you won't be clear to the next person.
FWIW I think that without having encountered the term ('chess engine') before, connecting chess ~ game and so chess engine ~> chess game engine is a pretty reasonable path to take in interpreting unfamiliar jargon.
Some of that hijacking is done by various front end JS libs, I've seen sites/projects where that kind of thing was happening and none of the devs weren't even aware it was part of some "batteries included" toolkit.
They are not hijacking anything, imo. They are simply using Notion.so to power the website. It's a note-taking app and this is the regular behavior of Notion. Nothing out of the ordinary.
Down key makes you navigate "blocks". Space key doesn't do anything since you're not typing in Notion.
There's a way for the OP to get around this behavior and make their website act more like a blog.
That would require SSR on Notion pages instead of a cloudflare worker script on their public Notion site which they appear to be doing currently.
Well, Notion is hijacking it then, but the difference as a reader is irrelevant, the point is that I cannot press neither space nor down to scroll down (if you scroll manually then press down, it'll jump to the "highlighted" paragraph, no scroll down).
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/...
[1]: https://github.com/official-stockfish/Stockfish/blob/master/...