I was just brainstorming, and came up with a novel idea. If this has been discussed before, an admin can move/lock this topic.
Would it be possible to beat a game/level (let's take SMB for this example) by using heuristical/rule based methods? Note: I'm not asking to complete the game in the fastest time possible, but rather just beat the game. Rather than "hardcoding" button presses, it would be nice to see if you could just follow "rules of thumb" and see how far Mario can get.
For example, here are a few rules that you could potentially use to beat level 1-1 of SMB (and maybe more). This list is by no means exhaustive, or even correct.
Default: Hold the right (thanks NrgSpoon) key (and run in most cases)
1: If there's a pit, jump over it
2: If there's a goomba/turtle on the screen, jump on it or avoid it
3: If there's an obstacle in the way, and no enemy is present, jump over it
4: If there's a pit and then an enemy...
5: If there's an enemy and then a pit...
...
and so forth
Of course, implementing these rules is definitely "easier said than done." You would require the use of memory address to keep track of Mario's speed, position, and figure out a way to locate pits and enemies (and their various positions).
Actually, it would be VERY interesting to see how well a very rudimentary set of rules could perform, provided that each rule could be implemented.
Computationally, this should be very feasible, as there should be no depth/breadth first searching, as code should be generated on the fly (using the rules), and you wouldn't be able to "look ahead" by using a save-state.
I might be reaching too far, but ideally, the best set of rules should be able to clear an arbitrary arrangement of obstacles, provided that the scenario can be beaten.
If you don't understand what I am trying to convey, please forgive me. It is late, and I am tired. Also, I am not volunteering to search SMB for memory addresses, and write the code to do this. I am merely throwing out an idea that could be interesting/fun/cool to other members of this site. It sure seemed interesting to me.
Yes, it would be possible. However, what to do when the rule fails? For example, you jump across a pit, but bump into a flying turtle headfirst and die?
Or the pit is longer, and the next obstacle requires one to slow down and jump tall, not long?
Or there's an enemy immediately before a pit that you need to avoid, but when doing so by jumping over thereof, you fall into the pit? (Actually, your #5)
The rules necessary for the game's completion become long, and it still won't be generic; any non-trivial change to the levels and you may need to rewrite parts of the bot.
Yeah, I can see the rules become too "level-specific" and the rule list being pretty long, but just seeing a level being completed is enough to interest me. For example, it seems (and I am probably very optimistic) that world 1-1 of SMB is very forgiving, and it would be very satisifying to me to see it beaten with a small subset of rules required to beat the whole game. How forgiving are the rest of levels? No clue, probably not very.
I guess the main argument is that if the rules become too numerous and too "level-specific" you'll essentially be approaching the "hardcoded button-press" approach which I vouched against.
I also expect this to be a "trial and error" approach in programming, meaning that you would run your heuristic program, and see where it fails, and then add a rule to make sure it doesn't fail (and hope this rule is generic enough to apply to quite a few situations).
Once again I'm just brainstorming.
BisqBot made a TAS of SMB a while back which completed it using some random-press algorithm... I can't remember much of it right now. AFAIR it got to a certain level and got stuck. Or maybe Bisqwit just got tired of letting it run. :P
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
The better question is if a bot like this would actually save time or effort. It would be so hard to make, and so game dependent, it would probably be easier to make a TAS by hand.
It would be kinda cool to see in action though.
Would be nice if it was a competition, like doing a framework, you release it a day1 and the first to finish the game with the framework win.
And you can create new rules as you want and everything. It should work with memory address. Even if it's of no great use for tasing, it would be a nice competition.
I've always wanted to write a bot to play smb and then give it random hacks to test it out. I can dream, right?
I got as far as making (remaking? sounds like Bisqwit did it too...) one that held right+b and jumped randomly, then selecting one that was fast and didn't die. It would have beat 1-1 easily but basicbot caps out at 1024 frames which wasn't quite enough :(
As far as making a tas, depending on the game (like the ones FODA mentions.. and maybe a full run of PacMan?) it seems possible to write a bot to do something relatively mindless over and over again, making it much faster to just write a bot than to hand play.
which reminds of (shameless self-plug) my rampage run that beats the game by holding turbo a the whole time... simplest bot ever! (if you consider StickyKeys to be a bot, which I do ;)
I was thinking about something like this much earlier for Spy Hunter. I think the game is infinite, so you can't do a normal completion, so I was thinking about a score attack. However, the enemy sprites seem to be generated pseudo-randomly based on your movement.
I was thinking if there was something where you could input that the car can only press "up" or "up/left" or "up/right" so you can dodge stuff, and press one button to shoot, maybe there would be some way to see which would be the fastest way to get a certain amount of points. I was told however that it was pretty much impossible. I guess six is still too many input combinations.
Joined: 4/30/2006
Posts: 480
Location: the secret cow level
I know that one of the endurance races in Gran Turismo 3 was best accomplished by tying a rubber band around the analog sticks and leaving it for about an hour.
I know that one of the endurance races in Gran Turismo 3 was best accomplished by tying a rubber band around the analog sticks and leaving it for about an hour.
A similar method is used to max out distance stats in Perfect Dark's combat simulator.
Borg Collective wrote:
Negotiation is irrelevant. Self-determination is irrelevant. You will be assimilated.
When playing Mario Bros there is a few simple assumptions that can be made about it.
1. First the left+right stand jump should alway be used at the beggining of each new area in order to get the fastest inital speed.
2. After that B should always be held, with exception to circumstances where it would be theoretically quicker to go through a wall.
3. When entering a new area Mario always heads right.
4. Up button is never required.
5. A general guided path is required, e.g Mario needs to enter a pipe or reach the goal on the far right.
Of course to get something which could remotely TAS SMB efficently would takes 100's of rules and millions of re-records, but the rules would prevent the Bot from testing Billions or even trillions of pointless input.
EDIT: Would it be to program a bot to disasemble a rom so it can analyse the structure and strutural weaknesses of a game, I guess that feature would be neccessary in a universal TASbot.
When playing Mario Bros there is a few simple assumptions that can be made about it.
1. First the left+right stand jump should alway be used at the beggining of each new area in order to get the fastest inital speed.
2. After that B should always be held, with exception to circumstances where it would be theoretically quicker to go through a wall.
3. When entering a new area Mario always heads right.
4. Up button is never required.
5. A general guided path is required, e.g Mario needs to enter a pipe or reach the goal on the far right.
Of course to get something which could remotely TAS SMB efficently would takes 100's of rules and millions of re-records, but the rules would prevent the Bot from testing Billions or even trillions of pointless input.
I don't know if you even read my post, or were just musing, but the whole point of my idea was to eliminate the idea of re-records, and just complete the game.
I simply was speculating about how to do this, and using an "on the fly" approach with rules seemed to be the best way. Speed is not my primary goal. With better rules, I'm sure speed could be improved, but that's another story.
I suppose most of the "rules" would involve much calculation and reading of the level data. But, thinking about it that way, it's less prescriptive and more deductive.
The way I figure it, the rules would consider, per frame, Mario's current speed and acceleration, the closest pit(s), and the locations and directions of any enemies on the screen, so that making a mistake (that is, getting killed) is a mathematical impossibility.
Maybe this is just the logical extension of your original idea? I mean, it would break down to numbers and equations eventually- that's just how the game is stored in the ROM.
Yeah, that's a nice extension of my ideas. Something of this nature would essentially be a big "case" statement involving checking memory values based on what appears on the screen; and hopefully not involve any recursive backtracking, which was the whole reason I proposed this idea.
Basically these heuristics would output button presses that are hopefully constructive and work toward a goal of beating the game.
Yeah, good idea! An effective strategy to not die is to simply keep the paddle under the ball as much as possible.
22F = ball x location
20F = left bound of paddle
213 = right bound
That's all you really need to make the bot. You can set it up so that when the ball is more to the left than the left bound, move left, or conversely if it is more to the right than the right bound, move right.
Or in BasicBot (in FCEU 16), set Left to (mem(x22F))<mem>(mem(x213))
I also had it push A rapidly to make it "serve" the ball (though it didn't work the second level, oh well, it did something else cool by mistake) Not needed though.
Also, I set End when: to frame=1000 ... if you don't put an ending it only goes about 1024 frames anyways, and it seemed not to record properly without this end condition though in theory it shouldn't be needed.
Here's the resulting movie
Nothing fancy, but (almost) entirely generated on the fly with no rerecords (it says there was 1, but it was me during the start screen)
Worked on smb a bit too.
http://dehacked.2y.net/microstorage.php/info/5690/Super%20Mario%20Bros.%20bot.fcm
It checks it's position relative to enemies and jumps accordingly. It also jumps if it's speed is low (ie stuck and can't run forward).
I was stymied by the pit though, anyone know where this info is in the ram?
In case you want to try yourself:
A:
(((mem(x88)-mem(x86))<30)*((mem(x88)-mem(x86))>0))+(((mem(x87)-mem(x86))<30)*((mem(x87)-mem(x86))>0))+(mem(x57)<20)
B:
1000
Right:
1000
End when:
frame=1000
Everything else is 0.
That's all you really need to make the bot. You can set it up so that when the ball is more to the left than the left bound, move left, or conversely if it is more to the right than the right bound, move right.
A better idea is:
$n = ($rbound + $lbound) / 2;
if ($ballx < $n) left;
elseif ($ballx > $n) right;
else nothing;
This way it would move so tha tthe center of the paddle is always in the middle, instead of just trying to keep it within the edges of the paddle.
Alden, those movies are awesome! I didn't think anyone would consider, let alone attempt some of my ideas!!
Thank you so much for kick- starting this thread and allowing an idea to take shape. Now this pipe dream is a tiny bit closer to becoming a reality :).
