In this game, the goal is to trigger the longest chain reaction. Once you click on a cell, you can no longer click on any of them before they all stop moving. The chain reaction and the soothing sfx make it a relaxing game. You can play the game is various places, for instance here.
Comments
I always wondered what the best possible score could be.
I wanted to mathematically find the solution, but then figured ou it was probably an NP-hard problem. I also thought about implementing a simulation as a cellular automata to bruteforce it extremely fast, but it turns out the game does not work that way. Each cell behaves independently from the other ones, and then very quickly desync from each other.
I then went for the more basic method of just straightforward bruteforcing it. This still required me to make several patches for libTAS to make that possible (but I'm now happy to say you can now bruteforce seeds in libTAS. Well, when my PRs get merged at least).
After 75k tries, I decided to switch from extensively searching all seeds to a more clever method: only testing 10 randoms clicks for each seed, and extensively searching the most promising ones. This is based on the observation than some seeds generally give better results than others.
Shortly after, I changed strategy: patching the game to avoid having to rely on savestates, which made the search 7x faster and extensive seed search way costless.
I bruteforced 1.3 million attempts in over 5500 seeds, and here's the best solution.
The bruteforcer code in on Github. I also made a video of the bruteforcing in progress as I found it quite poetic.
Bruteforcing more seeds could find better solutions.
There might be slightly better results if you click on some cells to rearrange them before the big chain reaction, especially in unreachable areas of the most successful seeds. However, this adds a layer of complexity I did't want to get into, and preferred focusing on bruteforcing single-click solutions (this is a speedrun, after all ;))
Also, I still don't have proof that infinite loops are impossible. I just haven't found one. This is more of a math problem I think.
Note: I went for highscore, but current solution is not the longer chain in terms of time, as I got at least a 3057 one that takes 2 minutes to complete. I did not dig into that direction, but that could be a different category.
Joined: 7/11/2016
Posts: 21
Location: 🇰🇷 South Korea
zapkt wrote:
Also, I still don't have proof that infinite loops are impossible. I just haven't found one. This is more of a math problem I think.
It can be proven that each tile stops rotating after finite time, and thus there are no infinite loops.
Lemma: for any tile T, if the tile immediately to the left of T (if there is one) and the tile right above T (if there is one) stop rotating after finite time, then so does T.
Conclusion follows from the lemma with induction on row index + column index.
TL;DR of the proof of Lemma is that once those tiles stop rotating and T rotates enough to point left and upwards, T can't rotate anymore either. It turned out to be more complicated than it seems because a tile can rotate multiple times at once.
Proof of Lemma: Let f be the last frame where either of those two tiles rotates, or 0 if neither of them exists or rotates. After this point, any further rotation of T must come from the tile right below T or the tile immediately to the right of T (I'll omit "if there is one" from now on).
Now let f' be the first frame after f where T finishes its current rotating animation, or f' = f if T wasn't rotating in frame f. At this point, T has one of the four states:
pointing left and upwards: T cannot rotate.
pointing left and downwards: only the tile below T can rotate T, after which T points left and upwards, so T can only rotate at most once.
pointing right and downwards: two tiles can rotate T. If they rotate T simultaneously, it points left and upwards. If only one does, it points left and downwards. Therefore, T can only rotate at most twice.
pointing right and upwards: only the tile to the right of T can rotate T, after which T points right and downwards, so T can only rotate at most thrice.
In all of the cases, there are finitely many frames where T rotates, and T stops rotating after all those frames have passed.
Would it be possibile in teory to have an infinitely recursive chain reaction, or does the system feature irreversible entrophy?
Edit: nevermind it has been already explained
