Anyway, for those who are wondering why I'm included as an author in this submission at all, I'll try to give a brief explanation (Warning: this is going to be a long post regardless, and it involves a lot of math!):
My involvement is limited only to solving the "Lucky Draw" level. I have no other expertise regarding this game. For that, you will have to ask Walgrey.
The gimmick with Lucky Draw, and the sole reason I am involved at all, is because of how Lucky Draw works: It is a level whose success is determined only by RNG value, and nothing else (such as player input). It also has an extremely low probability of succcess: (63/64)^788 ~ 4.08x10^-6, or about 1 in 250000.
(BTW, I have no clue what "800 triggers" means, but I do know there are exactly 788 checks for player death. Hence the (63/64)^788 probability of success.)
So this got the math gears turning in my head, but to spare you all the details: I created a
Game Resources page with the information on how Lucky Draw determines whether an attempt is successful. I have also uploaded a
Lua script.
Anyway, my involvement: Walgrey already had a TAS that completed everything except Lucky Draw, and was running a BK2 after end of input, with the hope that Lucky Draw would eventually succeed after hundreds of thousands of attempts (that would be an encoding challenge!). As far as I know, Walgrey only got to attempt 120000 or so. It turns out (after coding a few Lua and C++ scripts) that the RNG value Walgrey had was not ever going to succeed, instead entering an infinite loop that repeats every 9722 attempts starting at attempt 2033. In fact, I found out a couple interesting things:
- There are exactly 1584919 values (out of 4294967295 possible) that allow for an eventual success. All successful values take no more than 228 attempts. Exactly 17726 of these values result in a success on the first attempt.
- Unsuccessful attempts end up in one of six possible infinite loops. The vast majority of values enter an infinite loop of period 9722 (of which hexadecimal value 0x63AD9C9E is one of the values in the infinite loop). Other possible infinite loops are: Period 204 (0xEA0347AF), period 121 (0xC7BA5605), period 79 (0xB6C0AF7A), period 1 (0x3D95930E), and period 1 (0x3F4AEF39).
The period 1 values look silly.
If you are wondering how I came to that conclusion, here is a package containing all the Lua and C++ files I used:
https://www.mediafire.com/file/7bcxk0lo9fqhkkl/famidash_alac_challengefix_LD_fastest_completion.zip/file
In particular, in order to determine the 1584919 eventually-successful values, I had to make all kinds of optimizations to the C++ code, even using bit matrices for calculations. (For comparison, running a Lua script over all 2^32-1=4294967295 values would have taken thousands of years.) The key things I noted is that:
1) Whether an attempt is successful is only based on the RNG value at the start of the attempt, and on nothing else,
2) The RNG value upon death is the RNG value that is used for the next attempt,
3) Because of how the
procedure works, the RNG value upon death is extremely likely to be one of 2^26-1=67108863 values, about 1/64th of all possible values.
This means that it is only necessary to set up a tablebase on these 67108863 "bad" RNG values (much like how chess has
endgame tablebases for positions involving a small number of pieces). I chose a size of 2 bits for each "bad" RNG value, resulting in a table requiring no more than 16MB of RAM. (The bits are used to classify each "bad" value, whether it is eventually-successful or enters an infinite loop.)
From there, I simply simulated in C++ each of the 4294967295 values until it hit a "bad" value in the table (very likely after the first attempt), allowing me to find all eventually-successful values without having to run all attempts to exhaustion. The total runtime was around 3 hours and 15 minutes (it may be possible to optimize this further, but I decided this was OK) and the 1584919 values are dumped into a TXT file which I included in the package.
So Walgrey's RNG value didn't work, but how can we find the smallest number of inputs needed to get to a value that
does work? I made a Lua script (in the
same package that I posted above) that solves for this value (using the TXT file with the 1584919 values). Note that this involves entering and quitting out of Lucky Draw first, in order to mix up the RNG with the "rand1" function. The resulting value I found is successful on attempt #64.
Now, if you don't like that the actual completion of the level occurs 8 minutes after end of input, I
did include a "fastest completion" BK2 file (in the
same package again) that optimizes for fastest completion. I used the same Lua script but this time only with the 17726 values that succeed on the first attempt. The resulting BK2 only takes 36 frames longer until end of input.
Is it improvable? Since the "rand1" function is used in at least one other level, it may be possible to change the timing of when you enter previous levels, and get a better RNG manipulation at the very end. However, I am not interested in going
that far, and I doubt anyone else is either.
