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

Improved chess game compression (2018)

lichess.org

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Improved chess game compression (2018)

#31

Post by Someone »

mlyle wrote: post #26
chongli wrote: post #23

Earlier quoted context omitted.

it feels like cheating to call it the OCR record holder This is how humans recognize text though. For the most part, humans don’t try to read languages we don’t understand. To deny a computer access to context is like asking a human to transcribe a language they don’t understand.

I'm a pretty fast typist but if you ask me to transcribe latin text of gibberish or of a language I don't know.... not so fast. A lot of it is how much I have to slow down to be accurate in recognizing characters.

I would guess your typing also gets significantly slower. Mine does; I’ve gone through periods where I had trouble typing the word in because my muscle memory turned it into int.

Re: Improved chess game compression (2018)

#32

Post by SilasX »

gowld wrote: post #30
willvarfar wrote: post #7

Hmm, a lot of effort to make documents small, but then storing it in mongodb?!?! If size and performance are a focus, just store them in a normal sorted table with compression (e.g. leveldb, or mysql using rocksdb). This means all these small documents can be compressed with repetition between games and not just within each game. And probably much much faster and simpler etc. Basically, the size taken by the database…

Games are quite small -- under 50 turns, each under 2 bytes in binary, but more if you start with simple text languge before compression. You need to compress each game individually. Would database-wide compression work?

I see several levels of compression:

1) First, as you mentioned, the limited symbol table for expressing all the moves.

2) But not every move is possible; you just need a way to order all the possible moves and then say the nth of those moves.

3) Even better: not all of those moves are equally likely. You can define (n cycles of) a chess playing engine that ranks all moves and reserves shorter symbols for the best moves (as judged within that time frame). Players tend to select higher ranked moves, so that’s another regularity to exploit.

Of course, 3) comes at the cost of compression/extraction time.

Re: Improved chess game compression (2018)

#33

Post by hinkley »

gowld wrote: post #29

> Our database runs on 3 servers (1 primary, 2 secondaries), each with two 480GB SSDs in a RAID 1 configuration Algorithmically cool, but quite a lot of work to save Converting the data to the new format cost more than upgrading disks.

In the conclusion they mentioned rate of growth as well.

If rate of growth is disk usage is at or below the rate of growth in mid-tier SSDs, then yes, it's $500/yr. If you are growing faster than that, then an improvement might be saving you $350/yr + $150/yr², and a wall in the future might be pushed out for years.

With your Cloud provider, it might be hard to get more disk, memory, or CPU without paying for more of the other two. Also, many real organizations and vendor agreements are full of the most stupid artificial constraints. Just because someone else can build a 1PB SSD storage array doesn't mean that any of my coworkers will be allowed to build one any time soon. CAPEX austerity measures are among the most frustrating penny-wise pound-foolish policies we have to deal with.

Re: Improved chess game compression (2018)

#34

Post by willvarfar »

gowld wrote: post #30
willvarfar wrote: post #7

Hmm, a lot of effort to make documents small, but then storing it in mongodb?!?! If size and performance are a focus, just store them in a normal sorted table with compression (e.g. leveldb, or mysql using rocksdb). This means all these small documents can be compressed with repetition between games and not just within each game. And probably much much faster and simpler etc. Basically, the size taken by the database…

Games are quite small -- under 50 turns, each under 2 bytes in binary, but more if you start with simple text languge before compression. You need to compress each game individually. Would database-wide compression work?

You do not need to compress every game individually. Behind the scenes, your mainstream database is storing the data in pages, and these pages - containing many adjacent rows - can be compressed.

The compression level achieved at a page level is much higher than compressing rows individually because there is lots of repetition between rows. It also speeds up io and other good things. It is almost always good, which is why the most modern database storage engines do it and do it by default.

Consider a csv file, and compare it to the same data stored as json objects, one row per line. The uncompressed json file is going to be much bigger, as the columns are repeated in every line. But both files gzip to much the same size, because all those keys are repeated again and again and the two files have basically the same entropy.

On the other hand, compressing each line in the file individually would be a poor choice, giving relatively poor gains.

There were database engines that did row-level compression, but these performed poorly and I know of nobody who used eg innodb compression.

Re: Improved chess game compression (2018)

#35

Post by jameshart »

steerablesafe wrote: post #16

As I understand it uses the Huffman-code for all moves including the opening moves. Alternatively statistics could be gathered for all first moves, all second moves, etc..., then different Huffmann-code could be applied for opening moves. I wouldn't be surprised if the statistics for the first few moves were significantly different to the moves deep into the game.

Probably worth just having short Huffman codes specifically to encode particular opening sequences, before referring to per-move coding

Re: Improved chess game compression (2018)

#36

Post by linkdd »

boarquantile wrote: post #28
jameshart wrote: post #17

the basis of this algorithm is to rank the possible moves from the current position, then use that to choose a Huffman encoding. In essence, they use a very naive single-move-look ahead chess AI to quickly rank moves giving them a crude measure for how ‘surprising’ a particular move would be at that point in the game. Interesting question: If you just generated the bit string that corresponded to taking the ‘most obv…

The most boring chess game according to Lichess move compression: https://lichess.org/study/5jQeJXXb

damn, that's some "obvious" moves right there
Post reply on HN