Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to build a chess engine

chessengines.org

Post reply on HN
Print view View original

11–20 of 58 posts

Re: How to build a chess engine

#11

Post by mtlmtlmtlmtl »

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

[1]: https://github.com/official-stockfish/Stockfish/blob/master/...

Re: How to build a chess engine

#12

Post by agalunar »

mtlmtlmtlmtl wrote: post #11

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…

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.

Re: How to build a chess engine

#13

Post by mtlmtlmtlmtl »

agalunar wrote: post #12
mtlmtlmtlmtl wrote: post #11

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…

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.

Re: How to build a chess engine

#14

Post by haunter »

mtlmtlmtlmtl wrote: post #11

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…

Here is the same in sjeng used by Apple in the macOS Chess.app https://opensource.apple.com/source/Chess/Chess-410.4.1/sjen...

Re: How to build a chess engine

#15

Post by nphard85 »

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

Re: How to build a chess engine

#16

Post by mtlmtlmtlmtl »

haunter wrote: post #14
mtlmtlmtlmtl wrote: post #11

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…

Here is the same in sjeng used by Apple in the macOS Chess.app https://opensource.apple.com/source/Chess/Chess-410.4.1/sjen...

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.

Re: How to build a chess engine

#19

Post by mtlmtlmtlmtl »

infogulch wrote: post #17

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

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.

Re: How to build a chess engine

#20

Post by bmacho »

franciscop wrote: post #2

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 scrat…

> 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

[1]: https://www.npmjs.com/package/chess.js

[2]: https://www.npmjs.com/package/ffish

Post reply on HN