Log In  

Cart #wijagabufi-0 | 2019-08-18 | Code ▽ | Embed ▽ | No License
1

I was reading earlier about the Fisher-Yates Shuffle method and - well, I'm a little confused. What is the purpose of its complexity ?

I mean if you just want to shuffle a deck of cards, for instance, you can do so in code as simple as this:

-- simple card shuffler
-- written by dw817

-- initialize variables
deck={}
rank="a23456789tjqk"
suit="schd"

-- build sorted deck
for i=0,3 do
  for j=0,12 do
    deck[j+i*13]=sub(rank,j+1,j+1)..sub(suit,i+1,i+1)
  end
end

::again::

-- display current deck
cls()
for i=0,3 do
  for j=0,12 do
    print(deck[j+i*13],j*10,i*8,13)
  end
end
print("press a key to shuffle",0,64,7)

repeat
  flip()
until btnp(🅾️)

-- shuffle that deck
for i=0,51 do
  r=flr(rnd()*52)
  deck[i],deck[r]=deck[r],deck[i]
end

goto again

In the Fisher-Yates method you are expected to use a technique that involves saving every single element that was chosen so it will not be chosen again.

What if any are the advantages of using a shuffle such as this based on a simple single-array index-swap as seen above ?

Failing that, what is YOUR method for shuffling items in an array that satisfy you they are properly scrambled ?

P#66748 2019-08-18 00:21 ( Edited 2019-08-18 00:23)

:: dredds

The “naive” shuffle method is biased, meaning some elements are more likely to be shuffled than others. The complexity of Fisher-Yates is to avoid that bias and ensure a fair shuffle.

There’s a good explanation here: https://blog.codinghorror.com/the-danger-of-naivete/

P#66788 2019-08-19 22:34

interesting! I planned to do a card game in close future. :)

P#66798 2019-08-20 15:59
:: dw817

Glad I helped someone, BGelais. :)

Okay, Dredds. Let me see if I can make a fair shuffle program that's not too complex.

P#66800 2019-08-20 18:40 ( Edited 2019-08-20 18:41)
:: dw817

Alright, definitely more complex. Ensures only one card is shuffled per set.

Likely this can be optimized.

Cart #wiwudariya-0 | 2019-08-20 | Code ▽ | Embed ▽ | No License

P#66801 2019-08-20 19:06
:: dw817

Here. I think this is best. Truly swaps two unshuffled cards at a time, 26 times, does not shuffle the same card with itself, equals 52-cards shuffled in all.

Cart #kohobubugo-0 | 2019-08-20 | Code ▽ | Embed ▽ | No License

P#66802 2019-08-20 19:17 ( Edited 2019-08-20 19:19)

Card game shuffles are a deep problem. Solutions that look good are usually wrong.

There are a few problems with dw817's (most recent) algorithm.

One is simply that its run-time is non-deterministic. It could potentially loop for a long time on that shuffle routine. During the final loop there's only one pair of cards that satisfy the conditional, but it attempts to find those cards with two rnd statements.

It also has at least two biases that I can spot :

Not a single card is ever in its original position.

With 52 cards and 52 potential slots it should be pretty common for one or two cards to wind up in their original slot. This is why the Fisher-Yates allows self-swaps. This is actually a pretty serious problem. If the first card dealt can't ever be the Ace of Spades, then you've penalized the player left of the dealer by eliminating one of four potential aces he could have been dealt with that first card.

(But if you allow self-swaps, you'll need to do more than 26 rounds of swaps... )

Information Leak. Cards can be predicted.

Because every card is swapped exactly once, if you know one card, you can predict the location of the card it was swapped with.

For example, If the first card dealt is the 2 of Spades, you could predict that the second card dealt will be the Ace of Spades. In poker, those cards would go to different players, so this would be a serious information leak.

P#66847 2019-08-21 23:14 ( Edited 2019-08-21 23:29)

Incidentally, in my poker game, I side-stepped this issue by not shuffling the deck.

The deck was generated in order and when I needed to deal a card I just pulled a random card out of the deck.

(I now look forward to someone better than me at math explaining to me why this was a bad thing to do and how it actually ruins the fairness of the game.)

P#66848 2019-08-21 23:20
:: dw817

Actually ApLundell, yours is a good solution at that. Kind of like 52-card pickup, grab a random card, hand it to someone, it's yanked from the list, when out of cards, put them all back in order and repeat the process.

I guess most of us coders would like to believe it's possible to shuffle a deck correctly and house the results in an array.

And - none of my solutions actually do a correct shuffle at that.

A correct shuffle would be to choose where to split the deck (1-52) from a sorted deck, then take each stack and make a new stack with a 50% chance of it pulling the bottom card from the left stack and if not, chooses the bottom card from the right stack, if any cards remain in either case.

This is actually how a physical sort (by hand) is done. I have a physical manual crank card shuffler here and that's how it does it. Usually I cut the deck right at 26 or as close as I can so both piles are even amounts.

I COULD write code to simulate this, maybe do it 3x in a row, and see the results - which I doubt will be terribly satisfactory as a hand shuffle only flips two piles together.

As for my previous solution, I was tempted to use a rotating index which would ensure maximum speed, but since PICO is so blindingly fast, I decided against it and lazily made it loop randomly until those two conditions were found, which, yes, does mean there is a 1-in-2704 chance of it getting the last 2-cards pulled successfully, otherwise it keeps looping until it does.

Once again, ApLundell, yours is an interesting solution and I certainly would call it completely fair at that.

I'm still working on my gaming calculator cart and may adopt your method for pulling playing cards as that key is an option available in it.

P#66854 2019-08-22 05:12

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2020-06-06 19:17 | 0.026s | 4194k | Q:68