Optimizing a puzzle from the Balatro game: discarding part of a poker hand to get a pair

General Usage Performance
1

Interesting problem from Balatro, from a hand of 8 without any pairs, if you discard n and draw n from the remaining deck of 44 cards. What’s the optimum n to maximize your chance of obtaining at least a pair?

I am sure many of you are obsessed by Balatro. So I wrote some code to simulate this. For 1m simulations it ran in about 0.077s per n.

Anyone wanna challenge my algorithm?

Edit: maximum n is 5

Edit: bug fix

Summary 
const WEIGHTS = vcat(fill(3, 5), fill(4, 8))

function init_draw(discard)
    # draw is the initial hand
    WEIGHTS .= 4

    @inbounds for i in 1:8
        WEIGHTS[i] = 3
    end

    # for 1 to 8 there are 3 cards left
    # for 9 to 13 there are 4 cards left
    # if any of the first 3 cars is selected then done
    l = 52 - 8
    for i in 1:discard
        # if it's one of the non-discarded cards
        j = rand(1:l)
        j <= 3*(8-discard) ? (return true) : (l -= 1)

        # so it's not one of the non-discarded cards
        # how many cards to skip
        k = j - 3 * (8 - discard)

        k1 = 8 - discard + 1
        @inbounds while k > 0
            k = k - WEIGHTS[k1]
            k1 = k1 + 1
        end

        k1 = k1 - 1

        @inbounds if k1 <= 8
            WEIGHTS[k1]==2 ? (return true) : (WEIGHTS[k1] -= 1)
        else
            WEIGHTS[k1]==3 ? (return true) : (WEIGHTS[k1] -= 1)
        end
    end
    return false
end

@code_warntype init_draw(5)

@time x5 = [init_draw(5) for _ in 1:1_000_000]; # 0.77586
@time x4 = [init_draw(4) for _ in 1:1_000_000];
@time x3 = [init_draw(3) for _ in 1:1_000_000];
@time x2 = [init_draw(2) for _ in 1:1_000_000];
@time x1 = [init_draw(1) for _ in 1:1_000_000];

sum(x5)/1_000_000
sum(x4)/1_000_000
sum(x3)/1_000_000
sum(x2)/1_000_000
sum(x1)/1_000_000
2 Likes
2

To me this looks more like a compute it exactly than simulate it kind of problem. But if I were to simulate it I would focus more on correctness than speed and do it by first principles.

using Random
function simulate(i, n)
    deck = mod1.(9:52, 13)
    successes = 0
    for k in 1:n
        shuffle!(deck)
        new_hand = vcat((i + 1):8, deck[1:i])
        successes += length(unique(new_hand)) < 8
    end
    return successes / n
end

This gives results not matching your function, so at least one of us computes it wrong. I don’t understand your code but I vaguely suspect that you maybe doesn’t take into account the possibility of getting (at least) a pair from the newly drawn cards alone.

2 Likes
3

Here’s my attempt at a very literal implementation (with horrible performance, no doubt):

using PlayingCards
using Random
using Statistics

haspair(hand) = length(unique(rank.(hand))) < 8

function setup()
	deck = shuffle!(ordered_deck())
	hand = pop!(deck, 8)
	
	while haspair(hand)
		deck = shuffle!(ordered_deck())
		hand = pop!(deck, 8)
	end
	
	return (; deck, hand)
end

function simulate(n)
	initial = setup()
	deck = initial.deck
	hand = initial.hand
	discards = rand(hand, n)
	new_hand = vcat(setdiff(hand, discards), pop!(deck, n)...)
	haspair(new_hand)
end

results = [mean([simulate(n) for _ in 1:100_000]) for n in 1:8]

# 0.47485
# 0.63741
# 0.6603
# 0.63925
# 0.58515
# 0.51174
# 0.4187
# 0.32071

So this implementation indicates that n = 3 is the optimal choice. Since the three of us each arrived at different conclusions, I would first figure out how to do it correctly, and then optimize :laughing:

4

I don’t immediately see any error in your implementation but 0.32 for discarding all cards and drawing 8 new ones is unreasonably low.

If we take out the 44 first cards of the ordered deck there’s no pair in the 8 leftover ones and then draw 8 random cards, we get a pair or more with probabability around

julia> mean([haspair(shuffle!([pop!(ordered_deck(), 44)...])[1:8]) for _ in 1:1000000])
0.880048
1 Like
5

Ah,

You must discard n distinct cards.

2 Likes
6

Good catch! In this version, I call sample from StatsBase.jl instead:

function simulate(n)
	initial = setup()
	deck = initial.deck
	hand = initial.hand
	discards = sample(1:8, n; replace=false)
	new_hand = vcat(setdiff(hand, hand[discards]), pop!(deck, n)...)
	haspair(new_hand)
end


# 0.477303
# 0.693983
# 0.80054
# 0.85373
# 0.88054
# 0.892853
# 0.892063
# 0.879777

So this version indicates n=6 is optimal, but n=7 is almost just as good, which matches your results!

7

definitely something to compute exactly:

julia> bigbin(n,k)=binomial(BigInt(n), BigInt(k))
julia> function prob(d)
       numfails = BigInt(0)
       for j=0:d
       jbar = d - j
       numfails += 4^jbar * bigbin(5, jbar) * 3^j * bigbin(d, j)
       end
        Float64(1 - numfails/bigbin(44, d))
       end
julia> [prob(i) for i=1:8]
8-element Vector{Float64}:
 0.4772727272727273
 0.6945031712473573
 0.8001359106010268
 0.8538426972913643
 0.8808784097354716
 0.8921780148382531
 0.8920093512183849
 0.880736355614703

PS. If you want exact results, return 1 - numfails//bigbin(44, d):

8-element Vector{Rational{BigInt}}:
        21//44
       657//946
     10597//13244
    115910//135751
    136663//155144
   6297931//7059052
  34182305//38320568
 156095218//177232627

Somewhat surprisingly, the denominators don’t blow up in our face.

7 Likes
9

Sorry n=5 is the maximum u can discard

10

U r right. I think the code needs a bug fix

13

without loss of generality you can always assume that 1:discard are the discards

14

does this take into account the number of cards drops after you’ve drawn them? like Say if you draw card 9 as your first draw then the number of 9’s drops to 3 so you can’t assume that the probability of drawing 9 is still 4/44 in your 2nd draw, infact it should be 3/43 etc.

Edit: oh I think it does. I see. Very clever but something still not clear. For the discarded. There are now only 3 in the deck so u need to draw 2/3 to make a pair. I don’t see how that’s accounted for here?

15

I hoped that I wrote the summation to be self-documenting if you read binomial(n,k) = number of ways to choose k elements out of n, without replacement, and n =binomial(n, 1) = number of ways to choose one out of n elements.

So let’s explain in words! We are discarding and re-drawing d cards. There are 44 cards left in the deck, so we will divide something by binomial(44, d).

We count the failure probability instead of the success probability, so our result will be 1 - numFail // binomial(44,d).

For failures, we count separately depending on j, the number how many of our d redrawn cards come out of the pool of already seen cards (the ones with 3 remaining partners in the deck, pre-redraw). These are the cases where we possibly regret having discarded the ace-of-spades for a re-drawn ace-of-hearts.

Since we only count failures, there are binomial(d, j) many possibilities when disregarding color (hearts, spades, etc); since we disregarded color, there are 3^j*binomial(d,j) possibilities.

Next we need to take into account the number of ways we can re-draw into a failure on the remaining hitherto unseen card values. There are jbar = d-j such cards; correcting for color gives a factor of 4^jbar. There are 13 possible card values; our opening hand represented 8 distinct values, so there are 5 unseen ones in the deck, making for binomial(5, jbar) many possibilities.

Multiplying up all the choices, and then summing over j gives the result.

You may also ask “why count failures instead successes”.

To understand the reason, consider the simpler question “draw 8 cards out of 52; what’s your chance of seeing a card value double?”. Well, all failures look the same: 8 distinct card values, giving binomial(13,8)*4^8 // binomial(52, 8). But successes are more varied! You have to count the possibility of single-pair, double-pair, triples, etc separately because the symmetry group (sym(13) x sym(4)^13) acts differently on them!

Counting under symmetry should be explained in any intro-to-combinatorics course (should also be implicitly covered in most statistical physics courses). If you like that kind of problem and also like a well-founded toolbox, consider taking a look (too long ago for me to explain the solution in formal terms, I forgot the fancy terminology. Something something stabiliziers under the group action?)

The advantage of having studied that kind of thing is that it’s not “clever” anymore, it’s rote use of standard techniques.

1 Like
16

Let me digest. I have studied discrete math and combinatorics too but each counting problem is an expression of art so still takes explaining for dumb dumb like me.

17

this part already lost me. sorry i am dumb despite an honours degree in maths

18

We are trying to count how many out of the binomial(44, d) possible redraws lead to a failure, i.e. no pair in the final hand.

Suppose that we have such a failure, and suppose that 0 <= j <= d many of our redraws have card values that equal one of the discarded card values. Then jbar = d-j many of our redraws have a card value that has not been seen before.

There are binomial(d, j) many possibilities for the j card values that are the same as one of the d discarded card values. Each one can be one of 3 colors (because one of the colors was already discarded!), hence a factor of 3^j.

For the other jbar = d-j card values, they must come out of the pool of 5 completely unseen card values, hence binomial(5, jbar). Each can be one of all four colors, hence a factor of 4^jbar.

1 Like