Does the LMP format actually guarantee that the resulting movie could have been made with the original Doom?
It seems to record actual user inputs - but it doesn't save them as key presses, but as speed and direction. I see three potential problems here, that might result in LMPs violating tasvideos' requirements for emulators/movie formats:
What happens when someone creates an LMP with a speed above 50? Will vanilla doom correctly cap the value?
A perfect straferun, SR50, doesn't allow you to turn at the same time (when done using vanilla doom), but it seems possible to create an LMP which turns and does a perfect strafe at the same time. Are there safeguards against this?
There are patches for prboom that use 2 bytes for the direction, resulting in greater aiming accuracy, but those are incompatible with vanilla doom. Were they used in existing TASes?
A way around these problems would be to TAS a doom game using JPC-RR while having LMP recording on. This would generate an JPC-RR movie for validation and an LMP for high-quality encodes.
The downside is that demo recording limits angles to 1 byte, reducing accuracy.
The other way around this would be to try for acceptance of LMP. It should be possible to create a tool that verifies whether an LMP uses invalid values or not and to use vanilla doom as a baseline for verification.
Quick bookmark because I just found the url: lmp format documentation
well, the idea of having an additional filter by game isn't exactly new ;)
andymac wrote:
[..]On the downside however, this would require a complete makeover of the site's code
Not really. Adding another filter with SELECT ... FROM movies WHERE gamename = '$gamename' should be enough.
It'd require adding an index to that column, and to clean up misspellings of gamenames in existing movies, but that's it. Selecting on a text field isn't the most performant operation, but afaik all those results are heavily cached nowadays, anyway.
(the original idea was a lot cleaner than that, but also more complicated/invasive to implement. Which is part of the reason why it was never actually done.)
Once that's done, adding some new tables with a game's meta-information should be possible. This could be information like "Pokemon blue is the same game as Pokemon red" (to display both on the same page) or "For the game Zelda Ocarina of Time, there's a page called ZeldaTricks".
It's not really complicated, very basic database stuff. However, it is work, and would require the admin's will to see it done, and someone elses will to implement it, and so far I haven't seen either.
I enjoyed it.
As with most RPG runs, some explanatory subtitles would make it even better. It's been a long time since I played it, and I wouldn't notice a sequence break or clever trick unless someone pointed it out.
I'll add a yes vote and the promise to watch it again if someone adds those subtitles.
and no, trick discoveries is in no way comperable with input.
That's the point I disagree on, and you merely stated this as a fact, without providing any arguments that might help me understand your view.
I understand why you're not happy about the situation (in your situation I probably wouldn't be, either), but that was not the question I've been asking.
MrGrunz wrote:
the only reason why the MM TAS was supposed to be that enjoyable to watch was the fact, that we could see so much new stuff there
so.. why did you release a WIP and tricks? Not sharing isn't the nice thing to do either, but releasing your tricks AND expecting them to be new and surprising when the run is finished doesn't really add up.
All things considered, I understand your frustration, but abeshi didn't actually release any of your stuff you didn't release yourself. And while he was doing it, he found a few tricks that'll help you and released them, too. Call me a glass-half-full guy, but in the end, it'll make your run better, not worse.
(but again, I know why you see things differently right now. You're human, and naturally the first instinct is "THAT GUY STOLE MY RUN!!". Hope you'll see things differently in a few day's time; in any case I'm glad you're working on your run and look forward to the day when it's finished.)
BTW, novelty isn't the only thing that makes a TAS interesting to watch. There are TASes I've watched dozens of times and will continue to watch.
Slowking wrote:
You really compare the work that goes into an optimised TAS of this length to the work that goes into finding a trick? How long have you been on this site?
No, I'm comparing the work that went into a few snippets of input that were reused (the thing abeshi did that's supposed to be bad) to the work that went into hundreds of tricks and routes that were developed by several people over the course of several years; tricks which every new zelda TAS uses and which is generally considered to be OK without asking for permission or giving credit.
I didn't check which parts were reused (or how many), but the arguments I saw in this thread all revolved around the kind of work that was copied, not the amount of work. Many argued that input was copied, but noone argued that the route was copied, even though the combined amount of work that eventually lead to the creation of the route is pretty huge.
@Wren: the method (a bomb jump) can be patented while copyright can apply to a specific implementation (the input file doing a bomb jump). In most countries, both things can be protected by law, just by different parts of it, with different requirements and restrictions.
But copyright usually requires the implementation to be non-trivial (i.e. a whole run, not a short snippet), and the US copyright law you cite has this Fair Use thing, which may or may not apply in this case, and is moot in japan anyway.
I don't consider laws made for the industry to be very useful here...
@Kirkq: something created with a program usually is not a derivative work of the program. If you wrote a new emulator based on FCEUX, then you'd have a derivative work of FCEUX. If you paint a picture, it's not a derivative work of photoshop (but possibly a derivative work of other images you used in the process). This post is not a derivative work of my browser. The letter you wrote is not a derivative work of your pen.
As such, the runs on this site aren't necessarily GPL'ed.
Whether the run is a derivative work of majora's mask is an entirely different question I cannot answer. Hopefully it'll never be relevant for this site ;)
Of course IANAL.
This may get slightly offtopic, but why is it an accepted standard to use routes, tricks, discoveries and everything from previous runs, but as soon as someone copies actual input it's a crime?
Remembering the discoveries of the ISG, then the SS with Nayru's Love, further refinements to ditch NL and use a variety of triggers, the forward SS and finally the extended SS, figuring all of that out took a large amount of time and skill, likely no less than the effort MrGrunz spent on the sequences that were copied (though it took a different skillset).
So why is it okay for MrGrunz (and everyone else) to use extended superslides without asking for permission, while input must not be touched?
(Sure, credit where credit is due, but then again I don't see any credit for discovering the IGS in all those zelda submissions, either. Not even on the game resources page, where those tricks are explained. Credits seem more of a courtesy option than a strict requirement.)
I actually didn't find anything in the rules forbidding the re-use of input, and I can only come up with one reason to treat input differently: "style". I can understand that copying the name input or personal stylistic choices may be considered disrespectful. But is that really the issue here? At least the point wasn't explicitely raised by anyone.
Showing off every mission sound like a good choice. More missions are more enjoyable to watch than idle turns.
I'm not sure about the S-rank goal - wouldn't that prevent some of the sneakier tactics that were used in the AW2 run?
Wow, that's impressive!
How did you manage to finish such a long WIP in such a short time? Have you been working on it in secrecy or is it due to the LUA scripts?
moozooh wrote:
Ok, here's a riddle: what's both unexpected and impossibly cool?
well, if you want proof, first attempt would be a brute force algorithm:
function recurse()
{
E = first place that's empty (needs a consistent order of the 5x5x5 cube's places)
report success if no empty place found
for all pentacubes P not yet used:
for all (3 to 24) unique orientations O of the pentacube P:
for all 5 cubes C of the pentacube P:
rotate P into orientation O, locate it so that C fits into E
if P fits into the 5x5x5 cube:
insert P
recurse()
remove P
}
The complete search tree suggests a running time past the heat death of our universe. Even though a lot of subtrees will be cut short, I don't think this'll lead to the solution unless it's lucky enough to find a working combination quickly.
In other words, we need to be smart about it, but so far I haven't had any idea for a either a smarter construction or a structural proof of impossibility.
I guess the best approach is to construct the cubes and spend a few hours fiddling with them, that may just find a solution.. but I don't feel like spending that effort ;)
For a speedrun of this length, there are better ways to entertain the audience.
For a playaround, this one seriously lacked tricks.
voting no; I don't think "low score" is a suitable category for this game.
Suffers a lot from Zeldaism: you manage to shorten the gameplay by an impressive amount, only to find that most of the remaining movie is unamusing stuff like menu interaction, cutscenes etc. This would be a clear yes if it was shorter, but ~10 minutes of doing the same glitch over and over again get boring quick. Meh.
it's been said already that true brute-force bots will never happen, but I'd like to throw the numbers around again.
amaurea wrote:
More like 10100000 rerecords for brute force.
so far, the universe has existed for about 8*1060Planck times.
The visible universe is roughly (1026)3 meters large, which is equivalent to 10183 cube Planck lengths.[1]
If we make a best-case-assumtion that the universe can host a fully working computer at each planck length (it can't) and those computers can test a combination every planck time (they can't), we'll end up with a maximum of 10243 combinations tested since the big bang.[2]
An NES controller has 4 buttons and a dpad. Thus there are 16*9=144 possible controller states for each frame (in a one-player game without L+R). Brute Forcing 113 frames of NES input (just under 2 seconds) would require calculating 144113 > 10243 combinations, pretty much exceeding the physical computation power of our universe.[3]
TASes that are assisted by smart bots attempting a limited set of possibilities (i.e. short sequences for luck manipulation, greedy strategies, heuristics, ..) are possible, but their possibilities are only slowly increased by computational powers. 1 more frame brute forcing = 144 times the calculations = 14 years of computer innovation (according to the most popular misinterpretation of Moore's Law).
An actual brute-force-bot that'll accept a ROM and a winning-condition and produces a TAS? Not in this universe.
[1] We don't know how large the non-visible parts of the universe are, but that doesn't matter. Only the visible portion has the chance to communicate the results of their computations to us.
[2] Discounting relativity and quantum effects for ease of calculation.
[3] With a quantum computer, we only need sqrt(n) steps instead of n, thus doubling the number of frames calculated in the same amount of time/space; raising the limit of our universe's computational power to no more than 226 frames.
/edit: fixed math because something as complex as a digital dpad confused me.
Atma did two test-runs, although I'm not sure if they're public.
All runs I know use largely different routes though, so I'm not sure if a comparison video will be useful past the first few rooms.
a) If in doubt, ask http://en.wikipedia.org/wiki/Point_in_polygon
The first two algorithms mentioned there are the most widespread solutions, for good reason. The first one is a bit faster, but you'll have to be more careful with corner cases (what if the line hits the vertex?). Nitrodon's triangle algorithm might work, too (I didn't check), but the point-in-triangle-calculations required are more expensive.
/edit: Hi Warp!
b) intersection of two non-convex polygons is complicated. Let's start with polygons A and B, the intersection consists of the (non-intersecting) polygons C1, ..., Cm.
One option is to check each edge of polygon A against each edge of polygon B, whereever they cross you'll have one vertex of one of the result polygons Ci. From there on, follow the edges of the "inner" polygon until you reach the next crossing and connect accordingly.
Unfortunately, the first part alone is O(n^2), and the second one isn't trivial, either (now which side is the "inner" side?). And there's still those corner cases where vertices coincide or where edges cross a vertex.
There are a couple of sweepline algorithms that can do it faster, but I don't remember the details.
Both problems are very fundamental algorithms of computer graphics, both well-researched with plenty of algorithms to use. I'm surprised you didn't find anything in your research.
* it just says "infinity is strange, by comparing things with infinity, we arrive at strange conclusions"
I wouldn't call it "strange", that sounds too much like voodoo. When you're inserting infinity into your usual formulas the result is simply undefined, because addition etc. is only defined on reals. When you're disguising infinity as "x" and continue calculating, you seem to get results, but they're wrong.
Let's go back a step. To determine which strategy is "better", we need some metric. Currently, we implicitely use the metric of expected value, which is useful in many areas, but doesn't give usable results here because it is infinite. We can reach some conclusions, but only if we're careful with our tools and formulas.
Remember, the expected value does not make any predictions about a single game, it's only useful if you're considering a very large sample. And once you do that, you'll notice that both strategies (switch or don't switch) are equal, because you'll have an infinite payoff either way and it doesn't get any better than that.
However, once you opened an envelope, it's still "better" to switch (1.1*x), this conclusion avoided the use of infinity and is thus valid. How is that possible? Because "better" means "higher expected value", which is only meaningful for a large sample. And we've used a conditional probability; the result is useful only as long as the condition remains the same.
Let's say you're playing the game 1000 times, each time you open the first envelope and read the number 64 (if you don't, discard the game and try again). If you stick to that envelope, you'll end up with 64.000. If you switch each time, you can expect to hold about 70.400 in your hands. True result.
Now we can't conclude "so switching is the better strategy, right?", because then we're randomly pairing up partial values. You correctly said that that's not meaningful, a proof follows.
p4wn3r wrote:
My solution is that the conclusion "Every value in infinite unbounded set A is less than a value in infinite unbounded set B implies that set B is preferable to set A" is not valid.
Consider the sets A and B, both being the sets of all integers. Let's pair their elements up to see which is larger:
..., (-2, -1), (-1, 0), (0, 1), (1, 2), ... -> each element of B is strictly larger
..., (-1, -2), (0, -1), (1, 0), (2, 1), ... -> each element of A is strictly larger
One distribution of (2^n,2^(n+1)) has probability P(n) = 2^n/3^(n+1). The sum of this series converges to 1, so it's clearly a valid distribution. (I never said that set had uniform distribution either, please read that again)
sorry, you neither said "non-uniform" nor did you give an actual distribution in that post, either. Yes, I missed rhebus's link. In any case, the solution is given in rhebus's link as well:
* just opening an envelope has an expected infinite payoff
* switching repeatedly has an expected payoff of infinity * 1.1^(amount of switches)
so while I'm aware that I can't just calculate with infinity like that, you should intuitively agree that an expected infinite payoff cannot get any higher by randomly switching closed envelopes, right?
(more precisely, if you want to argue that repeatedly switching is favorable, you need to find a different approach than the expected gains, to avoid the infinity in your formulas)
Once you actually open an envelope and notice that you're well below your expected infinite payoff, switching once is favorable. But since you opened the envelope, you can only switch once, avoiding the paradox.
If you're concerned that the correct strategy is "switch" no matter which number you picked: see the monty hall problem which has the same resolution. IMHO it's a non-issue.
Wait.. at time t (in seconds) the woman has a horizontal distance of 3.5*t feet to the streetlight (assuming she's directly under the streetlight at t=0).
A straight line from streetlight through the woman's head will touch the floor at
(3.5t) / 7 * 12 = 6t feet (interception theorem),
thus the tip of the shadow moves at 6 ft/s.
Of course the length of the shadow at any given time is the horizontal distance between the woman and the tip of the shadow, which is
(6t - 3.5t) = 2.5t feet
Did I misunderstand the question? Where's the derivative?
That can be answered by trivially applying the intercept theorem, which I learned in 8th class when I was 13. I'm not familiar with your scholar system, how old is a "first year calc student" actually?
It can be argued that it's impossible to have a uniform infinite distribution according to modern probability theory. While this solves the problem I brought up, it can be changed so that the set in discussion is { (2^n,2^(n+1)), n in Naturals }.
Nope. There is no uniform probability distribution for any discrete infinite set (or for any unbounded interval in continuous distributions), not in any variant of probability theory. Here's why, for the discrete case:
A uniform distribution must satisfy these conditions:
* the sum of all probabilities must be 1 (otherwise it's not a distribution)
* P(X=a) = P(X=b) for all a,b (otherwise it's not uniform)
Now what's P(X=a)? If P(X=a) = 0, the sum is 0. If P(X=a) > 0, the infinite sum doesn't converge.
You can use a different distribution that is valid on all positive numbers, but then you'll need to re-examine the part I coloured earlier. Depending on the value of money in your envelope, the chance that it's the lower amount is anything but 50%.
(Of course, since Bertrand was mentioned, we must also specify the exact method for determining the amounts. After picking a random number x, we could fill the envelopes with (x, 2*x), or (x/2, x), or maybe (42*x, 84*x). As soon as we use non-uniform distributions, the exact method matters.)
Dear Fabian,
back on page ~14 you helped me with some women trouble and I just noticed I never followed up on it. Now don't take all the credit for it, but that woman and I have been together for 3 years now. Just wanted to say thank you!
and because I don't want this post to lack any question: what career choices have you considered so far (besides the accountant thing you mentioned), and why didn't you stick with them? What's your criteria for a good career choice?
greetings,
Tub
Suppose that you have to choose between two envelopes, one contains X dollars and the other 2X dollars. After choosing an envelope with A dollars, you're given the chance to switch to the other one. To see if it's worthy, you assume that there's 50% chance the other one will have A/2, and another 50% that it'll have 2A. Summing, your expected gain will be 5A/4, thus it's better to switch. However, since that's true for every value, switching before even choosing the envelope would rise your expected value, and this is absurd.
I coloured your dinosaur problem.
Calculating the expected gain is valid, but assuming 50/50 to hold the smaller amount is flawed. If there's a limit to the money in an envelope (say between $100 and $10.000), you don't have a 50/50-chance if the envelope contains $190 or $6000. Note that if you pick an envelope with $1000, you're absolutely correct to say that switching is advantageous. But you'll only know after you actually opened the envelope and compared the value to the possible range.
Now you're saying: any amount goes. To which I reply: there is no uniform distribution over all numbers, your premise is flawed.
It's pretty difficult to give a precise answer unless you give a precise definition of the problem. The problem here seems to be whether we know something about the distribution or not.
Given the real-life source, we can safely assume that there's a finite range (i.e. surely no more than 10^90 digits) with a non-uniform probability distribution. It's also a discrete set, since there's only a is a limited amount of numbers that could be memorized by a human brain / expressed in the human language in a reasonable amount of time.
Case A: both players know the RNG (from previous matches) and have the ability to guess his probability distribution. Let's assume they've both guessed the distribution perfectly. Player 1 chooses exactly the median, player 2 can pick higher or lower, each choice having roughly 50% success rate.
Case B: both players guessed the same probability distribution, but both guessed wrong. Since Player 2 considers Player 1's guess to be the median, he'll throw a coin to pick higher or lower, yielding 50/50.
Given equal knowledge of both players, player 2 does not have an advantage
(as kuwaga explained there's a slight advantage for one of the players since we're operating on a discrete set, but only a very slight one, and we don't know for which of the players)
Case C: both players guessed a different probability distribution with a different median. Player 1 guesses the median to be M1, Player 2 guesses M2.
If each player just said his number, their chances would only depend on the quality of their guesses.
But, if one player goes first, the second one will adjust his guess to M1+\epsilon or M1-\epsilon.
And there's the advantage of player 2: if both guesses are far apart, he can claim the whole interval in between instead of only half.
If neither knows the distribution, Player two actually has an advantage!
This one will even work when both players just pick a random number, player 2 will have an advantage because he adjusts his numbers. But this will only hold true if we're limited to a finite range of numbers.
Now if we ignore human restrictions and accept any number with any distribution, we have an entirely different problem. Why? There is no distribution over all numbers and our concept of median goes right out the window. Without an actual median, the strategies break down.
Does player two still have an advantage? See this similar question for inspiration.
http://blog.xkcd.com/2010/02/09/math-puzzle/comment-page-1/
Assume that someone asked the question: "What is the computational complexity of merge sort?" Then someone answered: "That question is meaningless because calculating computational complexities always assumes an unlimited amount of RAM, and there's no such thing as an unlimited amount of RAM" [..]
[nitpick]
no, it doesn't assume unlimited ram. Since each computational step can only write to O(1) memory locations, memory complexity is always bounded by computational complexity.
On the other hand it's trivial to find an algorithm that uses no more than O(1) memory, but does not have a computational bound, even with 100% chance of termination.
[/nitpick]
by SDA timing, mukki's TAS is around 2:06, not 2:14. Jiano's unassisted run is indeed 3 minutes faster.
2 years of research by a lot of capable people do make quite a difference.
I remember a time when successive submissions of this game were fighting for mere frames. Everyone trying to squeeze the last bit of optimization out of this game.. or so we thought.
What you've done to this game is truly amazing. Hats off to all of you!
