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?
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.