Shuffling a deck of cards (was: Please add your programs)

[Commander#1]

Feel free to add your programs here. I'd love to have a selection of contemporary games to share with the community.

O.K. Jeff - here goes:

After I bought my VIC, I began to realize that in order to control the outside world, I would need to learn how to program.
Getting something to work on the screen would be good as that afforded me feedback rather quickly. I found that the screen -
the working area of the screen at least - was made up of 506 blocks (22 columns across by 23 rows down) and that each
block had it's own memory address. This was good. I could run a string of asterisks (*) across the screen, dividing it in to two
playing areas for a simple game of Black Jack - on area to play the cards and the other area for communications between me
and the computer. All four suits were already on the keys and so were the different colors. Just to get the game going, I
decided I didn't need any fancy looking cards like some of the commercial programs had. Everything at this point was looking
good. Then I went looking for a gaming program. Oh Boy ! ! ! THAT was not looking good at all!! Everyone of the programs
I looked at had the same problem - Duplicate Cards!!! This can *definitely* ruin your day in the middle of a game. So there
was my challenge - shuffle a deck and have no duplicate cards. O.K. - suppose I assign a number to each card, put the cards
in memory, and let the computer scramble the numbers - a job the computer is built for! What I came up with is the following:

10 print"[shift][clear/home]": dim A(52): for B=1 to 52
20 C=int(rnd(1) * 52) + 1
30 for D=1 to B: if A(D)=C then D=B: goto 20
40 if A(D)=0 then A(D)=C
50 next: next

This worked!! Everything's scrambled and no duplicate numbers!! Yea!! It just took about a minute and a half (about 90
seconds!!!!) to do it! After massaging this program a little bit, I discovered that most of the time was used in the last
two numbers. So, I tried the following: adding the numbers 1 through 52 gave the result of 1378. If I subtracted the total of
the first 51 numbers from 1378, I always wound up with the missing number. So, I modified the program as follows:

10 print"[shift][clr/home]": dim A(52): for B=1 to 51
20 C=int(rnd(1) * 52)+ 1
30 for D=1 to B: if A(D)=C then D=B: goto 20
40 if A(D)=0 then A(D)=C: E=E + C
50 next: next: F= 1378 - E: A(52)=F: E=0

This worked!! Time is now down to about 45 seconds - I could live with that.

Well (I know - deep subject!), I gotta go now. I have dinner date, so, I'll be back in a little while to explain things.

I'm back. Now the explanation. Line 10 clears the screen so that I can set up my playing field; sets apart 52 places in
memory (this is called an 'array') by way of the 'dim' (dimension) statement (because I've exceeded 11 places
which the VIC handles automatically) and labels it 'A'. 'B' is a counter used to check each position in 'A' for a duplicate
number or empty space. 'C' is a randomly generated number (the '1' in 'rnd(1)' is the 'seed' that produces the least
amount of predictable sequences. "52" gives the range of numbers from 0 to 51 and the '+ 1' adjusts the range to 1 to 52.
(By the way, a good tutorial on random numbers can be found right here at 'denial' - see "home page", "links", "related
resources", "compute magazine archive", "compute #8 - Jan. 81: random numbers part #1"; "compute #9 - Feb 81: random
numbers part #2"; "compute - Mar 81: part #3"; and "compute - Apr 81: part #4"; and also VIC-20 Programer's Guide).
'D' is a loop that sets the limits for checking 'A'. The 'if-then' statements do the actual checking for duplicate numbers or
empty spaces. If a duplicate number is found then 'D' is max'd out and another number is generated and the checking
starts again. If no duplicate number is found by the time the last space is addressed (per each iteration of loop 'D'), then
the new number is placed in the empty space and the face value of the number is added to counter 'E'. Then 'D' is up dated
(1st 'next') followed by 'B' being up dated (2nd 'next'). Every time 'B' is up dated by one, 'D''s limits are increased by one
- so, the search continues. 'F' is the 52nd number which is found by subtracting 'E' from 1378. 'F' is then placed into
space #52 of 'A'. Since that completes the shuffle and both 'B' and 'D' are max'd out, 'E' is cleared (0) and the program is
thus ready for another shuffle command.

I hope this makes sense to somebody out there. Maybe you can improve on this. Hope to hear from you.


Phil Potter.

[carlsson]

What I came up with is the following:

Such a cliff-hanger!

But seriously it is a good programming challenge how to simulate a deck of cards, shuffle those and make sure no duplicates occur. In the Black Jack played on casinos, I believe the dealer has a deck that consists of at least three or four regular decks, which means every card may actually end up more than once, but still a limited number of times before they reshuffle.

I'm eager to hear about your solution, perhaps in a separate thread. If you at this moment however is stuck with a problem, we can chime in and solve it together. The concept of having a limited amount of something and mark what is used or not is present in many scenarios, not only simulating a deck of cards.

[Mike]

What I came up with is the following:

Something like this?

Code: Select all

1 DIMD(32)
2 FORI=1TO32:D(I)=I:NEXT
3 FORI=32TO1STEP-1
4 X=INT(RND(1)*I)+1
5 T=D(I):D(I)=D(X):D(X)=T
6 NEXT

The 32nd card is exchanged with one of the first 31 cards, or left there. Then, the 31st card is exchanged with one of the first 30 cards, or left there. And so on... this way, all 32! combinations are realised with equal probability.

An alternative would be to use a string, instead of an array, as deck.

Greetings,

Michael

P.S.: I split these posts from the Welcome topic into an own thread.

[Mike]

I hope this makes sense to somebody out there.

Let's see:

Your program builds up the deck by getting a random number between 1, and 52, and comparing it against all other cards already in the deck.

This needs at least quadratic time, O(n²), since you first compare against 1, then 2, then 3 cards as the deck grows. Furthermore, in later stages, it gets more "difficult" to obtain a card not already in the deck, increasing the time further. The last card, even though it is known, has only a probability of 1/52 to be "chosen" by the RND() statement. Thus the 90, or 45 seconds for your two programs.

Maybe you can improve on this.

My solution above only needs ~1 second, when expanded to a full deck of 52 cards (just exchange the three occurrences of 32 with 52). It is an O(n) algorithm, i.e. run time only increases linearily with the size of the deck.

Greetings,

Michael

[Leeeeee]

this way, all 32! combinations are realised with equal probability.

Not quite. There aren't nearly enough bits in the Vic RND() function to realise all 32! combinations let alone all 52! combinations for a deck of cards.

Lee.

[Mike]

I know. The RND() function in CBM BASIC already repeats after ~58000 calls, as the programmers tried to 'improve' upon a linear-congruential generator by exchanging bytes in its state, breaking the generator.

But this is clearly a 'quality of implementation issue' of the RND() function, and does not falsify my algorithm.

Michael

[Leeeeee]

No it does not falsify the algorithm. What I was trying to point out was that you need a random number generator with at least as many distinct states as the outcome you're trying to randomly generate.

The RND() function in CBM BASIC repeats already after ~58000 calls

It wasn't just CBM, most Microsoft 6502 BASICs have the same broken RND() function. The sequence length varies depending on the start point but I think the longest sequence is less than 10^7 states.

But even if RND() worked optimally it would still only produce a sequence 2^40 states long which is short of the 32! needed by about 2.4*10^23 times.

Lee.

[Mike]

What I was trying to point out was that you need a random number generator with at least as many distinct states as the outcome you're trying to randomly generate.

This is in order, but does leave us with a smaller problem: how do we obtain a good seed for this random generator?

...

If I have such a good seed, I'd simply apply a variant base conversion to transform the seed into the deck, and wouldn't need to call the random generator at all.

Michael

[Gary_Leeds]

i always use RND(TI) for a variable seed in basic, where is the flaw in that?

Gary

[Mike]

Hi, Gary,

RND() in CBM BASIC only is (re-)seeded with *negative* numbers, so when you wanted to use TI as seed, you'd use something like:

Code: Select all

1 X=RND(-TI):CLR

(the CLR to clear variable space again), once, at the start of the program. This initialises the generator to start at a certain point of its number sequence.

From then, RND(1) gives new random numbers in the selected sequence. Any positive argument will work, with no difference in the outcome. Especially using RND(TI) won't get you "more random" numbers.

RND(0) ignores the seed, and calculates a "random" number from TI.

Finally, TI only provides for 24*60*60*60=5184000 different seeds[*], which is far less than necessary to feed a random number generator which could produce 32! ~= 2.6*10^35, or 52! ~= 8.1*10^67 different numbers.

But Phil surely didn't want to run a Casino upon his card shuffle routine anyway, and so all solutions thus far presented are good enough for the intended use.

Greetings,

Michael

[*]: TI indeed runs from 0 to 5184000, due to a bug in the jiffy clock counter. 0 won't work as expected, but the other ones do.

[IsaacKuo]

Hi, just going through old programming posts...

I just wanted to note that you typically don't need to shuffle the cards all at once. Instead, you initialize the cards in any convenient order. When it's time to draw a card, you pick a random card from the ones which are left. Your basic operations are:

INITIALIZE: dim c(51):cn=0

ADD CARD: c(cn)=NEW CARD:cn=cn+1

PICK CARD: t=int(rnd(.)*cn):CARD=c(t):cn=cn-1:c(t)=c(cn)

At all times, cn is the number of cards in the deck and c(0)...c(cn-1) are the values of the cards.

Whenever the user provides input, you reseed the random number generator with the timer. This means you get around the randomization limits of seeding the number generator just once.

You don't want to reseed the generator on every card pick, if your game may pick multiple cards per user input. For example, a popular solitaire game involves picking 3 cards at a time.