# What is the best strategy for Cookie-Clicker-esque games?

Today, I stumbled across the game Cookie Clicker, which I recommend you avoid until you have at least a few hours of time to waste.

The basic idea behind the game is this: You have a large stash of currency, which constantly increases at the given rate. At any given time, you have a series of upgrades, each of which has a cost $c_n$ and each of which has production value $p_n$. Upon purchasing an upgrade, the cost is deducted from my bank, and the rate of income is increased by the production value.

For example, if I have $1,000$ cookies increasing at a rate of $10$ cookies per second, I could purchase an upgrade $(150,2)$ which will have an end result result of $850$ cookies increasing at $12$ cookies per second.

I stumbled across this question which asked about one possible heuristic, but the heuristic in question was proven to have some flaws. (I also stole much of my notation from there)

I found the following formula to give the "time improvement" of any single upgrade, which is the amount of time that will be saved by purchasing that upgrade.

$$\text{Time Improvement} =\frac{g-x+\text{min}(0,x-c_1)}{p_0}-\frac{g-x+\text{min}(c_1,x)}{p_0+p_1}$$ Where $p_0$ is current production rate, $x$ is my current stash, and $g$ is the goal as to how many total cookies I want to have. Basically, this takes into account how long it is expected to take at the current and future rate, and how long it will take to re-earn the spent money/wait to earn the money to spend. Also, larger values are considered better.

From this, my strategy has been to purchase the upgrade with the highest time improvement. If I do not yet have enough money to buy the required upgrade, I set that upgrade's cost as my current goal and repeat the strategy. I don't think this is optimal though.

Although the game has no defined end, I am going set a goal of $4$ billion cookies, enough to buy the antimatter condenser. Assume that I have an initial rate of $0.1$ cookies per second. Here is the list of main upgrades in the game, although there are several other powerups:

Cost per item, Increase of cookies per second
15, 0.1
100, 0.5
500, 4
3000, 10
10000, 40
40000, 100
200000, 400
1666666, 6666
123456789, 98765


Upon purchasing an upgrade, the cost of that upgrade increases by $15\%$, although the production value remains the same.

What is the best strategy for games similar to this? Given a list of upgrades, how should I make my purchases to minimize the time it takes to reach four billion?

-
There's also selling, which was part of a possibly faulty strategy I used during those two days of my addiction to this game. –  Karl Kronenfeld Oct 14 '13 at 3:14
When does the game end? I mean does it end after a known fixed time from starting or does it end after a known number of purchases? Also are the set of upgrades fixed, meaning from start to end you have a fixed set of upgrades available and once you purchase an upgrade it vanishes from the set? –  triomphe Oct 14 '13 at 3:20
In the question you link to, it says that an upgrade takes some time to take effect, which depends on your current production rate. Here it doesn't. That seems like it could well change things. –  Ross Millikan Oct 14 '13 at 3:28
Strictly speaking, the game has no end. The general goal is to increase the production rate to be as high as possible, as quickly as possible. Also, you can purchase the same upgrade multiple times, but the cost increases 15% each time while the production value remains constant. –  PhiNotPi Oct 14 '13 at 3:31
There's no explicit winning condition, so it's up to the player to set goals for himself. To a good first approximation we could say that one strategy dominates over another if the first leads to production rate $X$ no later than the second for all sufficiently large $X$. It's not obvious that there is a globally best strategy under this definition -- though a concrete argument that there isn't would certainly be an interesting answer. (This could be because there's a limiting performance that can only be approached asymptotically, or there are two maximal but uncomparable strategies). –  Henning Makholm Oct 14 '13 at 13:16

You said you were looking for the best time improvement, but the object of the game is to maximize your cookie count. With a long-term strategy you can play the game in bursts by periodically choosing an optimal investment, then letting it run by itself in a background tab for the subsequent period of time.

So let's choose an idle period $T$ of 1 hour or 3600 seconds. The goal then is to maximize your score $C(t)$ at $t=T$ by investing in terms that contribute to $C$, but with the restriction that $C(t) \ge 0$ always. The terms of $C$ correspond to the investments in factories (cursor, grandma, ...).

You can invest in a term $nBt$ where $B$ is the factory's base yield (e.g. grandmas are 15) and $n$ is the number of factories you invested in. However the $i$th factory costs $P\times(1.15)^{i-1}$ where $P$ is the first price. The cost then of $n$ factories is the sum of exponenentials:

$$\sum_{i=1}^n P\times(1.15)^{i-1} = P {1 - (1.15)^n \over 1 - 1.15} \\ = {P\over 0.15} \times (1.15^n - 1)$$

Assuming you had no factories to start with, and you want to purchase (unknown) $n$ factories to leave it alone for (known) $T$ seconds. Your net gain $G(n)$ at that time is

$$G(n) = nBT - {P\over 0.15} \times (1.15^n - 1)$$ The best $n$ in this isolated case is probably found where $G'(n)=0$: $$BT - {P\over 0.15}{(1.15)^n \ln 1.15 } = 0\\ n = {\ln 0.15 - \ln\ln1.15 \over \ln1.15}+ {1\over \ln1.15}\ln({BT\over P})\\ n = 0.505822 + 7.155 \times \ln({BT\over P})$$

So, the sweet spots for T=3600 are

Factory       B          P      n (for T=3600)
--------  -----   --------   ----
Cursor      0.1         15   23.2
Grandma     0.5        100   21.1
Farm          4        500   24.5
Factory      10       3000   18.2
Mine         40      10000   19.5
Shipment    100      40000   16.2
Alchemy     400     200000   14.6
Portal     6666    1666666   19.6


This roughly says that a strategy for maximizing cookies is to buy about 20 of the current best factories, go away and then come back in an hour then sell everything. Of course it doesn't cover how you get to afford the $n$ units in the first place. So I have to admit this is at best a first step towards a more complete strategy.

-

I'd suggest starting buying a few of the smaller ones if your starting out, and move up from there. You definitely want the anti-matter condenser, but those do get pricy. One strategy i have used (and am using as I'm typing this) is to let the game run on it's own for a while, come back, buy a few more things, and continue. This has proven successful on many occasions. I've used this strategy since day one and now have 90,000,000,000 cookies (and counting), and this is only day 2. I also have a a fair amount of "makers", so its not like i'm just stockpiling all my cookies.

-
It sounds like the question asker is looking for an optimal strategy + proof of optimality though, not just Cookie Clicker tips. –  Dennis Meng Feb 6 '14 at 22:34