Using a Monte Carlo simulation to get Infinite in Marvel Snap
Who says math aren't applicable in real life?
Command Palette
Search for a command to run...
Comments
Join the discussionNo comments yet. Be the first to comment.
Search for a command to run...
Who says math aren't applicable in real life?
No comments yet. Be the first to comment.
In this article, I'll walk you through how I used a Monte Carlo simulation to make card choices and gain ranks in Marvel Snap's last ranked season.
Marvel Snap is a card game in which each player has a deck of 12 unique cards. They draw 3 of them at the start of the game and then draw 1 at the start of turns 1 through 6 when the game ends.
What immediately jumps out in this format is that decks are incredibly consistent. You will draw the majority of your deck every game, so elaborate combos are easy to pull off.
Let's do some quick math to demonstrate just how consistent:
...just kidding, we are programmers, and when you have a hammer, everything is a nail.
To start, let's use a Monte Carlo simulation to derive some basic draw chances in this game.
We will start with a sample deck of 12 cards. Then for a large number of iterations, in which the deck is shuffled, we will simulate a game and note the turn by which cards are drawn.
There are performant ways to write this simulation. If you are using java you probably don't even want to work with boxed types (please save us Valhalla!), but we are just going to ignore all that and truck along!
In the following code samples, I'm using Integer.MIN_VALUE as the sentinel value when the target cards are not found in a game.
final Map<Integer, Long> turnFoundCount =
IntStream.range(0, simulationLimit)
.parallel()
.map(dc -> returnTurnFound(game, targetCardsCollection, sampleDeck))
.filter(i -> i != Integer.MIN_VALUE)
.boxed()
.collect(Collectors.groupingBy(i -> i, Collectors.counting()));
It's easier to accumulate the percentages of earlier rounds since what we care about is the chance of having a card 'by turn X' instead of the individual draw chances per turn.
turnFoundCount.entrySet().stream()
.filter(e -> e.getKey() != Integer.MIN_VALUE)
.reduce(Map.entry(0, 0L), (partial, element) -> {
final Map.Entry<Integer, Long> result =
Map.entry(element.getKey(),
partial.getValue() + element.getValue());
log.info("Draw by turn {}, Percentage: {}", result.getKey(), result.getValue() * 100.0 / simulationLimit);
return result;
});
I swapped the seek function in returnTurnFound to simulate either seeking 'all of a group of cards being drawn by turn X' or 'any of a group of cards being drawn by turn X'. Again we could have made this generic but... oh well :)
private static int returnTurnFound(final Game game, final List<Card> targetCombination, final List<Card> deck) {
final List<Card> tempDeck = getShuffledDeckCopy(deck);
final Set<Card> hand = new HashSet<>();
int turnFound = Integer.MIN_VALUE;
//Draw initial hand
for (int i = 0; i < game.getInitialCards(); i++) {
drawCard(tempDeck, hand);
}
//Simulate a turn from the prespective of a player
for (int turn = 1; turn <= game.getNumberOfTurns() && turnFound == Integer.MIN_VALUE; turn++) {
for (int i = 0; i < game.getDrawsPerTurn(); i++) {
drawCard(tempDeck, hand);
}
turnFound = seekCombination(hand, targetCombination, turn);
// turnFound = seekAlternatives(hand, targetCombination, turn);
}
return turnFound;
}
The following draw chances are floored (not rounded) to two decimals since my past self just printed them without rounding them properly.
For any 1 card, chance to have drawn it by turn:
1 | 33.34% |
2 | 41.67% |
3 | 50.02% |
4 | 58.35% |
5 | 66.68% |
6 | 75.03% |
For any 2 cards, chance to have drawn them together by turn:
1 | 9.10% |
2 | 15.16% |
3 | 22.75% |
4 | 31.83% |
5 | 42.43% |
6 | 54.54% |
For any 3 cards, chance to have drawn them together by turn:
1 | 1.82% |
2 | 4.55% |
3 | 9.10% |
4 | 15.92% |
5 | 25.45% |
6 | 38.17% |
For any 2 cards, chance to have drawn either of them by turn:
1 | 57.60% |
2 | 68.19% |
3 | 77.28% |
4 | 84.84% |
5 | 90.91% |
6 | 95.45% |
For any 3 cards, chance to have drawn one of them by turn:
1 | 74.54% |
2 | 84.09% |
3 | 90.91% |
4 | 95.45% |
5 | 98.18% |
6 | 99.54% |
Being incredibly lucky and having opened Shuri, I initially constructed the deck above thinking that a greedy combo deck with her should be very powerful.
Shuri works with Black Panther and Red Skull to dump a ton of stats in a lane, and then any of Taskmaster, Arnim Zola, and Leader should ensure that I'm ahead in a second lane as well, winning out 2/3 lanes in the game.
Wong is there for redundancy, as he works the same way with Black Panther.
Yellowjacket and Adam Warlock, if drawn together at the start, give us extra draws to make the rest of the deck more consistent.
Now some of those ideas ended up working better than others. The late-game combo is indeed incredibly consistent. Looking at the stats above we can see that by turn 4 we have an 84.84% chance to have drawn either Shuri or Wong*.*
Of course, Wong only works with one of our 5 drops. We will need some more analysis to find out the likelihood of the deck going off as a whole.
Finally, as it turns out, there is only a 15.16% chance to have drawn both Adam Warlock, and Yellowjacket by turn 2, and empirical data suggests that there are a lot of cases where the opponent will randomly play in a way to turn off the extra draws, so is this combination even doing anything?
By modifying the above code I sought the percentage of times when any of the full combos would go off if uninterrupted.
Shuri -> Black Panther/Red Skull -> Taskmaster/Arnim Zola/Leader
Wong -> Black Panther -> Taskmaster/Arnim Zola/Leader
Without the Adam Warlock combo, there is a 69.58% chance that this deck will produce one of the above complete combos by turn 6.
I assigned a 66% chance to the Adam Warlock / Yellowjacket combo to draw a card if I have it in hand on turn 2, and a 33% of drawing another card on turn 3.
With these changes, the overall chance of the deck producing one of the above complete combos only goes up to 72.27%. As we saw before, it is rare having both of those cards in hand by turn 2, and the combo is consistent already, so it is probably not worth sacrificing the early game to boost the chance by so little.
After running this analysis and playing with the deck for a week I ended up cutting Adam Warlock and Yellowjacket for Scorpion and Storm. Storm feels good since we draw Zola by turn 6 75% of the time and for the times we don't the deck only plays for 2/3 of locations anyway.
To rank up in Marvel Snap, you need to retreat a large percentage of your games, since the titular Snap mechanic makes retreats cheap and loses on turn 6 after the stakes are raised, expensive.
Knowing that I'll only have an explosive finish 69.58% of the time, helped me make better decisions on how to snap and retreat, and get to infinite for the first time last season.
I'm still not sure about Scorpion, but this experience has given me better tools to think about spot counting when building a deck!