The game Thane describes is a member of the "Pig" family, aka "jeopardy dice games". Many variants have been solved by Neller and Presser; their two papers and a summary of variants are at http://cs.gettysburg.edu/projects/pig/pigCompare.html The thing that makes this type of game hard to analyze is that the "probability of winning from a given state" calculation is based on your roll/hold decisions, which are in turn based on which would give you a higher probability of winning, in a loopy way. (If you and your opponent both bomb your turns, you end up back in the same state.) As Neller and Presser say, "There is no known general method for solving equations of the form x = max(Ax+b, A'x+b')." The method they use is to find the probabilities by some sort of iterative approximation, but I think there are subtleties I haven't thought about, so I won't try to give more details than that. Doubtless if someone pointed this variant out to them, they could report perfect play and the winning probabilities from every position in short order. It doesn't look like they report komi -- which is, I suppose, the 2nd-player-bonus to leave the odds as close to 50-50 as possible? In that case it's not clear which player will have the advantage once komi is used, though we expect it will be small in either case. --Michael Kleber On 8/25/07, Thane Plambeck <tplambeck@gmail.com> wrote:

Target is selling a game called Toss Up. It comes with 10 identical 6-sided dice and a rulebook. Each die has 3 green faces, 2 yellow faces, and 1 red face.

http://www.areyougame.com/Interact/item.asp?itemno=PA7367

On a player's turn, he starts by rolling all 10 dice. Dice that come up as green are added to the player's score, one point per die, and are put aside. The player then has the option to roll again with the remaining dice. If at least one is green, all the just-rolled greens are then put aside, he gets that many more points, and he has the option to roll again, etc.

If ever the player fails to roll a green and also has at least one red, he is bankrupted. His total accumulated score becomes zero and all the dice are passed to the next player. If alternatively he manages to score ten points, he gets to start over with all ten again. Finally, a player can also decide to stop at any time, passing the dice on to the next player at any point.

Whoever is the first to score 100 points wins.

In a two person game, it's presumably got to be advantageous to be the first to roll. But suppose the second player is given a "fair" initial positive score X (ie, a komi) to compensate for that.

What is X?

-- Thane Plambeck tplambeck@gmail.com http://www.plambeck.org/ehome.htm

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

Okay, still tossing Toss Up around in my head... Let me back off for a minute to the simpler question of "solitaire Toss Up" (which is what Thane looked like he was playing "against" his kids anyway!). In this version, you're just trying to maximize your score on each turn; we ignore the race-to-100 aspect entirely. If you're playing with the original bankruptcy rule, where you only risk the points you've accumulated on the current turn, then in solitaire your cumulative score is irrelevant: we're just asking for which numbers of points n is the expected value of rolling again positive. This should be easy to answer, right? If you have n points so far, the value of stopping is n, while the expected value of rolling is E_roll(n) = p(bust)*0 + sum_i>0 p(roll i green) * E(n+i) Here E(n) is max(n, E_roll(n)), and the number of dice you roll is 10 - (n mod 10). That's because of the very important rule that if you roll until all ten of the dice are green, then you get to start over with rolling all of them, and the number of points you're risking is now over 10 -- and is potentially unbounded. This makes it tricky to solve the above equations for E(n): you'd like to do some downwards induction, starting from some values of n that are so large that you'd *never* roll the dice, so you know E(n)=n. But how large is large enough? Intuitively it ought to be something over 5000! (If you're allowed to start a sentence with "intuitively" and end with an exclamation mark.) Becuase with 5000 points, you have a 1/1024 chance of going bankrupt versus an expected outcome of rolling 5 green dice out of ten, with the deal sweetened by the fact that you also have a 1/1024 chance of making it to 5010 points and getting to decide again. With a computer, we can afford to be empirical about it: cap the upward induction of E_roll(n) at some specified value N, declaring arbitrarily that we never reroll if n>N, and then see how the expected value function changes with N. If we pick N=10,000 things have indeed stabilized, and we can compute the expected value of the game: E(0) is approximately 13.2393. So the optimal strategy beats Thane's 4-5 points per turn by quite a bit! And what is the optimal strategy? It turns out that you always roll if your number of points so far is less than 27! If you are lucky enough to get that high, here are the smallest numbers of points n for which you do not roll despite having 1,2,3,...,10 dice available: 29, 28, 27, 56, 105, 224, 483, 1072, 2371, 5220. That's all you need to know to score 13.23 points per turn on average -- which should probably be enough to beat sub-optimal players, even without solving the two-player version of the game. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.