[emulator accuracy] If we're saying the gap here is miniscule, and that's why we're offering the exception here, then the exception must be a blanket exception[..]
This seems like a once-in-a-lifetime opportunity to get to know moozooh in exchange for a couch. Not sure yet if I actually want to take it (or how my wife feels about offering couches to internet strangers (or if moozooh even remembers me (and if so, if he'd rather avoid me))).
Did you plan to visit Evoke's opening ceremony, or just saturday/sunday? I might offer a couch from friday to saturday, then go to evoke with you for saturday. I live about 3-4 train-hours away from Köln though, so we'd have to get up early and I'd probably leave during the animation compo.
If you insist, I can also mug you in your sleep.
not to mention the idea of coming back to this game for the first time in eight years seemed like a great nostalgia trip.
nostalgia trip indeed. Has it really been eight years?
I can't believe I missed this submission; maybe I need to lurk more frequently. Thanks tem, for another hour of my life well wasted. I thought your any% run was well broken, but this is just so much worse. There's a certain level of satisfaction in seeing those nasty timewasting traps being utterly ignored.
Interesting glitch! Makes me wonder what made the SM devs use the same memory location for two different variables, and what they named said variable in their source code.. from what I understand, SM doesn't come close to using all the SNES's memory, so why would they bother saving mere 2 bytes by reusing variables?
From a technical point of view, what happens here is a lot less glitchy than, say, firing any spazer/plasma-combination, but the effects on the run are obviously more extensive than a laggy MB fight. Then again, the effects on the route and gameplay are less extensive than, say, mockball.
One more (unsolicited) thought. When going for a category with a special goal (like low% or 100%), how strict should one be about reaching that goal? If one uses a glitch to manipulate the item counter to say "100%" without picking up every single item, has the 100% goal been achieved? Similarly, if one uses a glitch to effectively acquire missile expansions beyond those that were picked up and counted, is the resulting run 14% or 26224%?
Categories aside, it certainly was an interesting run. Thanks to sniq and everyone else involved!
It's somewhat of a misconception that the singularity is this infinitesimal point with infinite density. In mathematics, the term "singularity" is really synonymous with "undefined" - ie we don't know what happens at the singularity.
Alright, strike the "infinitely-dense object" from my initial post and replace it with "singularity". Both my questions still stand. GR has been shown to be inaccurate/incomplete at small scales anyway, so if the formulas can't make predictions, why is that even a big deal? Possibly even a bigger deal than the places where it does make predictions, and those predictions are known to be wrong? Why is there so much research into singularities, their influence on the universe, their nakedness etc when we shouldn't even trust the premise?
Except is has already been contradicted, by this other well proven theory called QM. We know both GR and QM to be mostly true in their domains, but we also know both to be inaccurate in corner cases, and at least one of them must be wrong about the center of black holes.
GR says that everything inside the event horizon must fall towards the singularity, hawking radiation says that it eventually manages to escape anyway.
GR says that there's a point of infinite density at the center, while heisenberg objects to particles existing at a precisely defined location (inside the point-like singularity) with a precisely defined momentum (zero).
Now two well-respected and well-proven theories disagree. Since this is a corner case for both GR (small scale) and QM (lots of gravity), I wouldn't trust either. If I had to pick a side, I'd notice that neither singularities nor hawking radiation have been observed, but the uncertainty principle has, so my money is on "no singularity". However, everyone else seems to disagree.
hi,
I know we have a few actual physicists in here, so let me ask this to an audience smarter than google:
By interpolating the formulas of relativity in certain situations, we arrive at a mathematical singularity. This has lead many popular physicists to postulate that there must be a physical representation of that mathematical singularity, a physical singularity, which is worth researching. To this day, singularities and black holes seem to be one of the most popular topics in physics forums and blogs. People just love to talk about them, about possibilities, hypothesises, interpretations and the stance on nudity of a yet unobserved object. Any wikipedia article on the subject talks about the singularity at the center of the black hole as if it was a scientific fact.
What I don't see is anyone acknowledging that an infinitely-dense object is in fact very very small, and it's been known for over a century that you don't trust relativity at those scales. Meanwhile, QM continues to shrug its shoulders and asks: "Uhhm, what's gravity?".
So my two questions..
* Am I wrong to be sceptical about any work on physical singularities until and unless we have a theory that both predicts singularities and is valid at the relevant scales? Why is the answer about the center of a black hole still "a scary singularity" instead of "we don't know, but there's no reason to panic yet"? Is it just because it makes for interesting discussion and sci-fi, or is there a good scientific reason for that?
* Have there been actual results from applying QM to situations where relativity predicts a singularity? Every now and then I catch an article claiming some breakthrough, but I lack the background to even understand the papers the articles are referencing, much less to figure out if they're valid or not.
So you want something similar to the windows magnifier, that upscales a portion of your screen, but with a special upscaling filter? Thanks to the magic of modern composited desktops, such a solution should be possible to implement without adding a frame of latency.
Google suggest there are open source implementations of similar tools, e.g. http://magnifier.sourceforge.net/ - could be used as a starting point, but obviously requires more coding.
This seems like a good thread to remind everyone about the presentations from cppcon2014, which are available on their youtube channel.
I highly suggest these four, but browse the channel for any other specific topic that might be relevant to you.
Scott Meyers, Type Deduction and Why You Care, video
Pretty dry topic, but important nonetheless. From the author of "Effective Modern C++", so skip this if you bought the book. Or skip the chapter and watch the video.
Herb Sutter, Back to the Basics! Essentials of Modern C++ Style, video
Several widespread design choices have been revisited for C++11/14. If you're using the newest standard, watch this to avoid writing "legacy style" code.
Walter E. Brown, Modern Template Metaprogramming, part 1, part 2
Very advanced stuff, but also very very useful for the few times when you really need it.
Andrei Alexandrescu, Optimization Tips - Mo' Hustle Mo' Problems, video
If you need a reminder how very small code changes can have large impacts on your code base's performance. Andrej is from facebook, so they have both a very large codebase and a server farm large enough that even tiny performance regressions can cost a lot in server and power costs.
Okay, fair enough. Though to be pedantic, in an infinite multiverse, somewhere there's a console that had the right combination of ionizing radiation strikes to initialize the RAM to the desired pattern. This is so far beyond "astronomically unlikely" as to be a complete joke, but infinite multiverses are weird that way.
There's also a universe where - right at the beginning of every boss fight - ionizing radiation strikes and changes the memory cell containing the bosses' HP value to 0. Let's allow gameshark codes!
Nach wrote:
If you can't prove that your precise selected combination of start up RAM choice is a valid one, I say reject it.
Just out of curiosity, has this been proven for the default state of the accepted emulators?
It's been a slow evening, so I wrote a small C program to simulate a turing machine.
It simulates the current busiest beaver with 5 states, which terminates after 47.176.869 steps.
#define S 5
#define TAPESIZE 0xffffffff
#include <cstdio>
typedef long long int LONG;
char nextstate[S][2] = {
{ 'B', 'C' },
{ 'C', 'B' },
{ 'D', 'E' },
{ 'A', 'D' },
{ 'H', 'A' }
};
bool symbol[S][2] = {
{ 1, 1 },
{ 1, 1 },
{ 1, 0 },
{ 1, 1 },
{ 1, 0 }
};
char movement[S][2] = {
{ +1, -1 },
{ +1, +1 },
{ +1, -1 },
{ -1, -1 },
{ +1, -1 }
};
int main() {
LONG position = 0;
char state = 0;
bool *tape = new bool[TAPESIZE]; // interleaved: 0, -1, 1, -2, 2, ...
size_t i=0;
while (true) {
LONG idx = position >= 0 ? 2 * position : -2 * position - 1;
if (idx > TAPESIZE) {
printf("Machine exceeded tape size at step %lu\n", i);
return 5;
}
bool read = tape[idx];
tape[idx] = symbol[state][read];
position += movement[state][read];
char s = nextstate[state][read];
if (s == 'H') {
printf("Terminated after %lu steps\n", i);
return 0;
}
state = s - 'A';
i++;
}
}
If we output a '9' each iteration, our output number would thus be 1047.176.869-1.
It is well below 1000 chars, so we can change the TM to a 6-state machine without problems. The busiest beaver with 6 states iterates more than 7.4 × 1036534 times. If you output a digit each step, then the result will not fit into the observable universe, which only has somewhere in the ballpark of 1080 particles. Of course, neither will the virtual tape - and I've yet to see a C++ compiler supporting 64KB pointer arithmetics.
Now feel free to obfuscate the code and figure out how much room is left to define the TM. How many states can we support? How big do you need the output number to be?
Bobo the King wrote:
To throw out a guess, perhaps one million or so digits.
It's also important that the halting program involves input, which this problem does not. That means the "problem space" is finite (all C++ programs with 1000 char length), rather than infinite(all C++ programs with 1000 char length * all possible input).
And yet, deciding whether a program terminates can be very difficult even for a fixed program with fixed input.
OmnipotentEntity has finally linked the very relevant busy beaver numbers. Read that article! Read it again!
It's important to note that even with extensive research, the exact value of BB(5) is not known - that is, even for turing machines with exactly 5 states and no input, we have not managed to determine for all of them whether they terminate.
Considering how fast BB numbers grow, for a 1000 char C++ program, I'm pretty sure the largest possible output is so large that it is impossible to contain its decimal representation within the observable universe.
There doesn't seem to be a good way to get money from Germany to the US.
* amazon gift cards purchased on amazon.de cannot be redeemed on amazon.com. I cannot purchase a gift card directly at amazon.com without a credit card, which I don't have.
* direct deposits outside the european union require a personal trip to the bank, a full-page form to fill out and incur fees that are unreasonably large even for such a manual process.
* I have avoided entering a business relationship with the crooks of a certain payment company, and that's not going to change.
* I don't have bitcoins.
sorry :(
It is worth noticing that time is not quite the same as the other spacetime dimensions for one reason - you can not travel backwards in time (in special relativity anyway).
How do you even define "traveling in time"? Movement is a change of position over time, so how does that work when you're talking about the position in the time dimension?
p4wn3r wrote:
If someone asks you "Do ghost particles exist? Yes or No?", what's your answer and why?
I don't read that question as a question about ghost particles, since the answer would not yield a better understanding of ghost particles, nor would it predict any new testable properties.
Instead, I read that question as a philosophical question about the concept of "existence": How do we define existence in such a way that the concept is useful even in weird corner cases like these? Cases that were unthinkable back when humankind first discovered the concept of existence, when existence were just the things we could see or touch?
Since this is a philosophical question, I refuse to attempt an answer.
Of course the scientific question is: "Does this set of formulas, which includes unobservable particles, accurately describe the experimental results we obtained?"
Same for warp's question. We all agree that time exist. Great. We also agree that formulas using a four-dimensional spacetime agree with experimental results and are thus a good model for the world we live in. Also great.
Does that mean that we can split our formulas into small parts, and for each part find a direct physical representation in the real world? Well.. try hitting the universe with a hammer until it breaks, sift through the pieces until you find time and ghost particles, then look at them in isolation. If you can't, you'll have a hard time answering the original question.
What you can ask is: "does time as it exists in the universe have dimension-like properties?". Considering that the simplest way to model time is as a dimension, I think you can answer that.
Oh, and don't forget that Novikov's self-consistency conjecture is just that: a conjecture, a sentence starting with "Wouldn't it be nice if ...?" Of course paradoxes are a problem, but they don't go away if you claim they don't exist, no matter how reasonable the conjecture sounds.
Warp wrote:
If this were to happen in real life, I don't even dare to guess what happens if a particle collides with itself. At the very least it ought to cause some kind of paradox.
Just to be clear, particles don't have a unique identity, so from the particle's point of view, it doesn't collide with itself, but just with another particle of the same kind. The SciFi-notion that terrible things happen if you see or touch your past self, but you're safe as long as you're just blindfolded in the same room, those are just SciFi.
The paradox would only arise from the causality loop, but that doesn't require both particles to be the same. Particle A could emit a photon B which [ travels around the black hole / falls into the worm hole / jumps into the Tardis ], thus arriving in A's past and hitting it.
Is not being able to alter the stats of all the enemies, how many spawn, items, etc... not enough? You can arbitrarily change those things as long as it doesn't fail any constraints.
[..]If you cannot do turing complete computations, you haven't been executing code.
lol, I even doubt whether you know what is "turing complete computations".
You can run "turing complete computation" in SQL.
Thanks for your condescending tone. Since you seem to have trouble with reading comprehension, I've readded a bit of context above. If you'd kindly reread it, you'd notice that I wasn't talking about SQL, but about the ability to alter game values - and that alone is not turing complete.
That being said, SQL92 is NOT turing complete. Several database vendors support extensions (like stored procedures) that make it turing complete, but that's not true for every SQL implementation. For a simple embedded SQL implementation in a game engine, I'd assume it to not be turing complete unless stated otherwise.
Anyway, simulating a turing machine inside the game is different from taking control over the game. There are also videos of people simulating turing machines using minecraft blocks and triggers. While awesome, I think that simulating a turing machine within the game is different from gaining control over the turing machine that's running the game. The latter is what we know as ACE runs, the first one is different enough that it'd deserve its own name.
Ok, I'll give you that running code inside a restricted environment can be a good challenge and may be fun to watch. And if the intended exploit is kept hidden enough, it may surprise a couple of viewers.
One of the questions every ACE run must answer is the following: does the run benefit from using the initial game as a vehicle?
Glitching a game with clever tricks can usually give a positive answer here: the breaking of the game is interesting to watch.
Watching frantic typing in Visual Basic before starting a nice demo is a negative; the parts before executing the payload aren't interesting; one should instead TAS the resulting executable directly.
Running code in a name input screen isn't really impressive when you know there's an intentional loophole in there. I can also run arbitrary code in Word by doing File -> Open -> navigate to Visual Basic -> right click the executable -> open -> enter code -> run. That'd certainly surprise some viewers ("Wait, you can right click?"), but when you know the trick, it's not impressive at all.
A great TAS will stay impressive even when the viewer knows how it's done. Finding out that a loophole was intentional usually diminishes that (not unlike finding out that an impressive run used cheat codes or easy mode), thus raising doubts whether the chosen vehicle adds enough to the run to be worthwhile. I concede that ACE runs using intentional glitches can be publishable, but they'd have to be held to higher standards to make up for that flaw.
/edit: y'all will have to agree with me, since this is my post number 1337 o_O
Is not being able to alter the stats of all the enemies, how many spawn, items, etc... not enough? You can arbitrarily change those things as long as it doesn't fail any constraints.
That's arbitrary memory manipulation, not arbitrary code execution. I'm not sure where "code execution" is unclear. If you cannot do turing complete computations, you haven't been executing code.
Nach wrote:
Why does it have to be machine code? What if a game in an interpretive language, and you can inject code in said language?
There's the grey area. We need to make a distinction between the application that's running, and the computing platform the game is running on. For the SNES, the platform is easy to determine: it's the hardware. For a PC, the platform could be the hardware. Or maybe just an OS. Or the browser. Flash. The Unreal engine. Whatever.
The existing ACE TASes gain full control over anything running on the platform, but do not change the platform (since it's hardware). I think the same distinction is useful for software platforms, too.
My personal criterion for "arbitrary" would be: can you use it to replace the game with SMB1, Tetris or any other game available on the platform? If you can't, it's not arbitrary enough.
To do so, you must exercise enough control over the platform to
stop the previously running game from executing
execute your own turing complete computations
load or create new game assets, including images and sounds
have full access to the platform's inputs (gamepad, keyboard, mouse, ...) to load new data
have full access to the plaform's outputs, usually video and sound
So for a HTML5 game, executing arbitrary JS should suffice: from there, you can replace the DOM, remove all existing code, listeners and timers, load new images and audio from data:// URLs and start a new game. You would not need to escape the javascript sandbox, the browser's sandbox, the OSs sandbox and then reboot into a hurd kernel. (Bonus points if you can though!)
Now you're asking: can your game engine qualify as a "computing platform" with the SQL accessible data being the "game"? I doubt it. From the way you describe it, the game inside the engine is modeled using declarative data, not code, so it's not a computing platform one can run applications on. If the "platform" is too weak to run any code, it's certainly unfit to run "arbitrary code".
Remember: if you're first looking at the things you can control, and then define the "platform" and "game" in such a way that the latter coincides with the things you control, then you might be stretching the terms.
Nach wrote:
Also, does it have to be an unintended exploit?
Finding and showcasing unintended exploits is a big part of the fascination of the category. Otherwise, it's no different than programming your own executable and running that, and I think we already have a demo scene for that.
I won't argue whether or not we could still call it ACE, I'm just saying that it wouldn't be publisheable here if it didn't feature a huge exploit. The movies we have all feature a central element: the ability to surprise the viewer. Typing something into visualbasic and then *gasp* running the code? Not very surprising, not interesting, nothing this site would care about.
The problem with the Amiga is a different one. UAE already supports savestates, and some of the runs on the (now inactive) recordedamigagames.org were using some kind of tool assistance.
But most amiga games have some kind of copy protection. Usually invalid sectors on the disks that return different data each time they're read. So, game dumps come in two flavors:
* .adf images. They just store the data of reading each sector once, and will thus fail to boot copy protected games. Most games distributed by .adf are cracked, i.e. have the copy protection removed. Tasvideos.org does not accept run on modified games.
* .ipf images. This stores the results of reading the disk several times, but it's a proprietary, closed source format made by the Software preservation society. As far as I know, it is not deterministic and cannot be used in a rerecording emulator. Not to mention that we couldn't claim that everyone dumped the original disks themselves: the tool to dump disks in this format isn't public.
Thus, while it should be possible to add rerecording to UAE, the list of games we could actually TAS would be minimal.
The easiest way to list the games would be to modify the emulator to keep track of initialization, similar to valgrind. For older consoles (NES/SNES), the overhead should be manageable.
Patashu wrote:
And if it's really a 1/256 chance, couldn't someone dedicated enough on console get this to happen?
The 1/256 chance is only true if we assume that every bit has a 50/50 chance to be 1 or 0 before initialization. Due to slight differences in hardware, that's rarely the case. If you want to do it from power-on, your best bet is to buy 256 NESs and hope that one of them favours the 0x80 value you need.
It'd be easier to play a different cart, play it a while in the hopes that it sets the correct value, switch to SMB and do a soft reset. Pick a game that uses the same memory address for a known and manipulateable purpose and you're good to go.
While I understand the academic interest in reducing the kill-counter, the resulting run felt pretty boring.
There's a lot of slow movement, evading enemies, there's a lot of backtracking, and when a boss comes around, the best you can hope for is a clever skip that doesn't take a full minute of heart-refreshing. Those that are fought look unimpressive due to the requirements of revenge-teching.
And then he takes a long detour just to kill that poor defenseless plant and OMG HOW IS THAT PACIFIST?
Choosing good secondary goals to make a run more interesting is more of an art than a science, and it's always influenced by the viewer's taste and the target audience (e.g. hardcore fans vs. casual viewers).
But there are two properties that I'd consider universally bad:
* Instead of choosing a goal, choosing to satisfy a broken ingame counter of that goal, thus sidestepping the actual goal.
* Choosing a goal that is invisible to the player, like a counter in a menu that's never accessed.
Aiming for a kill counter of 0 was a great vehicle for the sotn community to research glitches and break the game in new ways. But showing off that it can be done does not require a TAS; and a TAS cannot show off the true potential of tool assistance when being restricted by this particular goal.
Voting no due to dullness. I think it's a good thing to have this submission, since 0-kill-runs are a part of sotn research history, but I consider the run too dull to be frontpage-worthy, and too confusing in its goals for casual viewers.
Depending on what you allow as a "formal system", there's always one where the number is definable.
Well, the formal system itself must be definable with a finite amount of information (or else it's not definable in practice; we cannot read an infinite definition in order to know all of its axioms. A formal system with an infinite definition would not be very useful.)
Sound reasonable. But to define a formal system with a finite string, you need - guess what? - another formal system to describe it in. You can happily construct an infinite formal turtle tower, but in the end, you have to start *somewhere*, and the very first formal system you use cannot be restricted in the way you like.
And depending on the initial formal system (and the amount of recursion you did), you get a different set of definable numbers.
Warp wrote:
Thus couldn't we define our set as "all the real numbers definable by a finite statement in any possible (finite) formal system"?
no, see above. Since "finite formal system" is ill-defined, so is the set.
Warp wrote:
There have to be some numbers that are impossible to define using a finite amount of information.
"finite amount of information" is another one of those intuitive things that translate poorly to mathematical definitions.
If you're a constructivist/finitist/intuitionist/whatever (and there are many examples of excellent mathematicians who subscribe to these views), you'd simply think that uncountable sets are bullshit and people should try to redefine analysis in a way that doesn't create a jungle of undefinable entities.
Makes me wonder.. did anyone even come close to that goal? To avoid undefinable entities, one would not only need to restrict analysis to contain only a countable number of numbers, one would also need to restrict analysis to allow only a countable number of statements. That seems.. very limited; possibly useless.
Language theory, for example, works on strictly countable objects: sets of words over a finite alphabet. Still, most properties of languages are undefinable and/or undecidable simply because the amount of properties of languages is larger than the (countable) amount of automatons we can construct to decide them. I cannot imagine a theory of analysis that doesn't inevitably run into the same problem.
Warp wrote:
Let's define a subset of the real numbers which consists of all numbers that are expressible with a finite definition. I understand that this is (most probably) an ill-defined set, but let's just assume that it can be well-defined, just for the sake of argument.
Read rhebus's post again. It's well-defined only for a given "language" or "formal system" that gives meaning to the definition. That's not just an addendum for formal correctness; it's a very important point.
Warp wrote:
The rest of the real numbers, thus, cannot be expressed with any finite expression whatsoever.
Read rhebus's post again. They cannot be expressed with any finite expression in the previously specified formal system. Depending on what you allow as a "formal system", there's always one where the number is definable.
Warp wrote:
Those numbers cannot be the answer to any problem (because, by definition, any number that's the answer to a problem is defined by a finite statement, ie. the problem itself, and thus belongs to the countable set defined above.) If those numbers cannot be the answer to any problem, and they cannot be expressed in any way, what's their use?
No single number in this set can be the answer to a problem formulated in the formal system used. You might find problems where the answer is a subset of these numbers, or the whole set. You might find statements in a different formal system that apply, like "any number with property X (as defined by formal system A) is undefinable in formal system B". I'm sure you've seen proofs that the set of decimal representations of prime numbers cannot be decided by a regular language, and you know why these proofs are useful.
Warp wrote:
Do they even "exist" (by some definition of "exist")?
While we cannot define each of these numbers individually, we can define sets of these numbers. p4wn3r has just defined the set of all reals in a simple, finite way. If you tie "existence" to definability, they still exist.
The compliment X'={-1,1} is a finite set, thus closed by question (b). This means our set X is open.
Careful. The definition allows for a set to be open, closed, both or neither.
By question b, we know that {-1,1} is not open, but we cannot assume it to be closed unless we first prove that the complement is open.
p4wn3r wrote:
So, did you like the topological proof of the infinitude of primes? :)
