This nicely illustrates the point of the Hutter Prize, that efficient compression comes from understanding the content on a nontrivial level.
Improved chess game compression (2018)
21–30 of 36 posts
Re: Improved chess game compression (2018)
#22This reminds me where many years ago I learned about the world record holder for computer optical character recognition (OCR) accuracy. The computer scientists took as a target an eastern European chess journal which printed move-by-move reports of tournament chess matches. They incorporated a crude chess engine in the recognition step estimating the liklihood of next moves and combining that with the OCR engine likl…
> It took hundreds of hours of human review time to find a single OCR mistake from this process!
This stands out to me as improbable. Not in that the error rate could be that low, but in that they actually had humans spend hundreds of hours checking the accuracy of difficult character recognition. How did that happen?
Re: Improved chess game compression (2018)
#23This reminds me where many years ago I learned about the world record holder for computer optical character recognition (OCR) accuracy. The computer scientists took as a target an eastern European chess journal which printed move-by-move reports of tournament chess matches. They incorporated a crude chess engine in the recognition step estimating the liklihood of next moves and combining that with the OCR engine likl…
That's really awesome, but it feels like cheating to call it the OCR record holder. It's really OCR + context. However it would be interesting if you could apply the same idea at the word and sentence level of written language. I'm guessing there are people that already do this.
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.
Re: Improved chess game compression (2018)
#24This reminds me where many years ago I learned about the world record holder for computer optical character recognition (OCR) accuracy. The computer scientists took as a target an eastern European chess journal which printed move-by-move reports of tournament chess matches. They incorporated a crude chess engine in the recognition step estimating the liklihood of next moves and combining that with the OCR engine likl…
> It took hundreds of hours of human review time to find a single OCR mistake from this process! This stands out to me as improbable. Not in that the error rate could be that low, but in that they actually had humans spend hundreds of hours checking the accuracy of difficult character recognition. How did that happen?
Put a handful of grad students in a room for a week and you have hundreds of hours right there.
Re: Improved chess game compression (2018)
#25This reminds me where many years ago I learned about the world record holder for computer optical character recognition (OCR) accuracy. The computer scientists took as a target an eastern European chess journal which printed move-by-move reports of tournament chess matches. They incorporated a crude chess engine in the recognition step estimating the liklihood of next moves and combining that with the OCR engine likl…
> It took hundreds of hours of human review time to find a single OCR mistake from this process! This stands out to me as improbable. Not in that the error rate could be that low, but in that they actually had humans spend hundreds of hours checking the accuracy of difficult character recognition. How did that happen?
I searched out the article: "Reading Chess", 1990, HS Baird and Ken Thompson. (Yes, that Ken Thompson).
http://doc.cat-v.org/bell_labs/reading_chess/reading_chess.p...
It doesn't actually quantify the human proofreading time. I might have recalled incorrectly; I heard about this in the late 1990's as a war story from another OCR researcher.
Re: Improved chess game compression (2018)
#26Earlier quoted context omitted.
That's really awesome, but it feels like cheating to call it the OCR record holder. It's really OCR + context. However it would be interesting if you could apply the same idea at the word and sentence level of written language. I'm guessing there are people that already do this.
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.
Re: Improved chess game compression (2018)
#27Earlier quoted context omitted.
> It took hundreds of hours of human review time to find a single OCR mistake from this process! This stands out to me as improbable. Not in that the error rate could be that low, but in that they actually had humans spend hundreds of hours checking the accuracy of difficult character recognition. How did that happen?
I searched out the article: "Reading Chess", 1990, HS Baird and Ken Thompson. (Yes, that Ken Thompson). http://doc.cat-v.org/bell_labs/reading_chess/reading_chess.p... It doesn't actually quantify the human proofreading time. I might have recalled incorrectly; I heard about this in the late 1990's as a war story from another OCR researcher.
It's an embarassing problem to have a system with "accuracy to high to measure"!
Re: Improved chess game compression (2018)
#28the 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
Re: Improved chess game compression (2018)
#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.
Re: Improved chess game compression (2018)
#30Hmm, 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?