Author Topic: Re: Fisher-Yates Shuffle  (Read 884 times)

0 Members and 1 Guest are viewing this topic.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Fisher-Yates Shuffle
« Reply #15 on: October 28, 2019, 04:38:11 pm »
Ah! back on topic ;-))

That is relatively easy, 8 * 52 = 416, so number deck cards 0 through 415.
Use mod 4 to help decode the suits. Maybe If deckNum mod 4 = 0 then a Club ...
Use mod 13 to help decode and determine Ace thru King, If deckNum mod 13 = 0 then Ace....

OK an 8 deck Shu or Shoo or shoe however it's spelled: (update: it's shoe)
Code: QB64: [Select]
  1. _TITLE "8 deck demo of FY" 'B+ 2019-10-28
  2. SCREEN _NEWIMAGE(800, 720, 32)
  3. _SCREENMOVE 300, 20
  4. low = 0
  5. high = 415
  6. DIM deck(low TO high) AS INTEGER
  7.  
  8. PRINT "Here is the 8 Deck Shoe: "
  9. FOR c = low TO high
  10.     deck(c) = c
  11.     PRINT Card$(c); ", ";
  12.     IF c MOD 13 = 12 THEN PRINT
  13. PRINT: PRINT "Press any to wakeup..."
  14.  
  15. FOR i = 1 TO 5
  16.     CLS
  17.     PRINT "Shuffling..."
  18.     'F-Y shuffle
  19.     FOR c = high TO low + 1 STEP -1
  20.         r = INT(RND * (c - low + 1)) + low
  21.         SWAP deck(c), deck(r)
  22.     NEXT
  23.  
  24.     'show deck
  25.     PRINT "Deck: "
  26.     FOR c = low TO high
  27.         PRINT Card$(deck(c)); ", ";
  28.         IF c MOD 13 = 12 THEN PRINT
  29.     NEXT
  30.     PRINT: PRINT "Press any to wakeup..."
  31.     SLEEP
  32.  
  33. FUNCTION Card$ (dn) '4 chars long
  34.     SELECT CASE INT(dn / 13) MOD 4
  35.         CASE 0: Suit$ = "H"
  36.         CASE 1: Suit$ = "C"
  37.         CASE 2: Suit$ = "D"
  38.         CASE 3: Suit$ = "S"
  39.     END SELECT
  40.     SELECT CASE dn MOD 13
  41.         CASE 1 TO 9: cv$ = LEFT$(_TRIM$(STR$(dn MOD 13 + 1)) + " ", 2)
  42.         CASE 0: cv$ = "A "
  43.         CASE 10: cv$ = "J "
  44.         CASE 11: cv$ = "Q "
  45.         CASE 12: cv$ = "K "
  46.     END SELECT
  47.     Card$ = cv$ + "_" + Suit$
  48.  
« Last Edit: October 28, 2019, 07:36:33 pm by bplus »

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Fisher-Yates Shuffle
« Reply #16 on: October 28, 2019, 04:50:33 pm »
Isn’t the quickest way to shuffle just to use a for loop and swap values?

FOR I = LBOUND(Cards) TO UBOUND(Cards)
    SWAP Cards(I), Cards(INT(RND * NumberOfCards))
NEXT

I think there is a reason why RND is multiplied by I (and thus why you start at top number and work down) and RND is not multiplied by number of cards but that seems intuitive doesn't it?

It's been 3 years since I've studied this, let me see if I can find reason. I think it had something to do with the best distribution of cards with the least swappings. Certainly the swapping ''distances'' shrink working from top down if that makes any sense.

Offline doppler

  • Forum Regular
  • Posts: 241
    • View Profile
Re: Fisher-Yates Shuffle
« Reply #17 on: October 28, 2019, 05:33:03 pm »
Let's go a little off topic.  Some big sports celebrity who liked to play big time baccarat.  Convinced a Vegas casino to use only 1 deck and not change it as long as he played.  He played for a very long time and won big time.  His average was against the odds.  Of course the casino cried foul, but could not prove anything.  They withheld his winnings to the point he had to SUE to collect.  That suit is still pending.  They did figure out how he won.  It was all their fault from the beginning.  (Single deck)  Even though the deck was shuffled after every play.  It took experts to figure out what happened.

It was new, brilliant and simple.  What he did was recognize the back pattern card edges.  At the manufacturer for cards they are printed as one sheet then cut into cards.  By memorizing the card edge back pattern and knowing how the cards are produced.  Knowing the card numbers 1-9 and all the ten's.  Winning became easy.

FYI, This was a while ago.  Casino's don't sit still when they lose money.  The mob quote "It's not personal, it's business." applies to casino's.  Don't try it yourself.  You will loose kneecaps for sure.


Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Fisher-Yates Shuffle
« Reply #18 on: October 28, 2019, 07:14:44 pm »
Hi doppler,

That was interesting about learning about card manufacture.

Hi Steve,

I found the reason at Wiki why you should't select RND from the whole deck but lowest to i (or work in reverse from bottom up)

Here is the essential idea in a paragraph:
 
FY implemetation errors.PNG



Also:
Code: QB64: [Select]
  1.     FOR c = high TO low + 1 STEP -1
  2.         r = INT(RND * (c - low + 1)) + low
  3.         SWAP deck(c), deck(r)
  4.     NEXT
  5.  

can be replaced by:
Code: QB64: [Select]
  1.     FOR c = high TO low + 1 STEP -1
  2.         SWAP deck(c), deck(INT(RND * (c - low + 1)) + low)
  3.     NEXT
  4.  

which saves an assignment and line of code as you had in another part of your suggestion.

« Last Edit: October 28, 2019, 07:44:39 pm by bplus »