[srean]

Paging sdenton4.

Once when I was in grad school I noticed an announcement for a lighthearted programming competition for rock-paper-scissors playing agent. The deadline was barely hours away and I was behind on a report for funding or course work, I can't recall now.

As it always happens with me, a non-serious non-essential task suddenly looks attractive over some work I had been procrastinating on.

With no time available to code up a submission from scratch i I just rigged up the zlib compression library to decide the next play. It considered appending the 3 potential completions of the play so far and compressed the sequence. Whichever appended symbol gave the maximum compression was my agent's next move.

It was just a few lines of code and it did surprisingly well. A universal compression library/algorithm that works better for short strings would have performed better. Zlib is an universal compressor but does not converge to the entropy of a sequence very fast.

[woliveirajr]

Seems a lot like Normalized Compression Distance (https://en.wikipedia.org/wiki/Normalized_compression_distanc...) and Kolmogorov Complexity.

[srean]

Good compression, necessarily, requires good "next token" probability estimation. I was essentially using zlib's implicit probability estimator.