Change from BCI to more efficient method

[Aktanusa]

No description provided.

[OttMatiisen]

May I suggest a quick solution while more efficient method is in development:
While using BCI, find the best building/upgrade and all buildings/upgrades that are cheaper than the aforementioned unit.
Then calculate time and cookies to get to that upgrade from zero cookies
After that, start comparing those numbers with cheaper buildings/upgrades to find out, if buying that building in the meantime would get you to that number of cookies faster.
If that's true, tag that building/upgrade with green and start comparing all over again until comparing the green unit with cheapest unit is done.
(Apologies, I'm not good at giving explanations even in my native language)

[Aktanusa]

Hmm, if I understood you correctly, did you want me to change it in the meantime to cost/cps + cost/Δ cps? Basically what FC is using. While that won't be hard to do, I do want to finish my research on finding an even more efficient way, programming wise. My current plan is to maybe have 3 settings. 1. BCI, 2. cost/cps + cost/Δ cps. 3. This more efficient way. I choose this is in terms of computation complexity. 3 is the most complex so Cookie Monster may run real slow on slower computers that can't handle it. 2 is less complex, and the least is 1.

[YoavKa]

The idea of having multiple settings sounds optimal to me. After looking around a bit I stumbled across this question, that shows another way to choose building order, by computing the upgrade with the best time improvement and than recursivly trying to find upgrades with positive time improvements in order to shortend the time to wait for the specific upgrade. The question: http://math.stackexchange.com/questions/525371/what-is-the-best-strategy-for-cookie-clicker-esque-games

[svschouw]

The MAX((total cost) - (current cookies), 0) / cps + (total cost)/Δcps is the correct formula. That's basically saying: "how long until I break even if I want to buy/pursue this investment". The first part is waiting how long you can buy it in seconds. The second part is the return on investment in seconds.

I've implemented a version on my own fork on 86463f6. Feel free to use whole or part of this code.

[Aktanusa]

Thanks @svschouw. Though again, that's only comparing two at a time which is flawed. You need to compare the whole picture. There are times where a<b, b<c with the original formula where the most efficient buying order isn't a, b, c. If you want an example, I can calculate one. As for doing MAX((total cost) - (current cookies), 0), I've not thought through on how this is more efficient than just cost/cps + cost/Δ cps, but I still think it isn't as efficient as comparing all buying combinations. Hopefully I made sense, lol.

[svschouw]

You're welcome @Aktanusa. I've tried my best to try and understand exactly what you meant. Unfortunately I failed in that. I do not see how this formula is comparing two at a time. This formula only contains variables for one item, which gives a number. Compare all those numbers and take the lowest, and that's your best upgrade to buy. Maybe the confusion comes from the (total cost) component, by which I meant the total cost of the given item (same as your cost), as opposed to the cookies still needed (which is (total cost) - (current cookies)). But maybe you understood that as the total cost of the two items to compare?

As for the MAX((total cost) - (current cookies), 0), this it to take into account the fact that you might already have enough cookies to buy some of the items, but not enough to buy others. (Note that my (total cost) is the same as your cost). The only problem here is the (current cookies) part, which changes every tick. But it is necessary, as you can cross the boundary it being better to buy the cheaper one now and waiting until you can buy the very expensive one at any time.

If I can reproduce my original calculations I will post them here. Unfortunately I haven't kept them after I'd found out it was a simple return on investment calculation.

[Aktanusa]

No, the total cost is still per one item. There was no confusion on that. I'll explain what I mean by comparing two items. The original cost/cps + cost/Δ cps formula was a simplification of the comparison of:

a.cost/cps + b.cost/(cps + a.cps) vs b.cost/cps + a.cost/(cps + b.cps)

(two items). When comparing three items:

a.cost/cps + b.cost/(cps + a.cps) + c.cost/(cps + a.cps + b.cps) vs a.cost/cps + c.cost/(cps + a.cps) + b.cost/(cps + a.cps + c.cps) vs b.cost/cps + a.cost/(cps + b.cps) + c.cost/(cps + a.cps + b.cps) vs b.cost/cps + c.cost/(cps + b.cps) + a.cost/(cps + b.cps + c.cps) vs c.cost/cps + a.cost/(cps + c.cps) + b.cost/(cps + a.cps + c.cps) vs c.cost/cps + b.cost/(cps + c.cps) + a.cost/(cps + b.cps + c.cps)

there is no simplification. As you also see, there is a lot more to compare which makes it even more complex to calculate. For n things to buy, there is n! comparisons. Using the simplified formula cost/cps + cost/Δ cps is fast and easy to calculate but sometimes not the most efficient as it doesn't look at all combinations. Generally though, it's pretty good. It only starts to be less efficient when there are 2 or more items that are close to the same "efficiency value". I don't have time to give you an example right now, I'll post one later.

As for using MAX((total cost) - (current cookies), 0), I understand that it is taking to account the current bank, and basically if you have all the money (cookies) in the world, you should really just do BCI like it is doing now, but with knowing that your formula is similar to cost/cps + cost/Δ cps, I still think it's still a bit off in terms of efficiency due to what I said above. I know that it's better that just BCI though, lol. You are right that with your formula needing the (current cookies) as a value can be problematic, but since "Century egg" changes the cps every 10 seconds, the recalculation happens every 10 seconds already. Hopefully all I wrote made sense again, lol.

[svschouw]

Ok, I'm starting to understand things now, partially with the help of another mathematically inclined friend. For now I'm going with the fact that my formula is "better than plain BCI" :P

There are times where a<b, b<c with the original formula where the most efficient buying order isn't a, b, c.

True, buying a could improve the the cps in such a way that now c becomes more viable than b. But the real question is whether a is always the best first option? Or is there an example where the best buying order starts with either b or c?

And that "proof" I was talking about was that a.cost/cps + b.cost/(cps + a.cps) vs b.cost/cps + a.cost/(cps + b.cps) can be simplified to cost/cps + cost/Δcps. I didn't understand you because I was confusing simplification with approximation (so I thought that you needed proof that the simplification was correct).

Also, with the help of that friend I found an easy counterexample as to why MAX((cost) - (current cookies), 0) / cps + (cost)/Δcps is still incorrect:
Given (current cookies) = 1000, a.cost = 100, a.cps = 100, b.cost = 1000, b.cps=110, cps=0.1, my formula would break down to basic BCI (since MAX(cost - cookies, 0) = 0).
But a.bci = 100/100 = 1 and b.bci 1000/110 = 9.9, which would say a is the better choice. However, first buying a would require you to wait a further 1 second to buy b, but first buying b would only require 0.9 seconds to buy a. So a, b is the best order. Basically, given the choice between only two already affordable upgrades, buy the one which gives the most increase.

But suppose you also had a third upgrade: c.cost = 400, c.cps=900 => c.bci = 2.25, it would be best to buy a and c first (cookies=500, cps=1000.1) and wait half a second to buy b.

So basically you would want to buy the best combination of upgrades which current money can buy, which is the knapsack problem, which is NP-complete, and it is not even considering options which you do not currently have enough cookies for.

Man, this problem is a lot more complicated than I originally thought. My formula seemed so intuitively good :(

TL;DR: this problem is very hard, but my formula is still a better approximation than the current BCI calculation :P

[Aktanusa]

True, buying a could improve the the cps in such a way that now c becomes more viable than b. But the real question is whether a is always the best first option? Or is there an example where the best buying order starts with either b or c?

There are example where the best buying order doesn't start with a. For example:

Current CPS = 226.5785735502662
a.cost = 747.929200617538
a.cps = 681.6778533572583
b.cost = 742.0998752732398
b.cps = 699.5548482909151
c.cost = 348.9248174870489
c.cps = 129.09762796633072

Using cost/cps + cost/Δ cps, the buying order would be:

c, b, a

taking 4.335203035965191 seconds while the better order:

b, a, c

would take 4.299844025685106 seconds.

Also, with the help of that friend I found an easy counterexample as to why MAX((cost) - (current cookies), 0) / cps + (cost)/Δcps is still incorrect:
Given (current cookies) = 1000, a.cost = 100, a.cps = 100, b.cost = 1000, b.cps=110, cps=0.1, my formula would break down to basic BCI (since MAX(cost - cookies, 0) = 0).
But a.bci = 100/100 = 1 and b.bci 1000/110 = 9.9, which would say a is the better choice. However, first buying a would require you to wait a further 1 second to buy b, but first buying b would only require 0.9 seconds to buy a. So a, b is the best order. Basically, given the choice between only two already affordable upgrades, buy the one which gives the most increase.

I think you mean the best buying order is b, a?

Yep, this is a complex problem. I really wish some math person would just figure out a best formula for us, lol. Maybe your friend can do it (heh)?

Currently, my plan is to implement a somewhat approximation of the best buying order via doing something like this:

Take a base order using cost/cps + cost/Δ cps, so for example a base could be:

a, b, c, d

Then go through all combinations of moving one item around:

moving only a:
b, a, c, d
b, c, a, d
b, c, d, a

moving only b:
b, a, c, d
a, c, b, d
a, c, d, b

moving only c:
c, a, b, d
a, c, b, d
a, b, d, c

moving only d:
d, a, b, c
a, d, b, c
a, b, d, c

And then repeat as base when a new more efficient order is found. This is n_(n-1) combinations which is a lot less than n! combinations. Now looking at my own example, I even notice even more repeats, so really it's less than n_(n-1) combinations. Hopefully again you get what I mean, but yes you brought in new complexities by figuring out what is the best order when you have the cookies to buy already, lol.

[killergege]

Maybe you could expose the problem on http://math.stackexchange.com/ ?

[Aktanusa]

Hmm, maybe.

[svschouw]

My intuition says it's something along the lines of: two upgades A and B behave better than twice their average. Given that in your example, A and B are very similar, the combination would behave better than C, whereas individually they are worse.

But I've yet to find an extreme counterexample which makes the problem very clear.

[svschouw]

Maybe you could expose the problem on http://math.stackexchange.com/ ?

There are already some questions posted: http://math.stackexchange.com/search?q=cookie+clicker
The best question seemed to be http://math.stackexchange.com/questions/478494/explain-a-surprisingly-simple-optimization-result , although it does not ask this question, but one of the "answers" identifies the same problem. It does not give a solution however.

[Aktanusa]

Nice find, and too bad there is no solution. It was an interesting read, though I get lost easily as I don't know all the terms, lol.

[svschouw]

As you mentioned this issue again and said you were a bit lazy to implement it I would at least point you to my implementation svschouw/CookieMonster@bf33a1d.

If you want I can make a proper pull request.

There are also some other goodies on my https://github.com/svschouw/CookieMonster fork, like some code to help me determine whether it's best to buy an upgrade now, or wait until I have enough "Lucky!" cookies. But those commits are pretty raw.

[Aktanusa]

I'll take a look, thanks! And sorry for the wait, this enhancement has been open for a long time now, lol. Most likely this weekend is when I will have free time.

[Aktanusa]

@svschouw I've taken a look at your code and I'm processing it now.

Off-topic: I was wondering what is Golden CPS support in your later commits?

[Aktanusa]

@svschouw I reread what you wrote above and this part "But suppose you also had a third upgrade: c.cost = 400, c.cps=900 => c.bci = 2.25..." the BCI is 400/900 = 0.4444... not 2.25 in which it should be bought first.

[svschouw]

@Aktanusa Hmm, you're right; I confused the division. I tried to make the point that in some cases buying the one that gives the most upgrade is better than the ROI (let's call it that) formula, but in other cases it isn't. Although, clearly, an upgrade with 900 cps for 400 is even the best in that regard.

@Aktanusa About the "Golden CPS support", that tries to calculate your effective CPS if you were to click on the golden/wrath cookies every time it pops up. That depends on a lot of factors, including how many cookies you have (for the Lucky! cookie), but it can be up to 30x higher than your normal CPS. It displays what the change in golden CPS would be if you buy an upgrade/building, which I mostly use to see if I should buy an upgrade/building immediately or if I should wait for more cookies.

But it's pretty raw. For example, it assumes you get a golden cookie every 120 second, taking into account lucky upgrades, but not golden cookie upgrades (those that will make it appear 5% faster for example), because the exact calculations are very tricky and expensive (since it's basically a bell curve). Also it uses some very old simulation results about cookie chains. That said, I still think it is useful. But maybe complete discussion about it is something for another topic.

[Aktanusa]

So I did some simulation with different cookies in bank amount. Using the same example as you did, building a cost 100 and adds 100 CPS, building b cost 1000 and adds 110 CPS, and building c cost 400 and adds 900 CPS with starting CPS of 0.1, here is what I got:

Bank: 0.0
a b c 1011.8938652970066
a c b 1004.995904006003
b a c 10002.812120520439
b c a 10003.73206095277
c a b 4001.1109987768023
c b a 4001.209987767037
Lowest: 1004.995904006003
Order(s): a c b

Bank: 100.0
a b c 11.89386529700666
a c b 4.995904006002997
b a c 9002.812120520439
b c a 9003.73206095277
c a b 3001.1109987768023
c b a 3001.209987767037
Lowest: 4.995904006002997
Order(s): a c b

Bank: 400.0
a b c 8.896862300003662
a c b 1.998901008999999
b a c 6002.812120520439
b c a 6003.73206095277
c a b 1.1109987768026885
c b a 1.2099877670369839
Lowest: 1.1109987768026885
Order(s): c a b

Bank: 500.0
a b c 7.897861301002663
a c b 0.9999000099990001
b a c 5002.812120520439
b c a 5003.73206095277
c a b 0.9999000099990001
c b a 1.0988890002332954
Lowest: 0.9999000099990001
Order(s): a c b, c a b

Bank: 1000.0
a b c 2.9028563059976675
a c b 0.49995000499950004
b a c 2.8121205204389934
b c a 3.7320609527694
c a b 0.49995000499950004
c b a 0.543395166214853
Lowest: 0.49995000499950004
Order(s): a c b, c a b

Bank: 1100.0
a b c 1.9038553069966684
a c b 0.3999600039996
b a c 1.9038553069966684
b c a 2.8237957393270747
c a b 0.3999600039996
c b a 0.43229639941116443
Lowest: 0.3999600039996
Order(s): a c b, c a b

Bank: 1400.0
a b c 0.4759638267491671
a c b 0.0999900009999
b a c 0.4759638267491671
b c a 0.099000099000099
c a b 0.0999900009999
c b a 0.099000099000099
Lowest: 0.099000099000099
Order(s): b c a, c b a

Bank: 1500.0
a b c 0.0
a c b 0.0
b a c 0.0
b c a 0.0
c a b 0.0
c b a 0.0
Lowest: 0.0
Order(s): a b c, a c b, b a c, b c a, c a b, c b a

[Aktanusa]

Due to talks in Issue #68, it got me thinking. Instead of using the formula max(cost - cookies in bank, 0)/cps + cost/Δ cps, why not change it to the formula max(cost - cookies in bank, 0)/cps + cost/(cps + Δ cps)? It would then really be the "Payback Period" in terms of seconds to when it will "break even". Thoughts @svschouw?

Edit: I do realize, if I change cps to average cps to include wrinklers and golden cookies, the numbers would change like crazy all the time, though.

[svschouw]

well, if you change the second component from cost/Δcps to cost/(cps + Δcps) you take the time until you have the same amount of cookies as the moment you bought it, but by everything. So if you have 90cps and you have an item of 1000 cookies giving 10 cps, it will take 10 seconds to get back to where you were. But 90% of that is due to other things you have. So the item only contributed to 100 cookies of that. And I don't think you would want that. You want to see how long it takes for the item to pay for itself.

Another way of looking at it is: if you have a very huge CPS already compared to what you can buy, right component reduces to 0, so then the algorithm basically favors the items you can buy first, regardless of profit.

Also, changing listed cps to actual (or effective) cps does not matter if the actual cps is just a constant factor over the actual cps. Because you are just reducing the result by that factor. Although it might be a good reason NOT to include an actual unit, since it's meaningless in the face of wrinklers and golden cookies. But I don't care much either way.

[Aktanusa]

Well good thing I asked! Apparently I brainfarted and thought it was just a constant 1/cps multiplication to the right side. No idea what I was thinking, lol.

I'm confused as to why I shouldn't use the average CPS. I thought using the average CPS accounts for wrinklers and golden cookies.

[svschouw]

First of all, you need to know Δecps (the change in effective cps by buying the upgrade). Otherwise you are just comparing apples and oranges. But suppose you just calculate F = ecps/cps and then do Δecps = Δcps * F. Then the eroi formula becomes eroi = max(cost - cookies, 0)/ecps + cost/Δecps = max(cost - cookies, 0)/(Fcps) + cost/(FΔcps) = [max(cost - cookies, 0)/cps + cost/Δcps] / F = roi / F.
So you're just multiplying the current ROI calculation with a constant 1/F factor. It really doesn't matter, but like you said: the numbers will fluctuate wildly which I'm not a fan of.

[Aktanusa]

Hmm, very good point. So in the end the formula still is the same. Thanks again for your thoughts! I'm no math person, lol.

[Aktanusa]

While it is a common multiplier so the order wouldn't change, but currently any type of frenzy changes the numbers since the current CPS is calculated that way. A fix would be just undo the multiplier, but should I do it?

[svschouw]

I am a bit of a math person :). Good point about the frenzy. I remember a bit of code which undid the frenzy, but that could just be my own golden CPS calculations. So yeah, if your goal is a stable number, then undoing the frenzy multiplier could be a good idea.

[Aktanusa]

How about adding wrinklers to the formula?

max(cost - cookies in bank - wrinkler sucked cookies, 0)/cps + cost/Δ cps

[svschouw]

You could technically count them as cookies you have to spend, so sure.

[Aktanusa]

I'll probably make it an option to add wrinkler sucked cookies to bank in calculations

[DanielNoord]

The only problem in this thread that has not been solved can be found in #4
Therefore, I am closing this issue!

[Aktanusa]

@DanielNoord Actually, our current calculation is not perfect. I actually wrote many years ago a solution in pure Java using dynamic programming on a way to find an even more efficient method. If you would like to implement it, I can go find that code and post it somewhere. It's pretty CPU intensive though. Up to you if you want to reopen this.

[DanielNoord]

Hm, could you explain what is wrong with the current calculation?

I am not really in favor of making CM more CPU intensive though, so I am not sure if I would like to add that.

[Aktanusa]

True, buying a could improve the the cps in such a way that now c becomes more viable than b. But the real question is whether a is always the best first option? Or is there an example where the best buying order starts with either b or c?

There are example where the best buying order doesn't start with a. For example:

Current CPS = 226.5785735502662
a.cost = 747.929200617538
a.cps = 681.6778533572583
b.cost = 742.0998752732398
b.cps = 699.5548482909151
c.cost = 348.9248174870489
c.cps = 129.09762796633072

Using cost/cps + cost/Δ cps, the buying order would be:

c, b, a

taking 4.335203035965191 seconds while the better order:

b, a, c

would take 4.299844025685106 seconds.

Also, with the help of that friend I found an easy counterexample as to why MAX((cost) - (current cookies), 0) / cps + (cost)/Δcps is still incorrect:
Given (current cookies) = 1000, a.cost = 100, a.cps = 100, b.cost = 1000, b.cps=110, cps=0.1, my formula would break down to basic BCI (since MAX(cost - cookies, 0) = 0).
But a.bci = 100/100 = 1 and b.bci 1000/110 = 9.9, which would say a is the better choice. However, first buying a would require you to wait a further 1 second to buy b, but first buying b would only require 0.9 seconds to buy a. So a, b is the best order. Basically, given the choice between only two already affordable upgrades, buy the one which gives the most increase.

I think you mean the best buying order is b, a?

Yep, this is a complex problem. I really wish some math person would just figure out a best formula for us, lol. Maybe your friend can do it (heh)?

Currently, my plan is to implement a somewhat approximation of the best buying order via doing something like this:

Take a base order using cost/cps + cost/Δ cps, so for example a base could be:

a, b, c, d

Then go through all combinations of moving one item around:

moving only a:
b, a, c, d
b, c, a, d
b, c, d, a

moving only b:
b, a, c, d
a, c, b, d
a, c, d, b

moving only c:
c, a, b, d
a, c, b, d
a, b, d, c

moving only d:
d, a, b, c
a, d, b, c
a, b, d, c

And then repeat as base when a new more efficient order is found. This is n_(n-1) combinations which is a lot less than n! combinations. Now looking at my own example, I even notice even more repeats, so really it's less than n_(n-1) combinations. Hopefully again you get what I mean, but yes you brought in new complexities by figuring out what is the best order when you have the cookies to buy already, lol.

I already explained it in this thread. I basically implemented this in Java.

[DanielNoord]

Hmm this still seems like quite a bit of computations.

I was wondering in what scenario's "buying current lowest pp building" is not the optimal strategy.
Is the situation you describe an actual real scenario in the game? Or is it just imagined?
And if it is, can we describe the situation in general? For example, "When building a and b are on the same level".

The only situation I currently know is when "A building can reach the x amount of building achievement".
This situation would be fairly easy to implement (I think). We can cache the cookies needed to reach the next achievement threshold and check during calculation of PP's for each building if the user has passed the threshold and change the pp accordingly.
We could even make this the standard behavior: 1) Cache cookies till next threshold, 2) Compute PP of going to threshold, 3) Compare threshold-pp with next-building-pp, 4) if thershold-pp is lower show that one.

I believe this will be the most important moment when "buying current lowest pp building" is not the best strategy, but I am not sure. So please do tell if there are any other situation where it is not the best strategy and if they can be generalized.

[Aktanusa]

To be honest, it is just in theory. The problem is, I don't really have a way to test if it will ever happen in game. This has nothing to do with chain buying yet either. That's a different issue.

Off topic: For chain buying, like you are thinking, we would need to calculate for every achievement not already earned and store it as cache that would be needed to recalculated every time something changes. I had ideas, but never got already to implementing them. The other old popular addon, FrozenCookies, already had chain buying there.

[DanielNoord]

Do we have the old code of FrozenCookies somewhere?

[Aktanusa]

It's on GitHub somewhere.