Dice game... wrecking my head :)

DeVore

Dlouth, I think you are right... I'm going to fix the bugs in my code and test to see if it matches your results.
I'm basically just geeking out OCD-like on this now because , I dunno... reasons

DeVore

Ok, I've basically proven that MS cant do random.

I thought I was chasing bugs in my code but I just couldn't see any. Eventually I forced my program to just do 1,1 and hand checked it. It was consistently wrong, it produces % wins of about 18% over 10,000 runs. That's waaaay off on that number of iterations.

So I had it print out the actual results, line at a time and checked them and they are all correctly identified. Analysing this gives this distribution of winning pairs:

1s 301
2's 293
3's 297
4's 313
5's 297
6's 305

Seems ok... there isnt a huge bias towards any given number in any of the rolls either... but still, the number of matches considerably exceeds the expected number. ie: we should see 1667 matches, but we see 1807 instead...

Turns out, even using the new seed generator of Randomize()... the random function in VB has some issues of producing the same number in a row... hence the slightly higher match rate but the roughly correct distribution of numbers...

Now I have to go write my own randomiser

DeVore

I'm nothing if not persistent.

So, I wrote my own randomiser and hey presto... it works. The results I got for small number dice are:

N, M, Losses, Wins, % Win for M

 1 ,  1 ,  833268 ,  166732 ,  16.6732%
 1 ,  2 ,  694939 ,  305061 ,  30.5061%
 1 ,  3 ,  578077 ,  421923 ,  42.1923%
 2 ,  2 ,  948987 ,  51013 ,  5.1013%
 2 ,  3 ,  871958 ,  128042 ,  12.8042%
 3 ,  3 ,  978773 ,  21227 ,  2.1227%

Those look good so I'll run the bigger numbers too.

DeVore

The results for the bigger numbers are:

N, M, Losses, Wins, % Win for M

 1 ,  1 ,  833467 ,  166533 ,  16.6533%
 1 ,  2 ,  693709 ,  306291 ,  30.6291%
 1 ,  3 ,  578424 ,  421576 ,  42.1576%
 1 ,  4 ,  481961 ,  518039 ,  51.8039%
 1 ,  5 ,  401641 ,  598359 ,  59.8359%
 1 ,  6 ,  335149 ,  664851 ,  66.4851%
 1 ,  7 ,  278186 ,  721814 ,  72.1814%
 1 ,  8 ,  233057 ,  766943 ,  76.6943%
 1 ,  9 ,  193878 ,  806122 ,  80.6122%
 2 ,  2 ,  949424 ,  50576 ,  5.0576%
 2 ,  3 ,  871883 ,  128117 ,  12.8117%
 2 ,  4 ,  783843 ,  216157 ,  21.6157%
 2 ,  5 ,  694529 ,  305471 ,  30.5471%
 2 ,  6 ,  607487 ,  392513 ,  39.2513%
 2 ,  7 ,  527653 ,  472347 ,  47.2347%
 2 ,  8 ,  456209 ,  543791 ,  54.3791%
 2 ,  9 ,  391299 ,  608701 ,  60.8701%
 3 ,  3 ,  978931 ,  21069 ,  2.1069%
 3 ,  4 ,  934458 ,  65542 ,  6.5542%
 3 ,  5 ,  873204 ,  126796 ,  12.6796%
 3 ,  6 ,  802380 ,  197620 ,  19.762%
 3 ,  7 ,  725325 ,  274675 ,  27.4675%
 3 ,  8 ,  647969 ,  352031 ,  35.2031%
 3 ,  9 ,  574071 ,  425929 ,  42.5929%
 4 ,  4 ,  989245 ,  10755 ,  1.0755%
 4 ,  5 ,  961739 ,  38261 ,  3.8261%
 4 ,  6 ,  918679 ,  81321 ,  8.1321%
 4 ,  7 ,  862477 ,  137523 ,  13.7523%
 4 ,  8 ,  797529 ,  202471 ,  20.2471%
 4 ,  9 ,  729780 ,  270220 ,  27.022%
 5 ,  5 ,  993636 ,  6364 ,  .6364%
 5 ,  6 ,  975575 ,  24425 ,  2.4425%
 5 ,  7 ,  944303 ,  55697 ,  5.5697%
 5 ,  8 ,  899891 ,  100109 ,  10.0109%
 5 ,  9 ,  845908 ,  154092 ,  15.4092%
 6 ,  6 ,  995890 ,  4110 ,  .411%
 6 ,  7 ,  983482 ,  16518 ,  1.6518%
 6 ,  8 ,  959584 ,  40416 ,  4.0416%
 6 ,  9 ,  924301 ,  75699 ,  7.5699%

dlouth15

That looks more like it.

Here's a small function in some form of basic to calculate it.

Function Prb(n, m)
	Prb=1
	For i = 0 to n-1
		Prb = Prb * ( 1 - (5/6)^(m-i) )
	Next i
End Function

ray giraffe

I have a formula for (2,M) which agrees with DeVore's results.
I'm confident I can finish a formula for (3,M) with a bit more work but (4,M) is beyond me.

I have a little proof that the probability that N throws of a coin match the next N throws in any order approaches (1/sqrt(Pi*N)) as N becomes large.


The most useful information for DeVore right now is probably that the 95% margin of error is approximately 1/sqrt(n).

In other words with a million runs, 95% of the simulation probabilities are correct within 1/1000=0.001=0.1%

For example, with (1,2) the exact answer is 30.55555% and the simulation answer is 30.6291% which is within 0.1%.

With the formula we can see that if he increases his simulation to 4 millions runs each, his margin of error drops to 0.05%.

DeVore

I ran 1,1 and 1,2 up to 4M iterations each and the results are:

 1 ,  1 ,  3332320 ,  667680 ,  16.692%
 1 ,  2 ,  2777824 ,  1222176 ,  30.5544%

So, it seems like your info is accurate!

DeVore

dlouth15 wrote: »

That looks more like it.

Here's a small function in some form of basic to calculate it.

Function Prb(n, m)
	Prb=1
	For i = 0 to n-1
		Prb = Prb * ( 1 - (5/6)^(m-i) )
	Next i
End Function

When I run this over N=1..6 and M=N..9 I get this:

1	1	16.67
1	2	30.56
1	3	42.13
1	4	51.77
1	5	59.81
1	6	66.51
1	7	72.09
1	8	76.74
1	9	80.62

2	2	5.09
2	3	12.87
2	4	21.81
2	5	30.97
2	6	39.78
2	7	47.95
2	8	55.33
2	9	61.87

3	3	2.15
3	4	6.66
3	5	13.05
3	6	20.60
3	7	28.68
3	8	36.80
3	9	44.60

4	4	1.11
4	5	3.99
4	6	8.68
4	7	14.85
4	8	22.01
4	9	29.67

5	5	0.66
5	6	2.65
5	7	6.26
5	8	11.40
5	9	17.74

6	6	0.44
6	7	1.91
6	8	4.80
6	9	9.19

ray giraffe

Formulas:

(1,m) is
1-(5/6)^m

(2,m) is
(1/6)*(1-(5/6)^m-m*(5/6)^(m-1)*(1/6))
+(5/6)*(1-2*(5/6)^m+(4/6)^m)

(3,m) is
(1/6)^2*(1-(5/6)^m-m*(5/6)^(m-1)*(1/6)-COMBIN(m,2)*(5/6)^(m-2)*(1/6)^2)
+(15/36)*(1-2*(5/6)^m-m*(5/6)^(m-1)*(1/6)+(5/6)^m*((4/5)^m+m*(4/5)^(m-1)*(1/5)))
+(5/6)*(4/6)*(1-3*(5/6)^m+3*(4/6)^m-(3/6)^m)


[Aside:

The pattern in the number of terms is the number of partitions of an integer n: 1,2,3,5,7,11 etc.
http://oeis.org/A000041

So (4,m) will have 5 terms (of which only 2 are doable).

End Aside]



Here are the exact answers for (1,m) , (2,m) and (3,m) in % to 3 decimal places

16.667%
30.556% 5.093%
42.130% 12.809% 2.135%
51.775% 21.618% 6.539%
59.812% 30.598% 12.664%
66.510% 39.220% 19.835%
72.092% 47.200% 27.465%
76.743% 54.412% 35.114%
80.619% 60.822% 42.480%

along with the errors in DeVore's simulation

-0.013% 0.000%
0.074% -0.035% 0.000%
0.028% 0.003% -0.028%
0.029% -0.002% 0.015%
0.024% -0.051% 0.016%
-0.025% 0.031% -0.073%
0.090% 0.034% 0.003%
-0.049% -0.033% 0.089%
-0.007% 0.048% 0.113%

And of course 95% of those are within 0.1%, as predicted

DeVore

It seems that just like GleeSonger ... the brute force diverges from the formula once N goes over 3. I have a suspicion there is something lurking in the larger numbers of dice that make things a bit more complex for the formula, but I cant rule out errors in the code of course. The accuracy at the lower numbers makes me doubt the code slightly less as it doesn't care how many dice there are, it either matches or it doesn't.

dlouth15

ray giraffe wrote: »

Formulas:

(1,m) is
1-(5/6)^m

(2,m) is
(1/6)*(1-(5/6)^m-m*(5/6)^(m-1)*(1/6))
+(5/6)*(1-2*(5/6)^m+(4/6)^m)

(3,m) is
(1/6)^2*(1-(5/6)^m-m*(5/6)^(m-1)*(1/6)-COMBIN(m,2)*(5/6)^(m-2)*(1/6)^2)
+(15/36)*(1-2*(5/6)^m-m*(5/6)^(m-1)*(1/6)+(5/6)^m*((4/5)^m+m*(4/5)^(m-1)*(1/5)))
+(5/6)*(4/6)*(1-3*(5/6)^m+3*(4/6)^m-(3/6)^m)

Ray, How did you arrive at those?

dlouth15

I did a simulation against Ray's formulas and got the following errors:

 0.001%
-0.001%  0.001%
 0.000% -0.001% -0.001%
 0.002%  0.001%  0.000%
 0.000% -0.001%  0.000%
 0.001% -0.002%  0.001%
-0.001% -0.004%  0.000%
 0.000% -0.002%  0.000%
 0.000% -0.002% -0.004%

Which is very close indeed. Well done Ray.

ray giraffe

dlouth15 wrote: »

Ray, How did you arrive at those?

(2,m) first:

P(player 2 wins and player 1 has equal dice)
+
P(player 2 wins and player 1 has different dice)
=
P(2 throws are equal, call the value x)*P(next m throws have at least 2 x's (using Binomial Distribution))
+
P(2 throws are different, call the values x and y)*P(next m throws have at least 1 x and at least 1 y (using Inclusion-Exclusion Principle))
=
(1/6) * (1-(5/6)^m-m*(5/6)^(m-1)*(1/6))
+
(5/6) * (1-2*(5/6)^m+(4/6)^m)



Now look at (3,m):

P(3 throws all equal to x)*P(next m throws have at least 3 of x)
+
P(3 throws have 2 equal to one value x and 1 equal to a different value y)*P(next m throws have at least 2 of x and 1 y)
+
P(3 throws are all different and equal to x,y and z)*P(next m throws have at least 1 of x,y and z)
=
(1/6)^2 * (1-(5/6)^m-m*(5/6)^(m-1)*(1/6)-COMBIN(m,2)*(5/6)^(m-2)*(1/6)^2)
+
(15/36) * (1-2*(5/6)^m-m*(5/6)^(m-1)*(1/6)+(5/6)^m*((4/5)^m+m*(4/5)^(m-1)*(1/5)))
+
(5/6)*(4/6) * (1-3*(5/6)^m+3*(4/6)^m-(3/6)^m)


There may be a much less laborious way to calculate these using generating functions possibly

DeVore

I think we can safely say that there is no elegant general solution (or at least none that we can find!) which is curious considering how simple a problem it is to state. I suppose its like Einstein said, when seeking the truth leave elegance to the tailor

DeVore

If N is something like 5 then its going to get very complicated. We'll have to consider variations like xxxx,y, xxx,y,z and y,y,x,x,x etc

Yakuza

I'm going to have a brute-force bash at this over the bank holiday weekend.
This is how I'm going to restate the problem, holler if I've missed something:

In my previous post, I worked out how many unique combinations there were of N dice (so 252 in the case of 5).

You roll 5 dice.

So if I'm going to roll 5 dice, then there is a 1 in 252 chance of me getting the same distinct set of rolls as you.
If I roll 6 dice, there are 462 unique combinations, 6 of these are going to be valid super sets of your roll (your roll plus 1 or 2 or 3 or 4 or 5 or 6), so my probability should be 6 / 462.

If I roll 7 dice, there are 792 unique combinations, 36 of which are going to be valid super sets of the original roll (the original roll and 1,1....6,6), so the probability should be 36/792.

My conjecture is that the probability is 6^(M-N) /(#unique rolls of M dice (which I've yet to find a neat formula for))

I'll get my C# simulation head on over the weekend and see if expectation matches reality

ray giraffe

Stop the presses!!

Henry on stackexchange got a recursive formula!!

It appears to agree with our results, but it's way better

http://math.stackexchange.com/questions/1493150/probability-n-dice-results-are-subset-of-m-dice-results

MathsManiac

Yakuza wrote: »

I'm going to have a brute-force bash at this over the bank holiday weekend.
This is how I'm going to restate the problem, holler if I've missed something:

In my previous post, I worked out how many unique combinations there were of N dice (so 252 in the case of 5).

You roll 5 dice.

So if I'm going to roll 5 dice, then there is a 1 in 252 chance of me getting the same distinct set of rolls as you.
If I roll 6 dice, there are 462 unique combinations, 6 of these are going to be valid super sets of your roll (your roll plus 1 or 2 or 3 or 4 or 5 or 6), so my probability should be 6 / 462.

If I roll 7 dice, there are 792 unique combinations, 36 of which are going to be valid super sets of the original roll (the original roll and 1,1....6,6), so the probability should be 36/792.

My conjecture is that the probability is 6^(M-N) /(#unique rolls of M dice (which I've yet to find a neat formula for))

I'll get my C# simulation head on over the weekend and see if expectation matches reality

In the sentence that I've highlighted in bold above, you have assumed that these 252 unique combinations are equiprobable, but they are not, since the number of non-unique combinations contributing to each unique combination varies. Similarly later with your 792 combinations, etc.

dlouth15

Ran Henry from StackExchange's numbers against the simulation and got the following errors for the simulation.

-0.001%
 0.000%  0.001%
 0.000%  0.000%  0.000%
 0.002% -0.003%  0.001%  0.000%
 0.002% -0.001% -0.001%  0.000%  0.000%
 0.002%  0.001% -0.002%  0.001%  0.000%  0.000%

The R code he supplies runs instantly.

Yakuza

MathsManiac wrote: »

In the sentence that I've highlighted in bold above, you have assumed that these 252 unique combinations are equiprobable, but they are not, since the number of non-unique combinations contributing to each unique combination varies. Similarly later with your 792 combinations, etc.

D'oh, I was taking an a posteriori view I guess. I'm going to get cracking on some simulations later anyway. I'm teaching myself R so the code linked above looks like a good way to get started!

dlouth15

Yakuza wrote: »

D'oh, I was taking an a posteriori view I guess. I'm going to get cracking on some simulations later anyway. I'm teaching myself R so the code linked above looks like a good way to get started!

When you paste the R code into a text editor you might find some of the minus signs are a different character, a slightly longer dash. You may need to change these back into proper minus characters to get the code to run.

Yakuza

Results below from C# model (run for from N = 1 to 10 and M from N to 10 with a million iterations, each run takes about 5-6 seconds on average).

	1	2	3	4	5	6	7	8	9	10
1	0.1668	0.3056	0.4218	0.5184	0.5974	0.6654	0.7212	0.7665	0.8067	0.8381
2		0.0511	0.1286	0.2158	0.3054	0.3923	0.4725	0.5438	0.6082	0.6654
3			0.0214	0.0654	0.1271	0.1979	0.2746	0.3515	0.4248	0.4932
4				0.0109	0.0375	0.0815	0.1369	0.2014	0.2701	0.3410
5					0.0064	0.0242	0.0563	0.1003	0.1532	0.2142
6						0.0041	0.0167	0.0405	0.0757	0.1203
7							0.0028	0.0120	0.0302	0.0587
8								0.0020	0.0091	0.0232
9									0.0015	0.0070
10										0.0012
	1	2	3	4	5	6	7	8	9	10
1	1.0006	1.0002	1.0012	1.0012	0.9988	1.0004	1.0004	0.9988	1.0006	0.9995
2		1.0035	1.0042	0.9985	0.9982	1.0002	1.0010	0.9994	0.9999	1.0012
3			1.0002	0.9995	1.0035	0.9978	0.9997	1.0011	1.0001	0.9989
4				1.0037	0.9837	1.0013	0.9965	0.9978	0.9982	1.0022
5					1.0036	0.9919	1.0057	1.0027	0.9958	0.9998
6						1.0025	1.0013	1.0023	1.0016	0.9969
7							1.0185	0.9958	0.9947	0.9979
8								1.0189	1.0146	0.9866
9									0.9826	1.0141
10										1.0088

Below the results is the ratio of my results to the R results (I got the script from stack exchange to run first time, just pasted it into NotePad++ then into R, worked like a charm). My model is reasonably close, but I'm running 10 million iterations now (from 1 to 19), will update when it finishes, hopefully this will reduce the variance a bit more. I estimate it will take about 3 hours to run so there's a while to wait yet

I had a few issues with the .Net RNG, the .Next(1,7) operator seemed a bit biased but using .Next(0,12000) \ 2000 +1 seemed to produce better results.

Code attached for reference.

gleesonger

Yakuza wrote: »

I estimate it will take about 3 hours to run so there's a while to wait yet

I had a brief look at your code, on my (terrible) machine it took; 37s to run 1m trials. I made two structure changes to your code;
1) Your storing the results in a string, this will be inefficient, I moved it to an array which counts the number of faces in a trial, ie; int[] hand = new int[6]; hand[SingleRoll()-1]++;
2) I am dubious about the claim that .Next(1,7) is bias. I noticed no difference on my machine. In fact as your approach uses integer division which will give more weight to all faces expect 6 which will have a lower weight.

Making these changes reduced the run time to 4.3s.

I assume your machine is multi cored, you can use the Parallel.For loop on your outmost loop to increase the speed in line with the number of cores you have. So if you have a quad core machine the time taken on my machine would drop to aprox 1s.

If these speeds (incl quad core) translate to you, then you will see the runtime drop from 3hrs to 5mins.

Yakuza wrote: »

I had a few issues with the .Net RNG, the .Next(1,7) operator seemed a bit biased but using .Next(0,12000) \ 2000 +1 seemed to produce better results.

If this is a concern then I suggest you look at a third party packge like numerics.mathdotnet.com. Take a look at Mersenne Twister.

Yakuza

I'm fairly familiar with multithreading on C# and of course it would be an obvious area to improve performance, I just wanted a quick and dirty solution and wasn't looking for the optimal solution. I won't be running this again, I suspect, it was just to brute force guess some probabilities (and the whole thing is now moot as a recursive formula has been found!). The machine is a Dell XPS M1730 laptop, 2008 vintage so there are faster machines out there. It was the 190 (n = 1..19 and m = n to 19) runs of 10,000,000 that I expected to take 3 hours.

The reason I used strings was that I already had a routine for counting the numbers of characters in a string and I was too lazy to do something with arrays! For completeness, I'll check out your code and see what improvements it makes.

I found that there were consistently fewer runs of "11" or "22" than I'd have expected using Next(1,7) and Next(0,12000) \ 2000 +1 seemed to clear it up.

dlouth15

You might be interested in this. While most of the programs here - with the exception of the R code - are Monte Carlo simulations, this C++ program is a brute force method. It has one optimisation in that it it only cycles through combinations, not permutations, of the dice throws. So if 1112 comes up, then this also covers "1211", "2111" and so on. This then is compared only with combinations of the other player. If there's a win then the permutations of each of the first and second player's throws are calculated, multiplied together and added to the win total.

Here's some results. Takes a few seconds on my computer.

            1          2          3          4          5          6          7          8          9         10
1  0.16666700 0.30555600 0.42129600 0.51774700 0.59812200 0.66510200 0.72091800 0.76743200 0.80619300 0.83849400
2  0.00000000 0.05092590 0.12808600 0.21617800 0.30598400 0.39220000 0.47200400 0.54412200 0.60822300 0.66452300
3  0.00000000 0.00000000 0.02134770 0.06539350 0.12664000 0.19834700 0.27465000 0.35113600 0.42479600 0.49376400
4  0.00000000 0.00000000 0.00000000 0.01089890 0.03811940 0.08140510 0.13741900 0.20184600 0.27058600 0.34026800
5  0.00000000 0.00000000 0.00000000 0.00000000 0.00635324 0.02438890 0.05596290 0.10001400 0.15385300 0.21425300
6  0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00406482 0.01669440 0.04044540 0.07557440 0.12065000
7  0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00278240 0.01201890 0.03037240 0.05881130
8  0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00200315 0.00899496 0.02350630
9  0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00149916 0.00694093
10 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00115682

And the program itself. It is in C++ but it should be fairly easy to translate it to java, c# etc.

#include <iostream>
#include <cmath>

using namespace std;

// class rollset represents a set of rolls of a die.
class rollset {
protected:
	int numdice;  // number of throws in the roll set.
	int maxthrow;  // faces of the die (normally 6)
	int* arrThrows;  // array to hold a multiset of throws

public:
	// creator
	rollset(const int pmaxthrow, const int pnumdice) {
		setNumdice(pnumdice);
		setMaxthrow(pmaxthrow);
		arrThrows = new int[pnumdice];
		reset();
	}
	// destructor.
	virtual ~rollset() {delete [] arrThrows;}

	// Get and set methods.
	const int* getArrThrows() const {return arrThrows;}
	int getMaxthrow() const {return maxthrow;}
	void setMaxthrow(int maxthrow = 6) {this->maxthrow = maxthrow;}
	int getNumdice() const {return numdice;}
	void setNumdice(int numdice = 5) {this->numdice = numdice;}

	// Update rollset to the next combination.
	bool update() {
		bool finished = (arrThrows[0]==maxthrow);

		if (!finished)
			for (int i = numdice-1 ; i >=0 ; i--) {
				if (arrThrows[i]<maxthrow) {
					arrThrows[i]++;
					for (int j = i ; j < numdice; j++)
						arrThrows[j] = arrThrows[i];
					break;
				}
			}
		return (finished);
	}

	// Reset rollset back to initial configuration
	void reset() {
		for (int i = 0; i < numdice; i++)
			arrThrows[i]=1;
	}

	// Calculate permuations of current combination.
	unsigned long long permuations() {
		unsigned long long numerator = fact(numdice);
		unsigned long long denominator = 1;
		int lastthrow = arrThrows[1];
		int currentcount = 0;

		for (int i = 0; i <= numdice; i++)
			if (i < numdice && arrThrows[i]==lastthrow)
				currentcount++;
			else {
				denominator *= fact(currentcount);
				currentcount = 1;
				lastthrow = arrThrows[i];
			}
		return numerator / denominator;
	}

	// Calculate a factorial
	static unsigned long long fact(int n) {
		unsigned long long fact = 1;
		for (int i = 1 ; i <= n ; i++)
			fact *= i;
		return fact;
	}


	// Determine if the current object wins against "other".
	bool wins(rollset &other) {
		int othermax = other.getNumdice();
		int *firstresults = new int[maxthrow]();
		int *secondtresults = new int[maxthrow]();

		// First player
		for (int i=0 ; i < numdice ; i++)
			firstresults[arrThrows[i]-1]++;

		// Second player
		const int* otherArr = other.getArrThrows();
		for (int i=0 ; i < othermax ; i++)
			secondtresults[otherArr[i]-1]++;

		// See who wins
		bool win = true;
		for (int i = 0 ; i < maxthrow ; i++)
			if (firstresults[i] < secondtresults[i]) {
				win = false;
				break;
			}

		delete [] firstresults;
		delete [] secondtresults;
		return win;
	}
};

int main() {
	const int maxthrow = 6;  // no. of faces on die

	for (int i = 1; i <= 10 ; i++){
		for (int j=1; j <= 10; j++)
			if (j < i)
				cout << 0 << " ";
			else {
			rollset player1(maxthrow, i);
			rollset player2(maxthrow, j);
			long long wins = 0;
			do {
				do {
					if (player2.wins(player1))
						// update wins with no. of possible games this win represents
						wins += player1.permuations() * player2.permuations();
				} while (!player2.update());  // update player 2
				player2.reset();  // return to initialized state.
			} while (!player1.update());  // update player 1
			cout  << (double) wins /  pow(6, i + j) << " " ;
		}
		cout << endl;
	}
	return 0;
}

gleesonger

dlouth15 wrote: »

You might be interested in this. While most of the programs here - with the exception of the R code - are Monte Carlo simulations, this C++ program is a brute force method. It has one optimisation in that it it only cycles through combinations, not permutations, of the dice throws.

Nice approach.

M.T. Cranium

Visualizing the odds for a four-toss situation:

There are 1296 results (e.g. 1111, 1112, 2346, 3556, 4556, 3124, 4126 etc).

For the six cases of all four tosses giving the same result, no alternate ways exist so that these six cases all have probability of 1 in 1296. The overall probability of throwing the same number four times is 6 in 1296.

For the five cases of three 1's and one other number, four ways exist to reach that result, so for each of them the probability of each is 4 in 1296, and of any (with three 1's) 20 in 1296. As there are six groups like that, the overall probability is 120 in 1296. (cumulative now 126 in 1296)

For the five cases of two 1's and two of some other number, six ways exist to reach that result, so for each of them the probability is 6 in 1296. There are five such sets where 1 is one of the pairs, so that gives an overall probability of 30 in 1296 of throwing this combination. Then for two 2's, having already counted the one case with 1's, there are four more sets, another 24 in 1296 chance is added, etc (18, 12, 6) so that overall, there are 90 ways of throwing two pairs of numbers out of 1296.
(cumulative now 216 in 1296)

For the ten cases of two 1's and two different other numbers, each of them has 12 ways of appearing in sequence (as an example, 1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211) and there are ten such groups so that the chance of rolling two 1's and two other different numbers is 120 in 1296. And there are five other groupings like that based on pairs of 2's, 3's, 4's, 5's and 6's which gives a total of 720 out of 1296 chances of rolling a pair and two other numbers. (cumulative now 936 in 1296).

And this leaves us with cases of four different numbers. The chance of rolling any one of them is 24 in 1296, and there are 15 such groups for a total of 360. (example, to get 1234 also 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4312 4321 4213 4231).

The cumulative probability is now 1296 in 1296. One of the above outcomes has to happen.

Now, this gives us a foundation to judge the probability of matching the four-dice result with an independent throw of 4 or more dice.

When one throws four dice, the chances are obviously very low that there will be a matching outcome. The probability of specific outcomes are:

Any four of a kind ___ 1 in 1296
Any three of a kind __ 4 in 1296
Any two of a kind
__ (with another pair) 6 in 1296
__ (with two other n's) 12 in 1296

Four different numbers
__ each set _________ 24 in 1296

So that the chances of matching up with four throws will be 1 in 1296^2 or 1 in 1679676.

The chances of matching up a specific three of a kind outcome is 16 in 1679676.
The chances of matching up a specific two of a kind with another pair is 36 in 1679676 and
The chances of matching up a specific two of a kind with two other numbers is 144 in 1679676.

Finally the chances of matching four specific different numbers is 576 in 1679676.

What are the chances of being one number short of a match (to serve as a foundation for probabilities when five dice are tossed)?

To be one short of four of a kind, one must have rolled the appropriate three of a kind, so that gives us a probability of 4 in 1679676 that one could complete the set with a fifth throw, and the chances there are 1 in 6 so that overall in five dice, the probability is 4 in 6x1679676 which is somewhat lower than the initial probability, but clearly the person in this situation would soon manage a hit, the chances of missing the right number three times in a row is 125/216 so that by seven dice the chances have risen to 91/216 that you've matched this most difficult of the tests, if you were already at three hits after four tries.

I think the odds of matching even the more easily produced combinations (the four different numbers) must be so low that seven or eight tosses would be needed to bring probability up into the 50-50 range.

As an approximate check of that, I tested as follows for the specific outcome 1234 (which can be made 24 ways so that it has a 24 in 1296 chance of being the outcome, or 1 in 54 in round numbers).

On my first toss, I have a 2/3 chance of hitting a "good" number. On my second toss, I have a somewhat lower chance of hitting a "good" number. In the 2/3 of cases where I hit one the first time, I am now trying for half of the numbers on the dice. If I hit then, on the third toss I am looking for one third of the numbers. And if I hit there, I am looking for one sixth of them. Each time I miss, my operating probability slides one turn to the right. So for one attempt, I might succeed totally and the chances of doing that are 2/3 x 1/2 x 1/3 x 1/6 or 2/108 or 1/54. So every 54 times I toss four dice, I will succeed in matching 1234 in some order. How about for five tosses?

Once every 54 times, the five toss trial will be "won" after four throws. But the trial is blind and the fifth throw, which is now meaningless, goes ahead. How many other times in 54 will the trial succeed? Well, that presumes one missed number. It doesn't matter which of the five tosses misses, one does. The chance that it misses will be 1/3 since two numbers on the dice are "no good" for the trial. There are five places this can happen in the trial. So the cumulative probability of the five-toss trial hitting is (1/54)+(5/3*54) or (2.67/54).

Each successive number of tosses takes that previous probability and adds basically one third of the next in the series (5 choose 1) then one-ninth of (6 choose 2 = 15) and 1/27 of (7 ch 3 = 28) etc (based on number of combinations for failed throws times probability of them) so that probability is gradually increasing rather slowly, for six tosses my estimate would be 2.67/54 + 1.67/54 = 4.33/54. For seven tosses, it's 4.33/54 + 1.04/54 which is 5.37/54. There must be third order terms that are negligible until you reach larger numbers, as this method may eventually exceed the limit of unity. It does show that the break-even point is probably 12 to 15 tosses, and given that we are testing relatively high probability outcomes, overall it will likely settle at 16 to 20 tosses required to give better than 50-50 odds of matching the sequence of four tosses of the dice. I tested this as follows for 1234

Trial 1

5 6 6 1 2 4 4 6 5 4 1 3 (12 tosses required)

Trial 2

3 5 3 5 1 6 2 6 1 5 4 (11 tosses required)

Trial 3

3 2 5 2 6 2 5 1 3 3 4 (11 tosses required)

note for the least likely outcomes, if one blended those into a mega-trial,

it would require this number of tosses for four of a kind:

1 _ 21
2 _ 27
3 _ 24
4 _ 23
5 _ 16
6 _ 18

(an average of 21.5)