User talk:Positive/Optimal Velocity

Your version passes all of my tests (so far) except that it doesn't take into account the maximum velocity set by the bot. Nice catch on the updateMovement() routine, that should get fixed too (my tests assume that behaviour already). --Darkcanuck 20:21, 15 July 2009 (UTC)

Great! Please replace 8.0 in the getNewVelocity function with currentCommands.getMaxVelocity(), and it should work I believe (I temporarily set it to 8.0, because I am not using the currentCommands class). :) --Positive 20:26, 15 July 2009 (UTC)

ok, that fixed it. Nice work! --Darkcanuck 20:33, 15 July 2009 (UTC)

I just noticed that this does allow some free acceleration, although it's capped at 1. Replacing this with the time-based calc in Voidious' second version should work. --Darkcanuck 20:41, 15 July 2009 (UTC)

I did, unfortunately, find one small problem with the code: decelTime(Double.POSITIVE_INFINITY). It takes a lot of time to process. So i guess at arguments around > 1000 it could simply return Rules.MAXVELOCITY (or a more elegant solution). Personally, I think the free acceleration provides no problem, and people not liking that particular change was the start of the discussion. --Positive 20:52, 15 July 2009 (UTC)

Yeah, I was going to suggest that we add an "if (distance > SOME_MAX_DISTANCE)", just accelerate freely, for sake of execution speed. That would be 20 if you assume max velocity is 8, but Fnl might prefer to have it calculated based on a MAX_VELOCITY constant...

The free acceleration is really a separate issue from the optimal velocity. Originally, you could go from -0.1 to 1.9, so even capping velocity at 1.0 would be a change. I sort of feel like if we're going to change it, we should do it the way Fnl envisioned, which is how I had it in that "Version 2". But that's an easy change, whatever is decided.

Oh, and nice work. =) This solution definitely feels right.

--Voidious 21:02, 15 July 2009 (UTC)

You're welcome. :) Hmm, I guess you are right. Fnl's change is more logical. I remember when I started with studying the movement rules I had expected something more like what he suggested. However, staying able to easily move at integer (whole) speeds is nice too. (I guess I'm a little biased, because Portia uses integer speed lookup tables). By the way, if it can't be >=20, I'm thinking something like "static private final double MAX_CALC_DISTANCE = Rules.MAXVELOCITY + Rules.MAXVELOCITY/Rules.DECELERATION * Rules.MAXVELOCITY/2;". --Positive 21:44, 15 July 2009 (UTC)

Hijack =)

I don't mean to hijack your work, but here's what I feel is a much simpler version of both your and Voidious's ideas =) Or at least, I find it easier to read:

         private static double getNewVelocity(double velocity, double distance) {
      
         if (distance < 0) 
            return -getNewVelocity(-velocity, -distance);
      	// If the distance is negative, then change it to be positive
      	// and change the sign of the input velocity and the result
      
         final double goalVel;
         if(distance == Double.POSITIVE_INFINITY)
            goalVel = currentCommands.getMaxVelocity();
         else 
            goalVel = Math.min(getMaxVelocity(distance),
               currentCommands.getMaxVelocity());
         
         if(velocity >= 0)
            return Math.max(velocity - Rules.DECELERATION,
               Math.min(goalVel, velocity + Rules.ACCELERATION));
      //else
         return Math.max(velocity - Rules.ACCELERATION,
                  Math.min(goalVel, velocity +  Rules.DECELERATION));
      }
       final static double getMaxVelocity(double distance)
      {
         final double decelTime =  Math.max(1,Math.ceil(
            //sum of 0... decelTime, solving for decelTime using quadratic formula
            (Math.sqrt((4*2/Rules.DECELERATION)*distance + 1) - 1)/2));
            
         final double decelDist = (decelTime / 2.0) * (decelTime-1) // sum of 0..(decelTime-1)
            * Rules.DECELERATION;
        
         return ((decelTime - 1) * Rules.DECELERATION) +
            ((distance - decelDist) / decelTime);
      }

--Skilgannon 11:20, 16 July 2009 (UTC)

Very nice. Your formula replacing the decelTime function is voodoo to me right now, but I've thrown enough numbers at it that I trust it works. =) I'd like to test this (I don't trust my own logic that it's equivalent :-P), then switch to this code, and also implement the new decel-through-zero rules. Also, I added one set of parens in there for clarity, hope you don't mind. --Voidious 13:47, 16 July 2009 (UTC)

Nice simplification. It passes all my tests, except for a new one I just added: starting vel=0, distance=+INF (returns NaN). --Darkcanuck 14:36, 16 July 2009 (UTC)

Ok, I fixed the infinity case, although I hate adding more if statements. As an explanation for the voodoo in there read on: =)

From the old decelTime method: distance <= (square(x) + x) / 2) * Rules.DECELERATION
lets solve for the case where they're equal, ie.
distance = (square(x) + x) / 2) * Rules.DECELERATION
distance/Rules.DECELERATION*2 = x*x + x
0 = x^2 + x - distance/Rules.DECELERATION*2
which is in the form 0 = ax^2 + bx + c
so we can use the quadratic formula x = (-b +-sqrt(b^2 - 4*a*c))/(2*a)
which gives us:
x = (-1 +-sqrt(1 - 4*(1)*(-distance/Rules.DECELERATION*2)))/2
because we need a positive answer (time) we need the + of the +-sqrt
so, simplified: x = (sqrt(4*2/Rules.DECELERATION*distance + 1) - 1)/2
and then take the ceil, because any partial tick used means a whole tick got used.

And I really need to start packing for my holiday to Mozambique... --Skilgannon 15:09, 16 July 2009 (UTC)

Thanks for the explanation, it's clear now. Enjoy your holiday. =) --Voidious 15:17, 16 July 2009 (UTC)

Okay, I finally analyzed your code. Great work! Although your version is not the same as the one I posted. Your version's getNewVelocity(-0.1,1000000000) == 1.9 while the old one == 1.0. So considering Fnl used your version, the alpha-2 version is exactly like the 1.6.1.4 version except for the "bugs". :)

Here's the modified function that makes them equal (for if it's decided we want that):

    private static double getNewVelocity(double velocity, double distance) {
        
        if (distance < 0) 
           return -getNewVelocity(-velocity, -distance);
     	// If the distance is negative, then change it to be positive
     	// and change the sign of the input velocity and the result
     
        final double goalVel;
        if(distance == Double.POSITIVE_INFINITY)
           goalVel = currentCommands.getMaxVelocity();
        else 
           goalVel = Math.min(getMaxVelocity(distance),
              currentCommands.getMaxVelocity());
        
        if(velocity >= 0)
           return Math.max(velocity - Rules.DECELERATION,
              Math.min(goalVel, velocity + Rules.ACCELERATION));
     //else
        // changed here:
        return Math.min(Rules.ACCELERATION,
        	Math.min(goalVel, velocity + Rules.DECELERATION));
        // we don't need a Math.max, because the goalVel can never
        // be below zero (because distance is always positive)
     }

--Positive 01:00, 19 July 2009 (UTC)

Oh my! I didn't realize "getNewVelocity(-0.1,1000000000) == 1.9" about the version in Alpha2 before... to me that seems like a really really bad thing, because of this scenario:

getNewVelocity(-1.0,1000000000) == 1.0
getNewVelocity(-0.5,1000000000) == 1.5
getNewVelocity(-0.1,1000000000) == 1.9
getNewVelocity(0.0,1000000000) == 1.0
getNewVelocity(0.5,1000000000) == 1.5
getNewVelocity(0.9,1000000000) == 1.9

The sudden jump in output between -0.1 and 0.0 doesn't make any intuitive sense at all I think. It really should be limited to 1.0 like in the old code, unless more accurate handling is done (as in Alpha3) --Rednaxela 05:03, 20 July 2009 (UTC)

Actually, Alpha2-style is also how the old code does it. You can go from -0.1 to 1.9 in Robocode 1.6.1.4. Positive, I noticed Skilgannon changed that, but I think the old way and Fnl's new way were the two main choices up for consideration. --Voidious 05:12, 20 July 2009 (UTC)

Ugh... I'm really really against the old way then, since it then makes it notably advantageous for a bot to optimize it's movement to do things like -2.0, -0.0000001, +1.9999999, instead of -2.0, 0.0, +1.0 as would be logical... It seems like a ridiculious quirk to have to optimize to... --Rednaxela 05:56, 20 July 2009 (UTC)

Well, I agree with Rednaxela that the way of the old code is obviously somewhat bugged (why be able to go from -0.00000000001 to 2.0, but from 0.0000000001 only to 1.0?). Capping it at 1.0 makes sure it can't really be exploited, and thus does not force programmers to make strange "never go to 0, only go to 0.000000000001" functions to exploit this. I believe many bots nowadays almost only travel in integer speeds, so capping shouldn't affect them much. In contrast the new idea rules will affect most robots (somewhat), and disallow them to stay at integer speeds while decelling through 0 from 1.0. My thought is that although the new time-based calculation is much more correct, capping keeps the game simpler. So I think it should also be considerd as choice. --Positive 06:07, 20 July 2009 (UTC)

Just my 2 cents... My feeling is that if we're going to change it, we should change it to the completely correct (split-tick by Fnl) version. Capping at 1 is a kind of middle ground, but it is still "incorrect", and it still introduces a strange optimization quirk: from velocity 2, it's always better to decelerate to 1 than to 0, since you can still get to -1 but you can also get back up to 2. I agree its impact would be much less on surfers, but if it doesn't fix the problem that Fnl set out to fix in the first place, I'm just not sure we'd want to change it at all. --Voidious 12:58, 20 July 2009 (UTC)

Buggy Alphas?

Hmm, are you sure? Darkcanuck ran a lot of tests on all the alphas and didn't find this bug, right? Anyway, if there are bugs in the alphas, I guess I'd vote to have more and re-run tests on the matchups that showed score differences. If all the differences went away, it might convince me to vote Alpha3. But that would cause more delay in 1.7.1.4, too... --Voidious 22:13, 7 August 2009 (UTC)

Okay Voidious, since you did most of the test anyway for the Alphas and seems to be fine with it, I will create 3 new alphas to replace the old ones. I guess that Darkcanuck did not check the getDistanceRemaining() like I did recently, and hence discovered the bug. --Fnl 22:17, 7 August 2009 (UTC)

Cool, sounds good. If this does eliminate a lot of the score differences, I would probably change my vote to Alpha3. That would really be ideal... but we'll see what happens, I guess. Thanks for your patience and diligence with this, Fnl! --Voidious 22:25, 7 August 2009 (UTC)

Ok, I think I see the source of some of the confusion. I tested all the routines proposed on the wiki (which may not be exactly the same as in the alphas) based on the idea that if distanceRemaining=0, then the bot is trying to stay at its current location so it may need to reverse if its velocity is non-zero. However, the API docs for setAhead() state that if the distance passed is zero, then the bot should decelerate to a stop -- none of our routines take this into account. But this doesn't mean that if distanceRemaining=0 then the bot should just decelerate, since there are cases (say velocity was 8 and we called setAhead(2)) where we need to correct for potential overshoots. So really what's needed is to add a "stopping" flag that's set when setAhead(0) is called -- this would be separate from distanceRemaining and would force the bot to slow to a stop (and then set distanceRemaining=0). --Darkcanuck 05:19, 8 August 2009 (UTC)

Hmm... you're right about what the API says, though to me anyway, what the API says seems odd. It means that setAhead(-0.00001) and setAhead(0.00001) mean nearly the same thing, yet setAhead(0.00000) can mean something very different than either of the other cases. This is indeed what the API docs specify, but that does seem... quite odd, at least in my mind. --Rednaxela 05:23, 8 August 2009 (UTC)

I agree, it was weird when I read it and I would much prefer the "hold this position" interpretation. But this whole thing started out trying to get the engine to follow its own published rules... :P --Darkcanuck 05:25, 8 August 2009 (UTC)