# Optimizing a puzzle from the Balatro game: discarding part of a poker hand to get a pair
**URL:** https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912
**Category:** Performance
**Tags:** probability
**Created:** [October 29, 2024, 12:15pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912 "2024-10-29T12:15:08Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 29, 2024, 12:15pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/1 "2024-10-29T12:15:08Z")
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**
>
> ```julia
> 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
>
> ```
---
### Author:  [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)
#### Post date: [October 29, 2024, 1:35pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/2 "2024-10-29T13:35:58Z")
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.
```julia
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.
---
### Author:  [@mthelm85](https://discourse.julialang.org/u/mthelm85)
#### Post date: [October 29, 2024, 3:23pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/3 "2024-10-29T15:23:38Z")
Here’s my attempt at a very literal implementation (with horrible performance, no doubt):
```julia
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 😆
---
### Author:  [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)
#### Post date: [October 29, 2024, 3:59pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/4 "2024-10-29T15:59:13Z")
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
julia> mean([haspair(shuffle!([pop!(ordered_deck(), 44)...])[1:8]) for _ in 1:1000000])
0.880048
```
---
### Author:  [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)
#### Post date: [October 29, 2024, 4:10pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/5 "2024-10-29T16:10:48Z")
Ah,
> [@mthelm85](#):
>
> `discards = rand(hand, n)`
You must discard `n` _distinct_ cards.
---
### Author:  [@mthelm85](https://discourse.julialang.org/u/mthelm85)
#### Post date: [October 29, 2024, 4:22pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/6 "2024-10-29T16:22:02Z")
> [@GunnarFarneback](#):
>
> You must discard `n` _distinct_ cards.
Good catch! In this version, I call `sample` from StatsBase.jl instead:
```julia
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!
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [October 29, 2024, 5:12pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/7 "2024-10-29T17:12:47Z")
definitely something to compute exactly:
```julia
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)`:
```julia
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.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 29, 2024, 8:03pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/9 "2024-10-29T20:03:49Z")
Sorry n=5 is the maximum u can discard
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 29, 2024, 8:11pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/10 "2024-10-29T20:11:26Z")
U r right. I think the code needs a bug fix
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 29, 2024, 8:43pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/13 "2024-10-29T20:43:22Z")
> [@mthelm85](#):
>
> `setdiff(hand, hand[discards])`
without loss of generality you can always assume that `1:discard` are the discards
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 29, 2024, 8:45pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/14 "2024-10-29T20:45:22Z")
> [@foobar\_lv2](#):
>
> `4^jbar * bigbin(5, jbar) * 3^j * bigbin(d, j)`
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?
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [October 29, 2024, 10:19pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/15 "2024-10-29T22:19:57Z")
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.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 29, 2024, 10:29pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/16 "2024-10-29T22:29:43Z")
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.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 29, 2024, 10:33pm UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/17 "2024-10-29T22:33:29Z")
> [@foobar\_lv2](#):
>
> 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.
this part already lost me. sorry i am dumb despite an honours degree in maths
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [October 30, 2024, 12:55am UTC](https://discourse.julialang.org/t/optimizing-a-puzzle-from-the-balatro-game-discarding-part-of-a-poker-hand-to-get-a-pair/121912/18 "2024-10-30T00:55:22Z")
> [@xiaodai](#):
>
> this part already lost me
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`.