- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
Interesting story:
I was in a casino once, playing roulette. It was one of those where they listed the previous numbers. I was making "corner bets" based on that sequence. I was winning at a steady rate. Eventually the croupier asked if I had a "system". I replied, perfectly honestly, that I didn't and that I was going on hunches. A few bets later I cashed in my chips and found another table, and tried to win "less often".
On the same occasion, before I started betting, I was watching my mate bet (and the sequence display). I then started "suggesting" the next bet. And my mate started winning - he was seriously impressed. That's when I started play with myself ( :hanzo: :giggity:). It was the first and only time I played roulette in a real casino).
Admin
I'd hack the compiler. Clearly needs to propagate through to others compiling the code in the future, but...
http://scienceblogs.com/goodmath/2007/04/15/strange-loops-dennis-ritchie-a/
Admin
Hmm - not quite - if the PRNG is badly seeded. See http://www.ibm.com/developerworks/library/s-playing/ for an infamous example
Admin
I am not sure it meets the requirements but instead of a list of previous numbers, I would maintain a list of weights associated to each number. At the beginning, all weights would be 1, so each numbers has a equal chance to be drawn, but the weight would decrease for the last draw (down to zero if repeated number) and then slowly increase back as the number ages. And the list of weight being calculated afters each draw will be passed back unmodified to the next draw. And I would forget to check that the list of weights, used as an argument to the drawing function, has sensible values in it (I can forget that, it is not part of the requirements), so I could assign an high value to a number, artificially increasing the chances it is drawn. Of course, the part calculating the weights for the next round should take care of cleaning any such too high value.
Admin
They'd still continue to make a profit, because I wouldn't expect most people to notice the pattern. In order to take advantage of it, you need to bet on all but three numbers each round.
I'm not sure how a pattern of bets would work, since there's no obvious reason for the number-generation code to even have the bets as an input
Admin
You know 2^31 rolls would take about 68 years at one roll a second, right? I don't think our programmer is prepared to wait that long.
Admin
I don't even pretend to know what this is supposed to mean. In what reality do what same numbers come up surprisingly frequently? Real world events often follow Poisson distributions. In a Poisson distribution the probability of certain results is much higher than others, but the sequence in which they occur is truly random. Harold Wilson, the former British Prime Minister, was originally a brilliant statistician and he wrote a paper about this for, of all things, football, in which he showed that although the results showed a Poisson distribution (i.e. 0 goals more probable than 1 which was more probable than 2, and so on) the results of matches taken as a whole were random. Another example: lightning strikes are not random because some places have a higher ceraunic index due to altitude, geography, soil conductivity, wind and rain patterns. Therefore lightning strikes do show clusters but this is due to the underlying mechanism.
As a matter of principle, mechanical RNGs are not the best because of manufacturing tolerances. Although roulette wheels are made very accurately there is always some bias, but it doesn't matter because roulette is not a fair game (the house has a permanent advantage). A lottery based on balls is biased because no two balls will be exactly identical, let alone all of them. Probably the best random number generators are those based on radioactive decay of an isotope in a heavily shielded environment, with white noise diode generators a close second. The original British lottery - Premium Bonds - used a white noise generator, I believe. Because a lottery is a very unfair game, it is not necessary as part of the design that the numbers be random. Thay can be pseudo-random so long as the algorithm is uncrackable. An even distribution of numbers in a relatively short timeframe could give an attacker information to improve their chances - but as the probability of winning is typically only around 30%, the information will only allow them to lose money slightly more slowly. As I noted above, giving a system small flaws that a clever person can detect may actually raise the house income by keeping them gambling longer. A person with a "system" for roulette is good for a casino because they will keep betting, not realising that the house advantage means that in the end they will always lose if they carry on long enough.
Admin
I know, but we can rule this out, for a short-period PRNG could be compromitted by any statistician.
(For linear congruent generators it is not difficult to calculate its minimum period length and to find a seed that runs into that period length.)
Admin
I think I said that
Admin
Admin
Well, the second remark, you're right about that. I changed this afterwards, I don't know anymore why, but I wrote the original because I vividly remember having done that.)
Admin
By a machine?
Admin
That's why the balls (and afaik the machines too) are replaced in Germany so frequently that those differences won't become statistically significant.
Admin
No idea; that particular selection isn't televised.
Admin
We'll just have to assume that I am not bright enough to understand your posts, because the possibility that they might not be clear as to their meaning can be ruled out.
Admin
I've been working on this all night. I'm trying to program the known laws of physics into my application, then arranging molecules so that they create a human baby in my Matrix-esque world with my DNA. Then my clone will pick the same numbers I would when asked for a random number, but it will seem random to everyone else.
My project manager says we should be done by next Wednesday.
Admin
I agree with @Nick_Johnson: it's not preventing of runs, but the other part of this requirement: once number has been drawn, the probability of it being drawn again decreases, which would allow for punters to feel like a certain numbers are becoming HOT. This knowledge alone is likely to eat house margin in the long run completely.
Admin
Agree. It's making the numbers that already appeared less probable, which would make it predictable enough.
Admin
Uh... the opposite?
And it 100% depends on how you make the algorithm. Let's assume you're always betting after the streak, so you know that this particular number will never come up - that still leaves you with a house edge of one number's worth, which means that even if you prevent another number from ever coming up, or make the two previous numbers 50% less likely to appear, you're still on even money - and are likely to come up in black, due to the fact that not everybody knows the secret.
Admin
In general that is true. However in this case our goal was to create predictability that a savvy gambler can exploit to beat the house's advantage. We don't want anyone finding that pattern, because the house doesn't like to lose, and when it does it'll prompt investigation because (as you said) it really shouldn't lose.
Admin
It's plain security by obscurity, but it should work. For example, consider a generator that behaves randomly, until it hits the sequence "12, 32, 6", after which it outputs the number which is an SHA hash of n-th page of War and Peace concatenated with the phrase "purple monkey dishwasher", modulo 37, where n is the current minute of the day (also modulo however many pages War and Peace has).
Yeah, it's technically exploitable, but good luck finding that out.
Admin
Maciej, I am saying that making numbers HOT is the requirement here in this exercise. What the second requirement says is:
So it is to implement the Gambler's Fallacy. Such PRNG would be increasing the probability of specific number being drawn close to 1 after that number has not been seen in last 44 draws. Just drawing the numbers which did not show up in last 44 draws would give you needed advantage.
Admin
Only if the mean difference in probability outweighs the roulette game's house average.
Admin
Ah. I understand "hot" as "coming in streaks".
Anyway, it's still up to how much you tweak the probability. You can do that and maintain the edge provided the change is small enough (I think not more than 2,7 percent up, but I don't have the math handy).
The task doesn't call for that, though - it rather calls for decreasing the probability of a few last numbers. And you have much more leeway with that - you can, for example, make three last draws 20 percent less likely to appear and still maintain an edge.
Admin
I think there are two problems with this exercise:
A strategy that may work, though still sensitive to more expansive statistical analysis, is lowering the odds for the N-1 and N-2 rolls but increasing the odds on the N-3 and N-4 rolls. Possibly vary that on time-of-day.
If we assume rolls are on a fixed interval (say 1 roll a minute) then you've even got a good reason to even look at the time, and only make the skew exploitable in certain minutes.
Admin
So, the Lucky Deuce in question is the one dropped by the programmer who received this mess of a requirements statement?
Admin
I don't care enough to actually create and submit something, but everyone saying that implementing the spec still results in a house advantage is missing something - you don't have to follow the "no streaks" spec precisely. Introducing a subtle bug that makes it so after a streak, half the numbers are impossible (possibly depending on the number in the streak) gives you much better odds in that case. Other "reasonable" rules like preventing runs of one color or ascending streaks give you more opportunities.
If you're worried about other users catching on, make it time sensitive - if every so many rolls, you re-seed the PRNG based on the timestamp (for more "randomness", duh) then you can introduce a bug where some state is changed only at certain times. Something like a bad cast resulting in part of the timestamp overriding another field. If the glitch is triggered by a specific set of bits set in the timestamp then it doesn't correspond to the same time every day. That state being tweaked is the trigger for the other bugs, and only you know what times you can play for an advantage.
Making the bugs look unintentional would be a challenge, but I think it would definitely be possible.
Admin
You are adding a lot of randomness in the design of a table that doesn't result in randomness in the result. So making your life harder for no return. The whole "an SHA hash of n-th page of War and Peace concatenated with the phrase "purple monkey dishwasher", modulo 37, where n is the current minute of the day" can be replaced with an array of size (60*24), filled with numbers 0 .. 37 (double 0 was specified) in some random order.
It doesn't matter how much effort you put into obfuscating what method you used to order the numbers in the array. As far as the output is concerned you're simply indexing into an array by the time of day.
Admin
I threw together a quick proof-of-concept that lets SystemTimeToFileTime "accidentally" overwrite the stored last spin (for streak prediction) with the high word of the file time when reseeding for "extra randomness". When a streak happens, the code generates a non-streak result, stores it as the last spin, reseeds (just to be safe), then returns the overwritten last spin. This means that after a streak, the last number is predictable based on the high word of the time, which increments every 7 minutes or so. If the result is based off some hash of the random number, not just mod, then it would be very hard to notice a pattern in it.
Admin
Well yes, you are. But you're subject to code review, so the point is to hide your work - say, instead of reading from
/dev/urandomand hashing it for extra randomness, you accidentally stumble onto/home/me/War and Peace.txt...Point is, an array would work, but it's no fun.
chmod -r /dev/brain... Actually my idea was to overwrite the seed, so that the generator gets seeded with a predictable value.Admin
I suspect an array of random numbers, which you explain in a comment is used to store randomness for later use in case urandom hasn't accumulated entropy yet, will pass code review much more easily than a dependency on War and Peace.
Admin
Yeah, but if you can make it dependent on War and Peace in a believable way, that's worth like a billion style points.
Admin
Are we talking here about an English translation or the original? A reference in the code to "Voina y Mir" might cause someone to think that the Russian Mafia was taking an interest in the casino, and leave it severely alone in case of repercussions.
Admin
I think Thor could take Ymir any day!
Admin
There is no need to write a cheat function. The very fact that you know that the next number will not be one of the previous three skews the odds sufficiently that knowing this, you can beat the casino.
Admin
Probably by a randomly selected counting rhyme performed by a randomly selected person.
Admin
I was thinking that we need to have a very strong random number generator service, and a subtly wonky javascript client of that service.
Admin
What if instead of forbidding streaks of the same number, I forbid streaks of each possible characteristic? For instance, if there are two even numbers in a row, the next one will be odd.
Then I just have to wait for two noir, impair et passe in a row, and bet on the 4 or 5 Rouge, pair et manque numbers.
Admin
That becomes unprofitable way too fast. Completely blacklisting multiple numbers in a roll eliminates the house advantage to anyone who knows the pattern, and these patterns are both noticeable and likely to be followed even by a gambler who doesn't look at patterns. You're always walking a very thin line because the requirements already inherently reduce house advantage according to a pattern a naive gambler will follow.
Admin
A different idea: Say we're keeping a history of 20 rolls (even though we only show the customer the last 5). In case we roll the 3rd identical number, we actually trigger a bug which causes the N-20 roll to be recycled as the current roll. The only way to exploit is to (outside the actual site interface) monitor the roll sequence and if a duplicate comes up, roll on that number. 2/38 odds for a 36x payout is a nice profit in the long run.
Admin
Ok, so considering the requirements for this would rig the game against the house, seems like we'd have no choice but to require a list of gambled-upon numbers as an input.
Admin
LOL. It took this long for somebody to "pick this up". My idea, from the start was to use the second, or third, repetition as the trigger to activate the cheat. Because you have a legitimate reason to code for that situation. I was also going to use the creation of the "feeling" of randomness to disguise the actual cheat. My objective was to introduce a high level of predictability - say 1 in four or six, so many numbers (again 4 or six) after a repetition.
I would use, as part of the obscuration, loops and counters of four or six through out the code, the argument being that they are "factors" of 36 (0 and 00 being ignored). I am still trying to "find" an elegant coding sequence that functions as normal but produces a predictable result from a predictable event without shoving an effing great IF in there.
I still may do that, if I can get some time in my "coding happy place".
Admin
My thought was to use a memmove() to rotate the array of stored values and off-by-one the length argument so it writes outside the buffer into the 'current roll' field. I'm not gonna bother writing it out though.
Admin
Expanding: normally you rotate correctly. Check for the streak after the rotating, so you need to fix the history if you re-roll, which is where you can put the bug.
Admin
OK, so now the deadline is past I feel I can describe my idea (which, as I thought, I didn't have time to code up). :smiley:
The idea is based on smoke and mirrors. Let there be a server-based random number generator. Let that server use as strong a random source as you care to name, really secure, so that it can be used to power many different games of chance; because of that fundamental need for reusability, it spits out floating point numbers in the range $(0,1)$. Let that server use a nice heavily-secured web service to spit out the numbers, with lovely cryptographic signatures, etc. We then wrap that RNG source in a client-side function that unpacks it, checks the signatures, throws an exception (or whatever the JS thing to do is) if anything is untoward, etc.
But users don't directly bet on the glorified output of
rand()directly! We use that random number to pick an entry from the list of possible roulette results. Trivial wrapper. Except management have demanded (in a hurry, no less!) that we stop runs of three. Oh no! Well, we just keep a history of what was generated in the past and use that to exclude numbers if they would hit a run of three (we can just ask the underlying RNG system for the next value if that happens, or we can use the list to pre-filter the set that we select from). Easy. The idea is that we keep a list of previous values and can just check back through that list to see if there's a double-entry in it for the value that we currently have. Whenever we generate a new value, we add it onto the end of the list, truncate the list to two-entries long if it is longer than that (because that's all we really care about) and store it back into our persistent state. Fortunately, we can keep that client-side using some variation on HTML5 local storage, so we don't need to futz around with keeping all that stuff on the server. After all, we're a global operation and don't want to have to mess around with complicated central store if we don't need to.Can you spot the weakness yet?
[spoiler]The critical thing is that the state is in local storage, and doesn't prevent the user from changing it from outside the application. It also doesn't check the length before using it. Simply setting the state to a list of (pairs of) entries of all the values that you don't want lets you pick a result to fit any profile you like. Writing a program to do this is part left as an exercise for the reader.[/spoiler]
Better yet, code review might pick up on the weakness but won't identify it as a deliberate attack. You might even be able to get away with it…
Admin
Severe drawback: Can be exploited by anyone that knows enough JS and HTML5 (and can see through the obfuscation, if applicable).
Admin
If you're going to cash out, do you care that others do too?
Admin
Of course I do. As sure as heck there are some idiots among those "others" that misuse that feature so blatantly that the casino will notice it within hours if not minutes. And even if everyone was modest, the more participate, the more obvious such features become.
Admin
Continuing the discussion from Introducing the Lucky Deuce:
The problem with posting a programming challenge like this is that there is always someone who can't keep a secret. Rather than rush off to implement their fine idea, they publish on the forum and leave it to someone else, who may then gain the kudos. Or worse, someone else has had the same idea, kept it to themselves, written a good implementation of that idea -- and is then swamped under half a hundred other people who have read the idea, having seen it published by a blabbermouth.