Optimize Algorithm For Shut in Box Game
This game is a simplified version of Shut the Box. There are 9 tiles (1,2,3,4,5...9). The initial tiles are unflipped. You have 2 dices. Each round, the player rolls the 2 dices and their sum is S. After that, there are two options. The first option is to find the tile equal to S. If it is unflipped, you can flip it so that the tile becomes flipped up. The second option is to find two tiles that are unflipped such that the sum of the two tiles is S and flip them. You keep rolling the dice until one of the 2 situation happens:
If all 9 tiles are flipped at any time, the player wins.
If the player rolls a sum and cannot find any tiles to sum up to it or be equivalent to it, the player loses.
The problem is to simulate the game 100,000 times and improve the win percentage.
My current strategy is to check if S is unflipped and flip that. If a tile equal to S is not available, I try to find 2 tiles that equal to S, starting from the biggest available number. I'm thinking it's best to eliminate numbers like 9,8.. asap because the frequency of S being smaller than that is high.
Currently, my strategy has around a 5% win rate but it can apparently be optimized further to hit 10%. Are there anyways to optimize it further?
probability statistics
asked Jan 3 at 22:55
codetumbler
61
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
This game is a simplified version of Shut the Box. There are 9 tiles (1,2,3,4,5...9). The initial tiles are unflipped. You have 2 dices. Each round, the player rolls the 2 dices and their sum is S. After that, there are two options. The first option is to find the tile equal to S. If it is unflipped, you can flip it so that the tile becomes flipped up. The second option is to find two tiles that are unflipped such that the sum of the two tiles is S and flip them. You keep rolling the dice until one of the 2 situation happens:
If all 9 tiles are flipped at any time, the player wins.
If the player rolls a sum and cannot find any tiles to sum up to it or be equivalent to it, the player loses.
The problem is to simulate the game 100,000 times and improve the win percentage.
My current strategy is to check if S is unflipped and flip that. If a tile equal to S is not available, I try to find 2 tiles that equal to S, starting from the biggest available number. I'm thinking it's best to eliminate numbers like 9,8.. asap because the frequency of S being smaller than that is high.
Currently, my strategy has around a 5% win rate but it can apparently be optimized further to hit 10%. Are there anyways to optimize it further?
probability statistics
asked Jan 3 at 22:55
codetumbler
61
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
This game is a simplified version of Shut the Box. There are 9 tiles (1,2,3,4,5...9). The initial tiles are unflipped. You have 2 dices. Each round, the player rolls the 2 dices and their sum is S. After that, there are two options. The first option is to find the tile equal to S. If it is unflipped, you can flip it so that the tile becomes flipped up. The second option is to find two tiles that are unflipped such that the sum of the two tiles is S and flip them. You keep rolling the dice until one of the 2 situation happens:
If all 9 tiles are flipped at any time, the player wins.
If the player rolls a sum and cannot find any tiles to sum up to it or be equivalent to it, the player loses.
The problem is to simulate the game 100,000 times and improve the win percentage.
My current strategy is to check if S is unflipped and flip that. If a tile equal to S is not available, I try to find 2 tiles that equal to S, starting from the biggest available number. I'm thinking it's best to eliminate numbers like 9,8.. asap because the frequency of S being smaller than that is high.
Currently, my strategy has around a 5% win rate but it can apparently be optimized further to hit 10%. Are there anyways to optimize it further?
probability statistics
asked Jan 3 at 22:55
codetumbler
61
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This game is a simplified version of Shut the Box. There are 9 tiles (1,2,3,4,5...9). The initial tiles are unflipped. You have 2 dices. Each round, the player rolls the 2 dices and their sum is S. After that, there are two options. The first option is to find the tile equal to S. If it is unflipped, you can flip it so that the tile becomes flipped up. The second option is to find two tiles that are unflipped such that the sum of the two tiles is S and flip them. You keep rolling the dice until one of the 2 situation happens:
If all 9 tiles are flipped at any time, the player wins.
If the player rolls a sum and cannot find any tiles to sum up to it or be equivalent to it, the player loses.
The problem is to simulate the game 100,000 times and improve the win percentage.
My current strategy is to check if S is unflipped and flip that. If a tile equal to S is not available, I try to find 2 tiles that equal to S, starting from the biggest available number. I'm thinking it's best to eliminate numbers like 9,8.. asap because the frequency of S being smaller than that is high.
Currently, my strategy has around a 5% win rate but it can apparently be optimized further to hit 10%. Are there anyways to optimize it further?
probability statistics
probability statistics
asked Jan 3 at 22:55
codetumbler
61
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 3 at 22:55
codetumbler
61
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 3 at 22:55
codetumbler
61
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 3 at 22:55
codetumbler
61
asked Jan 3 at 22:55
codetumbler
61
61
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
codetumbler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
There is a table given here which indicates the optimal play given the current board state:
http://www.durangobill.com/ShutTheBoxExtra/STB2DICE.txt
Also this question has been answered here:
https://boardgames.stackexchange.com/questions/35476/whats-the-strategy-for-shut-the-box
answered Jan 4 at 0:05
Peter Foreman
2056
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
You can use dynamic programming to find the optimal strategy.
Go through the positions of the game, starting with the ones that are closest to the end of the game. For each state, compute the probability of winning. This is done by computing, for each die roll, the options you have available to you, selecting the one which gives you the best chance of winning (which you have already computed), and then summing up the win-probabilities of your best option times the probability of that die roll. You should also write down what that those best options were in each case. At the end, you will have the probability of winning from each position, and the optimal strategy in each position.
There are only $2^9$ positions, so I think this is computationally feasible.
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
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
});
}
});
codetumbler is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3061118%2foptimize-algorithm-for-shut-in-box-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
There is a table given here which indicates the optimal play given the current board state:
http://www.durangobill.com/ShutTheBoxExtra/STB2DICE.txt
Also this question has been answered here:
https://boardgames.stackexchange.com/questions/35476/whats-the-strategy-for-shut-the-box
answered Jan 4 at 0:05
Peter Foreman
2056
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
There is a table given here which indicates the optimal play given the current board state:
http://www.durangobill.com/ShutTheBoxExtra/STB2DICE.txt
Also this question has been answered here:
https://boardgames.stackexchange.com/questions/35476/whats-the-strategy-for-shut-the-box
answered Jan 4 at 0:05
Peter Foreman
2056
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
There is a table given here which indicates the optimal play given the current board state:
http://www.durangobill.com/ShutTheBoxExtra/STB2DICE.txt
Also this question has been answered here:
https://boardgames.stackexchange.com/questions/35476/whats-the-strategy-for-shut-the-box
answered Jan 4 at 0:05
Peter Foreman
2056
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
There is a table given here which indicates the optimal play given the current board state:
http://www.durangobill.com/ShutTheBoxExtra/STB2DICE.txt
Also this question has been answered here:
https://boardgames.stackexchange.com/questions/35476/whats-the-strategy-for-shut-the-box
answered Jan 4 at 0:05
Peter Foreman
2056
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jan 4 at 0:05
Peter Foreman
2056
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jan 4 at 0:05
Peter Foreman
2056
answered Jan 4 at 0:05
Peter Foreman
2056
2056
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Peter Foreman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
You can use dynamic programming to find the optimal strategy.
Go through the positions of the game, starting with the ones that are closest to the end of the game. For each state, compute the probability of winning. This is done by computing, for each die roll, the options you have available to you, selecting the one which gives you the best chance of winning (which you have already computed), and then summing up the win-probabilities of your best option times the probability of that die roll. You should also write down what that those best options were in each case. At the end, you will have the probability of winning from each position, and the optimal strategy in each position.
There are only $2^9$ positions, so I think this is computationally feasible.
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
add a comment |
You can use dynamic programming to find the optimal strategy.
Go through the positions of the game, starting with the ones that are closest to the end of the game. For each state, compute the probability of winning. This is done by computing, for each die roll, the options you have available to you, selecting the one which gives you the best chance of winning (which you have already computed), and then summing up the win-probabilities of your best option times the probability of that die roll. You should also write down what that those best options were in each case. At the end, you will have the probability of winning from each position, and the optimal strategy in each position.
There are only $2^9$ positions, so I think this is computationally feasible.
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
add a comment |
You can use dynamic programming to find the optimal strategy.
Go through the positions of the game, starting with the ones that are closest to the end of the game. For each state, compute the probability of winning. This is done by computing, for each die roll, the options you have available to you, selecting the one which gives you the best chance of winning (which you have already computed), and then summing up the win-probabilities of your best option times the probability of that die roll. You should also write down what that those best options were in each case. At the end, you will have the probability of winning from each position, and the optimal strategy in each position.
There are only $2^9$ positions, so I think this is computationally feasible.
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
You can use dynamic programming to find the optimal strategy.
Go through the positions of the game, starting with the ones that are closest to the end of the game. For each state, compute the probability of winning. This is done by computing, for each die roll, the options you have available to you, selecting the one which gives you the best chance of winning (which you have already computed), and then summing up the win-probabilities of your best option times the probability of that die roll. You should also write down what that those best options were in each case. At the end, you will have the probability of winning from each position, and the optimal strategy in each position.
There are only $2^9$ positions, so I think this is computationally feasible.
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
answered Jan 4 at 0:03
Mike Earnest
20.6k11950
20.6k11950
add a comment |
add a comment |
codetumbler is a new contributor. Be nice, and check out our Code of Conduct.
codetumbler is a new contributor. Be nice, and check out our Code of Conduct.
codetumbler is a new contributor. Be nice, and check out our Code of Conduct.
codetumbler is a new contributor. Be nice, and check out our Code of Conduct.
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3061118%2foptimize-algorithm-for-shut-in-box-game%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
