A better class of "brute force" bots could be designed as an evolutionary algorithm (specifically, a genetic algorithm). This would be painful to code, and possibly highly inefficient when done in Lua, but would still beat the two proposed methods in terms of speed (by several orders of magnitude). However, you wouldn't get "the" perfect solution, just one "good enough". It would also have lots of game-dependent code to check for objectives (but all of the other methods should as well, so no problem here).
The idea is to start with input that finishes the game* (or a level of the game, to make this more feasible); this can be from a TAS or from a regular run. You make several copies of this input, making random adjustments ("mutations"**) to each (one of which could be an unaltered version of the original input, but this isn't required). Maybe 100 to 200 children, depending on the size of the input.
You then "rank" each of these "children" input according to its "fitness" (e.g., checking if it finishes the level/game or not, if it dies in a "no death as a shortcut" run, if needs less input to finish the level/game, etc.). The best ranked "children" (say, 20 to 40 of them) input "survives" and have "children" of their own (use the same limit as for the first generation: a
total of 100 to 200 "children") which have mutations like before. Wash, rinse, repeat until you have input you like.
This will still take many weeks, probably months or even years of computation for a "large" game, but it will be billions of times faster than the two methods you propose. See
the Wikipedia article for some more information if you are interested in using this.
* = Strictly speaking, you can start with a set of completely random input (say, 100 to 200 random movie files) rather than a single "superparent" that finishes the game, but this will add a lot of time until you have any input that finishes the game.
** = Mutations can be: a change, the deletion or the duplication of a range of input. And should have relatively low probability of happening (consider that a movie might have tens of thousands of frames and even a small chance can happen far too often).
In the end, I was forced to manually reset the 68000 processor so the map hack could continue.
Edit: it seems that the map hack has reset along with the 68000 processor, and is back at failing at the same spot: about maybe 3-4 half-screens down from the initial position, after the first (vertical) rotating gray cylinder. This is around the area where the Knuckles cutscene happens, if I am not mistaken.
Edit 2: It seems I was wrong and it went all the way through. After going over the level as described, however, hitting 'B' had no effect except if I left capslock on (that is, if I ignored step 20). And now I know why your maps do not have backgrounds too.
The "status icons" between the score/ring/emeralds HUD and Tails' HUD only show for the relevant condition: in this case, a spindash being charged (displaying charge, at 100%), speed shoes (remaining frames), super transformation (remaining frames) and Tails remaining flight time (in frames). Invulnerability time, invincibility time (after being hit, for both players) and Tails' spindash charge are also displayed. The HUDs are only shown in "non-boring" more (using the same definition that Nitsuja used in his script) and Tails (and his status icons) only appear in Sonic + Tails mode (his status icons do if you are playing as Tails).
I used the GDlua library to convert several PNGs to the Lua format; the resulting images (which I saved with a "luaimg" extension) must be used alongside the script (and they total 50kB, or 10kB in 7z format). Using this format, GDlua is not needed at all for using the script; but there is the problem or distributing the images. Does anyone know a good place to upload lua-style images? ImageShack doesn't accept them.
For what is worth, the HUD script is here; it will not work without the images, though.
