Tic Tac Toe 1k Challenge

[raidho36]

Your AI has a fatal flaw - it always does exactly the same thing. I've quickly discovered winning strategies: top left - bottom left - bottom right and top left - top mid - center. It fails to protect itself every time.

You'd be surprised but getting the code to compress well is a difficult second-guessing process that requires substantial knowledge of the compression algorithm. As you mentioned, not all kinds of data are compressible, much less well compressible. At the same time, some kinds of data compress really well. So you need to know what you can exploit and what you should avoid. Also yes there are some characters that will corrupt the data stream, you need to produce such compressed output that doesn't contains these characters - odds of random 1024 byte string not to contain one specific character is 1.82% only - not to contain 2 characters is that squared i.e. 0.033% and so on. And it's a related figure - (good) compressors produce output that can not be encoded with fewer bits of data, same as white noise.

[Inny]

Just to put my opinion in there on compression: The decompression code probably has to be in your main.lua and be run, so that it gets counted as part of your character count. The same would be true for all clever string manipulation that gets done (which happened in some of the 1k terminal entries). love.math.decompress is just outside the spirit of the challenges, though if you're doing something super novel with it, explain your technique and see if the crowd finds delight in it or not.

If it's external, then you wouldn't count it. For instance, the compression we get from zipping main.lua and renaming it to a .love file, the result after that compression isn't your entry's size.

As for using lua-minifier, I'm cool with it, since you're going to be tweaking the bajesus out of your code to make the minifier work best. I had to with the asteroids challenge. But if you can beat the minifier, go for it!

The whole fun and spirit of these challenges is either (1) to see how many features we can fit within 1k, or (2) See how small we can get the character count of the smallest set of features.

[raidho36]

love.math.decompress is just outside the spirit of the challenges

yet

As for using lua-minifier, I'm cool with it

Come on you can't be for real. This minifying tool does same exact thing as real compression except worse because it only removes redundant characters from the stream but doesn't optimize total redundancy of the stream.

since you're going to be tweaking the bajesus out of your code to make the minifier work best

Which applies tenfold to using real compression? Yet real compression is bad-bad?

What are you smoking my man, please do share!

[Positive07]

My AI is totally flawed I know, I have the intention to improve it, yet I first wanted to get the size under 1K, when I added the AI it went over to 1400 bytes so I had to reduce the code a lot.

I challenge people to not use minifiers, I'm sure that they can do better and it feels good to reduce the size manually, and it goes with the no-tools no-help no-external-resources spirit of the challenge. I yet don't know what raidho did in order to get compression right so I can't tell you if I can consider it "in the spirit of the challenge", I still consider that if you explained the process we may change our mind

[raidho36]

I challenge people to not use minifiers, I'm sure that they can do better and it feels good to reduce the size manually, and it goes with the no-tools no-help no-external-resources spirit of the challenge.

Yes if it's put that way it makes total sense, but then you must produce all code by hand and minifiers are of limits. But it wasn't, and use of minifiers was prevalent even before this one. It reads a lot like "you can cheat on this test and use a calculator, but not a scientific one".

Without compression you write for lowest character count, with - for best compressibility. Compression algorithms can be very complex and predicting compressibility will be difficult without knowledge - character count has no complexity to it, it's just a number.

The zlib uses deflate and Huffman coding. Deflate detects string repetitions and substitutes the repetition with a reference to pre-existing identical string. Huffman coding computes occurrence frequency and encodes frequently used codes with fewer bits. Infrequently used codes inflate and take more bits than normal.

So you'll immediately see that it's OK to write more code as long as it's identical to something else, because it will be compressed to just one or two bytes per match during deflate pass. Additionally, if deflate produces a lot of identical codes, they get compressed further. Unique code however doesn't compress. This flips the table on its head - instead of avoiding repetitions, you try to reuse as much code as possible. But also, if you improve repetition through setting up something else, you often just increase in binary size despite better compression ratio. However minified code still compresses better and the better it is minified, the smaller is the binary. Pro tip: the minifier in the last link produces less compressible code.

Lastly, Lua loader will not load files as is, it will convert caret return (0x0a) to line feed (0x0d). That corrupts the binary and it can't be decompressed. Odds of not having it anywhere are just under 2% and you will usually have a whole bunch, due to Huffman coding. To work around this I use brute force, otherwise would pretty much require implementing the whole thing so I could use it halfway through for analysis (which I should totally do to see what code compresses into what). I try different combinations of whitespace, tab and newline characters and compression levels until I find some without offending characters and use the one with smallest binary size. That can increase the size by a few bytes, but that really depends on Huffman coder cooperation.

[Inny]

love.math.decompress is just outside the spirit of the challenges

yet

As for using lua-minifier, I'm cool with it

Come on you can't be for real. This minifying tool does same exact thing as real compression except worse because it only removes redundant characters from the stream but doesn't optimize total redundancy of the stream.

since you're going to be tweaking the bajesus out of your code to make the minifier work best

Which applies tenfold to using real compression? Yet real compression is bad-bad?

What are you smoking my man, please do share!

Well, it's just my opinion, but as ivan normally does these threads, he probably has his own opinion. But like I said, if you're doing something totally awesome and absolutely need that compression to get it to fit in 1k, then go with the Rule-Of-Cool. This isn't a competition against each other, this is a challenge for yourself.

[Positive07]

WOW! What raidho said totally makes sense! I can totally see the complexity of using compression.

Anyway, we are not disregarding entries, that is what I want to believe... Compression is fine, using minifier is fine, even if that is not the idea of the challenge and you should try to do everything by hand. (I also consider that using a minifier is pretty much the same as using a compressor, well they do stuff in a different way, but a tool is a tool)

The idea of a challenge is to challenge yourself, even if you can't meet the requirements (be under 1K) or if you need to disregard a rule (using external resources) or even some kind of not written rule like (don't use compression or don't use a minifier tool)

The idea is to try as hard as you can to create something amazing, something that works and does the job, trying to meet as many requirements as possible (mostly the mains one, making a TicTacToe, being under 1K), meeting them all is really hard anyway...

[raidho36]

I knew full well compression was gonna rustle some jimmies, it was intentional. It was a statement. Mangling variable names, removing comments and stripping every single character that's not essential - and saying with a straight face that it's a legit source code that's small. Hah! If the whole file is an incomprehensible mess expressly designed with a single core goal of taking fewest characters to write, it might as well be a binary string encoding the same contents.

That being said, compression is not a magic button, you can clearly see the code still barely fits in 1024 bytes limit. It took a lot of optimization to make enough room for flashing on victory, one byte at a time. I could drop resize and pixelation and there will be plenty of room for advanced AI but that's the size versus features trade-off I have to make - even in spite of using compression.