Posted: 8/7/2009 2:16 PM
Post subject: Lua Brute Force Bot: every possibility VS random input ?
Quote
BadPotato
Joined: 1/26/2009
Posts: 558
Location: Canada - Québec
Recently, I've been very interested about writing/learning a brute force bot with Lua and after spended many hours around this, I understand that there mainly 2 way to get the right result: 1. Random input : example (thanks to arukado for pointing me this) On each frame, the button have to win a test on a rand fonction, so basicly there should be about 50 % that a button is pressed or not... It should be very usefull for luck manipulation or for trying to optimize something on few frame. 2. Every Possibility Input: (I'm sure that there already that someone already think about this before myself, but I din't found any script..) This Lua script would probably require a lot more attempt(and time!!) than the random script... but if it have the right algorithm, It should actually test every single button possibility for each frame. Thought, at least this isn't a never ending "random attempt" and after doing every possibility to reach the "predefined target"of the script... this should be totaly frame perfect. (maybe there could be *still* an some way to do some other runs more entertaining with the same framecount, but this is an another story). Applying this from the power ON of a game with the right "memory target" and a "frame limit" number to help the bot... and you should get the best time, right??? This seem doing perfect sense and I've already trying to write the algorithm this... but after two attempt, I feel like I probably use the right way, so I'm asking you for helping me.(with pcsx) But first, here is some statistic that could scare you: Possibility for one frame with only one psx controller(L3/R3 enable, but not analog stick):
1 - idle 16 - 1button pressed 120 - 2button pressed 560 - 3button pressed 464 - 4button pressed 364 - 5button pressed 286 - 6button pressed 220 - 7button pressed 165 - 8button pressed 220 - 9button pressed 286 - 10button pressed 364 - 11button pressed 464 - 12button pressed 560 - 13button pressed 120 - 14button pressed 16 - 15button pressed 1 - 16 button pressed total: on each frame there about 4227 button combination (thought maybe these number are'nt exaclty right, but this is a lot for sure)
on a long game(large frame limit), that means a lot of possibility... and might took even some week of calculation, but I'm sure that some game would deserve it as well :) Maybe that lua isn't the most appropriate language for this algorithm, but I'm sure that we can found a way to do it. Here is my best attempt for now, but I suppose that I can do better ==> http://lua.pastey.net/120311-1q0h
Posted: 8/7/2009 2:34 PM
Quote
ntclark
Joined: 5/9/2008
Posts: 35
Location: USA
Here's a brute force bot I made for SNES Super Punchout. http://www.cc.gatech.edu/~ntclark/software/punchout_brute_force.lua It uses a branch-and-bound algorithm, with very game-specific bounding. I suspect any brute force technique will have to be very game specific. I know the code is ugly, but I was just playing around. The current implementation uses a save-state before every new input, and then rolls back to the save states to enter new input combinations. This was stupid; saving the state takes way too long (have to write to disk), and if I had to redo it I would create one state at the beginning and just apply all the different move orders to that initial state.
Posted: 8/7/2009 2:46 PM
Post subject: Re: Lua Brute Force Bot: every possibility VS random input ?
Quote
juef
He/Him
Player (155)
Joined: 1/29/2007
Posts: 208
Location: Québec, Canada
BadPotato wrote:
on a long game(large frame limit), that means a lot of possibility... and might took even some week of calculation, but I'm sure that some game would deserve it as well :)
Actually, it's more like billions of weeks. Following your example of the PSX game, what happens at the second frame? You still have 4227 possible button combinations. For those 2 frames alone, you'd have to test 4227^2 = 17867529 possibilities. The number of possibilities to check after 100 frames is in the 300 digits range. Brute forcing is good when there are very few possibilities to check for. For example, the Punch Out! bot is good because fights are short, some button combinations are useless and can be put aside, and while I haven't looked at the script, I'm guessing other things are coded such as perhaps something that checks if pushing a button at a given frame will actually do something (say, you won't try to punch right after a frame in which you did). ntclark said it best:
ntclark wrote:
It uses a branch-and-bound algorithm, with very game-specific bounding. I suspect any brute force technique will have to be very game specific.
Posted: 8/7/2009 3:04 PM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Just forget about any brute forcing methods. That just doesn't work. The Sun will explode long before you get to the 50th frame by a brute-force method. That's less than a second of gameplay.
Posted: 8/7/2009 3:44 PM
Quote
marzojr
He/Him
Experienced player (762)
Joined: 9/29/2008
Posts: 964
Location: 🇫🇷 France
Sega TASer of 2014 Sega TAS of 2014 Sega TASer of 2010 Sega TAS of 2010
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).
Marzo Junior
Posted: 8/7/2009 5:17 PM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
What would a "good enough" solution be good for, when the whole idea to use a bot is to get a frame-perfect solution? For a "good enough" solution you may just as well do it manually as currently and save yourself a huge amount of trouble. In order to be sure to get the perfect run, you have to try all combinations, and there simply are too many to try for that to be feasible. You could try to use smarter pruning algorithms such as A*, but even that wouldn't get you too far. (As a reference, consider highly-efficient chess programs using similar algorithms, and which are able to only calculate something like 15 moves ahead at most. And increasing the search depth even by one move increases the calculation time exponentially.)
Posted: 8/7/2009 6:51 PM
Quote
marzojr
He/Him
Experienced player (762)
Joined: 9/29/2008
Posts: 964
Location: 🇫🇷 France
Sega TASer of 2014 Sega TAS of 2014 Sega TASer of 2010 Sega TAS of 2010
Warp wrote:
What would a "good enough" solution be good for, when the whole idea to use a bot is to get a frame-perfect solution? For a "good enough" solution you may just as well do it manually as currently and save yourself a huge amount of trouble.
A "good enough" solution would possibly be better than anything a human might come up with, and it might reveal many tricks no one is aware of because the input patterns are too weird/erratic. And these new tricks might be explored (once understood) by someone in an attempt to improve the"good enough" solution. Moreover, given the way genetic algorithms work, you could get a "good solution" within the lifespan of the Universe without requiring MAJOR breakthroughs in computer technology and/or computer science. Consider a console that has 16 "buttons" that can be on or off (considering up/down/left/right to be one such "button" each). That amounts to 2^16 combinations for the first frame if all the buttons are used in the game (by the way: BadPotato *vastly* underestimated the number of combinations in his calculations); this amounts to about 10^289 combinations in 60 frames (1 second). If you could check 1 billion such possibility every second, it would take over 10^272 years to finish them all (that is, to test a single second's worth of input). Also, such a "good enough" solution might also come within 100 frames of theoretical "perfection" if enough generations are run. I further submit that nobody would know how close any such "good enough" solutions are to "perfection" because the "frame-perfect" bot will never finish executing -- unless it gets "lucky" and finds a shortcut from start to end of game in a couple hundred frames among the first few billions of attempts it makes.
Warp wrote:
You could try to use smarter pruning algorithms such as A*[...]
A* is actually not a pruning algorithm, but a search algorithm -- it only discards ("prunes") paths that have been proven to be longer than the best path found yet. A pruning algorithm stops examining a possibility when it is "proven" to be worse than the best found yet. This means it may end up skipping a possibility because the "proof" may not be perfect -- most chess playing programs use pruning algorithms at high depth and supplement it with a brute-force search at a lower depth to make sure it hasn't missed a possibility it would otherwise have eliminated (such as giving away the queen, a rook, a bishop and two knights -- all usually very bad choices -- in order to deliver checkmate). Likewise, for a TAS, taking 10 times as long to complete a stretch of the game might allow you to skip the rest of the level, saving minutes, but it could be pruned because the "best" run found so far takes a lot less time in that same stretch. Thus, using any pruning algorithms means you may not end with "the" best solution, but only another "good enough" solution.
Marzo Junior
Posted: 8/7/2009 8:47 PM
Quote
Potato_Stomper
Joined: 7/29/2009
Posts: 55
You could make a bot which randomly searches for abnormal behaviour. Let it repeat a simple thing like jumping at the flag pole in SMB again and again thousands of times each time with a little random/brute force difference and have it somehow contradict normal from abnormal behaviour. Flag comes down, screens goes black after x frames = normal Flag does not come down = report screens goes black after <x frames = report Obviously I can't make an example not discovered yet, but I guess the flag pole glitch may have been found sooner with this method. I don't know anything about porgramming though^^
Posted: 8/8/2009 4:40 AM
Quote
andymac
Experienced player (642)
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
I like Potato Stomper's idea, as a way of discovering obscure glitches that wouldn't be found otherwise. I'm not so sure of the genetic search algorithm, as I would say a computer would take (if not given an initial input that finishes the game) years to find a single solution to a short game, let's say SMB1. Given say, klmz's movie, and many other previous TASes as parents, I would say if mutation was to occur, the possibility of the game finishing at all would be less than 1/1000 and 1/100 for a creation of a file from chromosomes completely from parent TASes (a very generous probability for both of these). If mutation were not to occur, there would most likely be little or no discovery of new methods to make the game faster, because characteristics would only be obtained from parents which are assumed not to have perfect chromosomes (i.e. not 100% optimal). If perfect chromosomes were assumed there would be no point in a genetic search algorithm in the first place. However, mutating a TAS would mean doing millions of iterations before a solution that is found that completes the game, and completes it faster in some aspect (let's assume that the probability of finding a time saver is 1/1000, which is very generous, considering that human input would usually require this number of rerecords to find a new technique to implement assuming that their input was measurable and decisive, and not completely random). A lot of the time, imposing the restriction that the game must be completed otherwise that child will die at birth, will mean that some mutations, even though they don't complete the game may have some techniques that could contribute to a faster completion. Even if it does complete the game, the solution might have a high probability of being "bred out" in subsequent generations for other faults, and the new method may be lost. Obviously we cannot impose artificial restrictions in order to make the game progress faster eg: must complete levels 1-1, 1-2, 4-1, 4-2, and 8 because the optimal solution could be one that skips one or more of those levels (however unlikely that may be). One of the purposes of a genetic search algorithm in in fact to find techniques that humans couldn't, because otherwise, a human would make the TAS, so you must not assume the fastest solution is known, because of the probability of a sequence break occurring that means that a halfway goal is not obtained but the net time is faster. Even though obscure techniques may be found that humans would not be able to immediately see, I would assume that inherently obvious things such as frame precision may be ignored during a genetic search algorithm, because a human is not behind the wheel. For example you might lose a frame somewhere but save three somewhere else, and since the use of halfway checkpoints would not be able to be used, because of possible sequence breaks, the genetic algorithm may not be able to easily assess the health of the child, and the faulty characteristic may survive into subsequent generations. Most likely however, if the program is indefinitely run, the faulty characteristic will be bred out. All in all, I think that the genetic search algorithm has distinctly human traits about it. For a movie such as the current SMB1, the flagpole glitch has proven a successful trait and has survived into subsequent generations of TASes. Take the current SMB3, both Lord Tom and Mitjitsu had found improvements over the current run (two parents), so the successful characteristics were carried into the next generation. (one child). The difference, (I believe) is that computers are producing blind, random input, whereas the input provided by humans is decisive and has definite intent. IMO
Measure once. Cut twice.
Posted: 8/18/2009 12:34 AM
Quote
Desty
Joined: 12/3/2008
Posts: 15
Location: Dublin
Warp wrote:
What would a "good enough" solution be good for, when the whole idea to use a bot is to get a frame-perfect solution? For a "good enough" solution you may just as well do it manually as currently and save yourself a huge amount of trouble.
"Good enough" would be "at least 1 frame faster than the best existing TAS", for games that have already been TASed. Asking for the 'perfect' run straight away is expecting too much. Even then, genetic algorithms would fail if each child was supposed to be a complete solution to the game. It'd be black hole time, just like a simple brute-force search. Instead, you could use genetic algorithms as an assist to a normal, human-guided TAS. You'd set short goals like getting as close as possible to a certain waypoint. e.g. for SMB, in the first level from a given savestate, do 10000 rounds (with tournament selection) with a population of 200 input sequences, where the fitness function is "how close were you to the end of a level/key/pipe/etc", with the restriction that each input sequence can't be longer than your best effort (or the best effort from the best existing TAS). The population can be seeded with your best manual input (this helps avoid an extremely long initial period where every solution is awful). That way you're adding some human intuition and guidance to a fairly dumb but fast process, and providing a method by which good and bad solutions can be properly compared and ranked. When an acceptable solution is found, you pick a new waypoint starting from where the best solution ended up and repeat the process. I've been thinking about doing this for a while, but I don't know Lua and my TASing abilities are err... poor. I have written a couple of simplistic genetic programming systems in Java though, so it's not that hard... would love to see someone try it here.
Posted: 8/18/2009 1:16 AM
Quote
Mitjitsu
He/Him
Banned User
Joined: 4/24/2006
Posts: 2997
TAS of 2007 N64 TAS of 2007
I would assume "Good enough" means faster than what a human TASer would capable of doing without endless iterations. Brute force is not the way to go. You would need to use heuristics, that way the bot would have some understanding with the way the game works. At least that way ideal inputs to a relatively short and simple game could be found in several million inputs. Rather than more cosmic figures.