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++) {
                cardList.add(new Card(cards[n], rand.nextDouble()));
            }
            //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

Tuesday, July 13, 2010

Manual Counting & Muggins Comes to Cribbage Pro!

After what seems like a very long time to me, and I'm sure to others outside of Fuller Systems as well, we are simply over the top excited about the new manual counting and muggins features of the latest version of Cribbage Pro that was put to the Android Market early this morning (around 3am PST).  As we were playing, I mean "testing", this release I have to admit we all got very addicted to counting manually and mugging each other at every possible moment.  It really adds a new dimension to the game and it is a lot of fun.

We spent a long time in testing on this one too, as we developed it for both single player and multiplayer versions at the same time and it introduced a lot of complexity to the turn, count and point systems.  I mention this because although we did thousands of tests against it, you all are much better at testing all the variations then we are (there are over 150,000 of you now), so if you find any bugs or quirks, please do let us know at support@fullersystems.com

Other features are in this release (version 1.0.8) as well, that are worth mentioning here.  We have traded out the old "comic" style default avatars for a new set while at the same time letting you change the image to your own custom upload as well.  Although I know many of you really liked the old avatars, there were just as many who did not, and so we felt it best to go more neutral with the default set we provide while still giving the option for everyone to have whatever they want to represent them.  You can find the old ones with some searching if you really want your old one back.  The only other note on this feature; please keep it clean.  We will remove avatars from public view (you can keep them on your phone of course) if we get complaints and find that they are offensive. We reserve that right at our sole discretion as is noted in the EULA, but really don't ever want to have to use it.  Right now everyone seems to be doing good with it (mostly dogs and family actually).

Some other things changed too.  We changed the settings/options screens to be categorized and added a password protection setup/registration to the process.  This let's you move from one device to another (say one of those cool new Droid X phones) or create an entirely new account should you ever need to.  It will also let you recover your account more easily, without having to contact us and wait.  Perhaps more obviously, it also lets you keep your pesky friends/kids/significant other from killing your points and ranking or making you look bad in multiplayer.

Before you ask, we did also tweak the shuffling a bit in the release too.  Most everything is the same, except we changed the algorithm that generates our random numbers to use what is called a "Mersenne-Twister" algorithm that we seed with random bits from the device.  I'll spare you the details, but in the end we think it is faster (easier on your CPU) and produces a better random result in our tests.  You will find that many computer based card games use this algorithm when a true random source does not exist.  I doubt you will find it much different, but if you think the card mix is different in this release, I suppose it could be this change (although you would probably have to be a computer analyzing hundreds of thousands of hands like we did to really notice). I should note here that on multiplayer games we actually have a true random source (it uses a mix of sources you can find by doing a Google search like random.org for example).  This means the results you get in multiplayer games for a hand are as true to random as anything could be (that we know of anyway).

Finally in regards to changes, you will notice some UI tweaks in the game that include updated and bigger buttons, a mix of other alignment changes (like the lobby chat in multiplayer) and a new "Multiplayer Top 50" button in the stats page.  This new "Multiplayer top 50" is really just the same point system used for the regular/old "Top 50", but you have to have played at least 5 multiplayer games to be on that list.  We will make a few more changes to this list as time goes on to help provide a purer look at where players stack when put up against other real players.

To sign off for today, a final thought/request of you all.  What do you want to see next?  We have our ideas, but would love to hear from you!  Leave us your comments here, or email them to us.

-- Josh

Friday, May 7, 2010

Cribbage Pro Update Coming Soon!

Well, it has really been a while since we last posted, and this post will also be fairly short. I'm writing to let you all know that all is not quiet here at Fuller Systems, Inc. We are actively working on our next release of Cribbage Pro, and we are quickly approaching a release date.

We are very excited about the new features coming to the game, and just can't hold it in anymore - so here is a quick list of what is coming next:
  • Multiplayer! - Yes, it is finally coming and I have to say it has been a lot of fun just testing it out and playing it amongst ourselves. There are a ton of features in this category from time limits for games to in-game chat and a game lobby. Unfortunately, manual counting and "muggins" did not make this release, but it is coming soon afterward.
  • Improved Shuffling - Yet even more improvements to our shuffling algorithm to improve the distribution of the cards overall. The most significant change is for multiplayer, but the single player game also has a version of the improvements that can work on a mobile device effectively.
  • New Game Board - An improved layout and color for the game board to make it a little easier to read and to look a little more like a standard game board. It's not perfect yet, but it is a step in the right direction.
  • Dealer Selection - We have improved the random selection of who is the dealer for new games and now make sure that the loser of the last game is the dealer of any next game started immediately afterward.
  • Bugs... - Yes, we still had a few bugs to kill, and this release will squash them. Primarily this is the "resume state" bug where if you send the game to the background and come back it was not picking up where it left off - this is now fixed along with a few other minor bugs.
  • Improved Help File - We have spent some more time in the help file in writing out more about what the game is doing and why, and added in an FAQ section to help answer some of the common questions we get.
Well, this is the short list of what to expect coming next. If things clear through testing in the next few days, you will see this release in the Market. Until then, feel free to comment here or email us with your thoughts on these improvements and what you would like to see next. We always love hearing from you.

-- Josh

Wednesday, February 10, 2010

Of Points and Ranking

We have recently had a few comments and questions about the points and ranking system used in the Cribbage Pro game. These comments and questions have been very insightful and helpful in understanding a different perspective, and in response to some of this we are making a few changes to the system.

So, effective immediately, the following changes are now live in the "Top 50" tracking system:

  • Players with unfinished games over 50% of finished games will not qualify for the "Top 50" - they will simply not show up in the top 50 at all until they have played enough games through to bring the percentage back above the line.
  • Players at level 6 or above (points >= 2500) will not be awarded points for a win against a Novice computer player (and no loss of points for a loss) going forward. Players who have already accrued points, will retain their points.
  • Players at level 8 or above (points >= 2750) will not be awarded points for a win against an Intermediate or Novice computer player (and no loss of points for a loss). Players who have already accrued points, will retain their points.
  • The minimum award for a win against the advanced computer will be increased from 2 to 4 points, the intermediate win will stay at 2 but the novice will be decreased to 1.
We believe that these changes will close some of the "loop holes" players have found in the system and will make the ranking in the single-player game more "fair".

Please keep your comments and questions coming in, and let us know what you think.

Since I am writing a post on points and ranking, I should also spend a minute explaining the system being used. Again, if you have sent us an email with this question, the below is going to look familiar.

The first thing to mention here is that it is not a "Ladder" system or a simple points system, it is actually a ranking system which can be foreign to some, so I'll explain what that means. In the next update, we will include more details about the points system we use in the help file to make it more clear what is going on. It is definitely a miss on our part to not have that already included there.

In regards to the points specifically, it is a bit of a technical explanation, so I'll try and explain as best I can. The system is designed for ranking each player as accurately as possible, not a points system as stated earlier, and so as such we give virtual "points" or rankings to the computer players you are playing against (the advanced player is ranked as a "2500" point player). So the points then really is your "Rank" against all others, and just as others win and lose, their points will follow the same algorithm. Those computer players only have so many points themselves to "give away", and as your level goes beyond their level, you get fewer and fewer points up to the minimum amount of 2 points for a win (now adjusted as noted above). Similarly, if you lose then the system works in reverse and so the penalties are larger as your points are larger then theirs (up to the maximum of 41). The system we are using is very close to this one:


It is intended for player to player ranking more then computer ranking, which is why it seems odd right now. When we add the multi-player functions, it will make a lot more sense. However, we may change/tweak the algorithm as well as we are still in beta with it, and it can be concerning to be ranked high and lose so many points so quickly when you lose a game. We will likely keep this one for multi-player either way, as we believe it proves out to be the fairest we have found.

The three point levels the computer players are:

Advanced: 2500
Intermediate: 2000
Novice: 1500

You can use the formula given and these point levels of the computer players to calculate a potential win/loss point award as well. No extra points are given today for a skunk or double skunk beyond what you get by winning by so many points, and we currently do not have plans to change that.

-- Josh