It's very undeserving by your part by not crediting MrWint as an author especially when you straight bullied him on his movie. You dismissing him here too?
The fact that entertainment had to be pointed out when reading came off like a massive jab against the currently published movie (and your own prior one, even though you state "maximum entertainment").
On the topic of entertainment, in comparison to this and MrWint's I prefer Wint's direction of the movie compared to yours. So in terms of comparison and entertainment I'm giving this a Meh.
Shotgun the publication even after all I wrote, after all I have been the one who has reencoded all of Super Mario Bros..
xxNKxx wrote:
But example in 4-1 stage, nearly the flag, slow down to fire last enemy for entertainment, I think it's waste
MrWint wrote:
If anything, you are missing out on entertainment value you could have by spending these extra pixels more productively.
You want "ROBOTS" to go over this Lee?
Actually to add to my first point:
HappyLee wrote:
Of course we can collaborate, that's what I've been saying.
Curious on what happened to this btw.
WebNations/Sabih wrote:
+fsvgm777 never censoring anything.
Disables Comments and Ratings for the YouTube account.Something better for yourself and also others.
It's very undeserving by your part by not crediting MrWint as an author especially when you straight bullied him on his movie. You dismissing him here too?
What happened then is I offered a chance to credit MrWint as an author to our project, but only as an author who've found the 4-4 improvement, and MrWint kindly refused after some serious thoughts. In his own words:
MrWint wrote:
First of all, I'm happy to join you with your project to create an even better warpless TAS, but only if I actually can be helpful in the creation of whatever is left to do. I have already created the tools necessary to do precise optimizations, and I can apply them in furtherance of your project. It feels disingenuous to just join your project without actually contributing, maybe just to get this my submission out of the way of yours.
So I'm not bullying him or dismissing him or anything. I respect him and his work, and already give full credits of 4-4 improvement to him in my submission text. I don't find it necessary to credit him as an author just because he found the 4-4 improvement, since he didn't credit me as an author for all those previous improvements either. (And of course I'm not blaming him, because that's fair enough.)
Spikestuff wrote:
On the topic of entertainment, in comparison to this and MrWint's I prefer Wint's direction of the movie compared to yours. So in terms of comparison and entertainment I'm giving this a Meh.
I'm sorry to hear that. I don't know if that's your real judgement or just angry talk.
Recent projects: SMB warpless TAS (2018), SMB warpless walkathon (2019), SMB something never done before (2019), Extra Mario Bros. (best ending) (2020).
For a good example of how to defend one's work in a respectful manner, something that you seem to be quite bad at, check MrWint's posts here.
I have just read that thread and unfortunately all I can see is lots of people with severe misconceptions about what bots are and how they are used.
To start off, I heavily object to the name "exhaustive search bot". Just by a simple calculation at the size of the NES RAM and the possibility of inputs, it's pretty obvious that with current technology it's impossible to make a bot that's truly exhaustive. The amount of possibilities is too much, even for a computer to check.
What MrWint did, and actually very well, is to put the game mechanics into a simulation so that he could solve it with algorithms. That's a highly nontrivial achievement and I did not see anyone dispute that.
However, what most people should not confuse this with, is that just because a run uses a simulation it is more optimized than one that doesn't. The result of a simulation can only be trusted if what is assumed to make it is valid in the first place. HappyLee was simply pointing this out in that thread. There were many instances where a bot search was, strictly speaking unnecessary.
This should not be interpreted as belittling the run (and despite your statement, it was MrWint who actually assumed it was). The previous run is a very elegant solution to an artificial intelligence problem, namely how to TAS SMB with algorithms.
Regarding the "No" votes, I can say that any input on low entertainment they could have has already been diluted in the pretty obvious bias against the author that some people who posted demonstrated. It was stated that it was unfair that MrWint is not an author (even when HappyLee offered him an authorship and he declined on that thread you link to), that Lee is a one-trick pony for TASing one game, and that he was arrogant in that thread. Sometimes you come up with new ideas and end up only reinforcing what was already known. That's life, it's dumb for other people to assume otherwise.
To sum up, what this looks like to me is: someone submits a TAS using cool and interesting techniques to a known game. People get overhyped because of "OMG BOTS", then an experience TASer comes and points out the simulation was incomplete, and then a group of people, after the hype dies out, start nitpicking and cast some very dubious "No" votes.
With all due respect to GoddessMaria, mass hysteria and mob rule are very real things. I don't see why the community should be above criticism and find depressing that people cannot point this out without threats of intervention.
I totally agree with p4wn3r.
Just to add things up: I find MrWint's approach of TASing SMB (or any game) with algorithms highly intelligent and brilliant, even probably revolutionary. However, I do think it can be controversial in some ways, since it's just so different from the usual approach we've been practicing for years. For an observer or outsider, it can be seen as real progress and something really beneficial, but for an experience TASer like me, it can hardly make me happy, and actually got me worried.
Maybe very few could understand how I felt. It's like you study Go the entire life, and fight hard to be one of the top Go players, and then you meet Alpha Go, which would beat you almost inevitably. This really has nothing to do with my ego, but just some seemingly unimportant concerns that very few could understand.
Edit: BTW, I believe it's possible to make a bot that's truly exhaustive, for a small part. I'm interested to know how long does it take for a bot to exhaustive search 10 frames or 100 frames (for simple NES games, for example).
Recent projects: SMB warpless TAS (2018), SMB warpless walkathon (2019), SMB something never done before (2019), Extra Mario Bros. (best ending) (2020).
To start off, I heavily object to the name "exhaustive search bot". Just by a simple calculation at the size of the NES RAM and the possibility of inputs, it's pretty obvious that with current technology it's impossible to make a bot that's truly exhaustive. The amount of possibilities is too much, even for a computer to check.
Technically speaking that's not true in all cases, but that conversation would be a bit off-topic in this particular thread. I would write an essay about it, but maybe that would be better in a thread that's more on-topic with that subject.
Joined: 4/17/2010
Posts: 11495
Location: Lake Chargoggagoggmanchauggagoggchaubunagungamaugg
Warp wrote:
p4wn3r wrote:
To start off, I heavily object to the name "exhaustive search bot". Just by a simple calculation at the size of the NES RAM and the possibility of inputs, it's pretty obvious that with current technology it's impossible to make a bot that's truly exhaustive. The amount of possibilities is too much, even for a computer to check.
Technically speaking that's not true in all cases, but that conversation would be a bit off-topic in this particular thread. I would write an essay about it, but maybe that would be better in a thread that's more on-topic with that subject.
It's been split into a topic about bots, so it must be perfectly fine to resume this talk :)
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
I suppose that it comes down to how you define "exhaustive".
Let's take an example (which I'm personally extremely familiar with, as it pertains to my job): Suppose you are given, let's say, 20 random letters, and a large dictionary of English words (let's take the sowpods dictionary, which is used for official scrabble tournaments, and contains 276663 words), and your task is to find every single word in that dictionary that can be formed with any amount of those 20 letters.
If you find every single such word, without missing a single one, you could arguably state that the search was "exhaustive". But how long does this take?
An extremely naive approach would be to create every single possible permutation of up to 20 letters from that given set, and check if it appears in the dictionary. The number of possible permutations is over 20 factorial, which is absolutely enormous. (20 factorial alone is over 1018, ie. over 2 quintillion in American notation. The actual number of permutations is larger because you also need to check all the possible combinations of 19 letters, 18 letters, and so on.)
Even if you could check one billion permutations per second, it would take about 2 billion seconds to go through all of them, which would be about 77 years.
But how long does it take in practice? In actuality, producing that list of words that can be formed with those letters takes a small fraction of a second, even in a slow computer.
The trick is that you don't need to go through all the possible permutations of those 20 letters. When creating permutations, when you have taken two letters, you can check if any words start with them, and if they don't, you can skip all permutations that begin with those two letters. (The same goes of course for permutations of the first three letters, and so on.) This reduces the number of permutations to check to a microscopic fraction of the total. (There are also other algorithms possible for this task, which do not involve going through permutations of the 20 letters, but they aren't completely dissimilar to this idea either.)
Technically speaking the search was exhaustive: The resulting list contains every single word that can be formed with those letters, without missing any. However, the task didn't require 77 years to complete, but a small fraction of a second.
The point of this whole thing is that just because something may have a ginormous amount possible permutations or combinations doesn't automatically and necessarily mean that an "exhaustive search" (which I take to mean "finds the optimal solution") requires an exponential amount of time. (It can mean that, especially if the task is provably NP, but it's not necessarily so.)
Joined: 3/9/2004
Posts: 4588
Location: In his lab studying psychology to find new ways to torture TASers and forumers
In your example, couldn't you also go through all 276663 and prune the ones that contain any of the 6 letters not specified? I think that may end up being a much faster approach.
Warning: Opinions expressed by Nach or others in this post do not necessarily reflect the views, opinions, or position of Nach himself on the matter(s) being discussed therein.
Actually, what you are saying is simply that one algorithm is better than the other. For one particular problem. You can search all word combinations, or search all dictionary words. In this case, searching all dictionary words is more efficient.
However, if you are dealing with computer programs, to improve on the naive method requires the code to be extremely simplified. We already have an example of this. By the authors' account it consists of around 800 instructions and there is only a main loop without hardware interrupts. That's what makes it possible to simplify everything and perform the search.
With respect to the game this was discussed (SMB), one possible situation that a movement simulation does not cover is some sort of ACE setup that could glitch Mario through all the stages at enormous speed. Ruling out ACE quickly becomes unfeasible as the code grows in complexity. Moreover, for the particular submission, a shorter movie was presented. That alone suffices to prove the simulation in question was not complete.
It's like, when someone says "to make a computer play chess, you have to search millions of positions", and you reply "not really! chess might be one of these games where you can find a winning strategy without searching. While that really is true, there's no reason to believe we are anyway close to finding such strategy.
Extraordinary claims require extraordinary evidence. At some point if some guy comes up with a formula that plays chess perfectly, you have to ask what is more probable. That chess players and AI researchers for the last centuries all missed a key point in the game that someone eventually discovered like pulling a rabbit out of a hat, or that his/her proposed solution contains a mistake. In general, when something seems too good to be true, it usually is.
What if we use an open-source emulator, minus graphics and sound and all unnecessary process? Could anyone tell me how much it would be slower than MrWint's approach (simulation)? Theoretically it could fit all games, without code disassemble or creating a simulation.
Recent projects: SMB warpless TAS (2018), SMB warpless walkathon (2019), SMB something never done before (2019), Extra Mario Bros. (best ending) (2020).
Only one truly exhaustive search is: try all possible inputs.
Formula for this, is very easy: variants_to_check = variants_of_input^input_frames
where ^ -> rising in power.
For example, NES has: A B Select Start Up Down Left Right.
It is eight inputs.
All possible variants of this input:
variants_of_input = 2^8 = 256
Because you can press or not, each one independently.
Next accodring to formula above, movie with 67117 input frames will take:
variants_to_check = 256^67117 = 6.9462728 * 10^161633 (approximately)
So, you can say, that it's bigger than 1 with 161633 zeroes after.
You can't check it using all CPU power on the planet during your life.
You'll need then 1 and another few zeroes more centuries.
So, it's not feasable.
You have to somehow cut possibilities.
To able to cut the search, you need knowledge.
Most of time, you don't know where may lead this possibility, or may not.
For example, you may think that something is waste of time, but you just don't know
that waiting somewhere may allow to do some "trick" that will cut some time after.
So, you can't cut possibilities too early, but also you don't know how late you should wait to make sure that this will not help.
I see this "long term" advantages as main obstacle to make TAS, both for human and bot.
You can program some stuff for making decisions: how late/how early...
But this will make possibility that you've missed something.
You can go further. You may start proving based on code that something is not possible, and step by step simplify simulation of game to make it more predictalbe.
But then you'll have possibility that you've made mistake in your proofs.
So, exhaustive search may help only in very local situations, with simplified game simulation, and perform such jobs as subpixel positioning.
It's not really exhaustive. It's exhaustive only in terms of simplified game simulation.
Suggesting truly exhaustive search of the entire game is simply infeasible and totally unnecessary.
In my opinion, partial and limited exhaustive search is still exhaustive search.
For example, you want to exhaustive search one extremely difficult movement, which is 100 frames in search length, and you can limit inputs to A B Left Right only (probably because you don't find Up Down Select Start useful in this particular movements). Variants_of_input = 2^4 = 16, and variants to check = 16^100.
I don't find it feasible using lua script (since it's too slow), but it's totally feasible using MrWint's approach (as we all know he has succeeded in doing it). So my question was, could it be achieved without creating a model so it can fit any game?
Recent projects: SMB warpless TAS (2018), SMB warpless walkathon (2019), SMB something never done before (2019), Extra Mario Bros. (best ending) (2020).
For example, you want to exhaustive search one extremely difficult movement, which is 100 frames in search length, and you can limit inputs to A B Left Right only (probably because you don't find Up Down Select Start useful in this particular movements). Variants_of_input = 2^4 = 16, and variants to check = 16^100.
Limit to "A B Left Right" - is not truly exhaustive, except if you prove that any other button can't cause any usable effect.
But more than that. 16^100 is not feasable.
Simulation of this count of variants will take more than your life. :D
First, approximate 16^100 = 2.582249878 * 10^120 (aproximately)
And round down > 10^120.
Imagine 10^10 simulations in second on single CPU (unreal for current CPUs), then it is 10^110 seconds.
In year there is 365*24*60*60 = 31536000 seconds.
"Shortend" year by rounding down to 10^7 seconds.
Now for that single unreal CPU you need 10^(110-7) = 10^103 years.
\o/
If you have 10^9 such CPU, it will reduce only by 10^9, so yet again: 10^94.
This is unreal.
Real counts is about 2^64 which is around 10^19.
So after first reduction by CPU it is 10^9.
And after reduction by year it is 10^2.
Then, after reduction by CPU count that is 100, it's feasable.
If computations can be made on GPU which has many CPUs,
then many GPU can break it in months.
HappyLee wrote:
I don't find it feasible using lua script (since it's too slow), but it's totally feasible using MrWint's approach (as we all know he has succeeded in doing it).
For lua it will take kinda same. Lua just adds some time.
For example, in lua it may take ten times longer.
Reason why 100 frames may be feasable, just because using more strong assumptions.
And main such assumption is: no matter how you got particular state of machine (NES), you'll have same results using same inputs afterwards.
This is reducing variants enormously.
But this is yet again making search less exhaustive, because you can't claim that state is same, unless you have all memory and registers state to be same.
And it's very rare to happen. Just because there are: HV counters, scroll positions, enemy positions, and many many other stuff.
So basic approach to assume that state is same if main character has same state.
But even this may lead to problems, because he usually has not only position, but also: velocity, jump/land state, mode (big/short in mario), invtime (I-frames), hit cooldown, and may have many other stuff.
My search that was looking among 90 frames in Donald, is taking 6 seconds.
I used only two buttons: left and right. And state was only speed and position.
Nothing else.
Even though buttons just two: 4^90 is not feasable again.
As I said 2^64 = 4^32 is more real goal.
But it is assumed that you can make simulations extra fast.
HappyLee wrote:
So my question was, could it be achieved without creating a model so it can fit any game?
Mindless - no.
You have to program math model of simplified game behavior.
Thus, you need to reverse engineer it.
Only one truly exhaustive search is: try all possible inputs.
Which may be equivalent to say, in the example I gave, "the only truly exhaustive search is to try every single possible permutation of the 20 letters". Which is completely unnecessary, because the perfect answer can be found in a microscopic fraction of that.
(Not saying that's necessarily possible with a NES game. Just saying that finding a perfect solution doesn't necessarily require trying every possible combination of inputs. It could, depending on the game, but not by necessity in every single case.)
Just saying that finding a perfect solution doesn't necessarily require trying every possible combination of inputs.
Yes, it's not recessary.
But exhaustive means that you exhausted all other options.
So, there is no shorter input that finish game.
But you can't know that, just because you can't try all of them.
r57shell wrote:
You have to somehow cut possibilities.
To able to cut the search, you need knowledge.
Most of time, you don't know where may lead this possibility, or may not.
Just saying that finding a perfect solution doesn't necessarily require trying every possible combination of inputs.
Yes, it's not recessary.
But exhaustive means that you exhausted all other options.
That feels rather nitpicky. The goal is to find the optimal input. "Exhaustive" in this context can be taken to imply that the input is indeed provable to be optimal. Finding this optimal input doesn't necessarily require trying every single combination.
You seem to be arguing something like "you can't call it exhaustive if you don't go through every possible input", when that's not the point.
So, there is no shorter input that finish game.
But you can't know that, just because you can't try all of them.
The entire point of my example was to show that it's not always necessary to go through every possible combination to know that the end result is optimal. Depending on the game, there may be combinations of input that cannot lead to an optimal solution, and thus can be skipped.
Joined: 4/17/2010
Posts: 11495
Location: Lake Chargoggagoggmanchauggagoggchaubunagungamaugg
Games are different from words. Right in front of us people find glitches that cause unexpected shortcuts. Not even necessarily something that instantly ends the game. Just basically any glitch can happen if truly exhaustive search is done, regardless of our assumptions of clearly useless input.
If we disregard glitches, then indeed the search can be made very limited and still work for the intended game engine. But look at memory corruption techniques. Setting up what variables will go where, and how they will be broken, takes time that a simplified bot might consider suboptimal, or even obviously useless. But a few minutes after you end the stage that'd take you 10 minutes.
Like I said, it doesn't even have to be a major skip. Some minor glitch with enemy subpixels that only appears in the next stage and lets you save more time than you lose right now by causing this glitch.
It's called routing, and it can be insanely complicated. Building full simulation is sometimes not feasible, so unless the search is 100% exhaustive, there's still possibility that a movie can be improved.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
You seem to be arguing something like "you can't call it exhaustive if you don't go through every possible input", when that's not the point.
Yes, but my "support" of this point is different:
Warp wrote:
Depending on the game, there may be combinations of input that cannot lead to an optimal solution, and thus can be skipped.
How do you know?
How do you know that this cannot lead to optimal solution, or other way may lead.
"r57shell wrote:
Most of time, you don't know where may lead this possibility, or may not.
"r57shell wrote:
You may start proving based on code that something is not possible, and step by step simplify simulation of game to make it more predictalbe.
But then you'll have possibility that you've made mistake in your proofs.
So, my point: if you take some assumptions, then it's exhaustive with assumptions.
It's no longer purely exhaustive. And thus, you may miss something.
Possible outcome: "my exhaustive search tells me that it's impossible."
Later someone: "It is possible, I found the way to do it."
Side note: I was saying that you may find optimal solution without exhaustive search, because it may happen that common way of TASing just leads to optimal input for some games.
But presence of short input doesn't prove that all possibilities are exhausted.
No, they aren't. Not in this context. In this case we are talking about an algorithm to take some input data and find an optimal result. In this context it doesn't make sense to say "this kind of input is different from this other kind of input". Data is data. It doesn't matter what that data represents. What matters is what the end result is expected to be.
Right in front of us people find glitches that cause unexpected shortcuts. Not even necessarily something that instantly ends the game. Just basically any glitch can happen if truly exhaustive search is done, regardless of our assumptions of clearly useless input.
Just because you can't think of a way to cut down the search tree doesn't mean that it's impossible in all cases. With some tasks it could well be, but it's not necessarily so in all possible cases. This is the point I'm trying to make.
Joined: 4/17/2010
Posts: 11495
Location: Lake Chargoggagoggmanchauggagoggchaubunagungamaugg
r57shell wrote:
Possible outcome: "my exhaustive search tells me that it's impossible."
Later someone: "It is possible, I found the way to do it."
It's very close to what happened with MrWint's and HappyLee's SMB submissions. MrWint used some search that's not exhaustive, thought that's it's "exhaustive enough", or maybe "it's not fun anymore", and voila, his (partially) botted movie is beaten.
Warp wrote:
feos wrote:
Games are different from words.
No, they aren't. Not in this context. In this case we are talking about an algorithm to take some input data and find an optimal result.
Can you please be more specific and tell why you think that finding the absolute shortest sequence of inputs that beats the game is the same task (in this context) as:
Warp wrote:
Suppose you are given, let's say, 20 random letters, and a large dictionary of English words (let's take the sowpods dictionary, which is used for official scrabble tournaments, and contains 276663 words), and your task is to find every single word in that dictionary that can be formed with any amount of those 20 letters.
The major difference I see is that the answer to your words task can be checked directly: you just look into the dictionary and clearly see whether the particular word you invented is present or not. The answer to "shortest possible" requires having data to compare to, without having 100% of the possible data you won't be able to prove it's the shortest possible.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
The most obvious example of an assumption that can't possibly be wrong: if two sets of input lead to the same internal memory state in the game (i.e. every address has the same value), then there's no reason to explore possibilities starting from both sets of input data. You can drop one (the longer, or either if they're the same length) and just continue with the other.
Joined: 4/17/2010
Posts: 11495
Location: Lake Chargoggagoggmanchauggagoggchaubunagungamaugg
Ah thanks. But I'm still unsure how it's related to making sure a movie is "shortest possible".
The difference from the dictionary I see is this:
Sure, you can compare every memory state you get to all possible memory states, and disregard all the new input sequences that lead to some previously found memory state. But that doesn't tell anything about which memory state leads to absolute shortest movie. It's just not enough to check if the "word" you have is in the "dictionary" or not.
For example, let's say I have a savestate on frame 1000, I got there by executing certain inputs. It may be possible to reach this state sooner in the movie than in 1000 frames. Without testing all the possibilities up to that frame, I won't be able to prove that 1000 is the optimal frame for this state.
Then there's some movie after that frame. Let's say it beats the game in 5000 frames overall, so it lasts 4000 frames itself. I won't be able to prove that 4000 is the optimal movie length for the "game end" state without testing all other possibilities that are shorter.
Some of the search can be discarded based on this similarity, but not as much as in the "find all words" example.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany
[quote r57shell]
So, my point: if you take some assumptions, then it's exhaustive with assumptions.
It's no longer purely exhaustive. And thus, you may miss something.
[/quote]
It comes down to provable statements that can as additional information contribute to cutting down options that a brute force algorithm goes through while keeping the assertion that ''the end result is proven to be optimal''. So yes, I agree with the 1st part of what r57shell states in this quote, but now assume you could or would go through some specific for some statement or assumption relevant part in the game's code (maybe large enough that nothing else can influence it) and go through it and understand it and deduce from it that the information that this part of the code provides is enough to prove an assumption. Then it is valid to add this new trustable information to your search procedure without any risk of ending up with a non-optimal solution. So yes, using assumptions carries the questionable aspects over from a possibly incomplete search (incomplete with respect to not explicitly going through every input pattern option, even if an option has no chance to be successful to begin with) to these assumptions and how much of these are valid. And if some of the assumptions are invalid, then this might already allow for a faster TAS to exist, or this might aswell just mean that the assumptions could be ''repaired''/extended and adapted to a new situation and the TAS that the information-based search resulted in stays optimal. Generally, it can be the case that one took a stronger assumption than what one was able to prove about the assumption (i.e. one proves a weaker form of some assumption and then maybe by misconception or by overlooking something, one states the assumption in a stronger form and uses the strong version to reduce the number of options that a search process goes through), and in this case there's 2 things that can happen. Namely either this unproven part that makes the difference between the stronger assumption and the weaker assumption was crucial, was a key point for some different branch of inputs that would lead to a faster TAS than what one obtains, or one was ''lucky'' and taking the stronger assumption was harmless/inconsequential.
Edit: In such a situation where one wants to tackle a game with information-based brute force, one might want to prefer going for easily provable statements that have far-reaching implications.
collect, analyse, categorise.
"Mathematics - When tool-assisted skills are just not enough" ;)
Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on.
1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans.
2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai.
(last updated: 18.03.2018)
Can you please be more specific and tell why you think that finding the absolute shortest sequence of inputs that beats the game is the same task (in this context) as:
Warp wrote:
Suppose you are given, let's say, 20 random letters, and a large dictionary of English words (let's take the sowpods dictionary, which is used for official scrabble tournaments, and contains 276663 words), and your task is to find every single word in that dictionary that can be formed with any amount of those 20 letters.
I didn't say that they are "the same task", as in solving one automatically solves the other.
Both are optimization problems, in the sense that we want to find the best possible result as fast as possible. We know in both cases that the optimal solution can be theoretically found, and the sole question is how fast it can be found.
Not all such problems require an exponential amount of time (with regards to the size of the input). It's incorrect to state that it always does, no matter what, because it depends on the actual game in question.
The major difference I see is that the answer to your words task can be checked directly: you just look into the dictionary and clearly see whether the particular word you invented is present or not. The answer to "shortest possible" requires having data to compare to, without having 100% of the possible data you won't be able to prove it's the shortest possible.
That's like saying that it's impossible to prove that a given path between two points is the shortest possible path.
If you try to reduce game to totally valid model with all effects in game included, you'll end up having same impossible in real life times for search.
Easy example. There is well known blue-spheres bonus in sonic.
There are around 64 blue spheres, which you should grab.
Basically it's kind of "Travelling salesman problem".
If you try to brute force all inputs - not feasable (already discussed).
If you try to brute force all orders of grabbing blue spheres - that's 64! approximately 10^89 - not feasable again.
But! Imagine you did that. You did try all orders of grabbing blue spheres...
That's not enough. You also may grab them from four different directions.
This adds 4^64 (approximately 10^38) variants for each.
So, total approximation is 10^127.
Direction is important because you waste a lot of time for turning.
Okay, lets say we want to reduce options by assumption that having same position & orientation & grabbed spheres = same outcome for same input.
This will damage outcome just because there is speed up timings.
Longer you're in bonus stage, faster you go.
This may be wrong assumption. But it may be used as approximation.
More than that. If you make some wrong proofs that you claim is correct.
Then you may build wall to valid options, and people won't try them, because of authority basis.
He said that it's impossible, then it's impossible.
