On 9/12/07, Austin Nichols <[EMAIL PROTECTED]> wrote: > Graham-- > I realize this list is about half programming and half feature/help > requests, but I'm hoping you can elaborate on this comment for the > half-programmers on the list... I think you're saying that a "bad" > pseudo-random number generator (PRNG) might be, say, slightly more > likely to pick a Q on the first draw than the expected 1/100, or, more > interestingly perhaps, slightly more likely to pick an exchanged tile > on the next draw, say, and you suggest a shuffling procedure where you > reorder individual elements in a vanishingly small proportion based on > the probability of drawing an endpoint--but the shuffling procedure > you describe is a bit obscure to me, so I might be completely missing > your point...
Well, just to be clear, I'm not saying that there's a problem with the Quackle random tile chooser, just that a particularly bad system implementation of srand() and rand() *could* theoretically work its way back into games. I don't believe this to be the case here though. I *am* saying that the implementation of selecting tiles isn't as elegant as it might be ;-) One factor that does need to be checked carefully (Jason didn't post that part of the code and I haven't looked at it myself yet) is exactly how the initial seed is determined, and more specifically how many bits of entropy it represents. The purpose of a seed is to inject some *true* randomness into the Pseudo-random-number generator, because an unseeded PRNG would return the same sequence of tiles every time and play the same game over and over (if all players made the same choices each time). This is a common problem from cryptography, and it's vital that your initial seed can have a large range of values. Simply using the wall clock isn't usually good enough. Let's take it to extremes and suppose that you were fetching an 8-bit value from some hardware register that was truly random. Then there would only ever be 256 different sets of tiles and you would soon start repeating games. Many srand() implementations used to be only 16 bits, so although this is a little better, it's still bad. For really good randomness you need a PRNG with a large internal state (128 or 256 bits) and a similarly-sized initial seed drawn from a true random source. But lets assume you do have a 256-bit seed variable you can fill... if you get your seed by simply calling the wall clock to get the time of day (let's ignore the date for this hypothetical argument), you're really only initialising it with at most 32 bits (the ostensible size of the function), and more likely you're initialising it with far fewer because the number of clock tick units in a day is TICKS_PER_SEC * 60 * 60 * 24 Then there's the problems caused by random seeds not being evenly distributed across the bits within the word. For example, your clock may have a precision of 1000 TICKS_PER_SEC but in fact it's only updated on a 50HZ cycle so the values jump up 50 at a time. This makes anything where you take the modulo of the variable to pick off the bottom bits quite suspect, hence my suggestion to make your random decisions based on a single bit extracted from the whole rand() value. (Mind you that could be screwed up if an idiotic implementation set a parity bit within the word!) Anyway, back to your question: the 'card shuffling algorithm' is a classic in computer science because so many people get it wrong. The natural tendency is to pick one card from the pack at random and put it in the first position. This isn't ideal. Rather than go into it in detail, I'll now punt you to that guru of programming tricks, Job Bentley: http://www.cs.bell-labs.com/cm/cs/pearls/ (I think you need to check out the book, I can't see the article online) It's an algorithm that's been reinvented many times. I think the definitive one is Knuth: http://tekpool.wordpress.com/2006/10/06/shuffling-shuffle-a-deck-of-cards-knuth-shuffle/ Here's are some related articles: http://www.ddj.com/architect/184403979 http://www.everything2.com/index.pl?node_id=1010893 Finally, here's what can happen if you get it wrong!: http://www.cigital.com/news/index.php?pg=art&artid=20 Regards, Graham
