# 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