even if it's only one button, 2 states, that's stil 2^36000.
we can't get rid of this number of frames.
windows calc says it's about 1,2 x 10^10837, which is still too much possibilities (number of atoms in the universe is "only" 10^120...)
so pruning wouldn't be on the buttons combinations (at that scale, 2 and 4096 are very close numbers, yeah I know it sounds stupid).
we'd rather kill dead branches such as, forbid to go back in a already examinated state.
brute force won't work, as many situations loop : go forward one frame, go backward one frame ; or go forward 2 frames, then go backwards 2 frames. some games are playable with the "always go right" technique (beat'em up...)
chess games don't calculate every possible situation, only those very few many that make sense... and obey simple rules such as : no "loop".
sorry, might be a lot of mistakes in what I say, AI isn't a subject I know well. but I'm quite sure that the number of possibilities is a killer. you don't want to eval x^36000 possibilities, whatever x >= 2 is.
I never sleep, 'cause sleep is the cousin of death - NAS
Yes, I made an egregious error in that portion of my reasoning. I feel no need to invent an excuse as it happens sometimes.
The comments about quantum computers remain pertinent, though. Quantum computers allow you to do things like evaluate functions at multiple points simultaneously. That sounds like it fits the bill for searching for or generating movies that fulfill any particular goal, assuming it is meaningful to talk of a quantum computer that through superposition can contain all possible movies (it seems as if a 150M qubit computer should suffice, from my previous misguided arithmetic), and there is a way to transform that information into a state that yields a desired outcome with any reasonable probability.
Joined: 3/11/2004
Posts: 1058
Location: Reykjavík, Ísland
So pure dumb brute-forcing is out of the question. The only way I can even conceive doing this would to have the computer do just half a second at a time, then take the most progressed one and start again from that one. Yeah, there are 1237940039285380274899124224 possibilities in 30 frames with 8 buttons, but at least it's better than 4,096^36,000. :) Edit: of course, this wouldn't really work, for various reasons. Sometimes you need to slow down in one part to be able to go faster in another part, etc. It wouldn't work.
I think it would be easier and faster to just code an AI that can analyze the ROM and output a perfect movie.
Even easier than that would be to hire an army of software experts to analyze the ROM and build a perfect movie over several decades.
I have an idea - let's bitch back and forth about whether or not a theory of computing that is still in its early stages, not yet fully understood, and that may or may not be seriously implemented long after all of us are dead can solve a group of extremely complex and gigantic problems.
Or we can stay on topic instead!! YAY
I'd be interested in Battletoads, because it seems like a new time-saving glitch is found every time a new run is done.
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
36000^4096 = 4.12 x 10^18662 (In my haste I made an error)
4096^36000 = A much, much larger number though. (So the error was in xebra's favor)
xebra wrote:
OmnipotentEntity wrote:
Assuming a quantum computer running at 1 GHz ... I winnar is yuo!
I'm not really sure where any of that is coming from. Your comparisons of the methods of operation of classical and quantum computers are very ignorant, and are not remotely applicable or even meaningful. The reason I formulated my first response the way I did was because I didn't want to provoke the kind of response I got from you, and also because I was making a number of assumptions that I didn't wish to explain, hence my argument of "you are probably wrong, go read up on it if you really want to know." If you read up on it, you did a poor job.
Quantum computers do have clock frequencies (just like regular computers they have to perform operations on data, and they do this a certain number of times per second). They just aren't nearly as important compaired to register size. I chose 1 GHz because you probably wouldn't see a Q Computer running at 1 GHz, and it makes the math easy.
Anyways, there exists a quantum algorithm for performing a fairly general type of search more efficiently than the best classical aglorithm. The quantum algorithm is O(N^1/2) while the storage space required is O(Log[N]). That's decent though it's "only" a quadratic improvement over the classical algorithm. As we have been discussing it in this thread, "the perfect movie problem" has not been formulated (as I understand it) in a way that can exploit a more efficient search algorithm. I am assuming there is some way we can formulate "the perfect movie problem" as the type of search that can be performed quickly by the quantum algorithm. Since we are discussing a problem that is easily solvable on classical equipment and seems like it could be formulated as a search, and since the limits of quantum computation are not well understood, I think it's a reasonable if optimistic assumption.
Here is where you are mistaken. You're thinking of searches in the variety of P and NP problems. Unfortunately, the problem class of this is #P, because there isn't one right answer and you have to search through all possible combinations in order to find it (because there really is no way of ascertaining whether or not a one frame improvent can be made over the ten minutes from the emulation and the movie file). Which is why I didn't bother with the Big-O function, because the Big-O describes the asymptote of an algorithm, while here we have an algorithm that we can calculate will always run for a specific time, so Big-O is superfluous.
This is, of course, without pruning, which is probably a Good Idea™, as it greatly speeds up a similar, but vastly less complicated, problem, solving a Rubik's Cube optimally from a given posistion.
xebra wrote:
P.S. Wtf is a rectal figure? Rectal means "related to the rectum" which is in your ass, and if you want to be taken seriously, that's not the best place to pull arguments from.
Yes, that is the definition. Meaning in this case, that I have no way of knowing what we'll have to deal with in 10, 50, or 100 years, whenever Q Computers get up to snuff. But, I'm making some intelligent guesses that I have no evidence for, and no evidence could possibly be produced for any figure. Therefore, it's just as if I pulled it out of my ass. Which I did.
xebra wrote:
The comments about quantum computers remain pertinent, though. Quantum computers allow you to do things like evaluate functions at multiple points simultaneously. {snip}
If you didn't read my post correctly, that's what I was doing.
Deviance wrote:
the topic says "magically." So to stay on topic, they'll have to change their discussion of computers to genie lamps. :P
Only if they are quantum genie lamps that can produce a superposistion of all wishes I'd make, and then collapse to a single wish when I tried to act it in a non-deterministic way based on the probability of the wishes I'd make.
Because that would rock! ^^;
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Joined: 5/27/2005
Posts: 465
Location: Turku, Finland
I would like to see Final Fantasy V (snes) TAS done perfectly (every side mission & optional bosses etc.) but I would also accept just plain run through.
I'd also really like to see Final Fantasy VII speedrun even though it's on PSX. Also FF VIII and FF IX would be nice.
As you probably see, I'm pretty big FF fan :)
Stuff I'd like to see:
NES:
- Adventures of Lolo 2, Japanese version. Probably the hardest, most brain-busting puzzle game out there...it'd be fun to see the lil' blue ball blow through it at top speed. :)
- Zelda 2 done at lowest levels possible, without the warping glitch. I read on the GameFAQs boards that a 3-1-1 is possible...o_O
- Zelda 1 swordless, 3 hearts, and bare minimum items. For added style, pick up the wooden sword at the very beginning like normal, but just don't use it 'til Ganon... :p
Arcade:
- Gradius 3...at least 3 loops. That thing is friggin' insane compared to the SNES version...
- Battletoads, duh. Preferably all 3 players... :)
I painfully read through this thread and I don't know wtf. So somebody answer this for me.
Is it technologically probable that quantum computers will be able, at any time in the future, to brute force a perfect game of Super Mario Bros., or, would the task require such a ginormous amount of operations that more time than the universe has existed would be required to finish executing all of them?
I don't want math. Perfect Mario Bros., YES / NO ?
I've often asked myself this same question. With current whatnots, Legacy of the Wizard, Ultima: Quest of the Avatar, Super Metroid lowest %, or Umihara Kawase(just so we could know EXACTLY how fast it can go).
With not yet implemented whatnots, SM64 120 star, or Zelda 64. But if I could see any "perfect" video ever, a SSBM video against 3 computers not taking any damage, with no time goal, could potentially be the most awesome video ever.
you cant have 4 perfect players, one has to lose
Why is that? Don't some characters have advantages over others? Whichever is the best character will win, but that doesn't mean the others didn't play perfectly, just like you can play connect 4 perfectly and still lose because you went 2nd.
Joined: 4/8/2005
Posts: 1573
Location: Gone for a year, just for varietyyyyyyyyy!!
I was thinking of magic and 4 perfect Doom marines having a deathmatch, but...
How exactly would it be possible to produce a movie (no matter who or what produces it) where 4 players try to beat each other? After all, every one of them can use savestates and re-recording! Player-1 would see what others do and react perfectly to that situation. Then the other players would do exactly the same. There would be no single best thing to do because everyone could change their mind at ANY moment. (Have you ever played North & South against your friend so that both have only the cannons left?) Everyone (or a single movie maker) would just load their savestates and change their strategy constantly so that the movie could never get done. Producing a perfect battle between 4 players would be like... practically and theoretically impossible. At least my brain can't handle that kind of socially paradoxical 4-player situation. However, it would be nice to see perfect playing in... any game. NES and SNES games mostly. :)
This is like trying to play a perfect game of chess. In a 4-player run you're better off planning to have one player win than to try to play "perfectly" with all four; there are just too many possible variations to be able find which one is perfect.
Joined: 5/1/2004
Posts: 4096
Location: Rio, Brazil
michael fried: dont you think it may be possible to just run away indefinitely if the character is in disadvantage?
not to mention that if there are better characters then it would be imperfect to not choose the best one, therefore all 4 would be the same
Yeah, that's a very interesting theory. Derivative theories also directly apply to many everyday occurrences, such as voting or trading shares. They are mainly based on the effect of human incompetence to alter a given situation. It's psychology versus sociology. Psychology wins. :)
In regards to the Prisoner's Dillema, check out superrationality. It may be practical in a thread about a "perfect game."
Some games can be played perfectly with a loss. Michael mentioned Connect 4. The second player can play perfectly, which here means survive as long as possible. If he lost within the first four moves, well, he's retarded.
If Super Smash Bros. is comparable to Connect 4, then -- and for simplicity let's imagine only 2 players -- the loser will survive as long as possible, take as little damage as possible, lose as few lives as possible, etc etc etc. This all depends on the criteria you decide is important for "winning" without a technical win in Super Smash Bros.
Some games will never have a winner, but would be a stalemate. Those would be pretty shitty games in terms of theoretics. I just invented one in my head right now. Imagine a game where there are two players. One can move three spaces on an infinite grid, and the other can move only one. If the only way the game ends is for the slower piece to capture the faster one, then only a retard would ever lose as the faster piece. The game, from a theoretical perspective, is stale.
Now we're the retards in Super Smash Bros. The reason why the games are fun are because of our imperfections. Given such a vast amount of possibilities and decisions to make, we rely on quick wit and heuristics to read and predict the game.
For some reason, I'm imagining that a perfect game of SSB would just be players standing idle, incurring no damage. Or, maybe they could evade each other so well, no one would ever get hit. This is like the theoretical game I made up earlier, except on a finite plane. Given 4 characters, though, and limited level space, I'm not sure evasion would be possible.
We could use multi-variable graphs for all of the characters. We plot what we consider is important: speed, weight, power, jumping distance (to keep from falling in a pit.) The one with the most area would be the best player. This would be a bitch and a half to calculate though. Also, item drops may give a technically weaker opponent the advantage.
Gah, my brain just broke. Good luck.
SNES:
Chrono Trigger, Final Fantasy IV, Super Mario RPG
Systems not yet ready...hmm..
Nintendo 64:
70 Star Super Mario 64, High Score StarFox 64, F-Zero X time trials, Wave Race 64 high scores, Ocarina of Time, Majora's Mask, Paper Mario. Goldeneye 007, Perfect Dark,
GCN:
Tales of Symphonia, Paper Mario: The Thousand-Year Door, F-Zero GX, The Wind Waker
PS1:
Final Fantasy VII, Metal Gear Solid, Metal Gear Solid VR Missions
PS2: Final Fantasy X, Final Fantasy X-2, Star Ocean: Till the End of Time, Ys Arc of Napishtim (sp?), SSX High Scores (all versions), Metal Gear Solid 2, Metal Gear Solid 3, Devil May Cry 1-3, Arc the Lad: Twilight of the Spirits, GTA 3/VC/SA
X-Box: Halo, Halo 2, Project Gotham Racing, Ninja Gaiden
Joined: 11/22/2004
Posts: 1468
Location: Rotterdam, The Netherlands
I should add that it'd also be extremely interesting to see a Metal Gear Solid superplay with the "walk through walls" cheat. It's possible to mess up the game pretty badly with it and take huge shortcuts that way, similar to Bisqwit's Rockman v4.
