Even if you are a methodical, obsessive human, you probably do not shuffle cards like a computer. When computers do things, they prefer to be told how to do them with repetitive but clear commands, with clear stopping and starting points (this is one definition of an algorithm). How to shuffle cards (when human): get the deck and divide it into two piles with about twenty-six cards, but you know, it doesn't matter a whole lot if they are uneven. Interlace the two piles. You will probably want to make that part look fancy and impressive. They say to shuffle seven times for approximate randomness, but no one does that. You can get away with two or three times, and then if someone is still giving you the stink-eye, you let them cut the deck. Of course, if you are really good at this, you have learned to exactly cut the deck into even piles and interlace the cards one-at-a-time from each pile. If you are that good, you are no longer allowed to play cards. Strangely, you have to be a certain level of bad at it to stay in the game.
If you are a computer, you will shuffle cards a different way:
A. Someone gives me a stack of cards called "Unshuffled Cards."
B. I randomly select any one Unshuffled Card and move it to another stack, which I call. "Shuffled Cards."
C. I continue to do this until there are no cards in Unshuffled Cards.
D. I announce that I have a deck of shuffled cards: Shuffled Cards.
This has the benefit that you get an entirely shuffled deck after only one go-round. Also, notice that any card has an equal change to be in any place, so any shuffle order of the deck is equally possible. (Vocabulary word: a "permutation" of a deck of cards is an arrangement of the cards in a particular order.)
As a human on the other hand, no one is going to sit there while you move cards one at a time to shuffle the deck. Also, no one is going to trust you to pick a random not-cheating card to place on the shuffled stack. It is better for humans to take the slightly-less-random but faster and more impressive shuffling method.
The standard algorithm for shuffling is called the Fisher-Yates algorithm. It uses the steps above, except it does not make a new stack for the shuffled cards. To save memory, it just uses the end of the current stack to store the new stack of shuffled cards, like this:
If I have a stack of ten "cards," as in A, the computer will pick the first card (here it picked the six), and move it to the end. Notice in B, the 6 is now at the end, and the 10 has been moved into 6's old location. The computer will pick the next "card," from the underlined numbers. They are slightly out of order now that the ten has been shoved in, but the computer does not care, and it does not affect each card's chance of being picked. In B, the computer has picked the four to be the next card. In C, the 4 has been moved to the end, and the computer is selecting the next card from the underlined ones. Here it has picked the 8. The 8 stays where it is, but it is no longer a candidate to be picked. In D, it is not underlined. So, the area of the list of numbers to be picked gets shorter and shorter while the area of shuffled numbers gets longer. Eventually, the entire list of numbers is shuffled from back to front.
Let's talk C#.
I'm going to show you my C# implementation of the Fisher-Yates algorithm. At the top of my file, I have the above stuff. "UnityEngine" is what is called a namespace. The "using UnityEngine;" line is important because it tells the compiler where to look for the Unity-specific commands I'm using. It also tells the compiler that in the case of two functions having the same name, I prefer UnityEngine's version. This latter thing actually causes a small issue here. The UnityEngine namespace defines a command called Random. Random can do a lot of things (click the link for a complete list), but it does not do what I want, which is to give me a random integer in a particular range (note that with extra math, it can be forced to work, but it is easier to avoid that). So, here, on the line "private.System.Random.rnd = new System.Random();" I am telling the compiler to look in the System namespace to use that Random function instead of UnityEngine's. I have to specify with "System[dot]" because I have told the computer that by default I am "using" UnityEngine's commands.
System's Random is a pseudo-random number generator. It's main use it to take a number and give you another number in return. The numbers are more-or-less uniformly distributed, but it always gives identical lists of numbers. For example, a list might be "7, 5, 2, 2, 6, 8, 25." If you start with a seven, you will always get the 5, the 2, another 2, etc, so the starting number is critical in getting the appearance of randomness. You do not want to always start with a seven. (Vocabulary: the starting number is called a "seed.") The "new" command, when it is activated, looks at the user's current date and time and uses that to seed the generator, so two users are unlikely-ish to encounter the exact same list of "random" numbers. In the code below, the command "Next" is used, which gets the next number on the "random" list.
And there it is. I'm storing the cards currently as an array of numbers 0-51. That may change later as I figure out what to actually do with the numbers to turn them into visible cards...um...I'm working on it! (It would not be hard to do, probably, except that no one has written a tutorial for "how to work in Unity if you are a relic from the age of dinosaurs.")
No comments:
Post a Comment