Dice game... wrecking my head :)

DeVore

So here's the game:

You roll N dice.
I roll M dice (where M>=N).

I win if my roll includes all of your roll.

Example: N=4 , M=6
You roll: 1,1,3,4
I roll 1,1,2,3,4,6 ... I win!

You roll 1,3,4,6
I roll 1,1,2,3,5,6 I lose (I didn't roll at least one 4).

Is this just M c N ? For some reason I cant get my head around this lol!

I need a general formula because I want to have a matrix of N vs M odds.

Greenmachine

Okay couple of things.

You are not looking to have the greatest sum from the dice?
The winning Player appears to be player who has the highest unique value?
Does the value need to be unique to that player?

Say

I being (N) roll 5, 5, 5, 5

You roll (M) 1, 1, 3, 3, 3, 2

You have the only 2,
But I am I only player to have 5, no player has a 6.

You have confused things by listing N, before M,
I have left them as you have. Generally they are kept in alphabetical order on purpose so it is clear which values apply to which party.

Can't help you with the maths, but wan't to clarify what you were asking. :o

Hyzepher

I think N's roll must be a subset of Ms roll for M to win

DeVore

Yes, N's roll must be a subset of M's for M to win.

There is no consideration of the actual values or sum there of... just pattern matching.

Yakuza

My gut reaction is that this is a bit more subtle than [latex]M \choose N[/latex].

Consider a concrete example:
Rolling two dice, there are 36 possible combinations but only 21 unique combinations (I did this by hand, but verified with the method I used below)
Rolling three dice, there are 216 possible combinations but only 56 unique combinations.

Would then the probability of getting a match of the 21 possible 2-dice combinations from the 56 3-dice combinations be then 21/56 or 3/8?

4 dice; 126 unique combinations
5 dice; 252 unique combinations
6 dice; 462 unique combinations
7 dice; 792 unique combinations

I can't spot a pattern in this just yet (at work so can't give it too much time!)

How did I get the values above? I used SQL server and its set-handling capabilities.
By creating a table with 6 rows in it (values 1-6) and then joining to this twice, three times, four times etc.

I then took the resulting output and sorted it using two user-defined functions I googled (so that, for example, 2111, 1121, 1112 and 1211 all collapse to 1112) and took the distinct values of each.

Sample code:

create table #diceroll(	roll [int] NOT NULL)
insert into #diceroll values (1)
insert into #diceroll values (2)
insert into #diceroll values (3)
insert into #diceroll values (4)
insert into #diceroll values (5)
insert into #diceroll values (6)

select distinct dbo.udf_SortString(roll) from 
(
select convert(char(1),d1.roll) + convert(char(1),d2.roll) + convert(char(1),d3.roll) + convert(char(1),d4.roll) + convert(char(1),d5.roll) + convert(char(1),d6.roll) + convert(char(1),d7.roll) as roll
from #diceroll d1, #diceroll d2, #diceroll d3, #diceroll d4, #diceroll d5, #diceroll d6, #diceroll d7
) CombinedRolls6
order by 1

drop table #diceroll

DeVore

While the numbers are useful there is something wrong with the logic there. If it was just as simple as 21/56 then if M was also 2 it would be 21/21 = 1... a certainty!

This isnt as simple as it first seems

ClovisI

Not sure I understand the question.

Is 1,2 a subset of 3,2,1?

Assuming it isn't (i.e. that 2,1 WOULD be a subset) the answer is [latex]\frac{{{M}\choose{N}}5^{M-N}}{6^M}[/latex].

Yakuza

DeVore wrote: »

While the numbers are useful there is something wrong with the logic there. If it was just as simple as 21/56 then if M was also 2 it would be 21/21 = 1... a certainty!

This isnt as simple as it first seems

Yeah, I was a bit dubious myself that that was the answer, but lunchtime was over

DeVore

ClovisI wrote: »

Not sure I understand the question.

Is 1,2 a subset of 3,2,1?

Assuming it isn't (i.e. that 2,1 WOULD be a subset) the answer is [latex]\frac{{{M}\choose{N}}5^{M-N}}{6^M}[/latex].

Yes it would be a subset. The order is irrelevant (I should have made that clear). 1,2 is covered by 3,2,1.

DeVore

I can restate the game a bit:.

You roll N dice. (lets say in this case its 2 dice and you roll 3,4).
I roll M dice (in this case lets say 5 dice and I roll 1,1,3,4,6).

To win I must be able to match each of your dice results (a 3 and a 4 in this case) with two matching dice from my roll (ie: I must roll at least one 3 and one 4). The rest of my dice result are irrelevant. The order is irrelevant also (I just listed the results ascending from force of habit )

In my example, I win because I can push forward a dice showing 3 to match yours and a dice showing 4 to match your other dice. I've completely matched your roll, so I win. Anything else, I lose.

ClovisI

OK I see, that complicates things. It's a nice problem.

Is it necessary to find an exact formula? It seems unlikely that we'll find one that doesn't involve 5 or six disgusting nested sums.

You might be able to make progress in the limit as N and M get large keeping M/N constant though; then you can approximate things as uniform distributions.

E.g. for the simpler problem where the dice are replaced by two-sided coins, the exact form for the probability that M beats N is

[latex]\Sigma_{n=0}^N{{N}\choose{n}}(\frac{1}{2})^N\Sigma _{m=n}^{M-N+n}{{M}\choose{m}}(\frac{1}{2})^M=(\frac{1}{2})^{M+N}\Sigma_{n=0}^N\Sigma _{m=n}^{M-N+n}{{N}\choose{n}}{{M}\choose{m}}[/latex].

but if we let [latex]M,N\rightarrow \infty, M/N=\alpha[/latex]
this tends to

[latex]P(\alpha Y\geq X, \alpha(1-Y)\geq(1-X))[/latex] where X and Y are uniformly distributed in [0,1]. This actually evaluates to [latex]1-\frac{1}{\alpha}=1-\frac{N}{M}[/latex].

*Actually the last part is wrong, will fix later I'm busy now.

DeVore

Yeah... and I can solve this programmatically but I had been hoping for an elegant solution and I still somehow think there is one. But such a simple problem is really messes things up royally!

DeVore

A friend who knows his maths has offered this as a solution:

http://www.wolframalpha.com/input/?i=Sum%5b+Binomial%5bx+-+1%2c+n+-+1%5d+f%5en+(1+-+f)%5e(x+-+n)%2c+%7bx%2c+n%2c+m%7d%5d

He says:
I roll my n dice.
You start rolling yours.

Call it success when a roll of your dice matches my first roll. Success on your first roll happens with probability f =1/6, otherwise failure (probability 1-f), so keep going until you get a match.

Then start rolling again until you get a match of my second roll, and so on.

You want to find the probability of getting n successes within m rolls. The chance of getting exactly n successes in x >= m rolls *and* having success on the last roll x, is Binomial [ x - 1, n -1 ] f^n (1-f)^(x-n). Here the f^n (1-f)^(x-n) part comes from having n successes and x-n failures, and the Binomial [ x - 1, n -1 ] part comes form the fact that the first n-1 success can occur anywhere in the first x -1 rolls. So sum this up for x running from n (minimum possible) to m (number of rolls you are allowed). (Detail: the condition on the last roll being the n^th success makes this a sum over disjoint events)

ClovisI

Sounds like your friend made the same misinterpretation as me at first: he assumed that we only want "ordered" subsets.
Based on that incorrect assumption he's right, I see now that my first answer was off.

Greenmachine

I Don't know if this add anything or not.

If I my two dice first I see to basic outcome. I will roll two unique values, one the same value.
The chance of my rolling the same value twice is 1/6, and the chance of 2 unique values is 5/6.
Do you need to test for either outcome.

I ask because if my two dice are the same value the chance of rolling the correct value on your first roll is 1/6. You have 6 possible outcome and only 1 is favorable. Each individual roll has a 1/6 in 6 after this of achieving the required value and of course is independent of the other. Clearly if you had an unlimited number of rolls you would eventually roll the same value again.

If both my value are unique, there are 2 values that you have the chance to match on your first, or indeed any subsequent roll, once you match, my first value, each subsequent roll will each have as you know a in 6 chance to match. Again I am sure you understand this. I am just wondering if any of the proposal you have seen have tested for both case.

I at least am at little clearer on what your asking. The collective brains (mine excluded :pac:) can surely work it out. I heard mentions of subsets, and though I remember those, but what you have put in front of us is a lot more interesting than working out the chance of winning the lottery.

Which has given me a though. I believe there is formula only regarding the odd for a particular type of bet you do in bookies. I don't frequent them no can't help you. Something tells me if apply the concept in inverse, you might get somewhere.

Conceptually you for example pick 3 numbers in the lottery and place a bet on these. Your 3 numbers must be 3 of the 6 numbers drawn. In this case the pool of numbers is much larger, than in you dice game but it is a computational formulation e.g (5!/3!) but more derived. If you can work out what I am saying from my horrible explanation, you should be able to work back.

Or not, in which case, I will leave the thread, to those who know better. :pac::pac:

DeVore

The problem with reversing it (which was, to be fair, the first thing I thought of because its often easier), is that it pretty much becomes the same problem, just that you are going to subtract it from 1 at the end.

ie: the problem goes from match this specific set of outcomes with M dice,
to: match all of your M must match these OTHER outcomes and you are allowed N-1 failures to do so with repeats of N-1 non-matching numbers along the way

ie: if your roll was 3,4 with 2 dice and I have 5 dice then I need to roll at least 4 from the set [1,2,5,6] along with multiples of the same one (lots of 3's say, but no fours). Its actually at least as hard to work out

Its a bugger, but I think my mates way of doing it is the cleanest I've seen...

gleesonger

This is my approach,

let f(x) = (5/6)^x
let g(x) = f(x) + (1-f(x)) * g(x-1)
let g(M-N)=0 (ie recursive from M to N)

Probability_M_Wins = g(M)

Example of formula in Excel

I assume that there is no double counting allowed, ie if there are two IVs rolled then M must roll at least 2 IVs.

I am not convinced my approach works.
Code lines up with formula (excel) for all smallish values but once I get to M=12, N=4 I am out by 3% percent, not sure yet if this is due to a coding, precision or formula error. I'm guessing the later .

You can probably unwind the formula to remove the recursion. If the formula is right I might look into that.

C# code;

namespace ConsoleApplication1
{
    class Hand
    {
        public const int DIE_FACE_COUNT = 6;
        public readonly int[] simulation = new int[DIE_FACE_COUNT];

        public bool Contains(Hand smaller_hand)
        {
            for (int i = 0; i < DIE_FACE_COUNT; i++)
            {
                if (smaller_hand.simulation[i] > this.simulation[i])
                    return false;
            }

            return true;
        }

        public static Hand Simulate(Random rand,int num_throws)
        {
            Hand hand = new Hand();

            for (int i = 0; i < num_throws; i++)
                hand.simulation[rand.Next(0, DIE_FACE_COUNT)]++;

            return hand;
        }
    }

    class Program
    {
        static void Main()
        {
            for (int i = 0; i < 3; i++)
                RunSimulation();

            Console.WriteLine("Done");
            Console.ReadKey();
        }

        static void RunSimulation()
        {
            const int n = 3;
            const int m = 12;
            const int num_sims = 10000000;

            int win_count_n = 0;
            int win_count_m = 0;

            Random rand = new Random();

            for (int i = 0; i < num_sims; i++)
            {
                bool win_m = Hand.Simulate(rand, m).Contains(Hand.Simulate(rand, n));

                if (win_m)
                    win_count_m++;
                else
                    win_count_n++;
            }

            double win_percent_m = ((double)win_count_m) / num_sims;
            double win_percent_n = ((double)win_count_n) / num_sims;

            Console.WriteLine("Win N: " + Math.Round(win_percent_n * 100, 2));
            Console.WriteLine("Win M: " + Math.Round(win_percent_m * 100, 2));
            Console.WriteLine();
        }
        
    }
}

DeVore

I've also decided to brute force this and have written a VB program I'm refining at the moment to do N = 2...9 M = 2... 9 a Million times for each iteration and store the values. I'll have an output later today!

The formula I posted up above from a friend of mine turns out to be inaccurate because he misunderstood the game so its wrong.

This has gone from a simple "hey, I wonder what probabilities of the dice rolls versus perils in the game Armello are" to a death march of stubbornness about this math problem. I'm going to get those probabilities if it kills me.

I'll post the code here when I'm done.

gleesonger

I realised the error in my formula, there is a lower liklihood of hitting repetitive numbers, eg @ M=2,N=2; 1,1 has a probability of 1/36 wheres 1,2 has a probability of 2/36 because 2,1 can also occur which is equal. I'm looking at something now that might work.

What is the maximum expected size of M? Brute force could be made to be pretty quick.

DeVore

Max sizes of N=6 and M=12 more or less. Computational time doesn't seem to increase particularly fast with increases in either tbh!

Btw, wouldn't N=1 and M=1 have a probability of 1/6 (not 1/36 as you suggested?)

gleesonger

DeVore wrote: »

Max sizes of N=6 and M=12

Easiest for that is to brute force the answer and store in a lookup table beside the application. I suggest going over and above the required number in case you want to increase your max value of M and also including the brute force for a fall back when the values exceed your stored results.

DeVore wrote: »

wouldn't N=1 and M=1 have a probability of 1/6 (not 1/36 as you suggested?)

When I said 1,1 I was referring to the result of two die throws.

At M=2 and N=2 if the first player throws two dies of the same value (eg 1,1 or 2,2 or .... 6,6) then the chance of the second player matching that hand is 1/36.
However if the first player throws two dies of different values (eg 1,2 or 3,4 ,....) then the chance of the second player matching that hand is 2/36 as order doesn't matter. It think this distinction is the crux of the problem.

To get the correct answer I suggest posting to the maths section of stackoverflow, you could get a decent answers there. If you do, post a link to your question here so I can follow. This problem has tweaked my interest!

dlouth15

Are repetitions counted? For example if the opponent throws 3 1s must you also have 3 1s in your throw? Your first example seems to suggest that this is the case.

DeVore

Yes, exactly...

dlouth15

Thank you.

Ok, Let the n,m game be the game with the first player throwing n times and the second player trying to match it with m throws.

Consider the simplest. The 1,1 game. Here n=m=1.

Clearly the probability of the first player winning is 5/6. (and the second player winning being 1-5/6=1/6). I think you will agree with that.

Now we consider the 1,m game. Here the first player throws once but the second player has m throws. To win the first player must mismatch with each of the second players m throws. It is equivalent to playing the 1,1 game m times.

So the probability of the first player winning is now (5/6)^m. The probability of the second player winning is 1-(5/6)^m. Do you agree with this so far?

Now we generalise further. Instead of the first player throwing once he throws n times. The second player must find a match somewhere in his throws for each of the first players throws.

So the prob of matching the first of the first players throws is the same as the 1,m game.

1-(5/6)^m.

Having matched the first of the first player's throws, the second player now has m-1 throws left. He must now match the second of the first player's throws with one of his remaining m-1 throws.

The probability of finding a match on the second of the first player's throws is 1-(5/6)^(m-1). This is the equivalent of the 1,(m-1) game.

This is repeated n times.

So we have something like for the 3,m game:

[latex]\displayvalue{P\left(second\right)=\left(1-\left(\frac{5}{6}\right)^{m}\right)\times\left(1-\left(\frac{5}{6}\right)^{m-1}\right)\times\left(1-\left(\frac{5}{6}\right)^{m-2}\right)}[/latex]

For example for the the 4,6 game

[latex]\displayvaluee{P\left(second\right)=\left(1-\left(\frac{5}{6}\right)^{6}\right)\times\left(1-\left(\frac{5}{6}\right)^{5}\right)\times\left(1-\left(\frac{5}{6}\right)^{4}\right)\times\left(1-\left(\frac{5}{6}\right)^{3}\right)=0.0867728}[/latex]
Note the four terms. This is because n=4.

For the 1,1 game we have

[latex]\displayvalue{1-\left(\frac{5}{6}\right)^{1}=\frac{1}{6}}[/latex]

dlouth15

I'm getting the same result as gleesonger with his spreadsheet. Devore, is this what you wanted? It is an iterative formula, (gleesonger's is recursive) but in both cases for any reasonable number of dice throws, the computer should be able to calculate the probabilities instantly without using brute force.

DeVore

I'm just finishing up the brute force (which is actually kinda elegant in code) and we can compare the two approaches (experimental and theoretical! FOR SCIENCE!). I'll try and paste them here today. (just sanity checking the results now).

DeVore

Ok here are my results, I *think* they are right.

They are in the form (Rollloses is the number of times M player lost, and RollsWin is the number of times MPlayer won. Pw% is probability of a win for M in % form) I ran each [N,M] 100,000 times.

N , M , RollLoses, RollWins, Pw%

deleted cos they are wrong.

DeVore

Already I see something weird, the results for 4,4 and 4,5 are odd... how could 4,5 be less likely to win?

This code is generic too, its the same code that worked out 3,3 and 3,4 as well as 5,5 and 5,6 and it did them correctly!

Going to run 1000,000 times for the giggles, maybe it was just variance...

dlouth15

Can you do very small numbers like 1,1 ; 1,2 and 2,1? These should be fairly easy to analyse.

Lets look at 2,2. I get about 5 percent here. Can you list out the combinations you use to arrive at 20%. Perhaps your calculation of percentage is wrong. 20 is 1/5 of 100. 5 is one twentieth of 100.

sKeith

Formula to calculate PW% = RollsWins/1000

DeVore

If we work out 2,2 by hand...

Lets presume that the N dice are different (we'll add in the chance of them being the same later). So its a 5/6 chance that they are different.
The 2 M dice must both match one of the N dice. The first dice from M has a 2/6 chance of matching the second has a 1/6 chance of matching so combined they have a 2/36 chance or 1/18.

If the two N dice DONT match then the M dice have a 1/36 chance of matching.

so the odds are (5/6 * 1/18 ) + (1/6 * 1/36)

This gives 11/216 or .0506 or about 5.06%

---

1,1 is 1/6 or 16.66%

---

1,2 is 1- (5/6*5/6) .... ie the inverse of missing with both of the M dice.
Which is 1 - 25/36
which is 11/36 or 30.5%

---

2,1 is trivially 0. You cant ever win with fewer dice than you need to match.




I've deleted my results because I found some sloppy array index handling between procedures, running them again now.