Sign in to follow this  
Vortez

Skipbo cards distribution, need help...

Recommended Posts

Vortez    2714
Hi, i've develloped a little skipbo game of my own, and quickly realised than my cards wern't always well shuffled, even using multiple pass of as many algoritmh as i can trow at it. So, i've coded a little function to analyse the randomness of the cards in a given "deck"(a simple array with value 0 to 161) and return a int, the higher the better. It's was working fine but i then realised than many of the decks stored in a database of decks with high scores where similar. Like some kind of pattern. I latter read that i could sort my cards better simply by sorting them using much larger random numbers then sorting them accordingly.

That may solve the problem but, i downloaded from random.org like 225,000(deck) * 162(cards) = 35mo of random sequence numbers, and now would like to analyse them with a good algoritms to test the randomness of those.

So far i've been able to think about 2 nice algo that should work, but first, here's how a deck of skip bo cards is composed:

162 Cards................(12x12x18 = 162)
18 Skip-bo
12 one, 12 two, ect......(12x12 = 144)
12 Values................(144/12 = 12)
3 Dif. Colors per Value..(4 red x 4 green x 4 blue = 12)

Here's my first algorithm:
-build an array of 144 bytes and add the differances between each cards value, from 1 to 12, removing the 18 skipbos. The problem with this algorithm is that i don't know what's the maximum value i can get from that, and that dosen't tell if there if the random is too perfect, like all the cards always at the same interval, giving a high score but lacking distribution randomness.(like 0,1,0,1,0,1,0,10,1,0,1,0,1,0,1,0,1,0,1 -- perfectly random but now well distributed)

The second algorithm im about to code i think is based on the monte carlo altorithm, to make short, it will return me a pi value based on the distance from each cards within a circle, the more close to pi the result is the more random the sequence should be, and if the value is equal to pie, that mean that every cards in the sequence are evenly spaced. I think this is a better version of the previous algorithm, since it return similar result, but with a value in the range of 0.0 to 1.0.

I also tough about implementing another algoritm for verifiying series of same sequence, like 2,9,4, 7,5, 2,9,4, 1,10, 2,9,4, ect

So now, the only thing i would need i thing is some simple formula to tell me if a given card value in a sequence is well randomized, not just well spaced but also if the variation is good or not(like the 1s and 0s example above).

I totally suck at deciphering complex math formula, every time i try to understand one i just got an headhache and quit, lol. Any input apreciated.

Share this post


Link to post
Share on other sites
Sneftel    1788
There are a variety of standardized randomness tests out there; the Diehard tests are particularly well-known. No randomness test is perfect (running these tests on the digits of pi, for example, would suggest they were high-quality random, when in fact they're very predictable), but they can identify a wide variety of unwanted patterns.

Nevertheless, I think you may be making certain common mistaken assumptions about what "well shuffled" decks look like. What about the decks you generated made you feel they weren't well-shuffled? And what was your shuffling algorithm?

Share this post


Link to post
Share on other sites
Vortez    2714
Thanks for your input, yeah i already looked into diehard and nist librarys but when i run tests with those i always seem to get wrong result whatever the parameters i try to put into. That's why i decided the remake one myself, better than my old one.

Well for generating the decks, i used the insert at ramdom algo., then i tryed cuting the deck into 2(using bit of randomness for the size) and cutting it by almost 2 until they is no cards left, i also used the simple algorithm that add one card of each deck one after the other to reform 1 deck, then tryed a mixture of those, the 2 last gived good scores(using my very old code, not the one above) but like i said the decks where similar, like there was some pattern in it.

I've read that even a 32-bit rng cannot produce enough random numbers to sort a deck of 52 cards, but i just cant understand why. I only have 162 differants cards, how can a 32 bit numbers cant be random enough for that??

EDIT: Would Boost::Random class solve my shuffling problem?

[Edited by - Vortez on November 30, 2010 5:54:34 PM]

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Vortez
Thanks for your input, yeah i already looked into diehard and nist librarys but when i run tests with those i always seem to get wrong result whatever the parameters i try to put into.
What do you mean by "wrong result"?

Quote:
Well for generating the decks, i used the insert at ramdom algo., then i tryed cuting the deck into 2(using bit of randomness for the size) and cutting it by almost 2 until they is no cards left, i also used the simple algorithm that add one card of each deck one after the other to reform 1 deck, then tryed a mixture of those, the 2 last gived good scores(using my very old code, not the one above) but like i said the decks where similar, like there was some pattern in it.
Okay. There's a particular shuffling algorithm which everyone uses (the Fisher-Yates shuffle) -- why aren't you using that?
Quote:
I've read that even a 32-bit rng cannot produce enough random numbers to sort a deck of 52 cards, but i just cant understand why. I only have 162 differants cards, how can a 32 bit numbers cant be random enough for that??
A deck of 162 cards can be shuffled 12296942187394494341101789284917501765723005994271693066207625211678145401177289658609880984670515317835995074429904709708273401807824365415928975695099566042246320538220924308010459938381430588227927174194100982189204709615293198326390773410925903872000000000000000000000000000000000000000 different ways. That's a lot more options than 32 bits gives you.
Quote:
EDIT: Would Boost::Random class solve my shuffling problem?
It's still not clear to me what, if any, problem you actually have.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this