"random" cards aren't random

[pikoro]

I've been playing your solitaire game for quite a while, usually Klondike, and I've come to notice an issue with card distribution. Way too many times, cards are grouped on the stack, in a non-random order. For example, cycling through the stack one card at a time, I'll commonly get a BK, RQ, BJ, R10, etc.. in order. This occurs from the main stack as well as on the lower stacks when turning them over. Looking into it (I'm not at a place I can compile and test changes myself), it appears that the randomize(Card[] array) function isn't using any kind of seed when randomizing cards. I realize it's a PRNG, but when receiving things like 4 aces on initial deal, or cards in order for use, it takes away enjoyment from the game. I really do like it, but sometimes I can nearly clear the board before flipping my first card to the discard stack.

[TobiasBielefeld]

Hi! Thanks for the issue report.

My randomize method uses the default Random() constructor which "sets the seed of the random number generator to a value very likely to be distinct from any other invocation of this constructor." like the Android docs says.

I never experienced the issue you are describing, so my first guess is, that the problem could be related to your device.

Maybe Random rand = new Random(); doesn't work correctly, so I could just directly pass the system time as seed like Random rand = new Random(System.currentTimeMillis());. I can also move the declaration of rand outside the method, so it only needs to seed once when a game starts.

I can give you a test .apk file of the game to test those changes if you wish. But it would be signed with my signature, so if you have the F-droid version of the game, you would need to uninstall it first to install the test .apk.

[pikoro]

I've experienced this on 2 Nexus devices, a 5x and 6. One runs Lineage OS and the other is Stock 7.1.2.
Here are 2 more examples I captured this morning. One with a 3/2/2 split. 3 8s, 2 4s, and 2 Ks. The other with 3 9s. Like I mentioned, it's not every time, but seems to happen an awful lot. I'd be happy to test a new version.

[TodorBalabanov]

private void randomize(Card[] array)

    for (int i = array.length - 1; i > 0; i--) {
        if ((index = rand.nextInt(i + 1)) != i) {
            dummy = array[i];
            array[i] = array[index];
            array[index] = dummy;
        }
    }

You can remove IF in the FOR loop. This check will be done about 52 times. It is more time consuming that to swap once or twice i with itself.

Also, if you present Card[] as List<Card> you will be able to shuffle with Collections.shuffle(...).

[TobiasBielefeld]

Okay I also use Lineage OS, so I guess thats not the problem :)

@TodorBalabanov
I think Collections.shuffle() isn't necessary, because the docs say, that it uses the same algorithm to shuffle and it converts the list to an array to shuffle, then back to a list. So I think I can directly shuffle it as an array.
But it's worth a try, i got 2 files for testing:

This one with the changed seed:
app-release.apk.zip

And this one, using Collections.shuffle()
app-release-collections.apk.zip

Hope that these files can help

[TobiasBielefeld]

oh and I changed the rand.nextInt(i + 1) statement to rand.nextInt(i) so no IF necessary :D

[kleinj]

oh and I changed the rand.nextInt(i + 1) statement to rand.nextInt(i) so no IF necessary :D

This is a bad idea, as now the selection of the cards is biased. Let's assume we have 52 cards. Before, in the first step, i.e., for i = 51, the call to rand.nextInt(i+1) would yield a uniform choice between all indizes from 0 to 51. Thus, each of the 52 cards has an equal chance of becoming the last card of the array. Of the remaining cards (indizes 0 to 50), each card again has a uniform choices for becoming the next-to-last card, etc.

Now, with the rand.nextInt(i), for i=51, you will only uniformly draw a value from 0 to 50. Thus, the last card will never be placed in the last slot. Likewise, afterwards, the card at index 50 will never be placed in that slot, etc.

In the i+1 version, you can simply drop the if, as swapping in the case of i == index does what it's supposed to do - nothing :)

Your old version is also equivalent to Collections.shuffle(), so I don't think the problem lies in the shuffling; if there is a problem it has to be due to the random number generator.
I'm quite puzzled by the observed behavior, as your initial approach (a new, reseeded Random for each game) makes sense. Likewise, the contract for Java's Random should ensure that it behaves exactly the same for a given seed value, no matter the platform.

However, I've also observed quite noticable clustering (aces and 2's in close proximity) in my Klondike games with Simple Solitaire. Now, the human mind is quite notorious for finding patterns in noise and being especially bad at estimating probabilities, so it might just be that.

Does it make sense to use SecureRandom instead? I'm not sure about the current behavior on Android devices. If I recall correctly, in the past there were some issues with potentially having to wait quite a bit for the random bit generation when the system's entropy buffer was low. Perhaps you can offer SecureRandom as the generator as a configuration option for testing?

[TobiasBielefeld]

oh thanks @kleinj for the explanation! you are right :) I changed it back. I also thought about SecureRandom, but I had the opinion it would be a waste of battery to use a cryptographically secure RNG :D but maybe it could change the behavior, I will test it a bit in the next days and add it for testing!

[pikoro]

Just as an update, I still see this all the time. After playing through one particular deal, I re dealt the same cards and took a screenshot just after each time I turned the stack over. See the following link. Multiple sets of non-random dealings can be shown. https://photos.app.goo.gl/P0aXYxwRgt5HOrd63

[TobiasBielefeld]

Sorry that it takes so long, currently I have to invest nearly all my time in the university, it's the last semester with lectures...

I was playing around with SecureRandom, but it shows no difference.

I also looked at another Solitaire app:
https://sourceforge.net/p/solitairecg/code/ci/master/tree/src/net/sourceforge/solitaire_cg/Deck.java#l54
It uses the same algo to shuffle, the only difference is, that it shuffles 3 times at once. I wanted to test that too.

But I also wanted to add a "Mix cards" options, to mix the current cards, expect cards played in correct sequence and cards on the foundation. Maybe this could help (temporarily)

Well one solution would be to forbid placing cards with the same value next to each other in the shuffle, but that wouldn't be really random anymore.

[pikoro]

I was going to try downloading a copy of the code and playing with it as well. Perhaps shuffling the deck a few times after the initial shuffle could mix things up a bit?

[TobiasBielefeld]

I tried that too, but no real difference :) I tested the "Avoid same value next to each other" approach and it works pretty good. I'll upload the changes when I am back home.

[kleinj]

I found some discussion about using random number generators for card shuffling here, which might be of interest. The gist is that the standard random number generators in Java don't use enough bits for the seed, so it's not possible for all 52! different permutations to occur.

However, it's not immediately clear to me if that's the cause of the observed behavior. I.e., it could be that, while not all possible shufflings can be obtained, those that occur are "good enough" for human enjoyment.

Nevertheless, it might be worth it to explore the proposed approach, i.e., obtaining a sufficient number of true random bits and then seeding that to the AES based random number generator.

Regarding the "avoid same value next to each other": I found (but haven't verified the correctness) this article showing that it is highly likely in a given shuffled deck that you can find "same value next to each other". So, I guess, such a fix is a tradeoff between how it feels to the player and "true" randomness.

To check the randomness, would it make sense to do an experiment as follows: Generate a large number of shuffled decks, consider them to be 52-character words over the alphabet (1, ..., 13), ignoring the suit. Then, look at the n-grams, i.e., the 2- or 3-character sequences that occur, count those (summing over the decks) and check that each occurs roughly at the expected frequency? From my intuition, I guess all n-grams should be equally likely, but that might be wrong...

[TobiasBielefeld]

@kleinj thanks again! The articles are very interesting. So it is "natural" that same cards are next to each other. But the cases described by @pikoro seem pretty extreme. I think too, that the seed length isn't really causing it. 2^64 with the default PRNG are already enough possibilities in my opinion. But I would increase that using the AESCounterRNG, if it doesn't affect the performance too much (It already freezes my Android 8 VM).

My avoiding approach should be good enough for the player, to feel more random :) If someone wants true randomness, I added a settings entry to switch it back.

And I will try your proposed testings later, thanks again!

@pikoro If you want to play around with the possible changes: I added a getPrng() method at the end of SharedData.java, where you could change the PRNG. Or you maybe want to change randomize() in GameLogic.java. My changes are in the testing branch :)

[TobiasBielefeld]

Soooo I finally tested that like @kleinj said, and the result is: Every time it is the same result, it doesn't matter if I change the shuffling algorithm or the PRNG. So I guess I will stay with the "avoid similar cards next to each other" method.

[TobiasBielefeld]

I released the new app version 3.10 with this change. If it's good enough to solve this issue, I would like to close it :)

[lxkurko]

So which option is now the most random? I think that properly random shuffling of cards is the most important feature in any solitaire game, and should be the default option.

[TobiasBielefeld]

You can enable the true randomization in the expert settings (enable the expert settings category in the general settings first). In my opinion this solution should be okay. Because there were also some people on Google Play, which thought that there were too many "bad deals". I also planned to make a "Intro screen" for the first run of the app, where settings like this one should be presented. I hope this can be a solution for everyone :)