3 ms·

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

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

x86x87 3y ago
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.
- Timon3 3y ago
  This is illustrated very well in Sebastian Lague's video "Coding Adventure: Making a Better Chess Bot" (https://www.youtube.com/watch?v=_vqlIPDR2TU https://www.youtube.com/watch?v=_vqlIPDR2TU).
  - catapart 3y ago
    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.
    - Timon3 3y ago
      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 https://www.youtube.com/watch?v=iScy18pVR58
School-Cotton 3y ago
Because easy readable code is less important for competitive modern chess engines than maximum speed and memory efficiency.
Scarblac 3y ago
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."
awegio 3y ago
You need a compact encoding for chess engines that explore billions of states as fast as possible to plan the best move.
- solardev 3y ago
  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?
  - cylon13 3y ago
    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?
    - hutzlibu 3y ago
      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.
    - croes 3y ago
      It's not just reading, you need to process the data to get castling availability, en passant target etc.
  - somenameforme 3y ago
    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.
alexyz12 3y ago
You’ll never get to the moon on 4kb Apollo computers like that
personjerry 3y ago
While we're at it, just take a screenshot of the board
catapart 3y ago
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.
DesiLurker 3y ago
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.
about3fitty 3y ago
Yep, everyone’s happy until the cosmic rays hit
VyseofArcadia 3y ago
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.
- thriftwy 3y ago
  You can compress that JSON with a pre-trained dictionary and get a massive discount.
  - jiggawatts 3y ago
    “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…”
treyd 3y ago
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.
astrobe_ 3y ago
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 https://dreamsongs.com/RiseOfWorseIsBetter.html
- kaashif 3y ago
  > 90ies I've only seen 90s (nineties), never 90ies (ninety-ies). I am imagining the second one pronounced differently.
  - astrobe_ 3y ago
    I might have seen it somewhere, but probably written by a non-native as well ;-) Thanks for the correction.
  - deleted 3y ago
    [deleted]

x86x87 3y ago

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.

Timon3 3y ago
This is illustrated very well in Sebastian Lague's video "Coding Adventure: Making a Better Chess Bot" (https://www.youtube.com/watch?v=_vqlIPDR2TU https://www.youtube.com/watch?v=_vqlIPDR2TU).
- catapart 3y ago
  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.
  - Timon3 3y ago
    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 https://www.youtube.com/watch?v=iScy18pVR58

School-Cotton 3y ago

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

Scarblac 3y ago

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

awegio 3y ago

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

solardev 3y ago
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?
- cylon13 3y ago
  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?
  - hutzlibu 3y ago
    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.
  - croes 3y ago
    It's not just reading, you need to process the data to get castling availability, en passant target etc.
- somenameforme 3y ago
  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.

alexyz12 3y ago

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

personjerry 3y ago

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

catapart 3y ago

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.

DesiLurker 3y ago

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.

about3fitty 3y ago

Yep, everyone’s happy until the cosmic rays hit

VyseofArcadia 3y ago

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.

thriftwy 3y ago
You can compress that JSON with a pre-trained dictionary and get a massive discount.
- jiggawatts 3y ago
  “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…”

treyd 3y ago

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.

astrobe_ 3y ago

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 https://dreamsongs.com/RiseOfWorseIsBetter.html

kaashif 3y ago
> 90ies I've only seen 90s (nineties), never 90ies (ninety-ies). I am imagining the second one pronounced differently.
- astrobe_ 3y ago
  I might have seen it somewhere, but probably written by a non-native as well ;-) Thanks for the correction.
- deleted 3y ago
  [deleted]