Author Topic: Bridge Points Count Probabilities (original error found)  (Read 289 times)

Bridge Points Count Probabilities (original error found)
« on: March 15, 2019, 12:49:23 PM »
The other evening when playing bridge, one player was dealt a hand containing 26 points.  I then wondered what the probability was and thought: just the job for a simple program.

Background: each bridge player is dealt 13 of the 52 cards.  Simple points values are 4 for an Ace, 3 for a King, 2 for a Queen and 1 for a Jack (Knave).

Program: I arbitrarily distribute 4 lots of 4 points, 3 points, 2 points and 1 point through the 52-card pack - the array elements Pack%%(n, 0).  Then I randomly select 13 of the 52 cards and add up the points value - variable CardsValue%%.  For each points value obtained I calculate the probability of obtaining that value over many deals - elements Probs~&&(CardsValue%%, 0) and also the probability of getting that value or greater Probs~&&(CardsValue%%, 1).

The program I have written gives zero probability for points values 30 and 32 to 37.  They should have very small values, but not zero (you could get up to 37: 4 Aces, 4 Kings, 4 Queens and a Jack).

I wonder if you could find out where I have gone wrong.  It is strange that I should be able to make such an elementary error - don't tell Fellippe, he'll bar me from the site!

Thanks.

Code: QB64 [Select]
  1. CONST True = -1`, False = 0`
  2. DIM Probs~&&(40, 1), Pack%%(52, 1)
  3. _TITLE "Points Count Probabilities in Bridge"
  4. 'A = 4, K = 3, Q = 2, J = 1
  5. FOR N%% = 1 TO 4
  6.     FOR M%% = 0 TO 3
  7.         Pack%%(N%% + (13 * M%%), 0) = 5 - N%%
  8.     NEXT M%%
  9. NEXT N%%
  10.  
  11. OPEN "temp.txt" FOR OUTPUT AS #2
  12. 'FOR N%% = 1 TO 52
  13. '    PRINT #2, Pack%%(N%%, 0)
  14. 'NEXT N%%
  15. 'END
  16.  
  17.  
  18.     Count~&& = Count~&& + 1
  19.     FOR N%% = 1 TO 52
  20.         Pack%%(N%%, 1) = False
  21.     NEXT N%%
  22.     CardsValue%% = 0
  23.     FOR N%% = 1 TO 13
  24.         Dealt` = True
  25.         WHILE Dealt`
  26.             Card%% = 1 + INT(52 * RND)
  27.             IF NOT Pack%%(Card%%, 1) THEN
  28.                 Pack%%(Card%%, 1) = True
  29.                 Dealt` = False
  30.             END IF
  31.         WEND
  32.         CardsValue%% = Pack%%(Card%%, 0) + CardsValue%%
  33.     NEXT N%%
  34.  
  35.     Probs~&&(CardsValue%%, 0) = Probs~&&(CardsValue%%, 0) + 1
  36.     FOR N%% = 0 TO CardsValue%%
  37.         Probs~&&(N%%, 1) = Probs~&&(N%%, 1) + 1
  38.     NEXT N%%
  39.     IF Count~&& / 100000 = Count~&& \ 100000 THEN
  40.         CLS
  41.         PRINT Count~&&
  42.         FOR N%% = 0 TO 40
  43.             P0! = Probs~&&(N%%, 0) / Count~&&
  44.             P1! = Probs~&&(N%%, 1) / Count~&&
  45.             PRINT N%%; P0!; P1!,
  46.             IF N%% \ 2 = N%% / 2 THEN PRINT ""
  47.         NEXT N%%
  48.         RANDOMIZE (TIMER)
  49.     END IF
  50.  
  51. PRINT #2, Count~&&
  52. FOR N%% = 0 TO 40
  53.     P0! = Probs~&&(N%%, 0) / Count~&&
  54.     P1! = Probs~&&(N%%, 1) / Count~&&
  55.     PRINT #2, N%%; P0!; P1!
  56. NEXT N%%
  57.  
  58.  
  59.  
« Last Edit: March 16, 2019, 12:55:54 PM by Qwerkey »

Offline Petr

  • The best code is the DNA of the hops.
Re: Bridge Points Count Probabilities - where have I gone wrong?
« Reply #1 on: March 15, 2019, 01:10:38 PM »
Understand i correct,  that you use integer type _INTEGER64  (&&) for decimal numbers? Try PROBS array do as decimal.

edit:
I tried it too, but I didn't get a reason.
« Last Edit: March 15, 2019, 01:33:29 PM by Petr »

Re: Bridge Points Count Probabilities - where have I gone wrong?
« Reply #2 on: March 15, 2019, 01:22:33 PM »
Petr, I don't think that that's the error.  Elements Probs~&&(CardsValue%%, 0/1) ARE integers: they are counted up by 1 if that points value is obtained.  The probabilities (definitely decimal) are obtained by dividing Probs~&&() by Count~&& (also a large integer).

Re: Bridge Points Count Probabilities - where have I gone wrong?
« Reply #3 on: March 15, 2019, 05:47:50 PM »
I had trouble following your code so I worked up my own code study using your ideas I think.

I got these results for 10,000,000 hands:
 


With this code:
Code: QB64 [Select]
  1. DIM SHARED deck(1 TO 52)
  2. SCREEN _NEWIMAGE(800, 700, 32)
  3. _SCREENMOVE 200, 40
  4. FOR i = 0 TO 51
  5.     IF i MOD 13 = 12 THEN
  6.         deck(i + 1) = 4
  7.     ELSEIF i MOD 13 = 11 THEN
  8.         deck(i + 1) = 3
  9.     ELSEIF i MOD 13 = 10 THEN
  10.         deck(i + 1) = 2
  11.     ELSEIF i MOD 13 = 9 THEN
  12.         deck(i + 1) = 1
  13.     ELSE
  14.         deck(i + 1) = 0
  15.     END IF
  16.     'PRINT i, i MOD 13, deck(i + 1)
  17.     'INPUT "OK enter "; wate$
  18. PRINT "unshuffled:"
  19. showDeck
  20. shuffleDeck
  21. PRINT "Shuffled:"
  22. showDeck
  23. INPUT "Ready to run trials, press enter "; wate$
  24.  
  25. DIM SHARED totals(0 TO 37)
  26.  
  27. shuffles = 2500000
  28. FOR test = 1 TO shuffles
  29.     shuffleDeck
  30.     totalHands
  31. hands = 4 * shuffles
  32. PRINT "After"; shuffles; "shuffles or"; hands; " hands the totals breakdown was:"
  33. FOR i = 0 TO 37
  34.     PRINT "Points"; i, "amount"; RIGHT$(SPACE$(15) + STR$(totals(i)), 15); SPACE$(4), "percent:"; totals(i) / hands * 100; "%"
  35.  
  36. SUB shuffleDeck 'Fisher Yates or Knuth shuffle
  37.     FOR i = 52 TO 2 STEP -1
  38.         r = INT(RND * i) + 1
  39.         SWAP deck(i), deck(r)
  40.     NEXT
  41.  
  42. SUB showDeck
  43.     FOR i = 1 TO 52
  44.         tot = deck(i) + tot
  45.         PRINT deck(i); ", ";
  46.         IF i MOD 13 = 0 THEN PRINT " Total = "; tot: tot = 0
  47.     NEXT
  48.  
  49. SUB totalHands
  50.     FOR i = 1 TO 52
  51.         tot = deck(i) + tot
  52.         IF i MOD 13 = 0 THEN totals(tot) = totals(tot) + 1: tot = 0
  53.     NEXT
  54.  
B = B + ...

Re: Bridge Points Count Probabilities - where have I gone wrong?
« Reply #4 on: March 16, 2019, 07:12:40 AM »
bplus, thanks.  I tried a different shuffling method in my code and still got an error (although results not the same as my 1st attempt).  I think that I'm not understanding RND properly.  I'm assuming that yours is correct: the likelihood of being dealt anything above 32 points is extremely low.

Re: Bridge Points Count Probabilities - where have I gone wrong?
« Reply #5 on: March 16, 2019, 08:40:52 AM »
bplus, I replaced my shuffling method with yours (Fisher-Yates or Knuth shuffle: who they?) in my code, and unsurprisingly I now get good results.  So I am not quite understanding RND.  This makes one feel suspicious of one's intelligence!

Re: Bridge Points Count Probabilities - where have I gone wrong?
« Reply #6 on: March 16, 2019, 09:44:33 AM »
bplus, I replaced my shuffling method with yours (Fisher-Yates or Knuth shuffle: who they?) in my code, and unsurprisingly I now get good results.  So I am not quite understanding RND.  This makes one feel suspicious of one's intelligence!

Quote
(Fisher-Yates or Knuth shuffle: who they?)
https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

Quote
So I am not quite understanding RND
Int(RND * N) gives a range of Integers from 0 to N-1, so if you want the range from 1 to N just add 1 for good results.

Quote
This makes one feel suspicious of one's intelligence!
This is sign of intelligence! I thought I had cat's meow of shuffle routines until someone showed me Fisher-Yates!

I was surprised how fast 10,000,000 hands could be totaled but each shuffle does give us 4 hands to evaluate.
B = B + ...

Re: Bridge Points Count Probabilities - where have I gone wrong?
« Reply #7 on: March 16, 2019, 12:32:29 PM »
Int(RND * N) gives a range of Integers from 0 to N-1, so if you want the range from 1 to N just add 1 for good results.

I did manage to get that bit of RND right (thank goodness).  It's what I was doing with the numbers thus generated that was somehow wayward.  It was odd that my first two attempts were only a little in error.  I have since found that my original routine had a SWAP condition where the SWAP elements could be the same.  With that condition removed, even my method works.  This project now completed.  Thanks.
« Last Edit: March 16, 2019, 12:55:04 PM by Qwerkey »

Offline Jack002

  • Boss, l wanna talk about arrays
Re: Bridge Points Count Probabilities (original error found)
« Reply #8 on: March 16, 2019, 04:54:43 PM »
I always found this to be the simplest card shuffle routine

FOR a = 1 TO 52
    DO
        s = (INT(RND * 52) + 1)
    LOOP UNTIL (s <> a)
    SWAP cards(a), cards(s)
NEXT

QB64 is the best!

Re: Bridge Points Count Probabilities (original error found)
« Reply #9 on: March 17, 2019, 06:57:47 AM »
I managed to find a Website where these probabilities have been previously calculated.  We will be pleased (but hardly surprised) that our results are in strict agreement with known values.

http://www.durangobill.com/BrPtCntStats.html

Points  Probability      Relative to Program
0         0.00363896   1.00
1         0.00788442   1.00
2         0.0135612     1.00
3         0.0246236     1.00
4         0.0384544     1.00
5         0.0518619     1.00
6         0.065541       1.00
7         0.0802809     1.00
8         0.0889219     1.00
9         0.0935623     1.00
10       0.0940511     1.00
11       0.0894468     1.00
12       0.0802687     1.00
13       0.0691433     1.00
14       0.0569332     1.00
15       0.0442368     1.00
16       0.0331092     1.00
17       0.0236169     1.00
18       0.0160508     1.00
19       0.0103617     1.00
20       0.00643536   1.00
21       0.00377867   1.00
22       0.00210043   1.00
23       0.00111904   1.00
24       0.000559034 1.00
25       0.000264278 1.00
26       0.000116683 1.00
27       4.91E-005     1.00
28       1.86E-005     1.00
29       6.67E-006     1.01
30       2.20E-006     1.02
31       6.11E-007     1.00
32       1.72E-007     0.96
33       3.52E-008     1.28
34       7.06E-009     0.28
35       9.83E-010     1.02
36       9.45E-011     0.00
37       6.30E-012     0.00

Only for points count above 31 (where the probabilities are very low) do we see disagreement.  In the program, run for 1000000000 hands, the numbers of hands occurring with 32 or more points are few (and zero for 36 and 37).
 
« Last Edit: March 17, 2019, 07:06:52 AM by Qwerkey »

Re: Bridge Points Count Probabilities (original error found)
« Reply #10 on: March 17, 2019, 09:57:10 AM »
One final remark (a query, in fact).  Deriving the probabilities of Points Count is clearly something that can be achieved by a skilled mathematician - see the table at the URL of previous reply.

I thought that the probability of obtaining 37 points (the highly improbable highest possible score) would be derived as follows:

The 37 points are obtained by a hand with 4 Aces, 4 Kings, 4 Queens and a Jack.  To obtain such a hand the probabilites are as follows:

For the first card to be a King, there is a 4 in 52 chance.  Having selected that, there is a 3 in 51 chance to get a King.  And so on.

The chance to get this hand is (according to me):

4/52 * 3/51 * 2/50 * 1/49 * 4/48 * 3/47 * 2/46 * 1/45 * 4/44 * 3/43 * 2/42 * 1/41 * 4/40

This comes out to 1.4E-17, but the actual probability is 6.3E-12, so I'm only a factor of 450,000 out!

I was always befuddled by Permutations & Combinations in Maths, so would someone (bplus, I guess!) show where I have gone wrong?

Re: Bridge Points Count Probabilities (original error found)
« Reply #11 on: March 17, 2019, 11:38:35 AM »
Quote
I was always befuddled by Permutations & Combinations in Maths, so would someone (bplus, I guess!) show where I have gone wrong?

:D 52! permutations of ways a deck can be ordered, yet only one combination of 4 aces, 4 kings... 4 2's.
Quote
level 1
Who_GNU
1 point
·
5 years ago
To be exact, 52! equals 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000

Quote
8x10^67

How many hands of 13 from a deck?

 EDIT: formula for Combination = N!/(R! * (N-R)!)
52! / (39! * 13!)  OK Pete, time to test your string math! ;-))

Only 4 or those hands can have 4 Aces, 4 Kings, 4 Queens, and 1 of 4 Jacks

APPEND: Oh Hey! It's right in your link Qwerky!
Quote
The total number of possible 13 card hands is: COMBIN(52,13) = 635,013,559,600


So I was right 4/635,013,559,600

APPEND #2: I had wrong formula for combination originally. _integer64 might be able to handle the calculation.
« Last Edit: March 17, 2019, 12:12:59 PM by bplus »
B = B + ...

Re: Bridge Points Count Probabilities (original error found)
« Reply #12 on: March 17, 2019, 02:15:57 PM »
Yes! 52!/(39! * 13!) can be calculated within limits of _INTEGER64, suffix ~&&

Code: QB64 [Select]
  1. _TITLE "How many hands of 13 from a deck" ' B+ started 2019-03-17
  2.  
  3. '   How many hands of 13 from a deck?
  4.  
  5. ' EDIT: formula for Combination of N items taken R at a time = N!/(R! * (N-R)!) so we need
  6. ' 52! / (39! * 13!) =    52 * 51 * 50 * 49 * ... * 40
  7. '                      / 13 * 12 * 11 * ...      * 1
  8.  
  9. DIM a52_39(1 TO 13) AS INTEGER, a13(1 TO 13) AS INTEGER
  10. FOR i = 1 TO 13
  11.     a52_39(i) = 39 + i ' = 40, 41, 42, 43, ... 52 numerator multipliers
  12.     a13(i) = i '             1, 2, 3, 4, ... 13   denominator multipliers
  13.  
  14. ' To keep the numerator from getting too big reduce numerator terms by demoinator terms that divide evenly
  15.  
  16. 'reduce terms in a52_39 by terms in denominator mult 2 to 13
  17. FOR i = 13 TO 2 STEP -1
  18.     found = 0
  19.     FOR j = 1 TO 13 'is the array item divisible by i
  20.         IF a52_39(j) MOD i = 0 THEN a52_39(j) = a52_39(j) \ i: found = 1: EXIT FOR
  21.     NEXT
  22.     IF found = 1 THEN a13(i) = 1 ELSE a13(i) = i
  23.  
  24. ' multiply whats left in numerator and denomiator
  25. f~&& = 1: g = 1
  26. FOR i = 1 TO 13
  27.     f~&& = a52_39(i) * f~&& 'multiple numerators left
  28.     g = a13(i) * g 'multiply denominators left
  29.  
  30. PRINT "The number of hands of 13 in a deck is ";
  31. PRINT USING "###,###,###,###,###.###"; f~&& \ g
  32. PRINT "                                compare to 635,013,559,600"
  33.  
B = B + ...

Re: Bridge Points Count Probabilities (original error found)
« Reply #13 on: March 17, 2019, 02:46:33 PM »
bplus, the Windows Calculator handles that factorial equation and gives the correct answer.

Re: Bridge Points Count Probabilities (original error found)
« Reply #14 on: March 17, 2019, 03:06:12 PM »
Oh so it does, never thought to use it, thanks!
B = B + ...