10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to MSE! Nice question. I am adding the tag Operations Research, because that is exactly what you are after here. Unfortunately, I don't know enough of it to really help, but I bet someone else will. $\endgroup$ – N. Owad Jan 8 at 3:41
  • $\begingroup$ This could be written much more crisply to make it more accessible. Sate the rules-you buy buildings of one of three types and each building produces cookies. Presumably $\Delta$cps is the number of cookies per second that are produced by each building. You talk of cookies produced by the mouse, but I don't see that defined anywhere. Do you get one per click? $\endgroup$ – Ross Millikan Jan 8 at 3:48
  • 1
    $\begingroup$ @RossMillikan: In this toy example it looks like you get one per click. (In the actual game there are improvements unlocked later in the game that award multipliers on that too). $\endgroup$ – Henning Makholm Jan 8 at 3:53
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Incidentally, my quick-and-dirty implementation of this finds a route which ends with 16 cursors, 11 grannies, and all the upgrades in 117.28 seconds. The discrepancy from Poyo's answer is probably due to rounding issues. $\endgroup$ – Peter Taylor Jan 15 at 17:31
  • $\begingroup$ Oh, and it considers in total only 3601 states. $\endgroup$ – Peter Taylor Jan 16 at 8:46
  • $\begingroup$ Did you use a pruning algorithm of any kind? That seems like an unusually small number of states for that many steps. $\endgroup$ – Poyo Jan 19 at 21:13
  • 1
    $\begingroup$ No pruning, but the states are only generated on demand. $\endgroup$ – Peter Taylor Jan 19 at 21:21
  • $\begingroup$ What kind of search did you perform? If A*, did you use a heuristic that could be considered admissible? $\endgroup$ – Poyo Jan 28 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.