Building My Own Chess Engine | Hacker News

graceacupuncture - 04/09/2022 - NEWS - 169 Views

For what it's worth, there is a pretty solid conventional wisdom in this space.

> - A simpler but much faster engine will beat a more complex engine any time because the advantage of another ply easily outweighs the advantage of some clever algo.

Depends a lot on what you call "simple". Stockfish's search and evaluation subroutines are pretty complex and distinctly clever:

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

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

But I agree that early on, simple is the way to go. It's much easier to optimize a simple engine.

> - A 10x10 board with an unreachable edge has some advantages [...]

Maybe in theory, but FWIW I don't know of any modern engine that does this. A more popular variant of the 10x10 or 10x12 idea was, back in the day, the 0x88 layout:

https://www.chessprogramming.org/0x88

If you're going to be writing an engine today from scratch, use the bitboard representation. It's easy to implement and has the most resources out there if you need help.

(Bitboards is just the idea of representing the game state as a bunch of 64-bit ints, with one u64 per white/black type of piece.)

Your example use-case, of knight posisitions, is usually solved with bitboards using an 64-element array mapping squares to a bitboard of all the places a knight on that square can go. Here's where Stockfish does that:

https://github.com/official-stockfish/Stockfish/blob/b06ef36...

Other commenters have noted that you can do a slightly fancier version of this lookup table technique to solve for the sliding pieces (bishops and rooks (queens are a bitwise OR of bishops and rooks)), because the raw data is low entropy, so finding a perfect hash function ("magic bitboard", in the lingo) is fast enough to do on startup:

https://github.com/official-stockfish/Stockfish/blob/b06ef36...

It's existing techniques like this that make bitboards a good choice for beginners; if you get stuck, you can find resources online.

> - Optimization of engine code is much harder than optimization of the yield function.

Big +1 there! The yield function is also much easier to A/B test.

Building My Own Chess Engine | Hacker News

> - It is much better to not generate 'bad' moves than it is to prune them away after a lot of extra work has been done. Colin Wrights' law: 'You can't make computers faster, you can only make them do less work' clearly applies here.

Yes, but it's pretty hard to reliably get your move generator to generate good moves first. The other side of making mixmax search fast is quickly throwing out branches that aren't relevant.

For instance, delta pruning and null-move pruning do this by trying to detect if one of the sides has thrown the game with their last move; since minmax is about assuming optimal play on both sides, branches where someone makes a blunder aren't worth looking into.

> - memoization can bring insane speed gains.

Yup! Also, a lot of engines have optimized routines that let you undo a move quickly, without having to keep a redundant stack of every position's state, which would involve a lot of memcpy-ing.

Have fun! I had to stop doing chess engines, they were becoming too much of a distraction for me. I'm kind of glad ML-AI is starting to beat human-crafted AI in chess, that way the space can go back to being a fun little hacker cottage industry.

Edit: Oh! When making a chess engine, start by implementing "perft":

https://www.chessprogramming.org/Perft

That way you can compare how many legal moves your engine thinks there is in a position, versus how many Stockfish or some other known-good engine thinks there is. It's the closest thing there is to unit tests in the space.