Recommend
2 
 Thumb up
 Hide
28 Posts
1 , 2  Next »   | 

BoardGameGeek» Forums » Gaming Related » General Gaming

Subject: Probability problems rss

Your Tags: Add tags
Popular Tags: [View All]
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
It's been over four years since I last did this, and things have improved since, so ...

I have a program that will tackle probability problems. It started with the approach of doing it by the "do lots of times, collect statistics" approach (*) but later I added a way to do things exactly. Recently I made a big step forward on the latter, and some problems that would have taken longer than the age of the universe can now be done in milliseconds. But some problems (especially those of indefinite length) can't be solved exactly.

The main reason for this posting is to say, have you got any interesting problems? In part, because this might be helpful, in part because seeing other people's problems makes you think about whether and how those can be done.

If you can use a tool such as anydice, then that's obviously going to be better for you - not just because it's there to use. Things a bit less straightforward are probably more of interest. Doesn't have to be dice, drawing from a deck or cards, or things from a bag are also possible (the latter is less likely to be soluble exactly with the program).

The area that's unlikely to work is any problem requiring intelligence within the problem. A set of pre-specified rules, maybe.

Last time I tried this, there was a question about loaded dice. That was an area I had difficulty with exactly. Less so now. But I don't want to bias the problems, so I won't give examples of what I can do/have done here.

Obviously how well I respond depends in part how many problems get posted. But if the number is reasonable, I'll try to say at least something. That might be "I can do that without the program", it might be "I can't do that", or it might be an answer. In the latter case you'll probably get some output from the program that may or may not make sense directly, plus some comment. How quickly will depend on numbers, difficulty, and outside circumstances.

That's all I need to say. For those who might be interested, essentially I turn the problem into the notation the program takes as input, which I call an expression, and tell it what to do with it, including what output is wanted - there are various sorts available. Statistical output comes with confidence intervals. The program is written in C++.

(*) That's known as Monte-Carlo simulation, for which reason I call the program Monaco. Though the days I'm as interests in exact results.

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George P.E., PMP, DM
United States
Austin
Texas
flag msg tools
Hourglass Realm D&D 5e Play by Forum (PbF) Campaign DM (we'd love to have you join us!)
badge
U.S.S. Tautog (SSN 639) doing an emergency blow with me on it (see profile for details)
Avatar
mbmbmbmbmb
That is interesting. Does it compile easily in Visual Studio?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
GeorgeMo wrote:
That is interesting. Does it compile easily in Visual Studio?


It's a command line driven program (you can put some things in files, but I rarely do) written in pure C++98 (it predates C++11, and I've kept it there) without any external libraries. So it should. The only other person who has done anything with it might have compiled it with VS, but I never have. I compile it with Clang (I started with gcc when I first created the program) and run it on MAC OS X.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Andy Holt
England
Rayleigh
Essex
flag msg tools
This is not the cat you're looking for - some other cat maybe?
badge
tout passe, tout lasse, tout casse
Avatar
mbmbmbmbmb
There are C++ to Java translation programs so it may well easily port to Android.
Also MS Visual Studio has an optional feature for compiling C++ for Android (if VS is running on Windoze) or for iOS (if VS is running on a MAC). No idea how well any of these work.
There are native(ish) C++ available on both Android and iOS - again never tried them.

Chris has almost certainly taken some care to keep his code portable but I don't think he has a tablet (yet) or has tried it on his iPhone.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
andyholt wrote:
Chris has almost certainly taken some care to keep his code portable but I don't think he has a tablet (yet) or has tried it on his iPhone.


Porting to my iPhone is on my list. But it's a long list. (I don't just mean related to this program.) But it would need a GUI, however rudimentary. And I'd need to sign up as a developer and pay some money - though not until I'd developers the app on the Mac. But first step, a tutorial on writing iOS apps. (Not expecting that to be hard, but not trivial either.) Obviously I'd use Xcode as the development environment.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
OK, we went off on a software diversion. But my original question was did anyone have any problems of interest?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Larry L
United States
Stockton
California
flag msg tools
Roll for it
badge
I + I = 0
Avatar
mbmbmbmbmb
A good one is "exploding dice". For example, an old rpg you roll two dice, add to a base and compare to a total. What makes it interesting is that doubles add and roll over.

To keep things simple, roll two d6. Doubles add and roll again (and more doubles add and roll again). What is the probability distribution? (Of course you can get any number from 3 to forever, but feel free to stop at a reasonable cap, if you like)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
kwk442 wrote:
Only of interest to me, probably. I was thinking of trying to write an AI for Lost Cities but I don't know how to write a "minimax" when complete information is not known. I read the terms "expectimax" and "Monte Carlo tree search" but that's about as far as I got.


Unfortunately, that's not the sort of problem I can tackle, it's one involving intelligence, which as I mentioned isn't what my program does.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
RingelTree wrote:
A good one is "exploding dice". For example, an old rpg you roll two dice, add to a base and compare to a total. What makes it interesting is that doubles add and roll over.

To keep things simple, roll two d6. Doubles add and roll again (and more doubles add and roll again). What is the probability distribution? (Of course you can get any number from 3 to forever, but feel free to stop at a reasonable cap, if you like)


That's easy to simulate, the cap being simply the greatest number of re-rolls that happen to occur in the however many million results you try.

Exact results aren't possible (with this program) unless one puts a rigid cap on. Of course one could try different caps.

The re-roll criterion needs thought. You're rolling two dice and re-rolling doubles. I've actually done that with a different sort of cap: on your third double you get an error result. (I think we can all recognise that one.) My quick Google finds a more than two dice option used is re-rolling single dice that roll maximum. That of course can start with any number of dice.

Re-rolling a variable number of dice isn't that exact friendly either. But a trick us to actually make all the rolls at once. My guess is that five rolls of two dice, which is 60 million possibilities, will be the practical limit (one more would probably take hours, but I don't know how many).

The real win I recently added was to weight states. I don't currently see how to weight this problem. That makes it interesting to think about. I can see how to weight the "re-roll maximum" case to at least some effect, and possibly a significant effect.

But right now I don't have time to try it, nor this evening (playing games). But I will look into it.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
wayne mathias
United States
Niceville
Florida
flag msg tools
badge
Avatar
mbmbmbmbmb
Brute force seems the wrong approach in many cases.

Exploding dice: average value is 7
average value of doubles is 7
doubles appear 1/6 of time

7 + 7/6 + 7/(6*6) + 7/(6*6*6) + 7/(6*6*6*6) .................

So while it will never reach an absolute value it is easy to see what the limit approaches by simple inspection.

Is this a case of "When your only tool is a hammer every problem looks like a nail" ?

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
gxnpt wrote:
Brute force seems the wrong approach in many cases.

Exploding dice: average value is 7
average value of doubles is 7
doubles appear 1/6 of time

7 + 7/6 + 7/(6*6) + 7/(6*6*6) + 7/(6*6*6*6) .................

So while it will never reach an absolute value it is easy to see what the limit approaches by simple inspection.

Is this a case of "When your only tool is a hammer every problem looks like a nail" ?



No, it's a question of what was asked for.

Mean is easy. In fact it's even easier than you present it as, there's no need to introduce an infinite series to solve it.

Distribution, which was what was asked for, is harder. Because exploding dice are always positive, you can cap the re-rolls for any given target.

But it's still considerably more work than a mean.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Larry L
United States
Stockton
California
flag msg tools
Roll for it
badge
I + I = 0
Avatar
mbmbmbmbmb
A single exploding die where you reroll the maximum value isn't very complex. For example single d6, where you reroll sixes and add to 5 (some would add to 6 but it is essentially the same with a different range of values)

1-5: 1/6
6-10: 1/6^2
11-15: 1/6^3
and so on.

That's why I like the doubles problem. It is more challenging.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
RingelTree wrote:
A single exploding die where you reroll the maximum value isn't very complex. For example single d6, where you reroll sixes and add to 5 (some would add to 6 but it is essentially the same with a different range of values)

1-5: 1/6
6-10: 1/6^2
11-15: 1/6^3
and so on.

That's why I like the doubles problem. It is more challenging.


Even rerolling maxima gets more interesting with more than one die (where it is, as you indicate, boring).

I haven't done the doubles yet. It's posed an interesting question as to whether a certain reorganisation of the problem (for a given maximum number of rolls) leaves the distribution unchanged. (It leaves the mean unchanged, but that's boring.) If it does leave it unchanged it will allow me to increase the maximum size of problem (number of re-rolls) significantly.

But no time to try today (given my time zone). Maybe tomorrow, I'll see.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Julien K
Japan
Kyoto
flag msg tools
RingelTree wrote:
A good one is "exploding dice". For example, an old rpg you roll two dice, add to a base and compare to a total. What makes it interesting is that doubles add and roll over.

To keep things simple, roll two d6. Doubles add and roll again (and more doubles add and roll again). What is the probability distribution? (Of course you can get any number from 3 to forever, but feel free to stop at a reasonable cap, if you like)


If I got my math correctly, the probability should be something like this:
p(n)=p*(n)+(p(n-2)+p(n-4)+p(n-6)+p(n-8)+p(n-10)+p(n-12))/36

where p(n) is the probability of rolling n with exploding dice (obviously, p(i)=0 for i<=1), and p*(n) is the probability of rolling a natural n with two dice and without rolling a double (so p*(2)=0 and p*(3)=p*(4)=2/36 for example)

That would make a distribution that goes like this

2 0
3 0.0555555556
4 0.0555555556
5 0.112654321
6 0.112654321
7 0.1713391632
8 0.1157836077
9 0.1205430289
10 0.0634442635
11 0.0683358908
12 0.0096510485
13 0.0146785544
14 0.0099191332
15 0.0150862921
16 0.0101946647
17 0.0139621458
18 0.00893464
19 0.0112206965
20 0.0060535377
21 0.0067729613
22 0.0030054802
...

Interesting to see how it's easier to make certain higher rolls than other lower rolls. For example, it's very hard to roll an 18 compared to 19, 20 or 21, and it's easier to roll a 15 than it is to roll a 13, which in turns has higher probability than a 12

--- edit : added some missing * in the explanation of p*
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
OK, my starting point is the ideal problem - no limit on number of re-rolls - but simulated results only. (Unfortunately it's one or the other.) This serves as a baseline starting point. And over a hundred million results (which takes my program about a minute on my machine - yes, a dedicated program might be faster, the point is this can do many problems) I get these results. Note that the ranges in [] are estimated 95% confidence intervals. The results aren't exact, but they aren't bad.


Expression = until(r9+=(r0:=d6)+(r1:=d6),r0!=r1)
Number = 100000000

Number of results = 100000000
Mean = 8.40044
Standard deviation = 4.3314
Standard deviation of mean = 0.00043314
95% confidence interval = [8.39959, 8.40128]

3 - 5555377 ~ 0.0555538 [0.0555089, 0.0555987]
4 - 5554658 ~ 0.0555466 [0.0555017, 0.0555915]
5 - 11263425 ~ 0.112634 [0.112572, 0.112696]
6 - 11265014 ~ 0.11265 [0.112588, 0.112712]
7 - 17133241 ~ 0.171332 [0.171259, 0.171406]
8 - 11579049 ~ 0.11579 [0.115728, 0.115853]
9 - 12053578 ~ 0.120536 [0.120472, 0.1206]
10 - 6348327 ~ 0.0634833 [0.0634355, 0.0635311]
11 - 6829986 ~ 0.0682999 [0.0682504, 0.0683493]
12 - 965224 ~ 0.00965224 [0.0096331, 0.00967142]
13 - 1467763 ~ 0.0146776 [0.0146541, 0.0147012]
14 - 992509 ~ 0.00992509 [0.00990568, 0.00994454]
15 - 1510186 ~ 0.0151019 [0.015078, 0.0151258]
16 - 1017883 ~ 0.0101788 [0.0101592, 0.0101985]
17 - 1395930 ~ 0.0139593 [0.0139363, 0.0139823]
18 - 894294 ~ 0.00894294 [0.00892451, 0.00896141]
19 - 1122973 ~ 0.0112297 [0.0112091, 0.0112504]
20 - 607647 ~ 0.00607647 [0.00606126, 0.00609172]
21 - 676380 ~ 0.0067638 [0.00674775, 0.00677988]
22 - 300966 ~ 0.00300966 [0.00299894, 0.00302042]
23 - 361359 ~ 0.00361359 [0.00360185, 0.00362537]
24 - 132405 ~ 0.00132405 [0.00131694, 0.0013312]
25 - 182237 ~ 0.00182237 [0.00181403, 0.00183075]
26 - 109466 ~ 0.00109466 [0.0010882, 0.00110116]
27 - 145377 ~ 0.00145377 [0.00144632, 0.00146126]
28 - 84991 ~ 0.00084991 [0.000844218, 0.000855641]
29 - 108191 ~ 0.00108191 [0.00107549, 0.00108837]
30 - 59341 ~ 0.00059341 [0.000588656, 0.000598202]
31 - 71892 ~ 0.00071892 [0.000713686, 0.000724193]
32 - 35795 ~ 0.00035795 [0.000354262, 0.000361677]
33 - 42999 ~ 0.00042999 [0.000425946, 0.000434073]
34 - 20195 ~ 0.00020195 [0.000199184, 0.000204754]
35 - 25337 ~ 0.00025337 [0.00025027, 0.000256509]
36 - 12173 ~ 0.00012173 [0.000119587, 0.000123912]
37 - 15809 ~ 0.00015809 [0.000155645, 0.000160573]
38 - 8913 ~ 8.913e-05 [8.72987e-05, 9.09997e-05]
39 - 11473 ~ 0.00011473 [0.00011265, 0.000116849]
40 - 5954 ~ 5.954e-05 [5.80467e-05, 6.10718e-05]
41 - 7660 ~ 7.66e-05 [7.49037e-05, 7.83347e-05]
42 - 3996 ~ 3.996e-05 [3.874e-05, 4.12184e-05]
43 - 4804 ~ 4.804e-05 [4.67005e-05, 4.94179e-05]
44 - 2415 ~ 2.415e-05 [2.32057e-05, 2.51328e-05]
45 - 2934 ~ 2.934e-05 [2.82972e-05, 3.04212e-05]
46 - 1472 ~ 1.472e-05 [1.39867e-05, 1.54917e-05]
47 - 1988 ~ 1.988e-05 [1.90249e-05, 2.07735e-05]
48 - 957 ~ 9.57e-06 [8.98228e-06, 1.01961e-05]
49 - 1207 ~ 1.207e-05 [1.14077e-05, 1.27707e-05]
50 - 665 ~ 6.65e-06 [6.16305e-06, 7.17536e-06]
51 - 819 ~ 8.19e-06 [7.64765e-06, 8.77077e-06]
52 - 449 ~ 4.49e-06 [4.09301e-06, 4.9254e-06]
53 - 556 ~ 5.56e-06 [5.11626e-06, 6.04216e-06]
54 - 281 ~ 2.81e-06 [2.49954e-06, 3.15888e-06]
55 - 340 ~ 3.4e-06 [3.05679e-06, 3.78163e-06]
56 - 180 ~ 1.8e-06 [1.55485e-06, 2.08356e-06]
57 - 232 ~ 2.32e-06 [2.03944e-06, 2.63897e-06]
58 - 109 ~ 1.09e-06 [9.02786e-07, 1.31563e-06]
59 - 177 ~ 1.77e-06 [1.52704e-06, 2.05137e-06]
60 - 56 ~ 5.6e-07 [4.30043e-07, 7.28372e-07]
61 - 87 ~ 8.7e-07 [7.04387e-07, 1.07403e-06]
62 - 36 ~ 3.6e-07 [2.58513e-07, 4.99901e-07]
63 - 71 ~ 7.1e-07 [5.61839e-07, 8.96576e-07]
64 - 38 ~ 3.8e-07 [2.75371e-07, 5.23043e-07]
65 - 37 ~ 3.7e-07 [2.66932e-07, 5.11483e-07]
66 - 19 ~ 1.9e-07 [1.1956e-07, 2.98854e-07]
67 - 25 ~ 2.5e-07 [1.67514e-07, 3.709e-07]
68 - 15 ~ 1.5e-07 [8.85845e-08, 2.4983e-07]
69 - 15 ~ 1.5e-07 [8.85845e-08, 2.4983e-07]
70 - 8 ~ 8e-08 [3.74739e-08, 1.60941e-07]
71 - 8 ~ 8e-08 [3.74739e-08, 1.60941e-07]
72 - 3 ~ 3e-08 [5.72997e-09, 9.26846e-08]
73 - 6 ~ 6e-08 [2.40465e-08, 1.34368e-07]
74 - 2 ~ 2e-08 [3.98378e-10, 7.80162e-08]
75 - 5 ~ 5e-08 [1.7646e-08, 1.20769e-07]
76 - 1 ~ 1e-08 [0, 6.27034e-08]
77 - 3 ~ 3e-08 [5.72997e-09, 9.26846e-08]
79 - 4 ~ 4e-08 [1.15164e-08, 1.06898e-07]
80 - 1 ~ 1e-08 [0, 6.27034e-08]
81 - 1 ~ 1e-08 [0, 6.27034e-08]
82 - 1 ~ 1e-08 [0, 6.27034e-08]

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
However here's still simulated results for a maximum of 3 rolls. Yes 3 is much fewer than we are going to be able to do exactly, and a hundred million results for what is a state space of only 46656 is ridiculous. But it's easier to start low, then increase later.


Expression = until(r8+=1;r9+=(r0:=d6)+(r1:=d6),r0!=r1|r8==3)
Number = 100000000

Number of results = 100000000
Mean = 8.3615
Standard deviation = 4.16725
Standard deviation of mean = 0.000416725
95% confidence interval = [8.36068, 8.36231]

3 - 5555082 ~ 0.0555508 [0.0555059, 0.0555957]
4 - 5554454 ~ 0.0555445 [0.0554997, 0.0555894]
5 - 11263401 ~ 0.112634 [0.112572, 0.112696]
6 - 11267716 ~ 0.112677 [0.112615, 0.112739]
7 - 17133493 ~ 0.171335 [0.171261, 0.171409]
8 - 11585120 ~ 0.115851 [0.115788, 0.115914]
9 - 12053630 ~ 0.120536 [0.120473, 0.1206]
10 - 6361365 ~ 0.0636136 [0.0635658, 0.0636615]
11 - 6829327 ~ 0.0682933 [0.0682438, 0.0683427]
12 - 986562 ~ 0.00986562 [0.00984627, 0.00988501]
13 - 1466000 ~ 0.01466 [0.0146365, 0.0146836]
14 - 1022715 ~ 0.0102272 [0.0102074, 0.0102469]
15 - 1506284 ~ 0.0150628 [0.015039, 0.0150867]
16 - 1059460 ~ 0.0105946 [0.0105746, 0.0106147]
17 - 1388667 ~ 0.0138867 [0.0138638, 0.0139096]
18 - 941732 ~ 0.00941732 [0.00939841, 0.00943627]
19 - 1110790 ~ 0.0111079 [0.0110874, 0.0111285]
20 - 655969 ~ 0.00655969 [0.00654389, 0.00657553]
21 - 659183 ~ 0.00659183 [0.00657599, 0.00660771]
22 - 345457 ~ 0.00345457 [0.00344309, 0.00346609]
23 - 338676 ~ 0.00338676 [0.00337539, 0.00339817]
24 - 169063 ~ 0.00169063 [0.0016826, 0.0016987]
25 - 154733 ~ 0.00154733 [0.00153965, 0.00155505]
26 - 134838 ~ 0.00134838 [0.00134121, 0.00135559]
27 - 115575 ~ 0.00115575 [0.00114911, 0.00116243]
28 - 96635 ~ 0.00096635 [0.000960279, 0.000972459]
29 - 77548 ~ 0.00077548 [0.000770043, 0.000780955]
30 - 59823 ~ 0.00059823 [0.000593457, 0.000603042]
31 - 42688 ~ 0.00042688 [0.00042285, 0.000430948]
32 - 29939 ~ 0.00029939 [0.000296018, 0.0003028]
33 - 16948 ~ 0.00016948 [0.000166948, 0.000172051]
34 - 10643 ~ 0.00010643 [0.000104427, 0.000108471]
35 - 4323 ~ 4.323e-05 [4.19603e-05, 4.45381e-05]
36 - 2161 ~ 2.161e-05 [2.07177e-05, 2.25407e-05]

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Larry L
United States
Stockton
California
flag msg tools
Roll for it
badge
I + I = 0
Avatar
mbmbmbmbmb
Looks like Julien K's recursion is correct. Nice!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
However I need to modify the expression to work in exact mode. The one I use here gets identical results (I checked) but I can get exact results from it:


Flags = -exact
Expression = do3(r8|(r9+=(r0:=d6)+(r1:=d6);r8:=r0!=r1));r9
Number = 100000000

Number of results = 46656
Mean = 8.36111 = 301/36
Standard deviation = 4.16713

3 - 2592 ~ 0.0555556 = 1/18
4 - 2592 ~ 0.0555556 = 1/18
5 - 5256 ~ 0.112654 = 73/648
6 - 5257 ~ 0.112676 = 5257/46656
7 - 7994 ~ 0.171339 = 3997/23328
8 - 5405 ~ 0.115848 = 5405/46656
9 - 5624 ~ 0.120542 = 703/5832
10 - 2966 ~ 0.0635717 = 1483/23328
11 - 3188 ~ 0.0683299 = 797/11664
12 - 460 ~ 0.0098594 = 115/11664
13 - 684 ~ 0.0146605 = 19/1296
14 - 477 ~ 0.0102238 = 53/5184
15 - 702 ~ 0.0150463 = 13/864
16 - 495 ~ 0.0106096 = 55/5184
17 - 648 ~ 0.0138889 = 1/72
18 - 439 ~ 0.00940929 = 439/46656
19 - 518 ~ 0.0111025 = 259/23328
20 - 305 ~ 0.00653721 = 305/46656
21 - 308 ~ 0.00660151 = 77/11664
22 - 161 ~ 0.00345079 = 161/46656
23 - 158 ~ 0.00338649 = 79/23328
24 - 79 ~ 0.00169324 = 79/46656
25 - 72 ~ 0.00154321 = 1/648
26 - 63 ~ 0.00135031 = 7/5184
27 - 54 ~ 0.00115741 = 1/864
28 - 45 ~ 0.000964506 = 5/5184
29 - 36 ~ 0.000771605 = 1/1296
30 - 28 ~ 0.000600137 = 7/11664
31 - 20 ~ 0.000428669 = 5/11664
32 - 14 ~ 0.000300069 = 7/23328
33 - 8 ~ 0.000171468 = 1/5832
34 - 5 ~ 0.000107167 = 5/46656
35 - 2 ~ 4.28669e-05 = 1/23328
36 - 1 ~ 2.14335e-05 = 1/46656

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
Now I can push on to more rolls. But this approach is still brute force and the time taken grows exponentially. 5 rolls maximum is as far as sensible (a bit over minute, 6 rolls would take over half an hour, so possible, 7 rolls would take most of three days). With 5 rolls maximum:


Flags = -exact
Expression = do5(r8|(r9+=(r0:=d6)+(r1:=d6);r8:=r0!=r1));r9

Number of results = 60466176
Mean = 8.39892 = 10885/1296
Standard deviation = 4.32331

3 - 3359232 ~ 0.0555556 = 1/18
4 - 3359232 ~ 0.0555556 = 1/18
5 - 6811776 ~ 0.112654 = 73/648
6 - 6811776 ~ 0.112654 = 73/648
7 - 10360224 ~ 0.171339 = 3997/23328
8 - 7000992 ~ 0.115784 = 2701/23328
9 - 7288776 ~ 0.120543 = 101233/839808
10 - 3836233 ~ 0.0634443 = 3836233/60466176
11 - 4132010 ~ 0.0683359 = 2066005/30233088
12 - 583567 ~ 0.00965113 = 583567/60466176
13 - 887556 ~ 0.0146786 = 73963/5038848
14 - 599787 ~ 0.00991938 = 66643/6718464
15 - 912210 ~ 0.0150863 = 152035/10077696
16 - 616467 ~ 0.0101952 = 205489/20155392
17 - 844236 ~ 0.0139621 = 7817/559872
18 - 540312 ~ 0.00893577 = 22513/2519424
19 - 678468 ~ 0.0112206 = 56539/5038848
20 - 366156 ~ 0.00605555 = 10171/1679616
21 - 409524 ~ 0.00677278 = 34127/5038848
22 - 181925 ~ 0.00300871 = 181925/60466176
23 - 218422 ~ 0.0036123 = 109211/30233088
24 - 80501 ~ 0.00133134 = 80501/60466176
25 - 109692 ~ 0.00181411 = 3047/1679616
26 - 66618 ~ 0.00110174 = 3701/3359232
27 - 88056 ~ 0.00145629 = 1223/839808
28 - 51894 ~ 0.000858232 = 961/1119744
29 - 65124 ~ 0.00107703 = 67/62208
30 - 36279 ~ 0.000599988 = 4031/6718464
31 - 43434 ~ 0.000718319 = 2413/3359232
32 - 22311 ~ 0.000368983 = 2479/6718464
33 - 25740 ~ 0.000425693 = 715/1679616
34 - 12750 ~ 0.000210862 = 2125/10077696
35 - 15024 ~ 0.000248469 = 313/1259712
36 - 7998 ~ 0.000132272 = 1333/10077696
37 - 9324 ~ 0.000154202 = 259/1679616
38 - 5895 ~ 9.74925e-05 = 655/6718464
39 - 6498 ~ 0.000107465 = 361/3359232
40 - 4095 ~ 6.77238e-05 = 455/6718464
41 - 4212 ~ 6.96588e-05 = 13/186624
42 - 2646 ~ 4.376e-05 = 49/1119744
43 - 2520 ~ 4.16762e-05 = 35/839808
44 - 1602 ~ 2.64942e-05 = 89/3359232
45 - 1404 ~ 2.32196e-05 = 13/559872
46 - 941 ~ 1.55624e-05 = 941/60466176
47 - 766 ~ 1.26682e-05 = 383/30233088
48 - 557 ~ 9.21176e-06 = 557/60466176
49 - 420 ~ 6.94603e-06 = 35/5038848
50 - 324 ~ 5.35837e-06 = 1/186624
51 - 228 ~ 3.7707e-06 = 19/5038848
52 - 168 ~ 2.77841e-06 = 7/2519424
53 - 108 ~ 1.78612e-06 = 1/559872
54 - 75 ~ 1.24036e-06 = 25/20155392
55 - 42 ~ 6.94603e-07 = 7/10077696
56 - 27 ~ 4.46531e-07 = 1/2239488
57 - 12 ~ 1.98458e-07 = 1/5038848
58 - 7 ~ 1.15767e-07 = 7/60466176
59 - 2 ~ 3.30763e-08 = 1/30233088
60 - 1 ~ 1.65382e-08 = 1/60466176

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
But - and the point of the exercise - is that this is still really inefficient. I have better ways to do this now. I can easily make a simple saving, but I want to use so tools I've recently added to go significantly further. But they don't exactly match this problem, so I need to think how to recast the problem to match what I have. (One recasting I'm not sure if it's the same or not.)

And I was just going to sign off with something slightly better, with a hope of something definitely better tomorrow. When something just went wrong. So maybe tomorrow, maybe later.

(OK, I know what went wrong. It's not trivial to fix. Well, useful, in an unfortunate sort of way.)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
Not yet made the leap forward I'm hoping for (there's a reorganisation of the problem I'm not yet sure is equivalent, but if it is, I can do things much faster) and I'm running a program that still needs work to fix (but this example avoids the problems).

But one small step forward allows me to get to a maximum of six rolls in under three minutes (compared to previous estimate of half an hour).

Incidentally note that 6 rolls means that the results up to 11 are exact for any number of rolls. The previous results were exact up to 9, and the first difference is seen at 10 (though you would need more than six significant figures - which I could report - to see the difference, but the exact results are different).


Flags = -exact
Expression = do6(r8|(r01:=sorted2d6;r9+=r0+r1;r8:=r0!=r1));r9

Number of samples = 85766121
Number of results = 2176782336
Mean = 8.39982 = 65317/7776
Standard deviation = 4.32966

3 - 120932352 ~ 0.0555556 = 1/18
4 - 120932352 ~ 0.0555556 = 1/18
5 - 245223936 ~ 0.112654 = 73/648
6 - 245223936 ~ 0.112654 = 73/648
7 - 372968064 ~ 0.171339 = 3997/23328
8 - 252035712 ~ 0.115784 = 2701/23328
9 - 262395936 ~ 0.120543 = 101233/839808
10 - 138104352 ~ 0.0634443 = 53281/839808
11 - 148752360 ~ 0.0683359 = 2066005/30233088
12 - 21008233 ~ 0.00965105 = 21008233/2176782336
13 - 31952018 ~ 0.0146786 = 15976009/1088391168
14 - 21591800 ~ 0.00991914 = 2698975/272097792
15 - 32839574 ~ 0.0150863 = 16419787/1088391168
16 - 22191587 ~ 0.0101947 = 22191587/2176782336
17 - 30392552 ~ 0.0139621 = 3799069/272097792
18 - 19448822 ~ 0.00893467 = 9724411/1088391168
19 - 24425012 ~ 0.0112207 = 6106253/544195584
20 - 13177358 ~ 0.00605359 = 6588679/1088391168
21 - 14743256 ~ 0.00677296 = 1842907/272097792
22 - 6542522 ~ 0.00300559 = 3271261/1088391168
23 - 7864004 ~ 0.00361267 = 1966001/544195584
24 - 2888214 ~ 0.00132683 = 481369/362797056
25 - 3950416 ~ 0.0018148 = 246901/136048896
26 - 2385148 ~ 0.00109572 = 596287/544195584
27 - 3172552 ~ 0.00145745 = 396569/272097792
28 - 1851979 ~ 0.000850787 = 1851979/2176782336
29 - 2348398 ~ 0.00107884 = 1174199/1088391168
30 - 1287406 ~ 0.000591426 = 643703/1088391168
31 - 1569286 ~ 0.00072092 = 784643/1088391168
32 - 783373 ~ 0.000359877 = 783373/2176782336
33 - 934252 ~ 0.000429189 = 233563/544195584
34 - 439528 ~ 0.000201916 = 54941/272097792
35 - 550468 ~ 0.000252882 = 137617/544195584
36 - 270353 ~ 0.000124198 = 270353/2176782336
37 - 347070 ~ 0.000159442 = 57845/362797056
38 - 197850 ~ 9.0891e-05 = 32975/362797056
39 - 246702 ~ 0.000113333 = 41117/362797056
40 - 137127 ~ 6.29953e-05 = 45709/725594112
41 - 165144 ~ 7.58661e-05 = 6881/90699264
42 - 89328 ~ 4.10367e-05 = 1861/45349632
43 - 104232 ~ 4.78835e-05 = 4343/90699264
44 - 55695 ~ 2.55859e-05 = 18565/725594112
45 - 63318 ~ 2.90879e-05 = 10553/362797056
46 - 34986 ~ 1.60723e-05 = 5831/362797056
47 - 38982 ~ 1.79081e-05 = 6497/362797056
48 - 23177 ~ 1.06474e-05 = 23177/2176782336
49 - 24724 ~ 1.1358e-05 = 6181/544195584
50 - 15736 ~ 7.22902e-06 = 1967/272097792
51 - 15820 ~ 7.26761e-06 = 3955/544195584
52 - 10165 ~ 4.66974e-06 = 10165/2176782336
53 - 9550 ~ 4.38721e-06 = 4775/1088391168
54 - 6238 ~ 2.8657e-06 = 3119/1088391168
55 - 5446 ~ 2.50186e-06 = 2723/1088391168
56 - 3667 ~ 1.6846e-06 = 3667/2176782336
57 - 2968 ~ 1.36348e-06 = 371/272097792
58 - 2092 ~ 9.61052e-07 = 523/544195584
59 - 1576 ~ 7.24004e-07 = 197/272097792
60 - 1158 ~ 5.31978e-07 = 193/362797056
61 - 812 ~ 3.73028e-07 = 203/544195584
62 - 602 ~ 2.76555e-07 = 301/1088391168
63 - 392 ~ 1.80082e-07 = 49/272097792
64 - 278 ~ 1.27711e-07 = 139/1088391168
65 - 164 ~ 7.53406e-08 = 41/544195584
66 - 110 ~ 5.05333e-08 = 55/1088391168
67 - 56 ~ 2.5726e-08 = 7/272097792
68 - 35 ~ 1.60788e-08 = 35/2176782336
69 - 14 ~ 6.43151e-09 = 7/1088391168
70 - 8 ~ 3.67515e-09 = 1/272097792
71 - 2 ~ 9.18787e-10 = 1/1088391168
72 - 1 ~ 4.59394e-10 = 1/2176782336


Results are getting lengthy, so here are just the fully exact results (another option I have):


3 - 120932352 ~ 0.0555556 = 1/18
4 - 120932352 ~ 0.0555556 = 1/18
5 - 245223936 ~ 0.112654 = 73/648
6 - 245223936 ~ 0.112654 = 73/648
7 - 372968064 ~ 0.171339 = 3997/23328
8 - 252035712 ~ 0.115784 = 2701/23328
9 - 262395936 ~ 0.120543 = 101233/839808
10 - 138104352 ~ 0.0634443 = 53281/839808
11 - 148752360 ~ 0.0683359 = 2066005/30233088
> 11 - 270213336 ~ 0.124134 = 3752963/30233088



 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Pete K
United States
Arizona
flag msg tools
badge
new reviews: Bargain Hunter, Sushi Go
Avatar
mbmbmbmbmb
This list might be of some interest, if you're looking for ideas for linking games with probability analysis:

Some Games for Teaching College-level Probability Concepts
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
Found a better approach (though not the one I was thinking of, which didn't work) which has enabled me to get up to a maximum of 8 rolls in a minute and a half. The results are of course exact for an indefinite number of rolls up to a result of 15, and close enough for all practical purposes for quit a bit further. After all, needing 9 rolls is a one in over a million event.


Flags = -exact
Expression = v0:=multi_select8from[head36{2,4,6,8,10,12}];rloop0(s0,(!r0|r8)&(
r9+=r8:=e0));r8|(r9+=select_from{3,4,5,5,6,6,7,7,7,8,8,9,9,10,11})
;r9

Number of samples = 51883209
Number of results = 42316648611840
Mean = 8.39999 = 2351461/279936
Standard deviation = 4.33122

3 - 2350924922880 ~ 0.0555556 = 1/18
4 - 2350924922880 ~ 0.0555556 = 1/18
5 - 4767153315840 ~ 0.112654 = 73/648
6 - 4767153315840 ~ 0.112654 = 73/648
7 - 7250499164160 ~ 0.171339 = 3997/23328
8 - 4899574241280 ~ 0.115784 = 2701/23328
9 - 5100976995840 ~ 0.120543 = 101233/839808
10 - 2684748602880 ~ 0.0634443 = 53281/839808
11 - 2891745878400 ~ 0.0683359 = 2066005/30233088
12 - 408400030080 ~ 0.00965105 = 291781/30233088
13 - 621147229920 ~ 0.0146786 = 15976009/1088391168
14 - 419744475360 ~ 0.00991913 = 10795897/1088391168
15 - 638401319640 ~ 0.0150863 = 591112333/39182082048
16 - 431404044135 ~ 0.0101947 = 28760269609/2821109907456
17 - 590831219550 ~ 0.0139621 = 19694373985/1410554953728
18 - 378084019830 ~ 0.00893464 = 12602800661/1410554953728
19 - 474822272430 ~ 0.0112207 = 1758601009/156728328192
20 - 256165428690 ~ 0.00605354 = 948760847/156728328192
21 - 286609025430 ~ 0.00677296 = 39315367/5804752896
22 - 127181851800 ~ 0.00300548 = 1059848765/352638738432
23 - 152876581770 ~ 0.00361268 = 5095886059/1410554953728
24 - 56138334000 ~ 0.00132663 = 233909725/176319369216
25 - 76796878950 ~ 0.00181481 = 284432885/156728328192
26 - 46353293550 ~ 0.00109539 = 171678865/156728328192
27 - 61676035470 ~ 0.00145749 = 228429761/156728328192
28 - 35981329320 ~ 0.000850288 = 99948137/117546246144
29 - 45655887690 ~ 0.00107891 = 507287641/470184984576
30 - 24997388310 ~ 0.000590722 = 277748759/470184984576
31 - 30512126250 ~ 0.000721043 = 113007875/156728328192
32 - 15189464655 ~ 0.000358948 = 12501617/34828517376
33 - 18170173260 ~ 0.000429386 = 33648469/78364164096
34 - 8495746470 ~ 0.000200766 = 94397183/470184984576
35 - 10713530160 ~ 0.000253175 = 14879903/58773123072
36 - 5198993820 ~ 0.000122859 = 28883299/235092492288
37 - 6764542200 ~ 0.000159855 = 6263465/39182082048
38 - 3784123710 ~ 8.9424e-05 = 14015273/156728328192
39 - 4819176540 ~ 0.000113884 = 8924401/78364164096
40 - 2601785970 ~ 6.14837e-05 = 28908733/470184984576
41 - 3239784720 ~ 7.65605e-05 = 4499701/58773123072
42 - 1674738540 ~ 3.95764e-05 = 9304103/235092492288
43 - 2061510480 ~ 4.87163e-05 = 954403/19591041024
44 - 1027062450 ~ 2.42709e-05 = 3803935/156728328192
45 - 1271149740 ~ 3.0039e-05 = 2353981/78364164096
46 - 633836430 ~ 1.49784e-05 = 7042627/470184984576
47 - 801649080 ~ 1.89441e-05 = 2226803/117546246144
48 - 415605015 ~ 9.82131e-06 = 9235667/940369969152
49 - 526219470 ~ 1.24353e-05 = 1948961/156728328192
50 - 282850380 ~ 6.68414e-06 = 174599/26121388032
51 - 352820610 ~ 8.33763e-06 = 435581/52242776064
52 - 185656020 ~ 4.3873e-06 = 3094267/705277476864
53 - 228636750 ~ 5.403e-06 = 7621225/1410554953728
54 - 118539420 ~ 2.80125e-06 = 1975657/705277476864
55 - 144877410 ~ 3.42365e-06 = 178861/52242776064
56 - 75241170 ~ 1.77805e-06 = 278671/156728328192
57 - 91532970 ~ 2.16305e-06 = 339011/156728328192
58 - 48667740 ~ 1.15008e-06 = 811129/705277476864
59 - 58682550 ~ 1.38675e-06 = 1956085/1410554953728
60 - 32229060 ~ 7.61617e-07 = 537151/705277476864
61 - 37990890 ~ 8.97776e-07 = 140707/156728328192
62 - 21365100 ~ 5.04886e-07 = 39565/78364164096
63 - 24410430 ~ 5.76852e-07 = 90409/156728328192
64 - 13878495 ~ 3.27968e-07 = 308411/940369969152
65 - 15306480 ~ 3.61713e-07 = 21259/58773123072
66 - 8896590 ~ 2.10239e-07 = 98851/470184984576
67 - 9434340 ~ 2.22946e-07 = 17471/78364164096
68 - 5670810 ~ 1.34009e-07 = 7001/52242776064
69 - 5755320 ~ 1.36006e-07 = 5329/39182082048
70 - 3599460 ~ 8.50601e-08 = 19997/235092492288
71 - 3477240 ~ 8.21719e-08 = 9659/117546246144
72 - 2254050 ~ 5.32663e-08 = 25045/470184984576
73 - 2060100 ~ 4.8683e-08 = 3815/78364164096
74 - 1370790 ~ 3.23936e-08 = 5077/156728328192
75 - 1180440 ~ 2.78954e-08 = 1093/39182082048
76 - 800460 ~ 1.8916e-08 = 4447/235092492288
77 - 647280 ~ 1.52961e-08 = 899/58773123072
78 - 448110 ~ 1.05894e-08 = 4979/470184984576
79 - 339660 ~ 8.02663e-09 = 629/78364164096
80 - 239895 ~ 5.66905e-09 = 1777/313456656384
81 - 170370 ~ 4.02607e-09 = 631/156728328192
82 - 121950 ~ 2.88184e-09 = 1355/470184984576
83 - 81090 ~ 1.91627e-09 = 901/470184984576
84 - 57960 ~ 1.36967e-09 = 161/117546246144
85 - 35910 ~ 8.48602e-10 = 133/156728328192
86 - 25110 ~ 5.93383e-10 = 31/52242776064
87 - 14310 ~ 3.38165e-10 = 53/156728328192
88 - 9600 ~ 2.26861e-10 = 5/22039921152
89 - 4890 ~ 1.15557e-10 = 163/1410554953728
90 - 3120 ~ 7.37298e-11 = 13/176319369216
91 - 1350 ~ 3.19023e-11 = 5/156728328192
92 - 810 ~ 1.91414e-11 = 1/52242776064
93 - 270 ~ 6.38047e-12 = 1/156728328192
94 - 150 ~ 3.5447e-12 = 5/1410554953728
95 - 30 ~ 7.08941e-13 = 1/1410554953728
96 - 15 ~ 3.5447e-13 = 1/2821109907456


(All the results are a factor of 15 up on the theoretically possible lowest terms, but I haven't worked out how to get rid of that factor and keep - or improve - the speed.)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ian Taylor
United Kingdom
Epping
Essex
flag msg tools
badge
Avatar
mbmbmbmbmb
Interesting project. I am curious as to what problems you ran out of computing power on. I have built similar programs before and have found that, for the problems I wanted to solve anyway, computers are so fast these days that I can brute force everything by just running 10 million simulations and looking at the average result (which most of the time is so close to the 'real' value it makes no difference).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
piemasteruk wrote:
Interesting project. I am curious as to what problems you ran out of computing power on. I have built similar programs before and have found that, for the problems I wanted to solve anyway, computers are so fast these days that I can brute force everything by just running 10 million simulations and looking at the average result (which most of the time is so close to the 'real' value it makes no difference).


I often run a hundred million samples. Whether that's good enough depends on two things.

The first is the often just psychological desire for an "exact" answer. I put exact in quotes because having got one, as a rational number, the next step is often to convert to a decimal and round, being little better than a simulated result ;if you know the confidence of the latter, always a good idea).

The second us how rare the event is. Four million results, for example, gives you a result with a relative error of about 1% when the event occurs about one hundredth of the time, a relative error of about 10% when it occurs one ten thousandth of the time, and is hopeless when it occurs one millionth of the time. Things that occur rarely are sometimes of interest, and thus there may be a problem.

Of results that aren't susceptible to improvement by some techniques I've been working on, a hard case related to cribbage. (Actually I typed that then realised there is an inprovement possible, but let's assume not for now. But I should go back to what I did.)

Scoring a cribbage hand of four cards and a turnup is not the fastest function. But it's not too hard. The number of hands us quite large, but manageable. But that's not what happens. Rather you are dealt six cards, choose two to discard, then add the turnup. Which two to discard? That requires intelligence, and I don't do that. But suppose we tried each pair we might discard, scored and averaged over the possible 46 cards turnup, picked the best, then turned up? That I have done, and the number of sample six card hands I wasn't doing multiple millions of (I forget how many I did do).

(Of course maximising expected payoff with turnup isn't actually optimum playing cribbage. But that's another story.)

I've got a more interesting example. But first some more results.

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.