Chance to win a game calculate with Dynamic prorgamming
1
Assume we have a bag with coins. Some of them have value 1 and same have value 2. It's guaranteed that the bag has at least one coin of value 2.
Alice and Bob play a game. Alice always starts. You alternately draw a coin and the player who draws the last coin with value 2 wins the game.
Now I am interested in the probability that Alice wins the game if there are x coins with value 1 and y coins with value 2.
I know how to solve this with normal probability theory. But I'm in the process of fully understanding Dynamic programming, so I'm interested in a Dynamic programming approach.
algorithm
asked Nov 23 '18 at 22:39
raegraeg
61
add a comment |
1
Assume we have a bag with coins. Some of them have value 1 and same have value 2. It's guaranteed that the bag has at least one coin of value 2.
Alice and Bob play a game. Alice always starts. You alternately draw a coin and the player who draws the last coin with value 2 wins the game.
Now I am interested in the probability that Alice wins the game if there are x coins with value 1 and y coins with value 2.
I know how to solve this with normal probability theory. But I'm in the process of fully understanding Dynamic programming, so I'm interested in a Dynamic programming approach.
algorithm
asked Nov 23 '18 at 22:39
raegraeg
61
You did not explicitly state a question. Did you tried anything so far? It's likely that nobody will post an answer without seeing any contribution from your side
– Kristianmitk
Nov 23 '18 at 23:35
add a comment |
1
1
1
Assume we have a bag with coins. Some of them have value 1 and same have value 2. It's guaranteed that the bag has at least one coin of value 2.
Alice and Bob play a game. Alice always starts. You alternately draw a coin and the player who draws the last coin with value 2 wins the game.
Now I am interested in the probability that Alice wins the game if there are x coins with value 1 and y coins with value 2.
I know how to solve this with normal probability theory. But I'm in the process of fully understanding Dynamic programming, so I'm interested in a Dynamic programming approach.
algorithm
asked Nov 23 '18 at 22:39
raegraeg
61
Assume we have a bag with coins. Some of them have value 1 and same have value 2. It's guaranteed that the bag has at least one coin of value 2.
Alice and Bob play a game. Alice always starts. You alternately draw a coin and the player who draws the last coin with value 2 wins the game.
Now I am interested in the probability that Alice wins the game if there are x coins with value 1 and y coins with value 2.
I know how to solve this with normal probability theory. But I'm in the process of fully understanding Dynamic programming, so I'm interested in a Dynamic programming approach.
algorithm
algorithm
asked Nov 23 '18 at 22:39
raegraeg
61
asked Nov 23 '18 at 22:39
raegraeg
61
asked Nov 23 '18 at 22:39
raegraeg
61
asked Nov 23 '18 at 22:39
raegraeg
61
asked Nov 23 '18 at 22:39
raegraeg
61
61
You did not explicitly state a question. Did you tried anything so far? It's likely that nobody will post an answer without seeing any contribution from your side
– Kristianmitk
Nov 23 '18 at 23:35
add a comment |
You did not explicitly state a question. Did you tried anything so far? It's likely that nobody will post an answer without seeing any contribution from your side
– Kristianmitk
Nov 23 '18 at 23:35
You did not explicitly state a question. Did you tried anything so far? It's likely that nobody will post an answer without seeing any contribution from your side
– Kristianmitk
Nov 23 '18 at 23:35
You did not explicitly state a question. Did you tried anything so far? It's likely that nobody will post an answer without seeing any contribution from your side
– Kristianmitk
Nov 23 '18 at 23:35
add a comment |
1 Answer
1
active
oldest
votes
1
Pseudocode: count the amount of ways alice and bob win, then you can get probability with that. Using quite a bit of notation abuse like booleans being 0 and 1
dp (x1, x2, isAliceTurn):
if x1 < 0: # last move was not actually a valid move
return <0, 0>
if x2 == 0: # game ended
return <!isAliceTurn, isAliceTurn>
# we can either remove a coin of type x1 or of type x2
return dp(x1 - 1, x2, !isAliceTurn) + dp(x1, x2 - 1, !isAliceTurn)
aliceWins, BobWins = dp(x1, x2, true)
print(aliceWins/(BobWins + aliceWins))
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
Thank you! But I don't see why this is DP solution. Shouldn't it be the other way around a from the smaller cases to the larger to be able to reuse calculations?
– raeg
Nov 24 '18 at 14:54
@raeg DP solutions can either be bottom up (smaller cases first, then big) which does not require recursion and needs to be done in a special order and the other type if top down, where you use recursion to solve big problems with smaller ones, and does not require thinking the order you need to do it. This is a top down approach
– juvian
Nov 24 '18 at 15:43
You're right, I hadn't thought of that. I don't understand your notation yet. What exactly do you mean by <0,0> and <!isAliceTurn, isAliceTurn> ? Does that mean that I have two variable aliceWins=0 and bobWins=0 and <0,0> at the beginning I add to both 0 and at <!isAliceTurn, isAliceTurn> I add only to one of the two 1 depending on who was just on?
– raeg
Nov 24 '18 at 17:24
@raeg isAliceTurn is just a boolean variable, when true <!isAliceTurn, isAliceTurn> is equivalent to <0, 1> (alice looses and bob wins) and when false to <1, 0> (alice wins and bob looses)
– juvian
Nov 24 '18 at 19:15
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
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%2fstackoverflow.com%2fquestions%2f53453584%2fchance-to-win-a-game-calculate-with-dynamic-prorgamming%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
1
Pseudocode: count the amount of ways alice and bob win, then you can get probability with that. Using quite a bit of notation abuse like booleans being 0 and 1
dp (x1, x2, isAliceTurn):
if x1 < 0: # last move was not actually a valid move
return <0, 0>
if x2 == 0: # game ended
return <!isAliceTurn, isAliceTurn>
# we can either remove a coin of type x1 or of type x2
return dp(x1 - 1, x2, !isAliceTurn) + dp(x1, x2 - 1, !isAliceTurn)
aliceWins, BobWins = dp(x1, x2, true)
print(aliceWins/(BobWins + aliceWins))
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
Thank you! But I don't see why this is DP solution. Shouldn't it be the other way around a from the smaller cases to the larger to be able to reuse calculations?
– raeg
Nov 24 '18 at 14:54
@raeg DP solutions can either be bottom up (smaller cases first, then big) which does not require recursion and needs to be done in a special order and the other type if top down, where you use recursion to solve big problems with smaller ones, and does not require thinking the order you need to do it. This is a top down approach
– juvian
Nov 24 '18 at 15:43
You're right, I hadn't thought of that. I don't understand your notation yet. What exactly do you mean by <0,0> and <!isAliceTurn, isAliceTurn> ? Does that mean that I have two variable aliceWins=0 and bobWins=0 and <0,0> at the beginning I add to both 0 and at <!isAliceTurn, isAliceTurn> I add only to one of the two 1 depending on who was just on?
– raeg
Nov 24 '18 at 17:24
@raeg isAliceTurn is just a boolean variable, when true <!isAliceTurn, isAliceTurn> is equivalent to <0, 1> (alice looses and bob wins) and when false to <1, 0> (alice wins and bob looses)
– juvian
Nov 24 '18 at 19:15
add a comment |
1
Pseudocode: count the amount of ways alice and bob win, then you can get probability with that. Using quite a bit of notation abuse like booleans being 0 and 1
dp (x1, x2, isAliceTurn):
if x1 < 0: # last move was not actually a valid move
return <0, 0>
if x2 == 0: # game ended
return <!isAliceTurn, isAliceTurn>
# we can either remove a coin of type x1 or of type x2
return dp(x1 - 1, x2, !isAliceTurn) + dp(x1, x2 - 1, !isAliceTurn)
aliceWins, BobWins = dp(x1, x2, true)
print(aliceWins/(BobWins + aliceWins))
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
Thank you! But I don't see why this is DP solution. Shouldn't it be the other way around a from the smaller cases to the larger to be able to reuse calculations?
– raeg
Nov 24 '18 at 14:54
@raeg DP solutions can either be bottom up (smaller cases first, then big) which does not require recursion and needs to be done in a special order and the other type if top down, where you use recursion to solve big problems with smaller ones, and does not require thinking the order you need to do it. This is a top down approach
– juvian
Nov 24 '18 at 15:43
You're right, I hadn't thought of that. I don't understand your notation yet. What exactly do you mean by <0,0> and <!isAliceTurn, isAliceTurn> ? Does that mean that I have two variable aliceWins=0 and bobWins=0 and <0,0> at the beginning I add to both 0 and at <!isAliceTurn, isAliceTurn> I add only to one of the two 1 depending on who was just on?
– raeg
Nov 24 '18 at 17:24
@raeg isAliceTurn is just a boolean variable, when true <!isAliceTurn, isAliceTurn> is equivalent to <0, 1> (alice looses and bob wins) and when false to <1, 0> (alice wins and bob looses)
– juvian
Nov 24 '18 at 19:15
add a comment |
1
1
1
Pseudocode: count the amount of ways alice and bob win, then you can get probability with that. Using quite a bit of notation abuse like booleans being 0 and 1
dp (x1, x2, isAliceTurn):
if x1 < 0: # last move was not actually a valid move
return <0, 0>
if x2 == 0: # game ended
return <!isAliceTurn, isAliceTurn>
# we can either remove a coin of type x1 or of type x2
return dp(x1 - 1, x2, !isAliceTurn) + dp(x1, x2 - 1, !isAliceTurn)
aliceWins, BobWins = dp(x1, x2, true)
print(aliceWins/(BobWins + aliceWins))
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
Pseudocode: count the amount of ways alice and bob win, then you can get probability with that. Using quite a bit of notation abuse like booleans being 0 and 1
dp (x1, x2, isAliceTurn):
if x1 < 0: # last move was not actually a valid move
return <0, 0>
if x2 == 0: # game ended
return <!isAliceTurn, isAliceTurn>
# we can either remove a coin of type x1 or of type x2
return dp(x1 - 1, x2, !isAliceTurn) + dp(x1, x2 - 1, !isAliceTurn)
aliceWins, BobWins = dp(x1, x2, true)
print(aliceWins/(BobWins + aliceWins))
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
answered Nov 23 '18 at 23:48
juvianjuvian
13.3k22026
13.3k22026
Thank you! But I don't see why this is DP solution. Shouldn't it be the other way around a from the smaller cases to the larger to be able to reuse calculations?
– raeg
Nov 24 '18 at 14:54
@raeg DP solutions can either be bottom up (smaller cases first, then big) which does not require recursion and needs to be done in a special order and the other type if top down, where you use recursion to solve big problems with smaller ones, and does not require thinking the order you need to do it. This is a top down approach
– juvian
Nov 24 '18 at 15:43
You're right, I hadn't thought of that. I don't understand your notation yet. What exactly do you mean by <0,0> and <!isAliceTurn, isAliceTurn> ? Does that mean that I have two variable aliceWins=0 and bobWins=0 and <0,0> at the beginning I add to both 0 and at <!isAliceTurn, isAliceTurn> I add only to one of the two 1 depending on who was just on?
– raeg
Nov 24 '18 at 17:24
@raeg isAliceTurn is just a boolean variable, when true <!isAliceTurn, isAliceTurn> is equivalent to <0, 1> (alice looses and bob wins) and when false to <1, 0> (alice wins and bob looses)
– juvian
Nov 24 '18 at 19:15
add a comment |
Thank you! But I don't see why this is DP solution. Shouldn't it be the other way around a from the smaller cases to the larger to be able to reuse calculations?
– raeg
Nov 24 '18 at 14:54
@raeg DP solutions can either be bottom up (smaller cases first, then big) which does not require recursion and needs to be done in a special order and the other type if top down, where you use recursion to solve big problems with smaller ones, and does not require thinking the order you need to do it. This is a top down approach
– juvian
Nov 24 '18 at 15:43
You're right, I hadn't thought of that. I don't understand your notation yet. What exactly do you mean by <0,0> and <!isAliceTurn, isAliceTurn> ? Does that mean that I have two variable aliceWins=0 and bobWins=0 and <0,0> at the beginning I add to both 0 and at <!isAliceTurn, isAliceTurn> I add only to one of the two 1 depending on who was just on?
– raeg
Nov 24 '18 at 17:24
@raeg isAliceTurn is just a boolean variable, when true <!isAliceTurn, isAliceTurn> is equivalent to <0, 1> (alice looses and bob wins) and when false to <1, 0> (alice wins and bob looses)
– juvian
Nov 24 '18 at 19:15
Thank you! But I don't see why this is DP solution. Shouldn't it be the other way around a from the smaller cases to the larger to be able to reuse calculations?
– raeg
Nov 24 '18 at 14:54
Thank you! But I don't see why this is DP solution. Shouldn't it be the other way around a from the smaller cases to the larger to be able to reuse calculations?
– raeg
Nov 24 '18 at 14:54
@raeg DP solutions can either be bottom up (smaller cases first, then big) which does not require recursion and needs to be done in a special order and the other type if top down, where you use recursion to solve big problems with smaller ones, and does not require thinking the order you need to do it. This is a top down approach
– juvian
Nov 24 '18 at 15:43
@raeg DP solutions can either be bottom up (smaller cases first, then big) which does not require recursion and needs to be done in a special order and the other type if top down, where you use recursion to solve big problems with smaller ones, and does not require thinking the order you need to do it. This is a top down approach
– juvian
Nov 24 '18 at 15:43
You're right, I hadn't thought of that. I don't understand your notation yet. What exactly do you mean by <0,0> and <!isAliceTurn, isAliceTurn> ? Does that mean that I have two variable aliceWins=0 and bobWins=0 and <0,0> at the beginning I add to both 0 and at <!isAliceTurn, isAliceTurn> I add only to one of the two 1 depending on who was just on?
– raeg
Nov 24 '18 at 17:24
You're right, I hadn't thought of that. I don't understand your notation yet. What exactly do you mean by <0,0> and <!isAliceTurn, isAliceTurn> ? Does that mean that I have two variable aliceWins=0 and bobWins=0 and <0,0> at the beginning I add to both 0 and at <!isAliceTurn, isAliceTurn> I add only to one of the two 1 depending on who was just on?
– raeg
Nov 24 '18 at 17:24
@raeg isAliceTurn is just a boolean variable, when true <!isAliceTurn, isAliceTurn> is equivalent to <0, 1> (alice looses and bob wins) and when false to <1, 0> (alice wins and bob looses)
– juvian
Nov 24 '18 at 19:15
@raeg isAliceTurn is just a boolean variable, when true <!isAliceTurn, isAliceTurn> is equivalent to <0, 1> (alice looses and bob wins) and when false to <1, 0> (alice wins and bob looses)
– juvian
Nov 24 '18 at 19:15
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- 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.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
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%2fstackoverflow.com%2fquestions%2f53453584%2fchance-to-win-a-game-calculate-with-dynamic-prorgamming%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
You did not explicitly state a question. Did you tried anything so far? It's likely that nobody will post an answer without seeing any contribution from your side
– Kristianmitk
Nov 23 '18 at 23:35