Well it could be possible to find the fastest route in SMB, but you would have to find some possibility, and decide which on is the best. But it could be possible.
If you take the rules you put, let the game run, see what is the final time, maybe look at that movie, arrange the rules, and let it play again, you should be able to do something. In any case, it would be a great concept/demo to see. A bot playing SMB.
Joined: 5/1/2004
Posts: 4096
Location: Rio, Brazil
I wouldn't buy that you've found the fastest route on SMB if you assumed it required pressing -> + B most of the time. What about the glitches we don't know about?
edit: hum, you want to find a fast route, not the fastest. I would like a bot to find the fastest completion on some game.
king's bounty (genesis) is the shortest published movie, which is 10 seconds long. 610 frames.
how long would it take to test every combination possible of 1p + 2p or just 1p that take 609 frames or less and see which ones finish the game?
(sorry for being off-topic)
I wouldn't buy that you've found the fastest route on SMB if you assumed it required pressing -> + B most of the time. What about the glitches we don't know about?
That's the killer in heuristics. It misses finding all the new glitches and little tricks that can be used to gain marginal improvements.
A heuristic bot, that is programmed with the assumptions in mind that running right with B held and jumping to avoid bumping into platforms is the way to victory, would never discover the fact that jumping backwards accelerates faster than jumping forwards, when starting from zero velocity.
I think the game where bots would have the most success is Fire Hawk's Rescue minigame, because the game actually says, "Hit A" or "Hit B" at the opportune moment.
Joined: 6/22/2007
Posts: 181
Location: Eastern Michigan University
Maybe I'm missing something, but for a bot... using any form of visual screen for non-debug is sub-optimal.
Using heuristics will only yield results as good as the human who programmed it, this really is the best place to start. At this point your computer has benchmarked a level.
The next step would be applying heuristics to segment the game into zones each representing a 'challenge'.
The computer would then run a compare state algorithm using mutated random input.
The computer would compare the data with the previous, building it's own set of heuristics for each zone.
So whiling running might be the fastest originally, eventually it knows that at start of zone 1, jumping backwards provides a lower frame count when entering the next zone.
I wouldn't buy that you've found the fastest route on SMB if you assumed it required pressing -> + B most of the time. What about the glitches we don't know about?
That's the killer in heuristics. It misses finding all the new glitches and little tricks that can be used to gain marginal improvements.
A heuristic bot, that is programmed with the assumptions in mind that running right with B held and jumping to avoid bumping into platforms is the way to victory, would never discover the fact that jumping backwards accelerates faster than jumping forwards, when starting from zero velocity.
Thats what genetic algorithms and fuzz-testing are for.
My Super Mario Kart bot has already discovered (and exploited) two new things I didn't know were possible in SMK.
Don't know if it's on-topic here... but my bot is now doing quite well
Joined: 4/30/2006
Posts: 480
Location: the secret cow level
Think about this: if you program your bot to abandon any control set that results in a death, say, there are probably quite a few that would run into that first goomba, so everything that came after that would be ignored.
Every time you throw in something like that, you can probably knock a zero (or maybe a few) off the number of possibilities.
Think about this: if you program your bot to abandon any control set that results in a death, say, there are probably quite a few that would run into that first goomba, so everything that came after that would be ignored.
Every time you throw in something like that, you can probably knock a zero (or maybe a few) off the number of possibilities.
... that checkers is solved it got me wondering whether it would be a harder task for a computer ... to find the fastest route through SMB1...
Some techniques for this:
(1) You can use a modified emulator to take a snapshot every frame and use them as states. But these will contain information you'll never need for a speed run e.g. your score, number of lives or number of bonuses.
(2) You can also reverser engineer the game's internal algorithms and rewrite them in a modern language such as C++ which will then run much faster than any emulation (and also allows you to cut away anything you don't need, e.g. your score).
(3) As a compromise you can emulate a simplified version of the game that doesn't contain stuff you don't need. Don't forget to set traps (or assertions) just for the cause that the information you've just cut away is still accessed from somewhere.
I don't think (1) works for any real game.
I've already done (2) but be warned: it's very, very complicated.
(2) You can also reverser engineer the game's internal algorithms and rewrite them in a modern language such as C++ which will then run much faster than any emulation (and also allows you to cut away anything you don't need, e.g. your score).
[...]
I've already done (2) but be warned: it's very, very complicated.
Can you clarify something for me? I always thought that emulators/ROMS were written in some sort of assembly language, which is among the most efficient (but painfully slow) ways to program. Wouldn't programming in a higher level language hinder this efficiency? Perhaps I didn't understand the statement.
Joined: 6/22/2007
Posts: 181
Location: Eastern Michigan University
DK64_MASTER wrote:
Kabuto wrote:
(2) You can also reverser engineer the game's internal algorithms and rewrite them in a modern language such as C++ which will then run much faster than any emulation (and also allows you to cut away anything you don't need, e.g. your score).
[...]
I've already done (2) but be warned: it's very, very complicated.
Can you clarify something for me? I always thought that emulators/ROMS were written in some sort of assembly language, which is among the most efficient (but painfully slow) ways to program. Wouldn't programming in a higher level language hinder this efficiency? Perhaps I didn't understand the statement.
I'm pretty sure ROM's just comply to the consoles SDK, which can be bought for a pretty penny. You can reverse them, and emulate them (like an emulator does). He is just saying, that he would write a specific emulator for Super Mario Bros.
Which would give him total control of the game.
Joined: 6/22/2007
Posts: 181
Location: Eastern Michigan University
ShadowWraith wrote:
Actually I think he was talking about re-writing the game so that you don't need to emulate it.
I think the word is porting, which can be quite tedious when you don't have source. However, to start you would have to have an emulator dump the needed files (sprites, maps). Then from there use a debugger and reverse the code to a HLL.
Yes I'm talking about re-writing the game.
Main reasons why re-written code is so much faster:
* E.g. the "adc" (add) instruction of the NES' CPU takes 30 lines of C code for proper emulation of all "side effects". When rewriting you usually don't need those side effects.
* When coding for 8 bit CPUs any value that doesn't fit into one byte must be split up into multiple instructions. Also some operations such as multiplication must be done "manually" on 8 bit CPUs (similarily to you were taught in school). Re-written code can do with one instruction what 8 bit CPUs needed many more instructions for.
* You know exactly what of the hardware the game needs for operation.
I can't imagine how tough it would be to try to copy the game's mechanics exactly, without the source.
Very very tough. I've fully copied a very simple game's mechanics (FlaschBier - a boulderdash clone) but for another game (Cauldron 2) I've excluded the enemies and then use the solver mainly for finding routes than for solving the game itself.
It might be possible with SMB1 (still provided there's someone with enough skill, time and patience) but I doubt anyone will succeed in doing this with later SMB or MegaMan games.
My Super Mario Kart bot has already discovered (and exploited) two new things I didn't know were possible in SMK.
Don't know if it's on-topic here... but my bot is now doing quite well
That is interesting. Intriguing to see what sort of things it does (letting up on the gas, for instance)... Do you provide it with guidelines on how to navigate the track, or is it all based on the bot watching the track itself? And what are the discoveries it's made, or do you not want to give that away?
That is interesting. Intriguing to see what sort of things it does (letting up on the gas, for instance)... Do you provide it with guidelines on how to navigate the track, or is it all based on the bot watching the track itself? And what are the discoveries it's made, or do you not want to give that away?
Does it let up on the gas? It shouldn't do... I thought it just sounds like it does during mini-boosts, but I haven't actually watched the key-presses to check.
I give the bot a (really bad) set of waypoints to follow, and it moves the waypoints about optimising them.
The discoveries it has made are the ability to skip laps by bumping into certain walls without hopping, and a way of making mini-boosts last longer.
Such techniques are often useful in smaller scale. For example, for predicting the randomness. Then it is good to write a simulator for the particular scenario of the game. I believe such technique was also used for TASing Clu Clu Land.
Joined: 1/16/2008
Posts: 358
Location: The Netherlands
DKMaster's initial idea of making a (realtime) program to beat a game sounds really interesting
read an article on a rule-based approach on Ms. PacMan lately
http://www.robotworldnews.com/100389.php
also, i can see that most of the discussion has changed to making programs to find optimal routes non-realtime... which i find equally interesting
e.g. Huffers' bot sounds great... finding tricks/exploits/etc already!
mind uncovering some details on it? :D
Reminds me of a time I put a rock on the mouse (on a laptop) and set a record for the game Hold The Button.
Funny enough, you can hold the button down, simply by left clicking, and then right clicking while still holding the left button down. Releasing the left button no longer helps. As long as you don't lose focus, you are 'holding the button'
TOOL - ASSISTANCE!
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
Reminds me of a time I put a rock on the mouse (on a laptop) and set a record for the game Hold The Button.
Funny enough, you can hold the button down, simply by left clicking, and then right clicking while still holding the left button down. Releasing the left button no longer helps. As long as you don't lose focus, you are 'holding the button'
TOOL - ASSISTANCE!
Press the button, then switch tab (like pressing right mouse button and scrolling in Opera). You can browse other pages and the button is still held!
Even better tool-assistance!
