[math-fun] dice solitaire
Martin Gardner fan John Kemeny (no relation to the Dartmouth mathematician) tells me that his niece Allison plays a kind of dice-based solitaire game ("Apparently it is all the rage at Duke, where she was, but is now spending a year at the London School of Economics" writes John) and is curious what the optimal strategy is and what the odds of winning are under optimal play. The player's goal is to knock out numbers from the set {1,2,...,12} until none remain, where the player knocks out one or two numbers on each turn as follows: the player rolls two dice, and may knock out either the sum of the two numbers or may knock out any two distinct numbers that have the same sum as the sum of the numbers shown on the dice. (Note that all that matters is the sum of the numbers the player rolls, not the numbers shown by the two dice individually.) If a player is ever in a situation where no such move is possible, the game ends. This strikes me as do-able by brute force, since there are only 2^12 states of the game (based on which numbers have been crossed out), so, starting from endgame positions and working backwards, one should be able to work out, for each position, what the optimal plays are (for each die-roll) and what the chance of winning is under optimal play. A priori, I see no reason to believe that the optimal strategy has a nice description, but then again I see no reason to believe that it doesn't! Jim Propp
At some point near the end of the game, we reach a point where the same throw can never be handled in more than one way, because no throw has more than one representation. From this point onward, the outcome is entirely determined by chance. Let's call such situations "moribund". For example, the situation is moribund if only one or two numbers are left; or if three numbers are left and the larger is not the sum of the two smaller. It seems to me that analysis should begin with a catalog of moribund situations and their probabilities of success. I propose that a situation be summarized as a string of digits without spaces, and because 10, 11, and 12 don't have their own digits, we use hexadecimal A, B, and C respectively. The situation 12, then, has only the 1 and 2 available. One's only hope in this situation is to roll 3, with a chance of 1/18. The moribund situation 3 can also only be won with a roll of 3. The situation 123 is *not*moribund, but the only choice it offers doesn't seem to affect the chance of winning. If one rolls a 3, then one must roll another 3 to win, whether one chooses to knock out 12 or 3. Depending on the exact rules of play, you might want to knock out the 3 rather than the 12 combination, because 12 lets you at least stay alive one more turn if you roll a 2, and this might matter if the rules say each player has their own board, and they take turns with the winner being the last left alive. On Sun, Oct 24, 2010 at 2:14 PM, James Propp <jpropp@cs.uml.edu> wrote:
Martin Gardner fan John Kemeny (no relation to the Dartmouth mathematician) tells me that his niece Allison plays a kind of dice-based solitaire game ("Apparently it is all the rage at Duke, where she was, but is now spending a year at the London School of Economics" writes John) and is curious what the optimal strategy is and what the odds of winning are under optimal play.
The player's goal is to knock out numbers from the set {1,2,...,12} until none remain, where the player knocks out one or two numbers on each turn as follows: the player rolls two dice, and may knock out either the sum of the two numbers or may knock out any two distinct numbers that have the same sum as the sum of the numbers shown on the dice. (Note that all that matters is the sum of the numbers the player rolls, not the numbers shown by the two dice individually.) If a player is ever in a situation where no such move is possible, the game ends.
This strikes me as do-able by brute force, since there are only 2^12 states of the game (based on which numbers have been crossed out), so, starting from endgame positions and working backwards, one should be able to work out, for each position, what the optimal plays are (for each die-roll) and what the chance of winning is under optimal play.
A priori, I see no reason to believe that the optimal strategy has a nice description, but then again I see no reason to believe that it doesn't!
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A very simple observation (before a full analysis): you need the sum of all your throws to attain 12*13/2 or 78. The chance of hitting this sum with a sequence of throws, without going over, is clearly pretty small, since the expected value is 7 per throw so on average you'll hit only one out of every 7 numbers. Thus, even perfect play is usually doomed. On Sun, Oct 24, 2010 at 12:40 PM, Allan Wechsler <acwacw@gmail.com> wrote:
At some point near the end of the game, we reach a point where the same throw can never be handled in more than one way, because no throw has more than one representation. From this point onward, the outcome is entirely determined by chance. Let's call such situations "moribund". For example, the situation is moribund if only one or two numbers are left; or if three numbers are left and the larger is not the sum of the two smaller.
It seems to me that analysis should begin with a catalog of moribund situations and their probabilities of success. I propose that a situation be summarized as a string of digits without spaces, and because 10, 11, and 12 don't have their own digits, we use hexadecimal A, B, and C respectively.
The situation 12, then, has only the 1 and 2 available. One's only hope in this situation is to roll 3, with a chance of 1/18. The moribund situation 3 can also only be won with a roll of 3. The situation 123 is *not*moribund, but the only choice it offers doesn't seem to affect the chance of winning. If one rolls a 3, then one must roll another 3 to win, whether one chooses to knock out 12 or 3.
Depending on the exact rules of play, you might want to knock out the 3 rather than the 12 combination, because 12 lets you at least stay alive one more turn if you roll a 2, and this might matter if the rules say each player has their own board, and they take turns with the winner being the last left alive.
On Sun, Oct 24, 2010 at 2:14 PM, James Propp <jpropp@cs.uml.edu> wrote:
Martin Gardner fan John Kemeny (no relation to the Dartmouth mathematician) tells me that his niece Allison plays a kind of dice-based solitaire game ("Apparently it is all the rage at Duke, where she was, but is now spending a year at the London School of Economics" writes John) and is curious what the optimal strategy is and what the odds of winning are under optimal play.
The player's goal is to knock out numbers from the set {1,2,...,12} until none remain, where the player knocks out one or two numbers on each turn as follows: the player rolls two dice, and may knock out either the sum of the two numbers or may knock out any two distinct numbers that have the same sum as the sum of the numbers shown on the dice. (Note that all that matters is the sum of the numbers the player rolls, not the numbers shown by the two dice individually.) If a player is ever in a situation where no such move is possible, the game ends.
This strikes me as do-able by brute force, since there are only 2^12 states of the game (based on which numbers have been crossed out), so, starting from endgame positions and working backwards, one should be able to work out, for each position, what the optimal plays are (for each die-roll) and what the chance of winning is under optimal play.
A priori, I see no reason to believe that the optimal strategy has a nice description, but then again I see no reason to believe that it doesn't!
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
There could be a bug in my analysis, but it's pretty simple to code this up and I see an expected win percentage, assuming perfect play, of only 0.00286247636201557 or about 1 in 349. Seems like it would be a frustrating game to play. Looking over the unforced moves, I don't on cursory glance see any trivial pattern. This could also be a two person game. On Sun, Oct 24, 2010 at 12:46 PM, Tom Rokicki <rokicki@gmail.com> wrote:
A very simple observation (before a full analysis): you need the sum of all your throws to attain 12*13/2 or 78. The chance of hitting this sum with a sequence of throws, without going over, is clearly pretty small, since the expected value is 7 per throw so on average you'll hit only one out of every 7 numbers. Thus, even perfect play is usually doomed.
On Sun, Oct 24, 2010 at 12:40 PM, Allan Wechsler <acwacw@gmail.com> wrote:
At some point near the end of the game, we reach a point where the same throw can never be handled in more than one way, because no throw has more than one representation. From this point onward, the outcome is entirely determined by chance. Let's call such situations "moribund". For example, the situation is moribund if only one or two numbers are left; or if three numbers are left and the larger is not the sum of the two smaller.
It seems to me that analysis should begin with a catalog of moribund situations and their probabilities of success. I propose that a situation be summarized as a string of digits without spaces, and because 10, 11, and 12 don't have their own digits, we use hexadecimal A, B, and C respectively.
The situation 12, then, has only the 1 and 2 available. One's only hope in this situation is to roll 3, with a chance of 1/18. The moribund situation 3 can also only be won with a roll of 3. The situation 123 is *not*moribund, but the only choice it offers doesn't seem to affect the chance of winning. If one rolls a 3, then one must roll another 3 to win, whether one chooses to knock out 12 or 3.
Depending on the exact rules of play, you might want to knock out the 3 rather than the 12 combination, because 12 lets you at least stay alive one more turn if you roll a 2, and this might matter if the rules say each player has their own board, and they take turns with the winner being the last left alive.
On Sun, Oct 24, 2010 at 2:14 PM, James Propp <jpropp@cs.uml.edu> wrote:
Martin Gardner fan John Kemeny (no relation to the Dartmouth mathematician) tells me that his niece Allison plays a kind of dice-based solitaire game ("Apparently it is all the rage at Duke, where she was, but is now spending a year at the London School of Economics" writes John) and is curious what the optimal strategy is and what the odds of winning are under optimal play.
The player's goal is to knock out numbers from the set {1,2,...,12} until none remain, where the player knocks out one or two numbers on each turn as follows: the player rolls two dice, and may knock out either the sum of the two numbers or may knock out any two distinct numbers that have the same sum as the sum of the numbers shown on the dice. (Note that all that matters is the sum of the numbers the player rolls, not the numbers shown by the two dice individually.) If a player is ever in a situation where no such move is possible, the game ends.
This strikes me as do-able by brute force, since there are only 2^12 states of the game (based on which numbers have been crossed out), so, starting from endgame positions and working backwards, one should be able to work out, for each position, what the optimal plays are (for each die-roll) and what the chance of winning is under optimal play.
A priori, I see no reason to believe that the optimal strategy has a nice description, but then again I see no reason to believe that it doesn't!
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
-- Check out Golly at http://golly.sf.net/
Oddly, I have no intuitions about which moves are better. Suppose the situation is 1234, and you roll a 4. Which is a better set to leave, 24, or 123? On Sun, Oct 24, 2010 at 3:46 PM, Tom Rokicki <rokicki@gmail.com> wrote:
A very simple observation (before a full analysis): you need the sum of all your throws to attain 12*13/2 or 78. The chance of hitting this sum with a sequence of throws, without going over, is clearly pretty small, since the expected value is 7 per throw so on average you'll hit only one out of every 7 numbers. Thus, even perfect play is usually doomed.
On Sun, Oct 24, 2010 at 12:40 PM, Allan Wechsler <acwacw@gmail.com> wrote:
At some point near the end of the game, we reach a point where the same throw can never be handled in more than one way, because no throw has more than one representation. From this point onward, the outcome is entirely determined by chance. Let's call such situations "moribund". For example, the situation is moribund if only one or two numbers are left; or if three numbers are left and the larger is not the sum of the two smaller.
It seems to me that analysis should begin with a catalog of moribund situations and their probabilities of success. I propose that a situation be summarized as a string of digits without spaces, and because 10, 11, and 12 don't have their own digits, we use hexadecimal A, B, and C respectively.
The situation 12, then, has only the 1 and 2 available. One's only hope in this situation is to roll 3, with a chance of 1/18. The moribund situation 3 can also only be won with a roll of 3. The situation 123 is *not*moribund, but the only choice it offers doesn't seem to affect the chance of winning. If one rolls a 3, then one must roll another 3 to win, whether one chooses to knock out 12 or 3.
Depending on the exact rules of play, you might want to knock out the 3 rather than the 12 combination, because 12 lets you at least stay alive one more turn if you roll a 2, and this might matter if the rules say each player has their own board, and they take turns with the winner being the last left alive.
On Sun, Oct 24, 2010 at 2:14 PM, James Propp <jpropp@cs.uml.edu> wrote:
Martin Gardner fan John Kemeny (no relation to the Dartmouth mathematician) tells me that his niece Allison plays a kind of dice-based solitaire game ("Apparently it is all the rage at Duke, where she was, but is now spending a year at the London School of Economics" writes John) and is curious what the optimal strategy is and what the odds of winning are under optimal play.
The player's goal is to knock out numbers from the set {1,2,...,12} until none remain, where the player knocks out one or two numbers on each turn as follows: the player rolls two dice, and may knock out either the sum of the two numbers or may knock out any two distinct numbers that have the same sum as the sum of the numbers shown on the dice. (Note that all that matters is the sum of the numbers the player rolls, not the numbers shown by the two dice individually.) If a player is ever in a situation where no such move is possible, the game ends.
This strikes me as do-able by brute force, since there are only 2^12 states of the game (based on which numbers have been crossed out), so, starting from endgame positions and working backwards, one should be able to work out, for each position, what the optimal plays are (for each die-roll) and what the chance of winning is under optimal play.
A priori, I see no reason to believe that the optimal strategy has a nice description, but then again I see no reason to believe that it doesn't!
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My analysis says to split. If you split, you end up with 24, which has an expected value of 0.143518518518519 (win by 6 or 2 4 or 4 2); if you don't split and have 123, your expected value is only 0.00771604938271605 (win by 4 2 or 3 3 or 2 4). Note that 6 (5/36) is much more likely than 3 3 (1/324) and that's the difference. On Sun, Oct 24, 2010 at 2:58 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Oddly, I have no intuitions about which moves are better. Suppose the situation is 1234, and you roll a 4. Which is a better set to leave, 24, or 123?
On Sun, Oct 24, 2010 at 3:46 PM, Tom Rokicki <rokicki@gmail.com> wrote:
A very simple observation (before a full analysis): you need the sum of all your throws to attain 12*13/2 or 78. The chance of hitting this sum with a sequence of throws, without going over, is clearly pretty small, since the expected value is 7 per throw so on average you'll hit only one out of every 7 numbers. Thus, even perfect play is usually doomed.
On Sun, Oct 24, 2010 at 12:40 PM, Allan Wechsler <acwacw@gmail.com> wrote:
At some point near the end of the game, we reach a point where the same throw can never be handled in more than one way, because no throw has more than one representation. From this point onward, the outcome is entirely determined by chance. Let's call such situations "moribund". For example, the situation is moribund if only one or two numbers are left; or if three numbers are left and the larger is not the sum of the two smaller.
It seems to me that analysis should begin with a catalog of moribund situations and their probabilities of success. I propose that a situation be summarized as a string of digits without spaces, and because 10, 11, and 12 don't have their own digits, we use hexadecimal A, B, and C respectively.
The situation 12, then, has only the 1 and 2 available. One's only hope in this situation is to roll 3, with a chance of 1/18. The moribund situation 3 can also only be won with a roll of 3. The situation 123 is *not*moribund, but the only choice it offers doesn't seem to affect the chance of winning. If one rolls a 3, then one must roll another 3 to win, whether one chooses to knock out 12 or 3.
Depending on the exact rules of play, you might want to knock out the 3 rather than the 12 combination, because 12 lets you at least stay alive one more turn if you roll a 2, and this might matter if the rules say each player has their own board, and they take turns with the winner being the last left alive.
On Sun, Oct 24, 2010 at 2:14 PM, James Propp <jpropp@cs.uml.edu> wrote:
Martin Gardner fan John Kemeny (no relation to the Dartmouth mathematician) tells me that his niece Allison plays a kind of dice-based solitaire game ("Apparently it is all the rage at Duke, where she was, but is now spending a year at the London School of Economics" writes John) and is curious what the optimal strategy is and what the odds of winning are under optimal play.
The player's goal is to knock out numbers from the set {1,2,...,12} until none remain, where the player knocks out one or two numbers on each turn as follows: the player rolls two dice, and may knock out either the sum of the two numbers or may knock out any two distinct numbers that have the same sum as the sum of the numbers shown on the dice. (Note that all that matters is the sum of the numbers the player rolls, not the numbers shown by the two dice individually.) If a player is ever in a situation where no such move is possible, the game ends.
This strikes me as do-able by brute force, since there are only 2^12 states of the game (based on which numbers have been crossed out), so, starting from endgame positions and working backwards, one should be able to work out, for each position, what the optimal plays are (for each die-roll) and what the chance of winning is under optimal play.
A priori, I see no reason to believe that the optimal strategy has a nice description, but then again I see no reason to believe that it doesn't!
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
participants (3)
-
Allan Wechsler -
James Propp -
Tom Rokicki