8 ms·

How to build a chess engine

230 points by fredrickd 4y ago

franciscop 4y ago
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...
- 1over137 4y ago
  >PS, this website also hijacks the "down key" and the "space key", making keyboard navigation harsh... Why would they do that? It's not like they made the keys do something else instead. :(
  - djbusby 4y ago
    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.
- NoThisIsMe 4y ago
  I see what you're getting at but for whatever reason "chess engine" in fact usually refers to what you're calling the AI player -- https://en.m.wikipedia.org/wiki/Chess_engine https://en.m.wikipedia.org/wiki/Chess_engine
  - franciscop 4y ago
    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".
    - greenpeas 4y ago
      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.
      - franciscop 4y ago
        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."
- jlittel 4y ago
  Engine is the common term in chess for the program that analyzes a game.
- bmacho 4y ago
  > 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). [0]: https://en.wikipedia.org/wiki/Chess_engine https://en.wikipedia.org/wiki/Chess_engine [1]: https://www.npmjs.com/package/chess.js https://www.npmjs.com/package/chess.js [2]: https://www.npmjs.com/package/ffish https://www.npmjs.com/package/ffish
  - megapoliss 4y ago
    Rough, Chess engine = Interface protocol (like UCI) + Move Generator + Evaluation Function. Article talks about evaluation function only (since it reuse move generator and interface).
- tr1ll10nb1ll 4y ago
  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.
  - franciscop 4y ago
    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).
- qwery 4y ago
  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.
mixedmath 4y ago
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. [1]: https://www.chessprogramming.org/Main_Page https://www.chessprogramming.org/Main_Page
- fredrickd 4y ago
  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 :)
paradite 4y ago
I'm also building an AI engine for games, where you can try different algorithms (heuristics, Monte Carlo tree search, expectimax, deep ML). For starter I made it for 2048. You can check it out here: https://ai-simulator.com/ https://ai-simulator.com/
mtlmtlmtlmtl 4y ago
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/src/tt.h https://github.com/official-stockfish/Stockfish/blob/master/... [1]: https://github.com/official-stockfish/Stockfish/blob/master/src/tt.cpp https://github.com/official-stockfish/Stockfish/blob/master/...
- agalunar 4y ago
  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.
  - mtlmtlmtlmtl 4y ago
    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.
    - agalunar 4y ago
      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.
nphard85 4y ago
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).
- orlp 4y ago
  > 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.
infogulch 4y ago
What is the most compact representation for a complete chess game state? Can it be as low as 64 bits?
- Etheryte 4y ago
  Since the board itself is 64 squares and there's many pieces that can move to any square on the board it can't be that low.
- mtlmtlmtlmtl 4y ago
  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.
- dmurray 4y ago
  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.
  - Sesse__ 4y ago
    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=e35fc5cb26925f12d78e0e0590ea578f&start=40 http://talkchess.com/forum3/viewtopic.php?f=7&t=77685&sid=e3... Practically speaking, https://github.com/tromp/ChessPositionRanking 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.
russianGuy83829 4y ago
horrible website, scrolling doesn’t work
- kcartlidge 4y ago
  Yes it does.
  - GuB-42 4y ago
    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.
    - kcartlidge 4y ago
      Fair enough. > Mouse-based scrolling works, it is the only thing that seems to work as expected. TBH that's the only option I used, hence the different experience.
tony_codes 4y ago
Great article. Buidling a chess engine is an awesome way to level up as a software developer! https://blog.devgenius.io/level-up-as-a-software-engineer-by-writing-a-chess-engine-896b7f8eb443 https://blog.devgenius.io/level-up-as-a-software-engineer-by...
Jaruzel 4y ago
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.
- tzs 4y ago
  Writing an engine you can beat is easy. 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.
- krsrhe 4y ago
  Rubbish chess engines aren’t fun. MacOS has one built in. Try CrazyBishop / TheChess / Chess Lvl.100 Or chess.com leveled bots, or play with handicap, Or play humans online! Infinite supply of beatable opponents.
thom 4y ago
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.
tikej 4y ago
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.
- btdmaster 4y ago
  https://boristrapsky.com https://boristrapsky.com (https://lichess.org/@/Boris-Trapsky https://lichess.org/@/Boris-Trapsky) plays against a typical, rather than perfect-playing, opponent but I could not find any source code.
- lgas 4y ago
  You might find https://www.youtube.com/watch?v=DpXy041BIlA https://www.youtube.com/watch?v=DpXy041BIlA interesting. He creates a tournament of "imperfect" engines.
dmeybohm 4y ago
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. [1] https://github.com/dmeybohm/wisdom-chess https://github.com/dmeybohm/wisdom-chess [2] https://wisdom-chess.netlify.app/ https://wisdom-chess.netlify.app/
ape4 4y ago
This seems wrong: // call this function again in 5 secs window.setTimeout(makeRandomMove, 500)
jeremysalwen 4y ago
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. You can check it out at https://github.com/jeremysalwen/grubchess https://github.com/jeremysalwen/grubchess.

230 points by fredrickd 4y ago

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

1over137 4y ago
>PS, this website also hijacks the "down key" and the "space key", making keyboard navigation harsh... Why would they do that? It's not like they made the keys do something else instead. :(
- djbusby 4y ago
  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.
NoThisIsMe 4y ago
I see what you're getting at but for whatever reason "chess engine" in fact usually refers to what you're calling the AI player -- https://en.m.wikipedia.org/wiki/Chess_engine https://en.m.wikipedia.org/wiki/Chess_engine
- franciscop 4y ago
  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".
  - greenpeas 4y ago
    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.
    - franciscop 4y ago
      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."
jlittel 4y ago
Engine is the common term in chess for the program that analyzes a game.
bmacho 4y ago
> 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). [0]: https://en.wikipedia.org/wiki/Chess_engine https://en.wikipedia.org/wiki/Chess_engine [1]: https://www.npmjs.com/package/chess.js https://www.npmjs.com/package/chess.js [2]: https://www.npmjs.com/package/ffish https://www.npmjs.com/package/ffish
- megapoliss 4y ago
  Rough, Chess engine = Interface protocol (like UCI) + Move Generator + Evaluation Function. Article talks about evaluation function only (since it reuse move generator and interface).
tr1ll10nb1ll 4y ago
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.
- franciscop 4y ago
  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).
qwery 4y ago
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.

mixedmath 4y ago

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. [1]: https://www.chessprogramming.org/Main_Page https://www.chessprogramming.org/Main_Page

fredrickd 4y ago
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 :)

paradite 4y ago

I'm also building an AI engine for games, where you can try different algorithms (heuristics, Monte Carlo tree search, expectimax, deep ML). For starter I made it for 2048. You can check it out here: https://ai-simulator.com/ https://ai-simulator.com/

mtlmtlmtlmtl 4y ago

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/src/tt.h https://github.com/official-stockfish/Stockfish/blob/master/... [1]: https://github.com/official-stockfish/Stockfish/blob/master/src/tt.cpp https://github.com/official-stockfish/Stockfish/blob/master/...

agalunar 4y ago
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.
- mtlmtlmtlmtl 4y ago
  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.
  - agalunar 4y ago
    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.

nphard85 4y ago

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

orlp 4y ago
> 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.

infogulch 4y ago

What is the most compact representation for a complete chess game state? Can it be as low as 64 bits?

Etheryte 4y ago
Since the board itself is 64 squares and there's many pieces that can move to any square on the board it can't be that low.
mtlmtlmtlmtl 4y ago
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.
dmurray 4y ago
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.
- Sesse__ 4y ago
  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=e35fc5cb26925f12d78e0e0590ea578f&start=40 http://talkchess.com/forum3/viewtopic.php?f=7&t=77685&sid=e3... Practically speaking, https://github.com/tromp/ChessPositionRanking 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.

russianGuy83829 4y ago

horrible website, scrolling doesn’t work

kcartlidge 4y ago
Yes it does.
- GuB-42 4y ago
  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.
  - kcartlidge 4y ago
    Fair enough. > Mouse-based scrolling works, it is the only thing that seems to work as expected. TBH that's the only option I used, hence the different experience.

tony_codes 4y ago

Great article. Buidling a chess engine is an awesome way to level up as a software developer! https://blog.devgenius.io/level-up-as-a-software-engineer-by-writing-a-chess-engine-896b7f8eb443 https://blog.devgenius.io/level-up-as-a-software-engineer-by...

Jaruzel 4y ago

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.

tzs 4y ago
Writing an engine you can beat is easy. 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.
krsrhe 4y ago
Rubbish chess engines aren’t fun. MacOS has one built in. Try CrazyBishop / TheChess / Chess Lvl.100 Or chess.com leveled bots, or play with handicap, Or play humans online! Infinite supply of beatable opponents.

thom 4y ago

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.

tikej 4y ago

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.

btdmaster 4y ago
https://boristrapsky.com https://boristrapsky.com (https://lichess.org/@/Boris-Trapsky https://lichess.org/@/Boris-Trapsky) plays against a typical, rather than perfect-playing, opponent but I could not find any source code.
lgas 4y ago
You might find https://www.youtube.com/watch?v=DpXy041BIlA https://www.youtube.com/watch?v=DpXy041BIlA interesting. He creates a tournament of "imperfect" engines.

dmeybohm 4y ago

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. [1] https://github.com/dmeybohm/wisdom-chess https://github.com/dmeybohm/wisdom-chess [2] https://wisdom-chess.netlify.app/ https://wisdom-chess.netlify.app/

ape4 4y ago

This seems wrong: // call this function again in 5 secs window.setTimeout(makeRandomMove, 500)

jeremysalwen 4y ago

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. You can check it out at https://github.com/jeremysalwen/grubchess https://github.com/jeremysalwen/grubchess.