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).