Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
MESHUGGAH wrote:
Well, looks like this port is very bad compared to the original one. I assumed that the number of tiles are not maximized. In this port, after tile 2048, the tile just disappears (?), so I don't know what's the point of continueing the game.
The tile does kind of exist as "4096", but without any graphic so it is invisible (but sometimes it glitches and shows some other number).
In fact, after testing by poking values into RAM (the board is represented by addresses 0xA54 to 0xA72, 2 bytes each, specifying the value of the tile), you can get "higher tiles" like 8192, 16384 and 32768, and the game will add the correct score. However, combining two 32768 tiles will cause them to disappear entirely and be replaced with a "no tile" in that position. This means the game can go on forever.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
WarHippy wrote:
Hey there. So, while watching the video I felt that something was off about the statue fight. After messing around with it for a bit I managed to save 1 frame on the fight and then another 1 frame on exiting the room. And then I saved 2 more frames from lag management in the next room.
https://tasvideos.org/UserFiles/Info/637843332967811119
It's such a small improvement that I don't think co-authorship is warranted. I just want what's best for the tas : )
Nice, I didn't think at first anyone would have tried to improve this TAS.
I'm all right with having this updated with WarHippy's latest improvement, and adding WarHippy as a co-author.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I am not familiar, but it sounds like you are describing sports betting. I'm sure there are at least a thousand articles out there that you can find.
That's all I can really say about it.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Patashu wrote:
Now, obviously you have to decide for yourself what 'symbols' means, but after doing that, what's the best you can come up with?
Assuming that we are using only elementary operations (addition, subtraction, multiplication, division, exponentiation, root) and elementary functions (e^, log(), ln(), abs(), and all trig and inverse trig functions):
The operation I could find that produces a large number of operations in its derivative is the f(x)-th root of x (that is, x^(1/f(x)), considered as a single operation joined to the function f(x), which has some number of operations itself).
By taking the derivative of x^(1/f(x)), we get x^(1/f(x)) * [f(x)/x - ln(x)*f'(x)] / (f(x))^2. That's three f(x)'s and an f'(x) in the formula, which gives rise to a lot of operations.
Let fn(x) be the nth iteration of rooting: that is, f1(x)=x and fn(x)=x^(1/fn-1(x)). In proper math notation, it will look like this (I had to use Paint because even LaTeX can't generate this properly):
Let c(n) be the count function of operations of the derivative of fn(x). Then c(1)=1, c(2)=7, and
c(n) = n+1+(n-1)+1+3+c(n-1)+n = 3n+4+c(n-1) (assuming I counted operations correctly)
or, in other words, the recursion c(n) - c(n-1) = 3n+4 for all n>=3. Solving this gives a quadratic 1.5n^2+5.5n+C, and with the value c(2)=7, we get c(n)=1.5n^2+5.5n-10 for all n>=2. (Note that as an exception, c(1) doesn't follow this rule because f(2)'s derivative can be simplified to reduce the number of operations, resulting in c(2)=7.)
So this gives quadratic growth with a coefficient of 1.5, the best I can find.
NOTE: The operations f(x)^x ("f(x) to the x") and f(x)^(1/x) ("f(x) root x") also generate three f(x)'s and an f'(x) in their derivatives, but unfortunately their iterations are easily simplified. This disqualifies both of them.
Edit: Added "the derivative of" in there. We're obviously taking the number of operations of the derivative of fn(x), not fn(x) itself.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
MESHUGGAH wrote:
FractalFusion wrote:
So if you really want something like a max score / max move TAS on a faithful port that is also manipulatable, I'm not actually sure if such a thing exists out there.
The original 2048 game is manipulatable (well... I mean there is randomness) and can go over the first 2048 tile.
edit: and the android port does the same.
By "manipulatable", I mean in the sense that the tile values can be manipulated at will so you can get, for example, all 2s, or all 4s. (There was talk earlier about manipulating the minimum 519 moves, which requires all 4s.) This is really what is meant, when we talk about extreme goals such as max score / max move / min move / etc.
As far as I know, there is no evidence that the original 2048 game, or its most faithful ports, can be manipulated to do such a thing.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I liked this. But the length of this TAS combined with how much is going on during the TAS means it is best watched in "episodes" over a few days.
A 30-minute version of the glitchfest is fine as well.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I mentioned in a previous post in the Rockman 2 Basic Master thread that Rockman 6 UH (this hack) is one of the better post-RM4MI hacks out there. Glad to see this TAS does not disappoint; I found it entertaining, with multiple weapon/equipment usage to get through the stages quickly.
I also like the different theming for each level, including the Sonic the Hedgehog stage and the third fortress boss Estark from Dragon Quest. The Pokemon boss from Rockman 2 Basic Master wasn't the first time something like this was done!.
Also, instant weapon switching is a must for hacks.
So, you see, I was just about to save Atrus and everything with this page I found.
But then I rolled a natural 1, and this just happened...
This is my favorite Myst TAS now just for how funny it is. (Judging from the music change there, you even fooled the game for a split second.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
So, I searched the site for "Playground", yet it seems there is still no official stance on what kinds of submissions and/or goals qualify for Playground that I can find.
Is there a specific list of goals that are acceptable to qualify a submission for Playground? Is there a specific list of goals that are NOT acceptable? Will this be determined by the discretion of a Judge and/or by community? If the goal exists on speedrun.com, would it be acceptable for Playground here? I was wondering whether things like that have already been decided.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Since you never use Super Sonic for anything useful, wouldn't it be better to get Chaos Emeralds in other Zones where convenient, instead of trying to get everything in Emerald Zone (having to backtrack extensively for rings in the process)?
I also noticed you only manipulated the trapped animals at the end of zones only once. The published movie does this many times.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
This week's Riddler classic is a pretty standard number theory problem. Find a six digit Carmichael number which can be written as ABCABC in base 10. As the Riddler notes, try to solve without writing a brute force code, you learn a lot of number theory doing this.
As usual, I will verify all possibilities, as in: "find all possible six digit ABCABC..." as opposed to "find any one six digit ABCABC...". (Intuitively, ABC is most likely to work when it is a prime that is one more than a factor of 1000. Doing so gets you quickly to 101101 which is verified to work, and so is sufficient to answer the question as it is stated.)
ABCABC=7*11*13*ABC (ABC not necessarily prime)
So 6, 10, 12 must all divide ABCABC-1; this means C has to be 1, and AB1 must be 2 (mod 3) and 1 (mod 4). There are two cases:
Case 1: AB1 is prime. Then AB0 must divide AB1AB0, and so AB0 must be a 3-digit number that divides 1000. Only one possibility allows AB1 to satisfy all conditions so far: AB1=101. This gives the solution 101101.
Case 2: AB1 is not prime. From the conditions above, AB1 can't have 2, 3 or 5 as a factor. Additionally, AB1 can't have 7, 11 or 13 as a factor, since squared prime factors aren't allowed. So AB1 must have distinct factors from 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 (larger factors would create numbers that are greater than 3 digits.) The only ways these factors can multiply to a 3-digit number AB1 are: 17*23=391 (not 1 mod 4), 17*43=731 (not 1 mod 4), 17*53=901 (not 2 mod 3), 19*29=551 (not 1 mod 4), and 23*37=851 (not 1 mod 4). None of them work, so there are no solutions when AB1 is not prime.
So the only solution is 101101.
Note: I have assumed that A is not 0, since the question clearly states finding six digit ABCABC. If A were allowed to be 0, then another solution would be 041041. (This is just an extension of Case 1 where we also check when 0B0 divides 1000.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I only noticed today that there is an updated version on accurate emulation (that was fast!).
Here's a 1080p60 comparison encode for the updated version of the TAS:
Link to video
By the way, in the submission's newest comparison table, the -1 in the second last row should be +1, and the 55329 in the last row should be 55293.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
So I'm just wondering, since this game has a lot of different versions on different systems as you can probably tell.
Since this is the fastest version of all of them (also it seems this version is closest to the original), does that mean that this TAS supersedes all other versions' TASes? Or can all versions' fastest TASes exist all together as currently published movies?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
HappyLee, I didn't know you were also interested in doing Mega Man X(5)! (Although I haven't done any Mega Man related TASes in ages.)
Are you planning to do anything else with Mega Man X5, or anything else Mega Man related?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Actually, the given source code is missing some critical files. I was going to dig into it to see how the game uses RNG, and it turns out the code is simply not there. In addition, BizHawk does not have a trace logger for Uzebox.
I managed to poke enough values to determine that the RNG (memory address 0x109, 4 bytes long, little endian) is sequentially determined as follows (but I was unable to determine how the game uses the value to determine whether the tile is a 2 or a 4):
* The initial value is 1
* The next value is calculated from the current value N by: (0x41A7*N) mod 0x7FFFFFFF (unless N is 0 in which case the next value is 0x1F0CCE42)
In any case, the RNG does not appear to change, except when determining the value of a new tile. So the tile value is unmanipulatable. Too bad.
If you want to manipulate tile values, you'll have to use a different homebrew version of 2048. I tested some other versions some months ago: this NES homebrew version, as well as this Mega Drive / Genesis homebrew version both have manipulatable tiles (as well as manipulatable positions).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Note: In case it is not clear, in Wordle, you are only allowed to guess English words (non-words are not allowed) in order to try to find the answer.
This GB Wordle version uses what is known as a bloom filter.
In short: If using bit fields, then to be perfectly accurate, every allowed guess is meant to be represented as a bit out of a (26^5)-bit bit field. However, 26^5 is way too much for the amount of memory a GB has. So instead, the bit field is reduced to 40000 bits (by a many-to-one operation), while introducing the possibility of false positive guesses.
You can see the 40000-bit bit field here in the source. The hash value, normally a 32-bit number, is modulo by 40000 and the resulting value recorded in the bit field.
(Note that it is possible to have more than one hash function for a bloom filter to reduce the number of false positives, but this implementation only uses one hash function, called "djb2" in the source.)
So actually there are a lot of false positives; for this version, there are over 2 million allowed guesses out of the 11 million or so possible. I made a Lua script to dump all allowed guesses (including false positives) (download the raw paste data; the preview is completely messed up) , which you can run in BizHawk to get the list if you want (it should take 1 or 2 minutes to run on a modern machine).
Just in case you want to play around with the false positive guesses for whatever reason. :)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
In case anyone really is fantasizing about a max score / max move TAS:
A number of these console homebrew versions, including those whose randomness can be manipulated at will, are incapable of going beyond 8192 for no apparent reason other than the developers not willing to create tiles with 5 digits on them. (For reference, the original version goes as far as possible, which is up to 131072, the max tile value possible.)
So if you really want something like a max score / max move TAS on a faithful port that is also manipulatable, I'm not actually sure if such a thing exists out there.
(By the way, such a TAS is going to last hours. Not that length of TAS has stopped anyone.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I finally got some spare time. As promised, I will explain how I found that it is impossible to have more than two distinct maximal sequences that both end in N:
As p4wn3r explained before, the Fibonacci fractions 1/1, 2/1, 3/2, 5/3, 8/5, etc. represent the boundaries for the quantity N/m regarding the length of the sequence ending in (...,m,N). The fractions approach phi=1.618...
(I added numbers to show how long the maximal sequence will be for each interval.)
Alternatively, we can look at the reciprocal fractions 1/1, 1/2, 2/3, 3/5, 5/8, etc. which are the boundaries for the quantity m/N regarding sequence length. The fractions approach 1/phi=0.618...
In order for there to be three or more maximal sequences, there needs to be three separate values m1/N, m2/N, m3/N all in the same interval, and no m/N in any better interval. The situation is shown below, showing the red interval labelled "n" where we want three values, and no value must be in the blue interval labelled ">n". F(n) or Fn means the nth Fibonacci number. (Note: This diagram is for n even. If n is odd, the diagram is reversed so the red interval is below 1/phi, rather than above it. Similar argument.)
Noting that each value m/N is equidistant from each other, it does not appear possible to put three values in the red interval and none in the blue interval. To show this, we just need to show that the red interval is less than twice as long as the blue interval. Or equivalently, the distance from Fn-2/Fn-1 to Fn-3/Fn-2 is less than three times that of the distance from Fn-2/Fn-1 to Fn-1/Fn:
|Fn-2/Fn-1 - Fn-3/Fn-2| = |Fn-22 - Fn-1Fn-3|/(Fn-1Fn-2) = 1/(Fn-1Fn-2)
|Fn-2/Fn-1 - Fn-1/Fn| = |Fn-2Fn - Fn-12|/(Fn-1Fn) = 1/(Fn-1Fn)
where the numerators have absolute value 1 because of Cassini's Identity.
Since Fn is less than three times as large as Fn-2 for n>=5 (note that Fn/Fn-2 tends to phi2 = 2.618...), it follows that 1/(Fn-1Fn-2) is less than three times that of 1/(Fn-1Fn), proving that it is impossible to have three values of m/N in the red interval and none in the blue interval, when n>=5. The cases n=2,3,4 can be ruled out simply by checking exhaustively for N<=6, and observing that for N>=7, there is always a value of m/N in an interval n>=5.
----
p4wn3r wrote:
Yes, I solved it two or three days ago knowing about zero-knowledge proofs and using the discrete log example on that page as a basis. I ended up with a solution that is practically the same as yours. Though I don't think anyone would be able to solve this unless they knew about zero-knowledge proofs in the first place.
P.S. The term "proof" is actually misleading; it's more like "zero-knowledge protocol" since there is always a nonzero possibility of falsely passing. Think about how some "primality tests" don't actually (in the mathematical sense) prove that a number is prime, and it's similar.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Edit: The comparison encode in this post is for the previous inaccurate version. The updated accurate version is here: https://tasvideos.org/Forum/Posts/513631
----
Comparison encode with previous TAS, all in 1080p60! I wasn't even intending to have 1080p60 as an option. How did that even happen.Link to video
So normally I don't make comparison videos of TASes that have vastly different routes. But I was watching the encode in the submission, and after 2 or 3 minutes, I lost all sense of how this game was supposed to function and my brain started to melt. (See, I don't know this game except for the few DOS/NES/SNES TASes I watched a long time ago.) So I figured I would put the previous submission in as a frame of reference. Hopefully it helps at least a few others out there who don't know the game.
P.S.: I made a slight change in one of the timing breakpoints (I think it was the first one) so that the music lined up better. The breakpoints listed in the submission text are just as correct as what I put down.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Curiously, the time given here appears to be the largest time that tasvideos can display. It comes out to be 922337203685.47 seconds, or 2^63-1 ten-millionths of a second. (2^63-1 is the largest possible signed 64-bit integer.)
Let c(n) be the count function of operations of the derivative of fn(x). Then c(1)=1, c(2)=7, and
c(n) = n+1+(n-1)+1+3+c(n-1)+n = 3n+4+c(n-1) (assuming I counted operations correctly)
or, in other words, the recursion c(n) - c(n-1) = 3n+4 for all n>=3. Solving this gives a quadratic 1.5n^2+5.5n+C, and with the value c(2)=7, we get c(n)=1.5n^2+5.5n-10 for all n>=2. (Note that as an exception, c(1) doesn't follow this rule because f(2)'s derivative can be simplified to reduce the number of operations, resulting in c(2)=7.)
So this gives quadratic growth with a coefficient of 1.5, the best I can find.
NOTE: The operations f(x)^x ("f(x) to the x") and f(x)^(1/x) ("f(x) root x") also generate three f(x)'s and an f'(x) in their derivatives, but unfortunately their iterations are easily simplified. This disqualifies both of them.
Edit: Added "the derivative of" in there. We're obviously taking the number of operations of the derivative of fn(x), not fn(x) itself.
This is my favorite Myst TAS now just for how funny it is. (Judging from the music change there, you even fooled the game for a split second.)
(I added numbers to show how long the maximal sequence will be for each interval.)
Alternatively, we can look at the reciprocal fractions 1/1, 1/2, 2/3, 3/5, 5/8, etc. which are the boundaries for the quantity m/N regarding sequence length. The fractions approach 1/phi=0.618...
In order for there to be three or more maximal sequences, there needs to be three separate values m1/N, m2/N, m3/N all in the same interval, and no m/N in any better interval. The situation is shown below, showing the red interval labelled "n" where we want three values, and no value must be in the blue interval labelled ">n". F(n) or Fn means the nth Fibonacci number. (Note: This diagram is for n even. If n is odd, the diagram is reversed so the red interval is below 1/phi, rather than above it. Similar argument.)
Noting that each value m/N is equidistant from each other, it does not appear possible to put three values in the red interval and none in the blue interval. To show this, we just need to show that the red interval is less than twice as long as the blue interval. Or equivalently, the distance from Fn-2/Fn-1 to Fn-3/Fn-2 is less than three times that of the distance from Fn-2/Fn-1 to Fn-1/Fn:
|Fn-2/Fn-1 - Fn-3/Fn-2| = |Fn-22 - Fn-1Fn-3|/(Fn-1Fn-2) = 1/(Fn-1Fn-2)
|Fn-2/Fn-1 - Fn-1/Fn| = |Fn-2Fn - Fn-12|/(Fn-1Fn) = 1/(Fn-1Fn)
where the numerators have absolute value 1 because of Cassini's Identity.
Since Fn is less than three times as large as Fn-2 for n>=5 (note that Fn/Fn-2 tends to phi2 = 2.618...), it follows that 1/(Fn-1Fn-2) is less than three times that of 1/(Fn-1Fn), proving that it is impossible to have three values of m/N in the red interval and none in the blue interval, when n>=5. The cases n=2,3,4 can be ruled out simply by checking exhaustively for N<=6, and observing that for N>=7, there is always a value of m/N in an interval n>=5.
----