Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
OmnipotentEntity wrote:
Do you allow strict opposite difference?
Yes, I called that out specifically as one of the 7 total distinguishable cases.
I didn't want to allow it, because why don't allow then 3 balls equal 2 balls, like 2 2 1 and 2 3? Probably it doesn't matter though. And you see here they are strict opposite.
OmnipotentEntity wrote:
I think you misunderstand what I'm considering the end state. Because there are 7 total distinguishable cases with 12 ways of making those 7 cases, I'm considering the end state to be when each ball is reduced to one viable hypothesis. Not just when I decide their relationship solely to the normal balls.
Okay, as far as I understand now, you mean answer is also telling their oddness, do they both lighter and equal between, etc.
OmnipotentEntity wrote:
Also I believe you may have entered the data in your calculator wrong? It's still 18Choose2, not 12Choose2.
One above is your calculation, below is mine. So, everything is fine.
If you mean that I should put choose from 18 - no, with my reasoning I should choose from 12.
And, yes, with additional case with strict opposite, multiplier would be 12.
OmnipotentEntity wrote:
Next, I'm going to set up a system for generating a graph, and perform an A* search on it using the entropy remaining as a heuristic function, and I'll see what shakes out.
I think the real trouble will be number of intersection of hypothesis.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
I don't think there is any strict relation between entropy and strategy for games like that when you can "tune" strategy on the way to the end.
For 12 balls and light/heavy odd ball there are already many subcases so it's already very tricky task. When you add second ball there are some things to consider. Do you allow strict opposite difference? for example, normal wieght is 5 and two odd balls are 4 and 6. so 4+6 = 5+5?
For single ball there is simpler version, when you know in what way it's odd: heavier or lighter. Then task is easier. So, you may try to solve 12 balls 2 heavier balls first, and find out smallest possible number of steps.
But, what comes to my mind: try original problem with 11 balls instead. Entropy should be lower, but I expect more steps. Reason is obvious, I don't know anology for first step of solution for 12 in case with 11 :p Edit: Ah, no, it works. I'm retarded. But 13 balls is log326 weighings = 2.966 I don't think 13 balls is possible in 3 steps.
OmnipotentEntity wrote:
So there are 7 total distinguishable cases: both heavier same magnitude, both heavier different, (same with lighter), and then one heavier one lighter x3 (H bigger, L bigger, same). However, if you're selecting from these 7 cases to simulate, because order matters in case where the balls are not identical, there are 12 total ways to choose these two balls.
So the total possible beginning states is 12 * 18C2 = 10.842 bits of entropy.
No, you have a mistake. 8*С212 = 9.044 bits of entropy.
Reasoning is following. First, choose an answer - places with odd balls. Variants with different answers are obviously different. So, now, the only reason why variants can be different with same answer is their weight. There are four possibilities: LL*3, LH, HL, HH*3. LL and HH multiplied by 3 because LL or HH can be < = > in their weight (only because in your task you may have L and L different). Order matters, because when we know answer, and pick two places in ordered way, we can place all eight those possibilities, and this would give different beginning states.
I can also say, that theoretically you don't need to know are they heavier or lighter to give an answer, so theoretically, you could delete this 8 multiplier and 2 multiplier in original task! This is another reason why I don't think there is strict relation with entropy.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
It's well described though. Main tricky thing is "normalized divisor". But put it aside for a moment.
Lets say the problem is hard. So, lets make it easier. Easier problem is when you want to divide number N words (limbs in terms of gmp) by 1 word (limb). It's easy. It's reduced to division of 2 word by 1 in succession.
XXXXXXX
-ZZ
You find such number Y so d*Y = ZZ and remainder is less than Y, which means one digit of dividend is turned into zero after subtraction. So, problem reduced into N-1 words division by 1 word.
Here where comes "normalized divisor". What if divisor is just one = 1? Then quotient is two words! For divisor 1 it doesn't make carries when you add quotient to ending result, but if you have divisor small, it may cause carry. Also, you may not have division that may output quotient 2 words size. That's why we normalize divisor, by shift of both: dividend and divisor. Because A/B is equal (A*2)/(B*2). Take care with remainder though.
Alright. Now we can divide arbitrary long number by single word. What if divisor is also arbitrary long? Well... reduce to simpler task: to division by single word again. What if we neglect all words (limbs) except most significant? Lets say D is original divisor, and D' is D with all zero words except most significant:
DDDDD = D
D0000 = D'
Then D > D', and X / D < X / D' (the higher the divisor, the lower the result).
Now, idea is similar. Lets divide X by D':
XXXXXXX
-ZZ
We need to find such y that y*D' = ZZ is less than XX and remainder XX - ZZ is less than D'. You can do that by simple division of two words by one. Now, instead of simple subtraction from X. We'll calculate y*D - multiplication of 'guessed' y by real D - with neglected words (limbs) turned back. This is single word times arbitrary long number multiplication. 1xM multiplication in terms of gmp (where M = number of words (limbs) of D).
Now, because X / D < X / D' result of y * D may be larger than we need. In this case we need to reduce y by one. And instead of additional multiplication, we just subtract D because: (y-1) * D = y * D - D. Taking into account that we want to subtract result from X, you could subtract y * D and if it turned into negative, you could add D back.
This is what is described in quote:
Such a quotient is sometimes one too big, requiring an addback of the divisor, but that happens rarely.
Now, you know highest word (limb) of quotient. And current X has current remainder. Repeat this process until X is less than D, and you're done.
And... why don't you just use gmp for example? Or other package that is made for things like that? :o
Regarding thing with probability... I'm not specialist there. I see only two ways. Numerical approach and Analytical approach. Numerical approach it's monte carlo or any other numerical. For example, you may integrate using various numerical methods, like Runge–Kutta, Euler method, or Gaussian quadrature...
Analytical approach is harder just because you have to scramble formulas. There are some packages for it, like in numpy for Python... but it's way complicated. I'm horrified from it. If you don't need to program stuff but just solve exact task like you noted, then you indeed may find distribution first, then apply suitable methods. Not for any integral of analytical funciton is expressed with elementary functions.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
I want to make it rigorous, so I'll start from simple facts.
First fact. If a < b then a * c < b * c, for any positive real numbers a, b, c.
Proof: if a < b then (a - b) < 0, thus a*c - b*c = (a - b) * c - negative times positive = negative, so a*c < b*c.
Second fact. if a < c and b < d then a * b < c * d.
Proof: Using first fact a * d < c * d, and using first fact second time a * b < a * d. So, a * b < a * d < c * d.
Third fact. if a < basen and b < basen, then a * b < base2n
Proof: basen * basen = base2n Using second fact: a * b < base2n where c = basen and d = basen.
Straight from this third fact, you can prove that z0 and z1 have this size.
Why they're not intersecting - conjunction of their size and multiplier.
Regarding to z1 - this formula is to reduce multiplication count, but if you open brackets you'll get more useful for prove formula: AAAAA*DDDDD+BBBBB*CCCCC. Using fact three you can tell that if a, b, c, d < basen then a*d < base2n, and b*c < base2n, thus a*d+b*c < 2*base2n.
This means, that it's either 0FFFFFFFFFF or 1FFFFFFFFFF, because 20000000000 is already = 2*base2n but it should be less.
Now, this means, that if you consider those two digits as last full carry propagation, then yes, this is last. But, if you mean that it's last digit where you should propagate carry - no. Look at this example:
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Selicre wrote:
I don't want to interact directly with Gens because I am running it in wine, and.. building 32-bit windows executables? That link to OpenGL? On Linux? No thanks.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
You said they are hidden: I was planning to do the same, but...
Also, fix this stuff. https://imgur.com/a/emK20jl
Btw, with rust you could write plugin instead of my dll, because rust is c++ friendly.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
difference with my encode:
camera fixed to screen centered - easy to change.
my encode has background - easy to disable.
sprites correct priority (sonic/tails/rings not always on top) - easy to make always on top.
I display glitchy invisible sprites: dead boss, blue things in marvel garden zone, magnetic platforms in flying battery zone... <- not easy to change. need to hardcode. had no time.
I didn't hide hud.
I show some object that I added in that time: spikes, monitors, and very few other objects.
And, objects off screen is full opaque.
The reason why I have background and correct priority - it was made with idea that original screen should seemlessly placed over it to prove that everything is right. Hud is visible because I display original screen, kinda same reason.
One can say that sprites on top is not a bug, it is a feature. I can't argue with that.
I tried camera smoothly following both, and with background enabled it makes weird move of it. I have issue with tails when he is "dead" because I don't know how to know is he alive atm, and I don't want to spend time on it. But when his position just reset - camera works fine. Just when he is dead, it's trying to reach some offscreen position.
There is nifty hack to fix transitions in stages: if difference of sonic position > 128, shift camera with same difference :b
As always, I'm not planning to update anything.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Chanoyu wrote:
Is the line of the jump not parallel to the line connecting the start and end points?
This is same what I said:
r57shell wrote:
And, btw, better approximation is having angle same with vector from start to target except very long distances along edge.
It's better in some cases, but it's not the best.
In case if you got it same way as I did, I'll describe a bit better.
I got it taking into assumption that shortest distance is lowest effort.
This thing is taken from physics, for example light travels shortest distance in some meaning (Principle of least action).
So, to reduce effort (energy/action), you would like to get from jump maximum profit. And this leads to idea to move along same direction.
Why it doesn't work? Because restrictions are awkward. You need to reach edge, and from there you can move fixed distance in any direction. This never happens in physics. You can't cut corners. You could solve this task using string with sliding ring holders along the edges. This should work.
By the way, origami approach also doesn't work, because it gives obviously wrong solution with corner in the middle of the jump :D
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
I can confirm this equation.
But I, myself, was solving case when both: start and target is not aligned on the edge.
And, it looks like this task is ugly, in the way that it doesn't have analytic solution, or at least no 'neat' analytic solution :(
And, btw, better approximation is having angle same with vector from start to target except very long distances along edge.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Interesting task that popped up in discord:
This is for the Nightfire TAS. Basically I'm starting at the black dot in and I need to get to the yellow point. Which of the lines would be the best to take?
I need to jump from A (the ledge i'm walking along) to B (the edge of the platform i'm going to land on)
The speed is constant and the jump length is always the same.
basically the line connecting A to B is always the same length
Addition from me: velocity same for move and jump.
So, you need to find trajectory that connects start point with target point, and distance traveled between borders is less than length of jump L.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Script updated, one gif added.
It's also about mercury boss.
Now it also shows trajectories to the point of decision of next target point.
Also it shows current player target by red rectangle around it.
One note about mercury boss AI.
Normaly his attacks is Fire, Fire, Drone, Staff in cycle.
But when it make choice to do Staff, if target player y position is above his y position, it moves target y position to move 60 pixels above to move upper, but suddenly change his next cycle to Drone instead, and attack timer to 20. So, in this way you may manipulate him to always pick Drone, if you have enough luck to make him lower than you at certain points of time.
Thus, my script also shows next attack according to this strategy.
If target player is lower than boss and next is Staff, it will show small letter d instead, meaning that he will go for Drone after 20 frames.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Script updated. Now it shows a bit of info about Mercury Boss.
Here some gifs, about 10 MB in total size
https://imgur.com/a/87KHA3Y
Mercury boss AI is following. There are three timers:
1) Attack timer. When it hits zero: pick attack. Delay is 250 frames.
2) Move timer. When it hits zero: pick new target position. Delay is 150 frames.
3) Aim timer. When it hits zero: pick player. Delay is 10 frames.
Only random thing here is "new target position".
RNG is placed at FF0312, it's single byte = index in 256 value list.
RNG array is at ROM:0541A2, RNG routine at ROM:05418E
There are three attacks:
1) Drone - thing hit boss
2) Staff
3) Fire
Drone AI has two phases:
1) It moves in circles - this trajectory is fixed, except perhaps some corner cases like lags / screen restrictions. It is just chasing corners of expanding box. This phase has two timers.
a) When first hits zero, box is expanded.
b) Second timer is size of box. When it reach maximum, drone goes back to the boss.
2) When drone got hit, it's similarily chasing but single point. Frequently changing it position. This phase has also two timers.
a) When first timer hits zero: go back to boss. Delay is 350 frames.
b) When second timer hits zero: change target position. Delay is 50 frames.
Random target of boss = position of target player + vector(RNG, RNG)/2 sign extended from bytes with some range clipping.
Random target of drone = position of top left corner of screen + vector(RNG, RNG) unsigned. Thus, it may not roll in range [256,319] positions of screen.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Spikestuff wrote:
Another thing to note, is that it looks like roughly the first 5 seconds will be lost.
Don't know how to go about this other than padding which unfortunately I forgot the command to on ffmpeg.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
If you would make topic about this game, or if you would make any research, you would probably didn't miss some well known shortcuts.
From top of my head:
1) Mercury first part there is hidden room. (2:08 fall down) I'm not sure is it faster or not.
2) Mercury second part at first electro door on the left side, you can climb higher (straight up to 2:35 time),
also IIRC you can skip more after.
3) Cybertox second part you may climb higher at right side (5:45).
Regarding 2p choice: I think you also can kill boss faster with 2p, but I'm not sure.
Nice bosses rng, well done.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
I might be wrong, but it doesn't seems to be even nearly optimal.
Many questions arising when you see combo: hit + this special move against single enemy. Is first hit just to avoid enemy hit you? If so, I don't think it's impossible to make special move at same frame as enemy appears.
In autoscroll where you move down, there are often enemies spawn and able to walk a bit before they get hit with special move.
