Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
CasualPokePlayer wrote:
Arbitrary Code Execution: If the PC (Program Counter) touches any RAM currently visible on the system bus, it is ACE.
What about glitches that cause the Program Counter to enter RAM, but the author does not quite have the control to modify that part of memory? (This is mostly hypothetical, since a game that is broken enough to have such a glitch will almost certainly have a glitch that leads to the type of ACE which I was talking about.)
CasualPokePlayer wrote:
Arbitrary ROM Execution: If a glitch can cause the PC touch any byte in ROM currently visible on the system bus, it is ARE.
CasualPokePlayer wrote:
Arbitrary Memory Corruption: If a glitch can corrupt any byte in writable memory or I/O currently visible on the system bus, it is AMC.
I'm pretty sure the existence of these two correlate with the existence of Arbitrary Code Execution.
I'm actually not sure if anyone used these terms seriously before.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Acumenium wrote:
ACE itself is achieved via rearranging and redirecting memory addresses in a way that it runs a program based on it... which this is doing.
Literally all code runs a program based on something. That doesn't say anything. :)
From my understanding, ACE is a very narrowly defined type of game-breaking state (distinct from other types of game-breaking states), based on what is being done (and not what *can* be done). ACE is a state where any desired sequence of values the author so chooses is promptly written to any desired addresses in RAM, and is immediately executed thereafter (or such equivalent power). Usually "promptly" is understood to be in the order of at least one byte per frame.
As far as I know, none of the non-playaround game-end glitch TASes even use the term "arbitrary code execution" as a branch. They just use "game-end glitch", even if the glitch used has the potential to cause ACE. This is because defining ACE in terms of potential causes is far too vague (Ex: Many games have ACE exploits in them. Does that make playing the game itself "ACE", because the game is capable of ACE? If not, where do we draw the line?)
That being said, Pokemon is so broken that I can't tell "how close to ACE" a glitch is. And I'm not familiar with the glitches in this TAS, so I certainly can't tell you exactly what limitations are being used here.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I didn't have a look, but how many frames did you need to wait to manipulate the card layout?
No one except me cares anymore how TASers end their TASes, so you can use whatever ending criteria you like. However, it would be nice to provide a version of the TAS that has the music on. I miss that.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Warp wrote:
FractalFusion wrote:
It turns out (see this article) that if f(x) and g(x) are analytic everywhere and not the zero function, with the limit as x--->0 of both functions being 0, then the limit of f^g must be 1.
By they way, the paper talks about f and g being real functions. Does that mean that the theorem does not hold for complex functions?
If the complex function is analytic, I don't think there isn't anything in the theorem that prohibits it. So I think it also applies for complex analytic functions.
Note that complex differentiation is more restrictive than real differentiation, in the sense that the following are all equivalent (such a function is termed "holomorphic"):
* complex differentiable (once)
* complex differentiable infinitely many times
* complex analytic
But there are a lot of complex functions; in particular, any function that does not satisfy the Cauchy-Riemann equations is necessarily non-holomorphic. So an example where the limit is not 1 (even when the functions are continuous at z=0) should not be too hard to come up with.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
What I am trying to say, is that the measurement used to measure SE as approximately 175 is not consistent with the measurement used to measure CH as approximately 79.
----
The measurement for SE used was:
Printed the I of "It's super effective!" at frame 494554
Printed the F of "Foe DRAGONITE fainted!" at frame 494729
494729 - 494554 = 175 frames
These 175 frames consist of:
* Super effective message
* Dragonite's cry and fainting
The measurement specifically includes Dragonite's cry and fainting.
----
The measurement for CH used was:
James's Caterpie, 30 HP, non-crit Water Gun
A pressed to select move at frame 54592
F printed at frame 54837
54837 - 54592 = 245 frames
James's Caterpie, 30 HP, crit Water Gun
A pressed to select move at frame 54618
F printed at frame 54942
54942 - 54618 = 324 frames
324 - 245 = 79 frames
The 245 frames in the non-CH scenario consist of:
* "_ used Water Gun"
* The attack which brings Caterpie's HP to 0
* Caterpie's cry and fainting
The 324 frames in the CH scenario consist of:
* "_ used Water Gun"
* The attack which brings Caterpie's HP to 0
* Critical hit message
* Caterpie's cry and fainting
By subtracting them, the measurement of 79 frames is for:
* Critical hit message
By subtraction, the measurement excludes any Pokemon's cry or fainting.
----
So there is an inconsistency in measuring SE compared to measuring CH; the measurement for SE includes a Pokemon cry/fainting, while the measurement for CH does not. Just going off the video, the effect of SE alone (removing all cries and fainting from the equation) I believe is around 90 frames. A little more than CH alone, but not much more.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
UnopenedClosure wrote:
I just went back and checked in my first draft (it was easier to get to) and looked at the timings for SE and Crit+SE. It looks like the exact numbers are slightly different (I observed the exact timings of the crit and SE textboxes to vary a little bit whenever I timed them, so I should amend my writeup to say about 172/79 frames), but the basic principle that I had was correct:
Super Effective (Blizzard on Dragonite)
Printed the I of "It's super effective!" at frame 494554
Printed the F of "Foe DRAGONITE fainted!" at frame 494729
494729 - 494554 = 175 frames
Crit + Super Effective (Zap Cannon on Aerodactyl)
Printed the A of "A critical hit!" at frame 493591
Printed the I of "It's super effective!" at frame 493672
Printed the F of "Foe AERODACTYL fainted!" at frame 493847
493847 - 493591 = 256 frames
If you're timing up to "Foe DRAGONITE fainted!", then you're including Dragonite's cry in there as well. Without the cry, I think it's shorter.
Or another way to say it: If you faint the opponent with a critical hit that's normal effective, then the time between:
* Printed the A of "A critical hit!", and
* Printed the F of "Foe ____ fainted!",
would be longer than 81 frames, I think.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Looks good. However, I have a few comments:
* At 2:22:50, it looks like you bike and then pick up HM07 Waterfall, so the game waits until the music fades out. I think it's faster to run to the item and pick it up (like for the Gold Teeth at 1:22:10).
* UnopenedClosure wrote:
the Super Effective text box takes 172 frames, whereas the Critical Hit text box takes 79 frames.
It seems to me the super effective text box alone should not take 172 frames. More like 93. 172 sounds like both Crit+SE text boxes together.
* UnopenedClosure wrote:
one of four OHKO moves (which I prefer not to use here since they produce an extra text box, and because their accuracy check doesn’t seem to be manipulable)
IIRC, from my experience in Gen III, most damaging moves have their accuracy rolled right before the text box that says "____ used ____!" There are some exceptions, though.
So it is difficult to manipulate because it occurs after the roll for the move called by Metronome. However, it may be possible to interrupt it with Help Menu manipulation.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
For reference, Warp's previous post on this question.
Analytic is actually important to this question. (A function f(x) is analytic at x=c if its Taylor series at x=c is equal to f(x) on some open interval containing c. It's stronger than just being "smooth", or infinitely differentiable.)
It turns out (see this article) that if f(x) and g(x) are analytic everywhere and not the zero function, with the limit as x--->0 of both functions being 0, then the limit of f^g must be 1.
If "analytic" is replaced with "infinitely differentiable", then the statement would be false. Ex:
f(x) = exp(-1/x^4) if x≠0, 0 if x=0,
g(x) = x^2
Both f(x) and g(x) are infinitely differentiable (including at x=0), limit as x--->0 of both functions is 0 and limit of f^g is 0. Note that f(x) is not analytic at x=0: its Taylor series is 0 at x=0 (all derivatives are 0 at x=0) but f(x) is not the zero function on any open interval containing 0.
However, there aren't any convenient ways to express functions that are infinitely differentiable but not analytic without using case notation. Rather than attempt to express such a function using some form of trickery that satisfies no one, I will just leave this question as I have already answered it.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I watched this a couple of times. It is much like the SM64 A Button Challenge: A remarkable technical achievement that absolutely cannot be reduced to "let's take any game and see how few times we can press ____".
Above all: While entertainment is subjective (I would agree), I emphasize that HappyLee, Kriller37, DaSmileKat, Kosmic & periwinkle laid out clear objectives (Primary: Minimize number of A presses; Secondary: Fastest completion) and achieved this TAS accordingly. Nothing can ever take this away from them. Not any voting polls. Not any judging decisions. Not anyone who resorts to attacking the authors' objectives in an attempt to keep this TAS off the site. No matter what happens, the authors did exactly what they set out to do with no strings attached, and they ought to be proud of it.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I have no clue why this game feels the need to use 30fps flickering.
Anyway, just a warning that, if you watch the Youtube encode, you need to watch it in 720p60 or greater. If you try to watch in 30fps (like I did at first), you will have no clue what is happening.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Oh, I didn't realize DOS was the "main" version of the game. I thought NES was the main version at first. Also it somehow reminded me of Karateka, but now I know it was by the same author.
I like how when encountering guards, the Prince takes one stab each time and decides he's had enough and leaves. Anyway I'm not familiar with what is and isn't a glitch in this game so I can't really say much regarding that.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I'll comment, since I actually watched it some time ago but didn't feel the need to comment back then.
It feels at this point that anything called "Kaizo" exists only to see players suffer (on Youtube, of course), and watching Let's Plays of these hacks can be somewhat entertaining. Unfortunately, a TAS removes this very thing, leaving something which looks like a TAS of any other SMB3 hack. Can a new SMB3 hack at least have custom music? Or at least some new mechanics like Mario Adventure? And I can admit that Mario Adventure is outdated nowadays, even though it was pretty cool for its time.
Also, I personally prefer hacks that make it look like I will have fun playing it. This hack, being a Kaizo hack, does the opposite.
Acumenium wrote:
What is the criteria for voters finding it entertaining for a hack to be accepted?
The only thing that determines whether a hack is accepted (or similarly for non-hacks, what tier a movie should go into) is the judge's opinion. Nothing else.
One could even argue that voting is completely useless.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Warp wrote:
For a project I would need to solve this:
Given x and a, solve y:
tan(y) * ((1 - a*sin(y)) / (1 + a*sin(y)) ^ (a/2) = x
If it's not possible with a closed-form expression, then an approximation (eg. using Newton's method) would be fine too.
Approximation is pretty much the only way I see.
You can replace sin(y)=z to get z/sqrt(1-z^2) * (1-az)/(1+az)^(a/2) = x and we need to solve it where |z|<=1
Assuming x is positive, we can take natural log of both sides:
ln(z) - (1/2)ln(1-z^2) + ln(1-az) - (a/2)ln(1+az) = ln(x)
Then if you want to use Newton's Method (assuming a good enough first guess):
next value = z - f(z)/f'(z)
where f(z) = ln(z) - (1/2)ln(1-z^2) + ln(1-az) - (a/2)ln(1+az) - ln(x)
and f'(z) = 1/z + z/(1-z^2) - a/(1-az) - (a^2/2) 1/(1+az)
Oh, I should have known it was a Mathologer video.
Apparently it's extremely well-known as "Fitch Cheney's Five-Card Trick". Furthermore I found out that not only is it possible to do for a deck of N=124 cards (the most obvious upper bound ensuring that, for N cards, there are enough ordered 4-card combinations to encode all unordered 5-card combinations), but it's easily proven AND there is an ingenious strategy that is reasonable to perform. It goes something like this (not a complete description, just brief):
Suppose the cards are numbered 0, 1, ... , 123 and the first person is given five cards n0, n1, n2, n3, n4 (assume it's in increasing order). Compute their sum mod 5 to be j, and keep the card nj. Then, given only what the other four cards are, there are exactly 24 possible values for the fifth card (by deleting the values of the four cards from the ordering and taking every fifth number); encode nj using the four cards and pass them to the second person. Then the second person just deduces what the fifth card is, from the four cards and their order.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
NxCy wrote:
OmnipotentEntity wrote:
You can add the final bit by handing the cards either face up or face down, which is very magic-trick-like, in that there's a trick. And that gives you the exact number of bits required to specify 1 of 48 unique cards.
There is a way to always correctly determine the final card solely from the four cards that were passed and their order. There's no additional trickery involved (handing the cards face up vs face down or providing additional information by other means). I guess there are probably multiple ways to do it, but the solution I saw is quite elegant.
(This is probably why mathematicians like setting up "prisoner problems", as opposed to "magic trick problems". Honesty can be enforced in the former case. :) )
This took me a while to figure out, but here's one way that isn't complicated and works with the playing cards specifically, while eradicating any form of trickery or deception (as in, no communication is allowed except to the extent spelled out by the given rules):
Out of 5 cards, there are at least two cards which are the same suit. Taking the ranks as the cycle A-2-3-4-5-6-7-8-9-10-J-Q-K-A-2-3-... , of two cards of the same suit, one of the cards is 6 or less steps ahead of the other in the cycle. So the strategy could be as follows:
First person: Out of the 5 cards given, take any two cards of the same suit. Keep the card which is n<=6 steps ahead of the other, and place the other card 1st in the set of four. Order the remaining three cards based on contract bridge: ranks from highest to lowest (A-K-Q-J-10-9-...-2) and if ranks are tied, suits from highest to lowest (spades-hearts-diamonds-clubs). Then arrange these cards in the 2nd to 4th slots indicating n as a lexicographic order:
low-mid-high: n=1
low-high-mid: n=2
mid-low-high: n=3
mid-high-low: n=4
high-low-mid: n=5
high-mid-low: n=6
Pass these cards to the second person.
Second person: Given the four cards, the card in the 1st slot indicates that the card kept by the first person is the same suit and 1-6 steps ahead in the cycle. The number of steps ahead is determined by the arrangements of cards in the 2nd to 4th slots above. Using this, the second person can determine the card held by the first person.
This is probably not optimal, in the sense that N=52 is not the highest number of cards for which there is a strategy that works. The optimal number is probably somewhat higher, but the strategy would be too complicated for a normal person to remember and it would take computation to figure out; it's similar to solving a covering problem.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
Evaluate
I knew it was similar to a question almost two years ago about sums of fourth powers of degree-3 algebraic conjugates.
(Well, not exactly. And I read NxCy's post first.)
Anyway, with a method of solution similar to what I did back then, it's possible to do without going past degree 3:
First of all, tan4(5pi/18)=tan4(13pi/18), so it is the same as evaluating tan4(pi/18)+tan4(7pi/18)+tan4(13pi/18).
Let a=tan(pi/18), b=tan(7pi/18) and c=tan(13pi/18). As NxCy stated above, if tan(x)=t, then tan(3x)= (3t - t3)/(1 - 3t2). Now, no matter whether we put x=pi/18 or 7pi/18 or 13pi/18, that gives us tan(3x)=1/sqrt(3), and so a,b,c satisfy the polynomial t3 - sqrt(3)t2 - 3t + sqrt(3)/3 = 0.
Since (t-a)(t-b)(t-c) = t3 - (a+b+c)t2 + (ab+bc+ac)t - abc which must be the same as t3 - sqrt(3)t2 - 3t + sqrt(3)/3, this gives a+b+c=sqrt(3) and ab+bc+ac=-3. So a2+b2+c2 = (a+b+c)2-2(ab+bc+ac) = 3-2(-3) = 9.
Finally, if we define f(n)=an+bn+cn, then f(n) is the solution to a recursive formula with characteristic polynomial t3 - sqrt(3)t2 - 3t + sqrt(3)/3 with the initial conditions f(0)=3, f(1)=sqrt(3), f(2)=9. That is: f(n) = sqrt(3)f(n-1) + 3f(n-2) - (sqrt(3)/3)f(n-3). This formula gives f(3) = sqrt(3)*9 + 3*sqrt(3) - sqrt(3) = 11*sqrt(3), and f(4) = sqrt(3)*11*sqrt(3) + 3*9 - (sqrt(3)/3)*sqrt(3) = 33 + 27 - 1 = 59. So the answer is 59.
Note that technically a,b,c aren't degree 3; the polynomial I gave doesn't have rational coefficients. Actually they're degree 6 and the conjugates include all tan(n*pi/18) with n=1,5,7,11,13,17.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Masterjun wrote:
I actually took a significant time thinking about the branch name.
Didn't know that. I thought you only took like 10 seconds which is what most submitters spend thinking about their AFD submissions, including me. So I also gave my 10-second thought on it.
Not that it matters now, but I have to admit that I initially didn't understand what this submission was about, even after reading the branch name and the first paragraph, and looking at the Youtube screenshot. Only when I got to "it just repeats the same 2-minute input over and over again" in the second paragraph did I understand.
I think any branch name short of "repeats the same input over and over in an infinite loop" can't immediately describe what kind of TAS this is, but I think that's the job of the submission text, not the branch name (though it's AFD so who really cares). However, I think at the time I would have found "infinite input loop" to be a bit more understandable than "repeated input".
By the way, this isn't the first AFD submission to involve infinite loop of inputs:
adelikat's FDS Super Mario Bros. 2 in ∞
If only the BizHawk team didn't get rid of the feature, it could have been possible to render the movie as being ∞ long. Mostly for fun though.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
Now we set up a contour to evaluate the integral. The contour goes from -infinity to +infinity at the line Im(z)=0 (A), and from +infinity to -infinity at the line Im(z)=2pi/c (B).
It sounds like the left and right sides of your contour are missing. I'm thinking of a rectangle like this, as t goes to infinity:
* On the left side, |ez/(1+ecz)| ≤ e-t/(1-e-ct) which approaches 0/(1-0) = 0, and so the integral (which is finite-length) approaches 0.
* On the right side, |ez/(1+ecz)| ≤ et/(ect-1) which, after using L'Hopital's Rule, approaches limit of e(1-c)t/c, which goes to 0 since c>1, and so the integral (which is finite-length) approaches 0.
The last point is important because, without it, nothing in the argument prevents it from working for (almost) all c, so you would end up with wrong conclusions like: when c=2/3, the integral is -3pi/2 (in fact, when c=2/3, the integral diverges to infinity).
I noticed that your substitution rewrites the function to avoid having any branch cuts. I did the contour integral differently, using the original function without substitution, but having a branch cut where the argument of the complex number is a negative number arbitrarily close to 0 (as shown in blue below). So it looks something like this, as r goes to 0 and R goes to infinity (here I used c=sqrt(21) to generate the poles, but it works in general for any c>1):
However, I am not aware of a way to do this without using contour integrals (and without using the beta function). I asked this question partly because I was wondering whether anyone had a way to evaluate this without using complex numbers or any of the non-elementary functions.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
Prove that no right triangle with integer side lengths can have a leg whose length is a multiple of the other.
Curiously, there is a proof involving only geometric construction.
HINT: Take the proposed triangle and fold the larger leg into the hypotenuse, one of the triangles created is similar to the larger one. What's going on with it?
I didn't expect something like this would have a geometric construction (it's obvious algebraically). But after seeing your hint, I can actually see now what it's like:
Here we have the triangle ABC with the hypotenuse horizontal. B is folded down onto the point D as shown, and it can be seen that ADE is similar to ABC.
Assume that ABC satisfies the property (AB, BC and AC are integers, with BC a multiple of AB).
BC=DC, so AD = BC-DC is an integer. By similarity, DE is a multiple of AD, and so DE is an integer. Also, BE=DE, so AE = AB-DE is an integer. So ADE is a smaller triangle satisfying the property. By infinite descent, this gives us an absurdity.
----
Here's a question that I was thinking some time ago but didn't post until now.
Let c be any real number greater than 1. Prove the following integral:
Ex: For c=2, the LHS is just the limit of tan-1(x) as x goes to infinity. That is pi/2, which is what the RHS works out to be. But how do we do the other values of c?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I'd personally write the branch name as "11-fold canon" rather than "repeated input", but that's just me.
Masterjun wrote:
SMW has quite a big number of framerules everywhere. It was practically impossible to know each of the 11 framecounter values I will end up with, before even starting the TAS. So if you just play back the inputs in an emulator, it won't sync. What is mostly needed for it to sync is adjusting the global framecounter (RAM address $0013) once at each syncpoint.
I knew it was too good to be true.
Figures no one is insane enough to actually do it for real, with 11 instances and everything. I would guess it may be possible on a game that is easier to edit input. SMB is the first one that comes to mind.
* On the left side, |ez/(1+ecz)| ≤ e-t/(1-e-ct) which approaches 0/(1-0) = 0, and so the integral (which is finite-length) approaches 0.
* On the right side, |ez/(1+ecz)| ≤ et/(ect-1) which, after using L'Hopital's Rule, approaches limit of e(1-c)t/c, which goes to 0 since c>1, and so the integral (which is finite-length) approaches 0.
The last point is important because, without it, nothing in the argument prevents it from working for (almost) all c, so you would end up with wrong conclusions like: when c=2/3, the integral is -3pi/2 (in fact, when c=2/3, the integral diverges to infinity).
I noticed that your substitution rewrites the function to avoid having any branch cuts. I did the contour integral differently, using the original function without substitution, but having a branch cut where the argument of the complex number is a negative number arbitrarily close to 0 (as shown in blue below). So it looks something like this, as r goes to 0 and R goes to infinity (here I used c=sqrt(21) to generate the poles, but it works in general for any c>1):
However, I am not aware of a way to do this without using contour integrals (and without using the beta function). I asked this question partly because I was wondering whether anyone had a way to evaluate this without using complex numbers or any of the non-elementary functions.
Here we have the triangle ABC with the hypotenuse horizontal. B is folded down onto the point D as shown, and it can be seen that ADE is similar to ABC.
Assume that ABC satisfies the property (AB, BC and AC are integers, with BC a multiple of AB).
BC=DC, so AD = BC-DC is an integer. By similarity, DE is a multiple of AD, and so DE is an integer. Also, BE=DE, so AE = AB-DE is an integer. So ADE is a smaller triangle satisfying the property. By infinite descent, this gives us an absurdity.
----
Here's a question that I was thinking some time ago but didn't post until now.
Let c be any real number greater than 1. Prove the following integral:
Ex: For c=2, the LHS is just the limit of tan-1(x) as x goes to infinity. That is pi/2, which is what the RHS works out to be. But how do we do the other values of c?