Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Very clever, but that's the problem, clever is never the correct solution.

With a few bytes more more you can create an implementation that is a lot easier to understand. Bytes are cheap, developer time isn't.



"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something."

https://news.ycombinator.com/newsguidelines.html

I'd especially hammer the point in this case, because clever hacks are very much on topic for Hacker News. They are, in fact, what gave birth to the word hacker and the idea of hacking in the first place. Not only that but it was precisely the clever hacks with no particular utility that were prized most highly!


If you are writing a chess engine you'll want to store hundreds of millions of positions while you search for the best move and at that scale a byte is important because it gets multiplied by an enormous factor.


But that is a totally different problem which requires far fewer bytes to represent. For that problem you are just considering of the valid pieces which made a move and what board that came from. Storing a single move is far cheaper than an entire board state.


Not when you include transpositions, where you arrive at the same position from a different move order, in which case saving board states instead of moves could be very valuable.


There are transposition tables for that though. They don't store the board state actually. For Stockfish, transposition table entries are 10 bytes each, 16 bits of which are the low bits(or high? Can't remember) of a zobrist hash of the board state. The other 48 bits of the hash are used for addressing into the hash table, but aren't stored in it. The rest of the entry will be stuff like the best move found during the previous search(16 bits), the depth of that search(8 bits), evaluation(2 different ones at 16 bits each), and various bits of data like node type and age of the entry(for deciding which entry to replace, because this table is always full). Collisions can occasionally happen, but saving a full board state to eliminate them would cost far too much, since no matter how big you make the table, it'll never be big enough to cache all the board states a search visits.

In Stockfish, there will only be one full-fledged board state in memory per search thread. So the size of the board state is pretty much irrelevant to performance. What's important is reducing the overhead of generating possible moves, applying those moves to the board state, and hashing the board state, which is what magic bitboards are for.


That's interesting, I didn't know about transposition tables, thanks for the explanation!


If they cared about that, then it wouldn't have been written in python. This is an exercise of the author showing how clever they are.


This is pretty standard ( or at least used to be 20 years ago ) in high performance chess programming, see

https://www.chessprogramming.org/Bitboards

https://healeycodes.com/visualizing-chess-bitboards




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: