I'll give 3 stars to the bot that comes up with the best solution to this.
Update 8/4 11:49am: The contest is over and shoyuken is the winner! Thanks to all who participated.
While investigating why some pages were loading slow, I noticed a lot of time was being spent on one particular game function: expToLevel(). If you're interested in math and want to take a stab at optimizing this, read on!
First, some background. The game doesn't actually store the level of your bot, but rather the exp of your bot. This makes some calculations easier, but others harder. In particular, converting exp to level is a very common operation that also happens to be very slow. This is where you come in! Here's the current PHP function (and its helper):
private function expToLevel($experience) {
$level = 1;
$totalexp = 250;
$tolevel = 50;
while ($experience >= $totalexp + $tolevel) {
$totalexp += $tolevel;
$tolevel = $totalexp * Experience::getMultiplier($level);
$level++;
}
return $level;
}
private static function getMultiplier($level) {
switch (true) {
case $level < 35:
return 0.3;
case $level < 80:
return 0.1;
case $level < 150:
return 0.08;
case $level < 180:
return 0.05;
default:
return 0.03;
}
}
As you can see, it starts at level 1, and keeps going up until the exp for that level exceeds the provided exp value. The higher your level is, the longer it will take to finish. This is dirty, ugly, and inefficient, but it works and was good enough as a quick hack when I was prototyping this game in 2010. Now that we're in 2012 and we have lots of high level bots, this has become a bottleneck on any page that lists a lot of bots (hall of fame, fight lists, long forum threads, etc.).
A better solution almost surely exists, probably one that doesn't involve a loop. In computer science terms, I have a linear time function and am looking for a constant time function. Other random notes:
- The language you use doesn't really matter (pseudocode is fine too) because it's really the algorithm that's of interest here, not the implementation, which I can handle.
- As a starting point, I imagine a closed-form solution to this would probably involve logarithms with the multipliers (.3, .1, .08, .05, .03) as bases.
- Using dropoff level total exp values as constants is fine, but other than those, try to keep it general.
- I'm looking for something pretty fully sketched out. I could probably work this out on my own with enough time, but it's the details that are going to take some time to get right.
- Use <blockquote> and <pre> tags if you want to format your code like mine.
- Hardcoding the exp values for each level is a valid solution, but I won't accept it here. This is what I'll end up doing if we can't find anything, but I'm hoping we can find something more elegant.
Good luck and thanks for making the game faster!
|
Why don't you calc the level only once and save it in a session variable?
|
You can't session variable a hundred bots for the hof.
|
calc it when then user is logged in :)
|
Why don't you calc the level only once and save it in a session variable?
Hm sorry, I'm not clear on the suggestion. These values are already cached on a per-request basis if that's what you were suggesting.
The problem is: given an arbitrary exp value, compute the level. To be clear, doing this once for your own bot (like on the workshop or showroom page) isn't a problem. It's certainly slower than it has to be, but it doesn't take a significant amount of time relative to everything else being done. Where it becomes a problem is on pages like the hall of fame where it has to be done hundreds of times for all different exp values. In these cases, it's taking a large percentage of the time spent rendering the page.
|
ah didn't think of the HoF page.. hm.. maybe you can do the calc on your sql database and create a view for just the levels.
|
You could have a ~500 row table of `level`.
Then make a procedure to find the ID of that level with the exp requirement.
|
ah didn't think of the HoF page.. hm.. maybe you can do the calc on your sql database and create a view for just the levels.
Thanks for trying to think outside of the box on this. I'm really just looking for a drop-in replacement for a heavily-embedded inefficient function though. I started this contest so someone else would work through the nitty-gritty math of it and spare me the effort. :)
I'm not concerned that it's being recomputed, and in fact would prefer that to the complexity that a caching strategy would add. If the page takes 1s to load and 500ms of it is spent on this function, a 1s and 10ms solution are effectively equivalent, despite one being an order of magnitude faster. If you throw in the fact that the 10ms solution only requires changing the body of a single function and that the 1ms solution requires rewriting database queries on probably every page, the winner becomes clear.
You could have a ~500 row table of level.
Then make a procedure to find the ID of that level with the exp requirement.
Yes, this is covered by the last bulletpoint in my OP. I'm hoping to not have to hardcode the exp values.
|
What if you split the ranges as below:
- $totalexp at lvl35 = A
- $totalexp at lvl80 = B
- $totalexp at lvl150 = C
- $totalexp at lvl180 = D
- Exp to go from lvl34 to lvl35 = E
- Exp to go from lvl79 to lvl80 = F
- Exp to go from lvl149 to lvl50 = G
- Exp to go from lvl179 to lvl80 = H
A, B, C, D, E, F, G, H are constants.
So program it like this:
If $totalexp < A then $level = 1+($totalexp)/(250*1.30^($level-1))
If A < $totalexp < B then $level = 35+($totalexp-A)/(E*1.10^($level-35))
The thing left is to solve for $level to make it explicitly in terms of $totalexp. It boils down to solving for X where: X = Y + W*Z^(X)
Do the same for the other categories. Will have to round down the the nearest integer as well.
|
you can try something like this, it is the calc in you while loop less, so it should be faster i guess.. I've not tested it btw ;)
private function expToLevel($experience) {
$level = 1;
while ($experience > 300) {
$experience = $experience - $experience * Experience::getMultiplier($level);
$level++;
}
return $level;
}
If you are only woried about the HoF page tho, i still suggest a view ^^
|
sorry, didn't know how to make that code thingy
|
private function expToLevel($experience) {
$level = 2;
$totalexp = 300;
$dropoff35=$totalexp*1.3^33;
$dropoff80=$totalexp*1.1^78;
$dropoff150=$totalexp*1.08^148;
$dropoff180=$totalexp*1.05^178;
if ($experience < $300){
$level = 1
}
elseif ($experience <$dropoff35){
$level = 2+ round down( log base 1.3 ($experience/ $totalexp))
}
elseif(($experience <$dropoff80){
$level = 2+ round down( log base 1.1 ($experience/ $totalexp))
}
elseif(($experience <$dropoff150){
$level = 2+ round down( log base 1.08 ($experience/ $totalexp))
}
elseif(($experience <$dropoff180){
$level = 2+ round down( log base 1.05 ($experience/ $totalexp))
}
elseif(($experience >=$dropoff180){
$level = 2+ round down( log base 1.03 ($experience/ $totalexp))
}
}
you could probably replace the hardcoded multipliers with variables if you want.
|
oops i made a mistake in the earlier post. this should be the corrected
private function expToLevel($experience) {
$level = 2;
$totalexp = 300;
$dropoff35=$totalexp*1.3^33;
$dropoff80=$dropoff35*1.1^55;
$dropoff150=$dropoff80*1.08^70;
$dropoff180=$dropoff150*1.05^30;
if ($experience < $300){
$level = 1
}
elseif ($experience <$dropoff35){
$level = 2+ round down( log base 1.3 ($experience/ $totalexp))
}
elseif(($experience <$dropoff80){
$level = 35 + round down( log base 1.1 ($experience/ $dropoff35))
}
elseif(($experience <$dropoff150){
$level = 80+ round down( log base 1.08 ($experience/ dropoff80))
}
elseif(($experience <$dropoff180){
$level = 150+ round down( log base 1.05 ($experience/ $dropoff150))
}
elseif(($experience >=$dropoff180){
$level = 180+ round down( log base 1.03 ($experience/ $dropoff180))
}
}
|
So i have 2 questions,
1 is the data on bots unauthorized correct (i get 163 631 1 81 rather than 163 631 1 18 for lvl 80 xp, that has a knock on effect later on)
According to what that func does in my opinion (dont do php, c# mainly) is for lvl lets say 75, its
300(1.3)^34(1.1)^(75-35)
for the amount of xp required for that lvl. right?
anyway:
public static double GetXpToLvl(long currentXp)
{
double modifier;
int levelBasis;
double baseXp = GetStaticData(currentXp, out modifier, out levelBasis);
double number = (1.0*currentXp) / (1.0*baseXp);
double lvl =levelBasis+ Math.Log(number, 1+modifier);
int y = (int)Math.Ceiling(lvl<=levelBasis?levelBasis+0.1:lvl) - levelBasis;
return baseXp*Math.Pow((double)(1+modifier), (double)y) - currentXp;
}
public static double GetStaticData(long currentXp, out double modifier, out int levelBasis)
{
long lvl2xp=300;
double lvl35xp = lvl2xp*Math.Pow(1.3,34.0);
double lvl80xp = lvl35xp * Math.Pow(1.1, 80 - 35);
double lvl150xp = lvl80xp * Math.Pow(1.08, 150 - 80);
double lvl180xp = lvl150xp * Math.Pow(1.05, 180 - 150);
if (currentXp < lvl35xp)
{
levelBasis = 1;
modifier = 0.3;
return lvl2xp;
}
else if(currentXp < lvl80xp)
{
levelBasis = 35;
modifier = 0.1;
return lvl35xp;
}
else if (currentXp < lvl150xp)
{
levelBasis = 80;
modifier = 0.08;
return lvl80xp;
}
else if (currentXp < lvl180xp)
{
levelBasis = 150;
modifier = 0.05;
return lvl150xp;
}
else
{
levelBasis = 180;
modifier = 0.03;
return lvl180xp;
}
}
Gets the exact amount of xp for the next lvl, according to those requirements set earlier.
Cheers.
|
Well i just read the 2nd post from Ender ;)
if you just return the lvl variable from my 1st function - that is the exact current lvl of the bot.
Cheers.
|
I've been working on this since it was posted.
Finally :)
With the help of Shoyukens post, which didn't work actually...But the same concept in a much faster formula.
Nice looking -> http://pastebin.com/0QEY3iBG
One lined -> http://pastebin.com/6FMGv7RZ
Basically, it uses if statements inside of the formula, which can be cut down into one line.
There is no bottleneck with this either.
Experience : 1000
Your level is 5
Page generated in 0.00010000000000000000479 seconds.
Experience : 10000000
Your level is 50
Page generated in 0.00010000000000000000479 seconds.
Experience : 1000000000000000000
Your level is 710
Page generated in 0.00010000000000000000479 seconds.
Experience : 1.0000000000000000537E+32
Your level is 1801
Page generated in 0.00010000000000000000479 seconds.
:D
|
Looped through 100 records of random experience
Page generated in 0.0023999999999999997898 seconds.
and 1000 records of random experience
Page generated in 0.010699999999999999442 seconds.
Just saying :)
|
yeah, i was missing $s and semicolons and a few functions, but Ender said he was fine with pseudocode and i figured he could do the fancy coding however he wanted
|
|
|
|
|
Not this time Rose, It's in my post :)
|
ah i see. alan pointed out to me that i made a mathematical calculation error in my post. the 45 should be replaced by a 55. thanks alan
private function expToLevel($experience) {
$level = 2;
$totalexp = 300;
$dropoff35=$totalexp*1.3^33;
$dropoff80=$dropoff35*1.1^45;
$dropoff150=$dropoff80*1.08^70;
$dropoff180=$dropoff150*1.05^30;
if ($experience < $300){
$level = 1;
}
elseif ($experience <$dropoff35){
$level = 2+ round down( log base 1.3 ($experience/ $totalexp));
}
elseif(($experience <$dropoff80){
$level = 35 + round down( log base 1.1 ($experience/ $dropoff35));
}
elseif(($experience <$dropoff150){
$level = 80+ round down( log base 1.08 ($experience/ $dropoff80));
}
elseif(($experience <$dropoff180){
$level = 150+ round down( log base 1.05 ($experience/ $dropoff150));
}
elseif(($experience >=$dropoff180){
$level = 180+ round down( log base 1.03 ($experience/ $dropoff180));
}
return $level;
}
|
The 45 looks correct to me. 35+45=80 which is what you need.
|
ah went the wrong way. the 55 should be replaced by a 45. check the original post. it was a 55 as alan pointed out and then in the updated post it's now a 45. all this multi-tasking is leaving minor errors anyways back to the show
|
oh btw, I was wondering if there was a deadline on this? The logo contest had a deadline and this one seems to have been left very open-ended.
|
Well I would assume it goes on until Ender gets a satisfactory solution or figures out something himself. So there probably isn't a set deadline.
|
Let's rephrase the question then. When will Ender be testing the solutions out? a number of the current posted solutions solve his issue with linear time functions. I understand that Ender is busy as he has already mentioned that he could not make a posting of July's winner announcement. If Ender is unsatisified with the solutions, I would expect that he would post feedback so we can better aid him in his algorithms.
|
Thanks for the all the submitted solutions so far. To winner yet, but here are some responses to things that have been brought up:
is the data on bots unauthorized correct
No! I should have mentioned this, but the table on BU is the bots2 leveling data. It's quite close to what bots4 uses, but not the same. Treat the function posted in my OP as the source of truth.
Well I would assume it goes on until Ender gets a satisfactory solution or figures out something himself. So there probably isn't a set deadline.
That is correct. I've been going through the responses, but it's taking time to do testing because the replacement function has to be 100% identical in terms of input/output to the old one. As you can imagine, a new function that produces a new result for any exp value could wreck untold amounts of havoc. There are a lot of corner cases and off-by-one errors to watch out for, so I'm using a set of automated test cases to compare the old version to the proposed new versions.
If Ender is unsatisified with the solutions, I would expect that he would post feedback so we can better aid him in his algorithms.
Here's some preliminary feedback on each submitted solution:
Saiyan Z - 2012-07-29 16:08:03
You may be correct here, but solving for $level yourself would be necessary for it to be accepted.
Petertjuh4 - 2012-07-29 16:19:27
This looks to be the same original loop, but rejiggered. This will still be slow because it's ultimately still looping n times to get to level n, making it linear time, not constant time.
shoyuken - 2012-07-29 16:36:05
I played around with this a little last night and it's looking very promising. I had to make some adjustments and I ran into the problem that seems to have been corrected in your latest post, but haven't had a chance to verify.
Tauren - 2012-07-29 17:27:02
This also looks like a promising solution, but I haven't had a chance to go through it closely because I'm focused on shoyuken's solution right now.
Alan - 2012-07-29 22:07:14
This also looks promising, but haven't looked at it closely yet because I'm focused on shoyuken's solution right now. Two high-level comments:
Readability counts when writing code. Four if/else blocks is preferable to quadruple-nested ternary statements because they are easier to understand at a glance (shoyuken's solution does a good job of this). Submitting a separate solution that has been scrunched onto a single line is another red flag. 99%+ of the slowdown in the original function is because it has to loop n times to return level n, not because it's on multiple lines. On measuring the efficiency of your new function, measuring the running time of a single call isn't a good benchmark. It has to be compared to the old function for it to have meaning and it needs to be run a large number of times, to the point where the old function runs for at least a few seconds. A good benchmark would show something like "ran old function 10k times, took 3s, ran new function 10k times, took 0.1s".
|
So, because my function is able to take less space, it gets flagged as a no go?
Awesome.
Mine is simple, yet elegant.
|
So, because my function is able to take less space, it gets flagged as a no go?
Awesome.
No, that's not what I said. I stated it was a promising-looking solution, but that I hadn't looked at it closely yet because I'm focused on shoyuken's solution. I'm examining these in the order they were submitted.
Mine is simple, yet elegant.
No, it's convoluted and messy. This is not a reflection or statement about you as a person. This is a statement about your code, so there's no need to get touchy because of a bruised ego. Take the constructive feedback I gave you and use it to write better code in the future.
|
|
|
No, it's convoluted and messy.
lolz.
|
|
|
Congrats shoyuken! With a few small tweaks, I got his pseudocode to work and confirmed it produces the same results as the old function in a wide variety of cases.
This code resulted in close to a 2 order of magnitude speed performance over the old one. I loaded the HoF sorted by level 3 times with the old code and 3 times with the new code for comparison. With the old code, the expToLevel() function had 733ms, 719ms, and 597ms spent on it. With the new code, it had 18ms, 16ms, 13ms spent on it. Quite an improvement!
Here's the new function. I pulled out the constant calculation to a static initalizer for reuse since they'll never change.
public static function init() {
self::$dropoff36 = 300 * pow(1.3, 34);
self::$dropoff81 = self::$dropoff36 * pow(1.1, 45);
self::$dropoff151 = self::$dropoff81 * pow(1.08, 70);
self::$dropoff181 = self::$dropoff151 * pow(1.05, 30);
}
/**
* Optimized expToLevel() function.
*
* @VisibleForTesting
*/
public function expToLevel($experience) {
if ($experience < 300){
return 1;
} else if ($experience < self::$dropoff36){
return (int) (2 + floor(log($experience / 300, 1.3)));
} else if ($experience < self::$dropoff81){
return (int) (36 + floor(log($experience / self::$dropoff36, 1.1)));
} else if ($experience < self::$dropoff151){
return (int) (81 + floor(log($experience / self::$dropoff81, 1.08)));
} else if ($experience < self::$dropoff181){
return (int) (151 + floor(log($experience / self::$dropoff151, 1.05)));
} else {
return (int) (181 + floor(log($experience / self::$dropoff181, 1.03)));
}
}
Since it's obviously extremely important that this code produce the exact same results as the old one, I wrote some fairly extensive test cases to confirm this. Here's what I used (using the PHPUnit framework) for those curious:
/**
* Tests that the new expToLevel() implementation produces the same results as
* the old one.
*/
public function testExpToLevel() {
// Test a handful of low exp values.
for ($exp = -2; $exp < 500; $exp += 5) {
parent::assertEquals(Experience::expToLevel_LEGACY($exp),
Experience::expToLevel($exp),
'Level for exp value ' . $exp . ' does not match.');
}
// Test a handful of higher exp values.
for ($exp = 1000; $exp <= 100000; $exp += 1000) {
parent::assertEquals(Experience::expToLevel_LEGACY($exp),
Experience::expToLevel($exp),
'Level for exp value ' . $exp . ' does not match.');
}
// Test a handful of much higher exp values.
for ($exp = 1000 * 1000 * 1000;
$exp <= 100 * 1000 * 1000 * 1000; $exp += 1000 * 1000 * 1000) {
parent::assertEquals(Experience::expToLevel_LEGACY($exp),
Experience::expToLevel($exp),
'Level for exp value ' . $exp . ' does not match.');
}
// Test +/-2 exp from each level boundary.
for ($level = 2; $level <= 200; $level++) {
$expAtLevel = Experience::levelToExp($level);
$seenPreviousLevel = false;
$seenCurrentLevel = false;
for ($exp = $expAtLevel - 2; $exp <= $expAtLevel + 2; $exp++) {
$legacyLevel = Experience::expToLevel_LEGACY($exp);
parent::assertEquals($legacyLevel, Experience::expToLevel($exp),
'Level for exp value ' . $exp . ' does not match.');
if ($legacyLevel == $level - 1) {
$seenPreviousLevel = true;
} else if ($legacyLevel == $level) {
$seenCurrentLevel = true;
} else {
parent::fail('Unexpected level: ' . $legacyLevel .
', while testing ' . $level);
}
}
parent::assertTrue($seenPreviousLevel,
'Didn\'t see previous level when testing: ' . $level . '.');
parent::assertTrue($seenCurrentLevel,
'Didn\'t see current level when testing: ' . $level . '.');
}
}
Congrats to shoyuken once again, and enjoy the 3 free stars. Others that submitted solutions, thank you very much as well! And other players that have no clue what is going on, enjoy the improved performance. :)
And of course please alert me to anything unusual you notice with this change in. It's an extremely low-level function used in countless places, so it could cause all sorts of problems if it's wrong. I've gone through pretty exhaustive measures to ensure it will behave the exact same way in all cases, but software bugs are an inevitable reality of programming, so be on the lookout.
|
Nice :) And it does load faster.
|
grats shoy, can i borrow a few stars? :)
|
2
