Joined: 3/11/2004
Posts: 1058
Location: Reykjavík, Ísland
Diablo 1 with three players (one of each class). That would be intense.
Edit: and naturally, I mean playing by "ironman" rules, which means you can't ever go back to town after entering the dungeon. (and no restarting in town if you die)
Yoshi's Island 100% all the way. Spezzafer's any% run was already impressive, but a perfect 100% would really have some incredible maneuvers. A 100% Super Metroid would also be nice.
Joined: 3/29/2005
Posts: 229
Location: The boonies.
I'm divided between Final Fantasy VI and a 100% SMB3 run that made extensive use of the Hammer Suit, simply because that was my favorite suit in any Mario game, ever.
For more current systems, I would give my left and right hands (respectively) to see perfect runs of Castlevania: Symphony of the Night and Castlevania: Lament of Innocence's Crazy Mode. In fact, I might give one of my feet as part of the deal for the Crazy Mode one, if it came to that.
Joined: 4/8/2005
Posts: 1573
Location: Gone for a year, just for varietyyyyyyyyy!!
After few decades we may have quantum computers powerful enough to produce perfect input for any game in less than a second. So, I don't think it's impossible that we eventually see all games done perfectly. Seriously! :)
Well, letsee,
For a Super Nintendo Game, there are 2^12 possible button combanations for every frame of play.
For a short game, like Super Mario World, we can search the first 10 minutes or so to find the fastest path based purely on button combanations.
Without intelligent pruning, this means that you'll have to search 36,000 frames over 4096 combinations each. For a grand total of about 4.12 x 10^18662 different movie files. Then it's just a simple matter of emulating them all and finding the one that produces the quickest time, which is several million operations each easy.
There is no way ever, even with a quantum computer, that that would happen.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Joined: 3/29/2005
Posts: 229
Location: The boonies.
OmnipotentEntity wrote:
Well, letsee,
For a Super Nintendo Game, there are 2^12 possible button combanations for every frame of play.
For a short game, like Super Mario World, we can search the first 10 minutes or so to find the fastest path based purely on button combanations.
Without intelligent pruning, this means that you'll have to search 36,000 frames over 4096 combinations each. For a grand total of about 4.12 x 10^18662 different movie files. Then it's just a simple matter of emulating them all and finding the one that produces the quickest time, which is several million operations each easy.
There is no way ever, even with a quantum computer, that that would happen.
Yes, but intelligent pruning isn't a terribly difficult matter, it's just more work than anyone here would ever care to do. Maybe we should call up the people who work on Chess algorithms and convince some of them to work on Super Mario World..... =P
Oops! You are Error of Ruto.
Those who are commenting about quantum computers not being able to perform such a search efficiently are probably wrong. I don't want to provoke another dick measuring contest a la MF and his MK64 times, so I won't give one of my usual lectures. I will just say comments like the one above convince me you probably haven't read more than the Popular Science course on quantum computing, and it is worth examining in detail how decent sized quantum computers and their algorithms will work if they are ever able to be built.
Well, at least the computer can probably notice if it's beaten the game if it compares each state to a state or a key part of a state that's known to be in the ending. Then when it tries each combination, it can stop early if it either reaches the ending state, in which case it holds onto that combination if it's the fastest one found so far, or it hits a known completion time.
put yourself in my rocketpack if that poochie is one outrageous dude
Assuming a quantum computer running at 1 GHz. (Very liberal, as most problems won't require more than a few MHz with a large register is usually sufficient to solve most problems quickly).
Now, because we're using a first generation quantum computer, let's assume we have 32 bits.
2^32 = 4,294,967,296 operations each cycle. And we have to emulate 10 minutes of Super Mario World 4.12 x 10^18662 times. Now, unfortunately, quantum computers are non-deterministic. So, in order to effectively emulate even a simple deterministic in a quantum computer you have to do every operation at least 3 times (Then it's only probable, but because there is probably a great number of isochronic files, chances are you won't achieve a desync in at least one of them; however, each canidate must be double checked with a deterministic machine for false positives).
We're assuming, very, very conservatively, that each movie file only takes 1.1 million (because I like round numbers) operations to analyze once, (without displaying anything of course, just simple number crunching because we're only looking for the trigger credits register to change). So, for an even vaugly probably outcome, each operation must be done 3 times. Good thing is, you're doing it for 4 billion different files at the same time.
So now you do it for each set of 4 billion three times, then you do it again on the best canidates in each set of 4 billion, etc, until you're left with a small number of canidates. Then you crosscheck them with a classical computer.
So, down to the math, we're only going to do the first iteration, because the 2nd, 3rd, etc, go much faster than the first, and are omitted for the sake of brievity.
So realivant rectal figures,
100 million ops per 4 billion files (1.1 million x 3 per op x 3 per try)
1 billion ops per second
so,
40 billion files per second
4 x 10^18662 files to check
1 x 10^18652 seconds
Now let's do this the opposite way, how many qubits are required to solve it within a human being's lifetime (arbitrarily selected to be around 70 years)?
2 x 10^9 seconds
4 x 10^18662 files to check
2 x 10^18653 files/second
100 million ops required/set
1 billion ops/second
10 sets/second
2 x 10^18652 files/set
ceiling(log2(2 x 10^18652)) = 61962 qubits/register according to Maple. Which is convienently close enough to 2^16 that it'd probably be easier to build the 65536 qubit processor than program for the 61962 processor.
So yeah, we're on 64-bit processor now. And I think the highest bit processor is 512. So, how long do you think it'll take to achieve a 65536 qubit processor? Certainly not in our lifetime.
I winnar is yuo!
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
After few decades we may have quantum computers powerful enough to produce perfect input for any game in less than a second. So, I don't think it's impossible that we eventually see all games done perfectly. Seriously! :)
That would like to be FF3 for many reasons :
-I wouldn't have to complete it.
-I would see how much the game can be broken with luck and glitch. (Maybe the sketch glitch could trigger the end game)
-I would like to see if it's possible to get the hidden sprint shoes at the exit of Arvis House (invisible unreachable chest)
I didn't really want to get in a big argument with you, OminpotentEntity, because it only engenders ill will, but you just keep talking and talking when you both have no expertise and are clearly incorrect. Let us examine your dubious claims:
OmnipotentEntity wrote:
For a Super Nintendo Game, there are 2^12 possible button combanations for every frame of play.
For a short game, like Super Mario World, we can search the first 10 minutes or so to find the fastest path based purely on button combanations.
Without intelligent pruning, this means that you'll have to search 36,000 frames over 4096 combinations each. For a grand total of about 4.12 x 10^18662 different movie files. Then it's just a simple matter of emulating them all and finding the one that produces the quickest time, which is several million operations each easy.
There is no way ever, even with a quantum computer, that that would happen.
I don't know where you got that final number from, but if there are 36,000 frames of input and 4,096 button combinations for each frame, that's less than 150 million movie files total. A search that small could easily be performed on modern equipment. Let's say you have a setup whereby you can emulate 10 minutes of SNES play in 1 second. That seems like an unbelievably conservative estimate to me. It would take you less than 5 years to test 150,000,000 movie files. Clearly this problem is not intractable. Since it's no doubt possible to test movie files orders of magnitude faster than that, say, through distributed computing or hardware emulation of the SNES, it is proven beyond a shadow of a doubt that perfect movies are not beyond our current reach.
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.
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.
As for your misgivings about building a many qubit computer, keep in mind building an N-qubit computer isn't the same as building a classical processor with an N-bit register, and that the reason we don't build classical processors with ten thousand bit registers isn't because we can't. Though it's true we have a long way to go from a 7-qubit computer (which has been built) to one that can do anything practical, quantum computing is still in its infancy, and the sky's the limit. You need only look as far as an LCD to find an example of a technology where arrays of millions of components are manipulated both rapidly and simultaneously. Granted, the pixels in an LCD don't represent the superposition of many states and don't need to be entangled, but really, the sky's the limit.
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.
I'll admit I know next to nothing about quantum computers. But I do know math.
xebra wrote:
I don't know where you got that final number from, but if there are 36,000 frames of input and 4,096 button combinations for each frame, that's less than 150 million movie files total.
Huh??? Why would you multiply the numbers? This is basic math...
Joined: 3/29/2005
Posts: 229
Location: The boonies.
xebra wrote:
I don't know where you got that final number from, but if there are 36,000 frames of input and 4,096 button combinations for each frame, that's less than 150 million movie files total.
No. Here's how the math works:
Frame 1: 4,096 possible button combinations.
Frame 2: 4,096 possible button combinations.
Frame 3: 4,096 possible button combinations.
....
Frame 36,000: 4,096 possible button combinations.
Since each possibility for each frame has to be cross-checked with each other possiblity for each other frame, this means the number of possible movies we're looking at is 4,096^36,000. Which may or may not actually be the number Omni gave us (4.12 e18662) but is sure as hell a lot bigger than 1.5 e8. (150 million, for those of you who don't speak scientific notation.)
But as I said before, intelligent pruning isn't very difficult. For Super Mario World, for example, you'll never need the L, R, or Start buttons, (barring possible glitches) and you'll never need either X or Y since they do the same thing, and you'll never need to press A and B together, since they override one another. That reduces the amount of possibilities per frame to 192. (I believe. I'm not entirely sure how to handle the "A != B" bit, but I'm pretty sure it basically means that between A and B there's only three possibilities.) Which makes the total number of possible movies much smaller and therefore much more manageable. (sorry I can't give you an estimate; I don't have maple.)
