Submission #8384: TaoTao's NES Flipull: An Exciting Cube Game "Normal" in 25:34.09

This run beats NES Flipull "Normal" mode in about 25:34. This is faster than my previous casual TAS by about 7 minutes. (Note that the old run has some advantages, because it starts from the stage 201 with an in-game code and the game timer ticks faster)

I used v1.0 of this game. There also seems to be v1.1, but I don't know anything about differences between them.

The RNG of this game depends on CPU cycles, so I used NesHawk for accuracy.

I used Lua bots to manipulate the RNG. The re-record count doesn't include trial-and-errors made by the bots.

"Flipull" is a simple puzzle game. The game objective is erase a pile of blocks. You always have a block and can throw it. When a thrown block collides with the same kind blocks, they will be erased. Afterwards, when a thrown blocks collides with the different kind block, they are swapped. This game was never released outside Japan.

This game has two modes, "Normal" and "Advance". In the normal mode, blocks are placed randomly. In the advance mode, placements of blocks are completely fixed.

The normal mode has 50 stages.

I wrote a solver to beat a stage generated by a specified RNG value with a minimum frame cost.

I examined the frame costs for throwing a block with a Lua script. By the way, if some blocks remain when you beat a stage, it takes 11 frames per block to erase them automatically. And, if you achieve "perfect clear" in a stage, it takes 96 frames for a fireworks effect.

Every stage has a specific number of blocks to beat it. If you beat a stage with exactly the required block count, it is called "just clear". "just clear" doesn't take any additional frame cost. Intuitively, you might think that it is always optimal to beat stages with "just clear". But for a certain reason, I often avoid "just clear" and also avoid erasing 5 or more blocks at once. This is related to the RNG (I will describe details later).

Note: in the NES version, if you have only moves which directly hits a wildcard block, it is considered a miss. (This point is different from the GB version).

In the normal mode, each stage has 65536 or 65535 placements which is determined by the RNG seeds.

This game has a very ad-hoc RNG, and you have to manipulate it carefully.

In this game, all the logics are processed within the NMI thread, while the main thread only updates the RNG state and increment the mainloop counter in an infinite loop. So, the RNG is sensitive to CPU cycles. Here is the infinite loop of the main thread (rand is at $0122):

@mainloop:
        lda     rand
        tax
        lda     0,x
        adc     rand
        sta     rand
        adc     rand+1
        sbc     #$11
        sta     rand+1

        inc     mainloop_counter

        jmp     @mainloop

As you see, this game updates the RNG using the contents of the zeropage. Note that the addition rand[0] = adc(rand[0], mem[rand[0]]). This adc instruction involves carry in many cases.

This game manages each players' inputs at $F3-$F8. So, if you can make rand[0] point to one of these addresses, you can manipulate the RNG by inputs. But, depending on the contents of the zeropage, this manipulation is not always possible.

For example, let's assume that rand[0] has value 0x70 and the zeropage is like below:

      x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF
...
0x70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 F1
...

In this case, the result of adc(0x70, 0) is 0x70 or 0x71, so rand[0] will continue to be incremented a bit slowly. When rand[0] reaches 0x7F, adc(0x7F, 0xF1) is 0x70 or 0x71, so rand[0] "loops" to 0x70 or 0x71. If such a loop occurs, it limits the range of the RNG state. So, if necessary, you have to manipulate to prevent such cases from occuring.

Especially, if the pattern [0x00, 0xFF] appears on the zeropage, rand[0] will be "stabilized" there. In fact, this pattern can appear at $D4-$D5. $D5 is the flag which indicates that a wildcard block will be appear on the board at the next stage, and it will always be 0xFF if you erase 5 or more blocks at once. So basically, you should not erase 5 or more blocks at once, except the last stage. (If you erase 3 or 4 blocks at once, $D5 can probabilistically be 0xFF depending on the mainloop counter, but you can easily manipulate this)

And, if you achieve "just clear", $E9 will be set to 0x80 later, and it makes difficult for rand[0] to reach $F3-. Especially, from stage 11 to stage 30, it is very difficult to manipulate the RNG in this condition due to the contents of the zeropage. So, I often avoided "just clear".

By the way, you can also cause the RNG stabilization intentionally with your inputs, and it is sometimes useful to manipulate the RNG. For example, when the player1 inputs nothing and the player2 inputs all the keys, the [0x00, 0xFF] pattern will appear at $F3-$F4, allowing you to stabilize the RNG at these addresses.

Some RNG seeds might be impossible (but I'm not sure).

The stage placement loops every 32 stages, but sometimes I couldn't manipulate the RNG in the same way due to the difference of the zeropage.

From stage 10 to stage 29, I didn't consider "just clear", because it makes the next RNG manipulation very difficult.

I treated the stage 50 specially. It takes no block throwing cost for the last move, and you can erase 5 or more blocks at once.

The numbers after RNG seeds are their frame costs. Frame costs doesn't include the costs for converting time into score.

I think my RNG manipulation is probably not theoretically perfect. But I believe you cannot improve this run without an understanding of the RNG and some computing resources.

ThunderAxe31: Claiming for judging.

ThunderAxe31: Oh boy, this looks extremely optimized. Great job! Accepting as a new branch.

despoa: Processing...