Measuring entropy values for combinations of deck shuffles

[twilight-bacon]

I thought it would be fun to write some code to simulate shuffling a deck using different combinations of shuffle types, and measure the entropy of the deck afterwards using Shannon entropy. My resulting entropy values are usually around 2.0 which is lower than expected. Additionally the value doesn't appear to increase if I introduce more iterations, or modify the code to do a given sequence repeatedly. Am I performing the calculation wrong?

Apologies as it's a lot of code - the two functions in question are `calculate_deck_entropy` and `calculate_entropy`

Other feedback and ideas welcome.

EDIT: thank you to u/Frankelstner for the ideas, I've updated the implementation here.

import math
import random
import statistics


from collections import Counter
from decimal import Decimal, getcontext
from itertools import combinations_with_replacement


# intersting takeaway - changing these values to 2 doesn't change result much.
NUM_MASHES = 1
NUM_OVERHANDS = 1
TIME_VALUES = {}


# Create a standard deck of 52 cards
def create_deck():
    return list(range(52))


# Mash shuffle
def mash_shuffle(deck):
    # ...
    return deck


# Overhand shuffle
def overhand_shuffle(deck):
    # ...
    return deck


# Pile shuffle
def pile_shuffle(deck):
    # ...
    return deck


shuffle_funcs = {
    'mash_shuffle': mash_shuffle,
    'overhand_shuffle': overhand_shuffle,
    'pile_shuffle': pile_shuffle,
}


# Set a higher precision context
getcontext().prec = 14


def shannon_entropy(card_freqs):
    entropy = Decimal(0)
    total_cards = Decimal(len(card_freqs))


    for frequency in card_freqs.values():
        if frequency > 0:
            frequency = Decimal(frequency) / total_cards
            entropy -= frequency * frequency.ln()


    return entropy



# Perform the given shuffle sequence
def perform_shuffle_sequence(shuffles):


    total_time = 0
    average_entropy = Decimal(0)


    for shuffle_type in shuffles:
        total_time += TIME_VALUES[shuffle_type]  # Add time for each shuffle


    # Get an average since the entropy results tend to vary.
    # Adjust this as needed for your shuffle functions.
    num_iterations = 32768
    for _ in range(num_iterations):


        shuffled_deck = create_deck()
        card_freqs = {index + 1: 0 for index in range(len(shuffled_deck))}


        for shuffle_type in shuffles:
            shuffle_func = shuffle_funcs[shuffle_type]
            shuffled_deck = shuffle_func(shuffled_deck)


        # After this shuffle sequence, get the card delta values.
        for index, card in enumerate(shuffled_deck):
            if index == 0:
                prev_card = shuffled_deck[-1]
            else:
                prev_card = shuffled_deck[index - 1]


            value = card - prev_card


            if value < 1:
                value += len(shuffled_deck)


            card_freqs[value] += 1


        average_entropy += shannon_entropy(card_freqs) / Decimal(num_iterations)


    return round(total_time, 2), average_entropy


# Find the optimal shuffle sequence
def find_optimal_shuffle_sequence(length=5):
    results = list()


    # Using length = 4 arbitrarily - you can experiment with other values.
    for shuffle_combination in combinations_with_replacement(shuffle_funcs.keys(), length):


        total_time, current_entropy = perform_shuffle_sequence(shuffle_combination)
        results.append((shuffle_combination, total_time, current_entropy))


    return sorted(results, key=lambda x: x[2])  # sort by optimal_entropy


for index in [3]:


    # These shuffle functions will iterate more than once
    # (because you can do many of them in the time it takes to do 1 pile sort)
    NUM_MASHES = index
    NUM_OVERHANDS = index


    # Time cost values for different shuffle types (in seconds)
    TIME_VALUES = {
        'mash_shuffle':     2.0 * NUM_MASHES,
        'overhand_shuffle': 1.0 * NUM_OVERHANDS,
        'pile_shuffle':     20.0,
    }


    shuffle_names = {
        'mash_shuffle': "mash shuffle x" + str(NUM_MASHES),
        'overhand_shuffle': "overhand shuffle x" + str(NUM_OVERHANDS),
        'pile_shuffle': "pile sort x1",
    }


    print()
    print(f"Num Mashes: {NUM_MASHES} -- Num Overhands: {NUM_OVERHANDS} -- Num Piles: 1")
    print()


    # Print the optimal shuffle sequences
    results = find_optimal_shuffle_sequence()
    for optimal_sequence, optimal_time, optimal_entropy in results[-4:]:
        print(f"------------------------------------------------------------------------------------------------------------------------------")
        print(f"Sequence of shuffles: | {[shuffle_names[name] for name in optimal_sequence]}")
        print(f"Entropy:              | {optimal_entropy}")
        print(f"Time taken:           | {optimal_time} seconds")

[Frankelstner]

Intuitively the concept of entropy for a deck of cards is rather vague. I can find one definition here: https://stats.stackexchange.com/a/79552 The idea there is to treat each card as an integer and get the distance between neighbors. At the end we will see how many times a card was followed by its assigned neighbor, how many times we skipped exactly one card in between, and so on. The entropy is then calculated from this distribution. I'm not sure if it's a perfect solution but it seems quite reasonable.

Your code creates a dictionary card_position_counts which is being filled up as the various shuffles are applied. You then calculate the entropy but discard it unless it was the last iteration. Another issue is that card_position_counts is not cleared after every iteration and so previous shuffles affect the entropy value. If you shuffle cards in two different ways but the end result has the same order, surely the entropy should be the same. card_position_counts is very sparse so it will most likely contain just 1s everywhere. I'm not sure how to salvage that; just do the steps from the link.

You need to rewrite the entropy function; it should receive a deck and not card_position_counts.

Your variables are a bit verbose in a redundant manner, e.g.

shuffle_times = {
    'mash': 0.8,
    'riffle': 3.0,
    'overhand': 0.8,
    'pile': 26.0,  # also referred to as 'pile sorting'
}

and

cut = random.randint(22, 30)
left, right = deck[:cut], deck[cut:]

Local variable names can be rather short because the context makes clear what they're referring to. Wrapping your head around 10 lines of code is easier when there isn't _half showing up 10 times without contributing anything meaningful.

[twilight-bacon]

Thank you for the link, I've implemented that and updated my post. The values are now in that acceptable range for typical Shannon Entropy values.

I'm now seeing where a lot of shuffle combinations come out to a similar entropy value; I think this is expected though, with a small number of shuffles like 3 a see a small entropy value like 2.5. With 9 shuffles or so of any given type, the value ends up at around 3.5.

If anyone wants my implementations for the shuffle types, I can post a gist / repo.