Hacker News Reader

Comment by solardev | Hacker News Reader

Meanwhile the non-comp-sci dev in me is like, "why not just store every position in a simple JSON so everyone can read it and everything can parse it". Yeah, it might be half a kB, but you don't have to run through mental gymnastics just to render the pieces...

View on HN

I feel like we have an interesting tragedy of the commons situation of software engineering.

On the one hand, storing positions on JSON is quick to implement, easy to understand, easy to read, easy to hack on, and junior engineers and the people who have to deal with your code later will be able to pick it up and run with it easily.

On the other hand, when just about everyone is making this same ease-of-use/performance tradeoff, software bloat happens. Our computers are so much faster and beefier, but we never actually seem to be able to enjoy the benefits of that, in part because software engineers keep optimizing for quick and easy.

Maybe we shouldn't dogmatically reach for the easy no-nonsense solution every time, and instead consider whether maybe a little nonsense might, over time, save people a lot of time.

You can compress that JSON with a pre-trained dictionary and get a massive discount.

“This Kafka queue collects the zstd-compressed BSON chess messages encoded as base-64 and distributes it to the chess engine VM scale set worker pool for processing… what? Everyone knows chess AIs need large scale and programmer time is expensive! Anyway, the Databricks cluster for move analysis is over here, and…”

Iy's not meant for humans to read directly. The compact representation helps performance amd storage a lot when it comes to looking at a lot of positions. If you were to store it as a json most of your time would be spent parsing.

This is illustrated very well in Sebastian Lague's video "Coding Adventure: Making a Better Chess Bot" (https://www.youtube.com/watch?v=_vqlIPDR2TU).

Awesome video and, I'll admit, the timing makes me curious to know if that video maybe inspired some devs to either pick up this kind of encoding work, or maybe just to finish up some encoding work that they had already started.

Most likely unrelated, I know! Just a wondering in passing.

It's definitely possible! Even more so considering Sebastian also started a Coding Challenge for Tiny Chess Bots: https://www.youtube.com/watch?v=iScy18pVR58

In the early 90ies, we used to have pocket electronic chess games. I used to have myself one that was about the size of a pocket calculator (it actually was also a pocket calculator), which included a tiny board with tiny, tiny chess pieces. Not a strong opponent and quite slow, but good enough for casual games on the road.

I doubt you could fit that JSON file in its NVRAM. Sometimes I wonder how much sooner we could have had what smartphones offer us today if some technical choices had been made more... wisely.

But that's the endless conundrum Worse is better [1].

[1] https://dreamsongs.com/RiseOfWorseIsBetter.html

> 90ies

I've only seen 90s (nineties), never 90ies (ninety-ies). I am imagining the second one pronounced differently.

I might have seen it somewhere, but probably written by a non-native as well ;-) Thanks for the correction.

You need a compact encoding for chess engines that explore billions of states as fast as possible to plan the best move.

Well, this is arguably a kind of compression, right? So you'd be trading CPU time for fewer bytes? Is that a desirable tradeoff at chess engine scales?

Is your assertion that it takes more time for a CPU to read values out of a 30 byte struct and do a couple shifts and branches than to parse a JSON representation?

The JSON needs to be parsed only once. Then it is (or can be) just any object to your liking.

JSON is for storing data as text. Not work with that text all the time.

It's not just reading, you need to process the data to get castling availability, en passant target etc.

Bit packing/mapping et c. isn’t compression the way you’re thinking. What it is, is concise. It requires that the program know what each bit means, rather than telling the program what a value means (as a json structure might), so it shifts where meaning is assigned strictly to the program—a convention must be encoded in the program, not figured out at runtime, though technically you could turn this back into a form of config if you wanted, it just wouldn’t be jumbled up with your data—but it doesn’t really compress the data itself. It’s just efficient at representing it.

[edit] shorter version of the above: it stores the values, but doesn’t store what they mean.

To give you an example, the Syzygy tablebase for all endgame positions with 7 pieces remaining is 18.4 TB. The estimated size for 8 pieces is 2 PB.

There are different applications for different things: If you want to host a website with real-world tournament results involving only humans, you probably can get away with using more bytes. But if you're writing an engine that uses pre-computed positions, you want to be as compact as possible.

https://en.wikipedia.org/wiki/Endgame_tablebase#Computer_che...

I did laugh a bit at this bit because "conventional server" and "64 TB RAM" is hilarious to think about in 2023, but will probably be the base config in a Raspberry Pi in 2035 or so:

> In 2020, Ronald de Man estimated that 8-man tablebases would be economically feasible within 5–10 years, as just 2 PB of disk space would store them in Syzygy format, and they could be generated using existing code on a conventional server with 64 TB of RAM

It's not compression in the normal sense of the word. Most parsing is directly to data. So e.g. you know the square of some piece is the next 5 bits. In languages that allow it you can cast directly from the next bit offset to an e.g. byte. This is going to dramatically faster than parsing much more loosely structured JSON. As database sizes increase you also get worse performance there, so it's a double hit. So with these sort of representations you get orders of magnitude faster and smaller. Sometimes there really is a free lunch!

Also I'd add the sizes involved here are kind of insane. I wrote a database system that was using a substantially better compression that averaged out to ~19 bytes per position IIRC. And I was still getting on the order of 15 gigabytes of data per million games. Ideally you want to support at least 10 million games for a modern chess database, and 150 gigabytes is already getting kind of insane - especially considering you probably want it on an SSD. But if that was JSON, you'd be looking at terrabytes of data, which is just completely unacceptable.

CPUs excel at decompression; more than one engineer has remarked to me that the fastest way to populate a cache is to decompress data in-line.

Mostly for automation. Bots don't need to read and they are very happy to parse data.

People like to use bots to run thousands or millions of simulated games to test how good their bot is at chess and have it ranked.

Other people like to use the bots that were created to play chess as practice toward a certain skill level. Beginners can pick bots that are proven to be beginner level, through thousands or millions of simulated games.

The smaller the data footprint for the games, the faster and more efficiently the bots can play, which reduces cost and time. In a more practical sense, AI/ML algorithms can be more efficient with tiny data sizes for a bunch of complicated reasons.

So, overall, this is "nerd sniping" to develop better chess players, both human and automated. It's not the most extensible presentation, I'll grant you, but I'm sure it's as fun as Regex Golf, or any other data-packing stuff.

P.S. I'm sure the comp-sci dev in you already knew all this; this is just a bill in case anyone read your comment and truly didn't already know all of this.

While we're at it, just take a screenshot of the board

in C/C++ code you dont really need to do mental gymnastics either. I can imagine writing a struct with some clever unions to decode this all in one shot. the main benefit as others have point out is 1) to store large number (think billions) of such game positions & searching through them. Also if you are developing for cloud deployment you probably want to use minimal storage needed for space & egress b/w reasons. last reason is something that may not be obvious but if you have some algos that can run efficiently on gpus then you probably want to lay the data out such that its easy(ier) to load in SIMD engines. overall not a bad idea.

Now try building a chess site to store millions of games with hundreds of millions of game states to search over. It's nice that you can very cheaply fit a board into a fixed size column on a database and store the entire game history into around a kilobyte.

You'd write a wrapper to extract our the dense form to something with a nice interface.

Because easy readable code is less important for competitive modern chess engines than maximum speed and memory efficiency.

My lazy brain says "just take the FENs, remove the slashes etc that are just for human readability, and compress the result with Gzip or do. Bound to be smaller in practice."

You’ll never get to the moon on 4kb Apollo computers like that

Yep, everyone’s happy until the cosmic rays hit

Reply on news.ycombinator.com