Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: Qwerkey on March 15, 2019, 12:49:23 pm

Title: Bridge Points Count Probabilities (original error found)
Post by: Qwerkey 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.  
  18.  
  20.     Count~&& = Count~&& + 1
  21.     FOR N%% = 1 TO 52
  22.         Pack%%(N%%, 1) = False
  23.     NEXT N%%
  24.     CardsValue%% = 0
  25.     FOR N%% = 1 TO 13
  26.         Dealt` = True
  27.         WHILE Dealt`
  28.             Card%% = 1 + INT(52 * RND)
  29.             IF NOT Pack%%(Card%%, 1) THEN
  30.                 Pack%%(Card%%, 1) = True
  31.                 Dealt` = False
  32.             END IF
  33.         WEND
  34.         CardsValue%% = Pack%%(Card%%, 0) + CardsValue%%
  35.     NEXT N%%
  36.  
  37.     Probs~&&(CardsValue%%, 0) = Probs~&&(CardsValue%%, 0) + 1
  38.     FOR N%% = 0 TO CardsValue%%
  39.         Probs~&&(N%%, 1) = Probs~&&(N%%, 1) + 1
  40.     NEXT N%%
  41.     IF Count~&& / 100000 = Count~&& \ 100000 THEN
  42.         CLS
  43.         PRINT Count~&&
  44.         FOR N%% = 0 TO 40
  45.             P0! = Probs~&&(N%%, 0) / Count~&&
  46.             P1! = Probs~&&(N%%, 1) / Count~&&
  47.             PRINT N%%; P0!; P1!,
  48.             IF N%% \ 2 = N%% / 2 THEN PRINT ""
  49.         NEXT N%%
  50.         RANDOMIZE (TIMER)
  51.     END IF
  53.  
  54. PRINT #2, Count~&&
  55. FOR N%% = 0 TO 40
  56.     P0! = Probs~&&(N%%, 0) / Count~&&
  57.     P1! = Probs~&&(N%%, 1) / Count~&&
  58.     PRINT #2, N%%; P0!; P1!
  59. NEXT N%%
  61.  
  63.  
  64.  
Title: Re: Bridge Points Count Probabilities - where have I gone wrong?
Post by: Petr 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.
Title: Re: Bridge Points Count Probabilities - where have I gone wrong?
Post by: Qwerkey 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).
Title: Re: Bridge Points Count Probabilities - where have I gone wrong?
Post by: bplus 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:
  [ This attachment cannot be displayed inline in 'Print Page' view ]  

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$
  19. PRINT "unshuffled:"
  20. showDeck
  21. shuffleDeck
  22. PRINT "Shuffled:"
  23. showDeck
  24. INPUT "Ready to run trials, press enter "; wate$
  25.  
  27. DIM SHARED totals(0 TO 37)
  28.  
  29. shuffles = 2500000
  30. FOR test = 1 TO shuffles
  31.     shuffleDeck
  32.     totalHands
  34. hands = 4 * shuffles
  35. PRINT "After"; shuffles; "shuffles or"; hands; " hands the totals breakdown was:"
  36. FOR i = 0 TO 37
  37.     PRINT "Points"; i, "amount"; RIGHT$(SPACE$(15) + STR$(totals(i)), 15); SPACE$(4), "percent:"; totals(i) / hands * 100; "%"
  39.  
  40. SUB shuffleDeck 'Fisher Yates or Knuth shuffle
  41.     FOR i = 52 TO 2 STEP -1
  42.         r = INT(RND * i) + 1
  43.         SWAP deck(i), deck(r)
  44.     NEXT
  46.  
  47. SUB showDeck
  48.     FOR i = 1 TO 52
  49.         tot = deck(i) + tot
  50.         PRINT deck(i); ", ";
  51.         IF i MOD 13 = 0 THEN PRINT " Total = "; tot: tot = 0
  52.     NEXT
  54.  
  55. SUB totalHands
  56.     FOR i = 1 TO 52
  57.         tot = deck(i) + tot
  58.         IF i MOD 13 = 0 THEN totals(tot) = totals(tot) + 1: tot = 0
  59.     NEXT
  61.  
Title: Re: Bridge Points Count Probabilities - where have I gone wrong?
Post by: Qwerkey 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.
Title: Re: Bridge Points Count Probabilities - where have I gone wrong?
Post by: Qwerkey 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!
Title: Re: Bridge Points Count Probabilities - where have I gone wrong?
Post by: bplus on March 16, 2019, 09:44:33 am
Quote from: Qwerkey 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!

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.
Title: Re: Bridge Points Count Probabilities - where have I gone wrong?
Post by: Qwerkey on March 16, 2019, 12:32:29 pm
Quote from: bplus on March 16, 2019, 09:44:33 am
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.
Title: Re: Bridge Points Count Probabilities (original error found)
Post by: Jack002 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

Title: Re: Bridge Points Count Probabilities (original error found)
Post by: Qwerkey 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 (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).
 
Title: Re: Bridge Points Count Probabilities (original error found)
Post by: Qwerkey 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?
Title: Re: Bridge Points Count Probabilities (original error found)
Post by: bplus 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.
Title: Re: Bridge Points Count Probabilities (original error found)
Post by: bplus 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
  14.  
  15. ' To keep the numerator from getting too big reduce numerator terms by demoinator terms that divide evenly
  16.  
  17. 'reduce terms in a52_39 by terms in denominator mult 2 to 13
  18. FOR i = 13 TO 2 STEP -1
  19.     found = 0
  20.     FOR j = 1 TO 13 'is the array item divisible by i
  21.         IF a52_39(j) MOD i = 0 THEN a52_39(j) = a52_39(j) \ i: found = 1: EXIT FOR
  22.     NEXT
  23.     IF found = 1 THEN a13(i) = 1 ELSE a13(i) = i
  25.  
  26. ' multiply whats left in numerator and denomiator
  27. f~&& = 1: g = 1
  28. FOR i = 1 TO 13
  29.     f~&& = a52_39(i) * f~&& 'multiple numerators left
  30.     g = a13(i) * g 'multiply denominators left
  32.  
  33. PRINT "The number of hands of 13 in a deck is ";
  34. PRINT USING "###,###,###,###,###.###"; f~&& \ g
  35. PRINT "                                compare to 635,013,559,600"
  36.  
Title: Re: Bridge Points Count Probabilities (original error found)
Post by: Qwerkey on March 17, 2019, 02:46:33 pm
bplus, the Windows Calculator handles that factorial equation and gives the correct answer.
Title: Re: Bridge Points Count Probabilities (original error found)
Post by: bplus on March 17, 2019, 03:06:12 pm
Oh so it does, never thought to use it, thanks!
Title: Re: Bridge Points Count Probabilities (original error found)
Post by: TempodiBasic on March 17, 2019, 06:02:59 pm
Hi guys
in what manner do you combine the combination https://en.wikipedia.org/wiki/Combination#Example_of_counting_combinations (https://en.wikipedia.org/wiki/Combination#Example_of_counting_combinations) (that has its mathematical weight) with the empiric simulation and probabilities on this limited set of hands?

as you can see at Example of counting combinations paragraph of the above  wikipage the question of probabilities of a score in 13 cards in single hand is the same for each score because each card is a single indipendent event with no duplication (you cannot have the same card twice in the same hand of the game of bridge)....

52!/ 13!*39!  = 52*51*50*.....41*40* 39!/13! * 39! =  52*51*50*.....41*40 / 13!

and here the code starts to configure a probability calculator of statistical combination  of indipendent events (13 cards of an hand) of a set of events (52 cards to 4 players)

Code: QB64: [Select]
  1. _TITLE "calcolo di eventi indipendenti autoesclusivi"
  3. CLS , 3
  4. COLOR 4, 3
  5. PRINT "We must know how much is the chance of an indipendent event in combining with other indipendent events of the same nature"
  6. INPUT "Please enter the total number of cases (52 cards?) ", NumTotalPossible%
  7. INPUT "Please enter the total number of cases to be to get goal (how cards need to have event?)", NumCasesUseful%
  9. chance = 1
  10. chance2 = 1
  11. FOR i% = 0 TO NumCasesUseful% - 1 STEP 1
  12.     chance = chance * (NumTotalPossible% - i%)
  13.     chance2 = chance2 * (i% + 1)
  14.     LOCATE , 2
  15.     PRINT i%, chance, chance2
  16.     _DELAY .1
  18. LOCATE , 2
  19. PRINT "press a key to continue"
  22. LOCATE 16, 1
  23. PRINT " For total events "; NumTotalPossible%; " and Useful events "; NumCasesUseful%
  24. PRINT " you have number of events:", chance
  25. PRINT "chance to get this combination:", chance / chance2
  26. chance = chance / chance2
  27. FOR i% = 1 TO NumCasesUseful% + 1 STEP 1
  28.     IF chance < 0 THEN chance = chance * 10
  30. PRINT "this means that you must put "; STR$(i%); "zero after 0. to write this number"
  31. PRINT "like here..."
  32. PRINT "0."; STRING$(i%, "0"); "1"
  34.  

In the statistical world the events are infinite and each single event is equal in amount of presence as we talk about indipendent events.
 In what manner can your probabilities, got on a large (at our eyes) but little champion of events,  be useful in the choice of strategy of the game?
Thanks for feedback
Text Only | Text with Attachments