How to build a chess engine(chessengines.org) |
How to build a chess engine(chessengines.org) |
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/...
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.
Is this undefined behavior or does the memory model of C++ guarantee anything given the reads/writes are presumably whole words?
I realise that the implementation doesn't actually have to be deterministic, but does the language guarantee anything in these cases?
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.
* 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.
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.
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 :)
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.
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.
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.
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).
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.
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.
Try CrazyBishop / TheChess / Chess Lvl.100
Or chess.com leveled bots, or play with handicap, Or play humans online! Infinite supply of beatable opponents.
For starter I made it for 2048. You can check it out here: https://ai-simulator.com/
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.
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.
// call this function again in 5 secs
window.setTimeout(makeRandomMove, 500)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...
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.
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.
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.
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.
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.
Chess computing is one area where there’s a lot of attention to hard details as well as the algorithms, lots of gems like this in the genre
"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
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".
Why would they do that? It's not like they made the keys do something else instead. :(
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.
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.
> 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.
> 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.
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."
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.
That would be 149 bits!
148 bits + 1 bit = 149 bits