How can I mathematically model and analyze an incremental game like Cookie Clicker?
$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 ctimes1.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.
optimization recreational-mathematics operations-research popular-math
asked Jan 8 at 3:29
PoyoPoyo
1515
$endgroup$
add a comment |
$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 ctimes1.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.
optimization recreational-mathematics operations-research popular-math
asked Jan 8 at 3:29
PoyoPoyo
1515
$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
add a comment |
$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 ctimes1.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.
optimization recreational-mathematics operations-research popular-math
asked Jan 8 at 3:29
PoyoPoyo
1515
$endgroup$
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 ctimes1.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.
optimization recreational-mathematics operations-research popular-math
optimization recreational-mathematics operations-research popular-math
asked Jan 8 at 3:29
PoyoPoyo
1515
asked Jan 8 at 3:29
PoyoPoyo
1515
edited Jan 8 at 19:43
Poyo
asked Jan 8 at 3:29
PoyoPoyo
1515
asked Jan 8 at 3:29
PoyoPoyo
1515
asked Jan 8 at 3:29
PoyoPoyo
1515
1515
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
add a comment |
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
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$
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
$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
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
$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
add a comment |
1 Answer
1
active
oldest
votes
$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.
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
$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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065779%2fhow-can-i-mathematically-model-and-analyze-an-incremental-game-like-cookie-click%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
$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
add a comment |
$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.
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
$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
add a comment |
$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.
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
$endgroup$
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.
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
answered Jan 14 at 17:19
Peter TaylorPeter Taylor
8,81312341
8,81312341
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
add a comment |
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
1
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$
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$
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
$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
1
$begingroup$
No pruning, but the states are only generated on demand.
$endgroup$
– Peter Taylor
Jan 19 at 21:21
$begingroup$
No pruning, but the states are only generated on demand.
$endgroup$
– Peter Taylor
Jan 19 at 21:21
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065779%2fhow-can-i-mathematically-model-and-analyze-an-incremental-game-like-cookie-click%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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