Recently, I've been interested in the optimization of the infamous incremental game Cookie Clicker.
From Wikipedia:
The user initially clicks on a big cookie on the screen, earning one cookie per click. They can then spend cookies on buildings, which will automatically produce cookies. Upgrades can improve the efficiency of clicks and buildings, and other mechanics lead to many other ways in which the user can earn cookies. Though the game has no ending, it has hundreds of achievements, and users may aim to reach milestone numbers of cookies.
The game can be simplistically reduced to nothing more than purchasing buildings, for which creating a heuristic for optimization isn't unreasonably difficult (especially when future outcomes aren't considered). However, it gets far more complicated when other mechanics such as selling buildings to recoup costs and building upgrades (which often have multiple indirect predicates based on other buildings) are introduced.
Let's take an extremely simplified scenario—how fast can we bake 5000 cookies total?
In this simulation, I assume a generous rate of ten human clicks per second, make calculations as if human-made cookies are not discrete, and don't account for the ability to sell buildings for a 25% return on the cost.
There are a total of three buildings and three upgrades (names shorted for brevity) which can be bought for fewer than 5000 cookies:
building | cost | Δcps | upgrade | cost | unlocked w/ |
---------|------|------| --------|------|-------------|
cursor | 15 | 0.1 | C1 | 100 | 1 cursor |
grandma | 100 | 1 | C2 | 500 | 1 cursor |
farm | 1100 | 8 | G1 | 1000 | 1 grandma |
Note that the cost of buildings is $\lceil c\times1.15^{n}\rceil$ where $c$ is the base cost and $n$ is the number of that type of building already owned.
C1 and C2 double the cookies produced by the mouse and cursors, while G1 doubles the cookies produced by grandmas.
Given these parameters, this is the "optimal" path my quick-and-dirty brute-force simulation found, clocking in at approximately 117.4 seconds:
time | cps | cost |
-------|------|------|
0.00 | 10 | | Begin clicking at 10 clicks per second (ergo 10 cookies per second).
1.50 | 10.1 | 15 | Buy the first cursor. This unlocks C1 and C2.
11.40 | 20.2 | 100 | Buy C1, doubling mouse/cursor production.
36.15 | 40.4 | 500 | Buy C2, doubling mouse/cursor production.
36.58 | 40.8 | 18 | Buy the second cursor.
37.07 | 41.2 | 20 | Buy the third cursor.
37.62 | 41.6 | 23 | Buy the fourth cursor.
38.25 | 42.0 | 27 | Buy the fifth cursor.
38.97 | 42.4 | 31 | Buy the sixth cursor.
39.79 | 42.8 | 35 | Buy the seventh cursor.
40.72 | 43.2 | 40 | Buy the eighth cursor.
43.03 | 44.2 | 100 | Buy the first grandma. This unlocks G1.
44.07 | 44.6 | 46 | Buy the ninth cursor.
46.65 | 45.6 | 115 | Buy the second grandma.
49.55 | 46.6 | 133 | Buy the third grandma.
52.82 | 47.6 | 153 | Buy the fourth grandma.
53.92 | 48.0 | 53 | Buy the tenth cursor.
57.57 | 49.0 | 175 | Buy the fifth grandma.
61.67 | 50.0 | 202 | Buy the sixth grandma.
81.67 | 56.0 | 1000 | Buy G1, doubling grandma production.
85.80 | 58.0 | 232 | Buy the seventh grandma.
90.39 | 60.0 | 267 | Buy the eighth grandma.
95.49 | 62.0 | 306 | Buy the ninth grandma.
101.16 | 64.0 | 352 | Buy the tenth grandma.
107.48 | 66.0 | 405 | Buy the eleventh grandma.
114.53 | 68.0 | 466 | Buy the twelfth grandma.
115.42 | 68.4 | 61 | Buy the eleventh cursor.
116.44 | 68.8 | 70 | Buy the twelfth cursor.
117.39 | 68.8 | | 5000 cookies baked! Question life choices.
(Interesting that farms are not considered. They have been a historically weak building.)
Just this small microcosm of the real game, however, required about 500 million brute force attempts to generate this strategy. This is obviously not practical and potentially suboptimal, and—most importantly—really unsatisfying. There must be a mathematical approach to optimizing this game and other systems that work like it, but I have yet to find such models.
Best Answer
Suppose that you have a sequence of purchases. Prove that the optimum time to buy each element in the sequence is as soon as you can afford it.
With that lemma in the bank, you can consider a set of states where a state is a tuple of the number of cursors, grannies, farms, cursor upgrades, and granny upgrades purchased. Form a digraph where each state has edges to the state with one more cursor, the state with one more granny, etc. Therefore each state has up to five edges. Add a new vertex "Target" and add an edge from each state to the target. Give the edges weights as the cost of the upgrade divided by the production rate of the source state.
Then you just need to do a standard shortest path search (Dijkstra's algorithm, A*, etc) in the graph. This should be much much much more efficient than the brute force you describe.