## Friday, July 16, 2010

### Cribbage Pro Shuffling & The Deck

So lately it seems popular to dig on the shuffling and claim that we are stacking the deck in the game to favor the computer player.  I'm not going to go into the "Hey, your game cheats" thing again and why people like to think the computer is cheating when they lose, and I'm not even going to go into how the game does it's dealing "every other" and so it could not favor one player over the other.  However, I do want to give everyone some actual data points for the discussion since it seems lots of people are excited about it.  So, for this post, here is some information you may find interesting.

As was mentioned in our last post about the latest release, we use a random number generator in single player mode to randomly pick the location of a card in the deck - so as to shuffle it.  In multiplayer it is from a truly random source, but in single player we use a "tried and true" pseudo-random source based on the "Mersenne-Twister" algorithm.  So what does that really mean though, what is the result of doing that and what does it look like?  How fair is it really?

Let's define some terms first.  We will call "fair" something that in all measurements possible seems to be as truly random as possible.  You may have a different opinion (like it should match a real world shuffle as strictly as possible), but we will not go there for this as there is so much debate about that single point we will simply not solve it here.  The second definition is around a "shuffle".  For this argument, let's agree to define it as the process used to randomize the deck.

So, without further delay, here is the code that does our "shuffle" in the game today:

rand = new MersenneTwisterRNG(new SecureRandomSeedGenerator());
//Loop through each card giving it a random value
for (int n = 0; n < cards.length; n++) {
}
//Sort by that random value
Collections.sort(cardList, new CardSortByKey());
//Store back into the byte array
for (int n = 0; n < cards.length; n++) {
cards[n] = (byte)cardList.get(n).getOrdinal();
}

There you have, it.  That is all there is to it and it is a direct copy/paste out of the game with comments and all.  If you can't read it, what it is doing is first getting that random number generator I mentioned earlier, the MersenneTwister.  It "seeds" it with the same kind of source that is used for security on your phone (that SecureRandomSeedGenerator makes that happen).  It then takes random numbers from that and assigns one to each card, and then it simply sorts them by that key and stores each card in that location.

So that is the shuffle, but what does the result look like?  Well, one of the best ways we have found to show this is in what is called a scatter/plot graph.  Now we could show you every single card and where it landed, but trust me, you could not read that graph/chart.  So what we will show you is what we will call "marker cards" in the deck and where they ended up after the shuffle.  We chose the "ace" card from each suite for that purpose, but we could just as easily choose anything else, it was just convenient to do that.  The data shown here comes from thousands of real games played - not just us running this in some test area - these are real decks used in real games that some of you may have played.  We got the data from a set time period and stopped at 3,000 decks.  Going anything beyond that and it gets very hard to visualize, but we could of course go to many, many more.

OK, you have been waiting patiently.  So here is the first graph:
This graph is for the ace of hearts (AH) and it is showing for 3,000 decks, where that AH was in the deck from position 0 (top of the deck) to position 52 (bottom of the deck).  As we progress this forward, what you end up getting is what really is a very random distribution.  If there was an inequality, it would stand out as a cluster surrounded by a lot of blank space - and you really just don't see that in the data.  Sure, there are some spots that are darker the others and some not as much, but in the end if you zoom in even, you will find that distribution is quite random from one deck to the next.  Just for informational purposes and to complete this thought, here are the other cards as mentioned:

So that is the distribution of cards in the deck as given by sample marker cards in the deck.  You will see that none of them look the same, this is a good thing, but at the same time don't get too into these and try to read much into them either.  I show it here to say simply this - it is clearly not favoring any deck position over any other.

There is one other way that we have found somewhat helpful in determining not just how distributed a card might be from one deck to the next, but generally how "well shuffled" a given deck might be.  To do that, you can consider looking at what the relative position of a card is now against the card that is positioned next to it in the deck and it's original position.  In other words, two cards may have started as being 1 position away from the other card, but how far apart are they now?  So if you give each card a starting point form 0 to 52 and then you shuffle and see how far apart they are from where they started relative to each other you get an interesting picture.  Of course the theory here is that the more that the results show some random separation, then it could be considered a good shuffle.  There is no "gold standard" we have found in this regard, and maybe we are the only ones looking at this.  Anyway, here is our data of a deck we grabbed from one at random:

Here it is averaged over 5 decks:

Now over 10 decks:

Do  you see a trend?  Here is at the 3,000 mark:

Yeah, we think it looks cool too.  It is almost smiling at you.  In fact, I think it looks like a really good distribution in a good random shuffle.  Things settling towards being equally distributed in the deck on average - meaning each has a decent chance of showing up just about anywhere.  If you consider the possible combinations of a deck, the more you approach that factorial, the more this graph will get flat.  That is exactly what should happen.  I think that is cool.

Feel free to add your interpretations in the comments or ask for other views of the data.  If you have some cool graph you would like to see (and you can tell us how to construct it somewhat), we will do what we can to give it to you.

In summary, we think this shows two very good perspectives on the shuffle and distribution in the game.  We hope you found it interesting and informative.  We think it fairly clearly shows the unbiased nature of the game and the random nature of it's results.  I'm sure some will disagree, but if you do disagree, please let us know why and what you may find more compelling or if there are parts we did not discuss that you would be interested in knowing more about.

-- Josh

1. Pegging is where you win games anyway. ;)

If you wanted to be as realistic as possible, each card could be an object with randomly generated attributes like surface composition, construction, cupping, bent corners (hey it's a friendly game right? That beat up old deck is just fine), and then feed all of that into a physics engine that...

I think your time would be better spent figuring out how to not disconnect players from the server in multi-player. What problems do you face for that?

2. Hey Jon, you made me laugh about the physics engine comment.

The multiplayer games disconnect on mobile devices for any number of reasons (there are many). Sometimes you will find that your phone is switching between cell towers and it hangs for a moment or drops, or it is switching between 3G and other options depending on your provider, or a mix of those things. WiFi is of course the best option to get a good connection. Finally, some devices simply have a hard time keeping an "always on" connection alive for long periods - why exactly, I can't say.

The way the game determines if you may be disconnected and will try and reconnect is by determining if it has heard anything back from the server in a set period of time (there is a heart-beat sent between the game and server regularly). We do that because in the scenarios I give above many times the device will not get any notice that it is really disconnected, it will just sort of "hang" and not get a "heart beat" from the server for a while. So we use this timer of sorts to determine it. Sometimes the cell carriers proxy data and it causes delays and forces disconnects as well.

So the server is almost always not disconnecting anyone, the server runs for weeks on end without restarting or dropping any connections. It is the device losing it's connection for one of many reasons and then re-connecting back up to the server.

In the last release, we tweaked the timer part of the disconnection/reconnection code a little to be a bit more aggressive in regards to reconnecting as we had conditions where folks would lose a game because it failed to realize it lost connection in time to complete their turn. Hopefully you find that when it does reconnect, that it is doing so successfully and your able to continue to play. If not, please let us know.

We are always looking for ways to improve this, and in each release we tweak a little more to make it just that much better each time.

-- Josh

3. I love cribbage pro, but I can't seem to find how I advance to higher levels. Can you point me in the right direction?

4. Thanks so much, Joshua.

5. Hi Josh,

I have a question that is basically the opposite of the "does your game cheat?" question.  I just had a 29 hand on cribbage pro after playing it just under 200 times (In my life, I have never even had a 28).  I read that the odds of having a 29 hand in 2-person play are 1 in 216,580.  Without trying to understand the technical stuff above, can you tell me if the odds are similar with cribbage pro, so I can bask in my newfound glory?  Much appreciated.

6. If it helps, I was using an iphone.

7. Well I can't comment on the work done to determine the odds of a 29 being 1 in 216,580 or not (Wikipedia seems to agree), we don't do anything in the game to alter the "odds" in any way.  We try and shuffle the deck as randomly as possible as demonstrated here, and given that and the same number of players and cards in the calculation of the odds are the same, I don't see any reason why the odds would be any different in a computer version of cribbage then they would be in the "real world".  You can of course play a lot more virtual games then you could "real games" because the shuffle, deal and general play of the cards is so much faster and when you add in automatic counting it is even faster.  As a side note, we do check the stats of our players somewhat regularly, and getting a 29 is very rare.

8. Thanks Josh,

I feel fully able to bask in the glory of my 29 hand now.

9. ok well you can throw all bs out u want but the facts r no. singel player gets 16 to20 point 75% of the time in one game so go and play it and then, explan all your bs

10. I have played cribbage for decades, Cribbage Pro is fun - but it in no way replicates the card game at a table with real people. The computer deals itself hands that only my Aunt Pat could possibly come up with, ha ha. Fun, but not real.

11. As we said in the response to "Rfennel" below, Is it trying to replicate "real life", no, not at all.  I won't re-post the same things again in this response, but to be clear, the game is not "dealing itself a good hand" in order to win.  We have proven this in the data shown above (feel free to call out any errors you see or any questions you have on any specific points I make) and I have repeatedly stated that anyone who wants to review the very code used in the game for fairness can do so by simply asking us for a waiver.  I truly hope someone will take us up on that offer, but ultimately I doubt it will make much of a difference for anyone but the one who does it unfortunately.  If you would like to take me up on that offer, just let me know.

12. So now you've addressed the shuffle, but here's the issue I have: the cut. I understand that it is possible for the computer to be dealt 555J (which it has, several times; I am yet to be so, ahem, lucky), but if I am the dealer, the computer will without fail cut a 5 or a J. Dealt 7788? It will cut a 6-9. I looked at my statistics and I'm pretty much 50-50 with the computer on the highest skill level, which is exactly what I would expect with a human player of comparable skill. However, when I lose, I lose by an enormous margin. Just today I played a game where the computer managed 3 20+ point hands back-to-back-to-back. Although I am responsible for one of the cuts in there, the computer's hands would have been significantly smaller if not for the ludicrously perfect cuts it made. While I am certain you have a defense that the process is entirely randomized, I have played around 150 games and the computer's luck should have run out at some point. It can be a little on the frustrating side at times.

13. Hi Jayson, thanks for the comments and question about the cut. Yes, there is a "defense" for how the cut is performed, but it really is just an explanation of how it is done. When the deck is presented for you to cut, it is shuffled the same as the decks used everywhere else and when done during play (after the discard) it is actually the same exact deck of shuffled cards it used to deal with (the cards that were dealt were removed as they were dealt, just like in real life). In fact, if you can see the cards in the spread out deck you can see that the number of cards are less than the amount shown when you cut for deal at the start of the game because of these missing cards. When you tap/select a position in that spread out deck it represents the card position in the deck that you selected and that card position is the card you are given. The same is true for when the computer does the cut, but in that case it picks a random number from the top to bottom of the deck (following the same rules as +4 from the top and bottom) and draws out that card. Whatever it has, it was it is given. The two systems (the one shuffling and the other cutting the card) have no communication with each other in any way and have no ability to manipulate the results in any way.

I realize this doesn't help in your frustration, but you can know that we have done everything we can to keep the game as fair as possible in every respect.

14. Hi Josh, since posting this I played a game because I hate feeling like a conspiracy theorist. I was beaten 121-71, nearly double-skunked, with the computer hitting 3 hands of 20 or more. My highest was 13. With me as dealer, the computer ended up with 7789 and cut an 8, and followed that up on my next deal with 6788, cutting a 7. On that second hand, I was holding two sevens, meaning that was the last in the deck. Maybe it's just good luck, and I'm sure I would have no gripes if it went the other way, but it just hasn't. Ever. I have had, to date, one hand of 24 points, and probably about three total of 20 or more. If I had the computer's luck, I would take my life savings and play it on green at the roulette table. Then I'd go to the Victoria's Secret Fashion Show, walk backstage and ask Miranda Kerr how quickly she can pack her things, cast off to Aruba with her and never play cribbage again.

15. Can someone please tell me how the dealer gets so many hands of "all of one suit"? Its impossible! I have 400 games and that bothers me by far the most.

16. I enjoy your game, but I play online against other players. I've been playing crib for 40 yrs. I have never seen so many big hands and so many of them. I'm sorry, real crib just doesn't work that way. it seems the game is already decided before you even play. it gets very frustrating knowing this app is not on the up and up. I don't know if some players have cheat programs or the game is set up that way, all I know, I consider myself a pretty good player, but it seems some games are fixed. Not just on the loosing end but I've won games where the hands I got are not common in a real game. Just wish it was like a real game of cribbage where skill prevails, not big hands one after another every game to decide the winner.

17. Hi Rick, glad to hear you enjoy the game. As you can see in this blog post, we take the fairness of the game very seriously, and can assure you that nobody is being favored in any way and that the game has not been compromised by any cheaters. The deck and all the cards are handled entirely on the server and only sent to the individual players at exactly the right times to be shown. It is impossible for anyone to install anything or modify their version of the game to gain any advantage.

The game uses a full true random shuffle (as described here) for each and every hand in every game, and this is not necessarily like what you might see in "real life". In the physical world, the deck is often not shuffled to a full random deck (rarely is in our experience), and this makes the experience quite different. This means that in our version, every possible hand is possible every time with the "odds" not changing from hand to hand. In a physical deck shuffle, the odds can and usually do shift depending on how well the deck is shuffled. If you have ever accused someone of "over shuffling the deck" or similar, you know what we mean. Because of this, we are not going for "exactly like real life" here, but instead "fair and unbiased". These are two different things, and likely why your experience is what it is. Feel free to email us at support@FullerSystems.com and I can share a lot more around this topic if you like, but it is too long for a comment on the blog.

18. Why is it on numerous occasions, I win or lose the online game and no points change hands. I've skunked people and the score stays the same. I'm still not convinced that this crib app is a fair game.

19. Hi Rick, this is likely because you are playing a "non ranked" game. Check the star icon on the games list to make sure it is on and listed as a ranked game if you want the results to count for points. If you would like to see anything further to convince you that the game is fair, please let us know specifically what you would like to see.

20. I really don't want to be one who whines about x, y or z, but I've been seeing a trend and it's bothering me. It seems like (not every time, but often enough that I notice it) that I have an either or choice w/r/t the opponent's crib (this happens much more online than in v. computer version). So I have, say, 1,2, 8,9,10,K. So basically I'm throwing K, small, (and if I choose K2, the 3 pops up, if I choose the 1, the four pops up). OR conversely, there's a hand where I know I'm taking a risk, throwing what I throw into the opponent's crib, and WAY too often the magic card gets cut. There's also way more 0 or 2 point (and, conversely, double run) hands than I ever experienced playing live. Again, I'm not trying to be conspiratorial on this, but I went from a 17 ranking to a 7 in the course of losing about 16 out of 18 games now. My winning percentage prior to that was about 55% so it's not like I don't know what I'm doing. Several of these have been of the I'm-winning by 17, 6 points from winning, and I get a zero and my opponent gets 67778. Again, my point is that this has been happening in a way that does not feel random, and this is based on experience, not a reaction to losing. I have no problem losing, but you get a sense of cards being stacked against you and it's unnerving. I don't think the system is "preferring" a player, but it does seem to prefer "interesting" or "unlikely/ironic/compelling" cuts and deals, with way more ebb and flow happening within a game than I've ever experienced playing live. I'm not even really asking for an explanation. I'm probably just gonna stop playing at this point. This is more in the nature of "it seems clear you think x about your product, or at least you're saying x about your product, but it's not behaving that way, in my experience, and perhaps you should look into it, or at least look at my last 25 games and see if it makes any sense to you.

21. And yes, while i do seem to go through spates of 0 and 2 point hands, the real issue is the miracle cut that happens way too often.

22. Hi "bobbym2", thanks for taking the time to write with your concerns. As you say, we are not "preferring" any player, and just the same we are not doing anything in the shuffle or dealing (or anything) to alter the outcomes of games. We have shown this here, and in multiple other posts, how we believe the game is being truly fair in it's dealings. We have also conducted a lot of analysis on the games played in multiplayer, and have produced a lot of material on this topic of discarding. You can start here: http://blog.cribbagepro.net/2012/10/discarding.html and read through the other posts on the same blog for that topic.

Specifically, in regards to the "cut", know that the card that is cut from the deck is the actual card in that position in the deck that the player who is doing the cut selects. So if you are doing the cut, and you select the 10th card in - that is the card that is pulled from that shuffled deck and shown as the cut card. We do not control the cut card in any way. We simply show the card that was selected each and every time. Anything short of that would be unfair and destroy the integrity of the game.

23. I play your online crib game. Lately for some reason my ranking is not advancing or decreasing. The points are going up and down but I'm stuck on a 50 ranking and it won't change.There was a upgrade a couple of days ago and seems to be screwed up since then. The rated box is checked off, so what is happening.

24. Hi Rick, this is actually a fairly common question because of how player levels are calculated and the "plateau" that is designed at level 50. The points and level system has different "break points" along the way, and the one at 50 is one of the bigger steps up to get to level 51. You can see this breakdown of points to levels in the FAQ here: http://www.cribbagepro.net/faq-how-to.html#q11

25. My friend and I both Have CribbagePro downloaded on our android phones. We each have over a thousand games against the computer. We'd like to play each other long distance. Can you walk me through setting this up or at least direct me to the specific site for setting it up. Tried to locate the directions myself but had no luck. Thanks