Solving Crew Battle Strategy with Math
alexirpan.com
alexirpan.com
The conclusion is: "Assuming this conjecture is true, I believe it means you should entirely ignore player strength when picking players, and should only focus on factors that aren’t tied to skill, like character matchups."
I say intuitively because for decades now Smash players have been making tier lists, with "official" ones selected by the world's best players. And the point of the tier list is that "assuming players are as good as humanly possible, which in-game characters are generally superior to others as dictated by the game's implementation."
And the essay does point out the importance of character matchups, though Smash tournament players will often consider that when playing multiple matches against opponents as well.
[1]: https://luminosity.gg/news/smash-ultimates-2nd-official-tier...
At the risk of spoiling the author's fun, note that crew battles never have more than 6 players per team, and a 12-city traveling salesman is well in the realm of brute-forceability. :)
N! for my ordering
N! for their ordering.
So you just need to brute force 720*720 lookups and evaluate "goodness" (expected payoff using the matchup matrix). Then look at the row (my ordering) that provides the best overall expected payoff given any column (their ordering). Easy. SIMD to the rescue. Then play that ordering. Just don't listen to John Nash rolling in his grave.
The TSP "alarm bells" are not really correct in this case. We're not trying to follow transitions (changes in who's playing what) to minimize cost. It's more like finding a nash equialibrium, where the two teams are choosing their deployment ordering (as posed in TFA), and that's it. If you don't know their ordering, you have to solve the really hard problem of finding that nash equialibrium, and that's where the computational problems come from.
---
To make it more realistic, say you want to adapt your next choice based on who's in the ring and who is left on your team. To do that, look at who is in the ring, and choose the ordering of the remaining players that maximizes the payoff as above. So you have to do a factor N more of these lookups. That will explode quick. But for 6 players, it's doable.
TFA also assumes that _winning_ has no cost which must certainly be wrong. You want a clean-up player in there somewhere. Above adaptive strategy would handle that.
Source: the part of the post literally a few paragraphs down from the quoted section, where I describe how to do this, acknowledge this is fast enough to brute force for real crew battles that run with small N, and then write code to do so ;)
is this a typo? That's enormous. Way bigger than factorial.
Let's assume it's a typo.
OK if I understand that correctly, that reduces the computational complexity at the expense of not looking forward far enough to preserve any optimal guarantees. Don't you want to keep in mind the future possibilities?
for example:
Suppose A beats C soundly (80%), and loses to D half the time.
Then suppose B has a 60% chance to beat anyone.
You just lost, and other team has C up, with D, D, D on deck. You have A, B, remaining.
Your maximize your one-step chance against C by playing A, but then have .5x.5x.5 chance of winning against remainig. Total odds: .8x.5x.5x.5 = .1.
Had you played B, you'd have .6x.6x.6x.6 = .12 at best (A does worse if B loses)
That's just something I dreamed up right now. The worst case could be much worse.
It's fair to say a nice POMDP solution is in order here, as that would probably solve the "realest" case.
https://www.wolframalpha.com/input?i=plot+%28n%21%29%5E2+vs+...
To be more specific - you get to O(n^22^n*2^n) by doing dynamic programming, which lets you avoid recomputing extra work for considering future ordering possibilities. This approach still implicitly considers all possible future orderings and acts optimally with respect to that.
You can read the original post for more details - at a high level you are building a cache of win probabilities assuming optimal play, starting from the base case of 1-player crew battles, and extending it by 1 match per step of the recursion until you get back to the top-level problem. It is sufficient to only do computation 1 step ahead if you have a cache for how to act optimally for all n future steps.
Yes dynamic programming is indeed faster than brute force and I think I can convince myself this is the same approach with a little thought.
I think everything we said here was correct (yes both of us) but I was responding to an incorrect understanding of your strategy (you aren't doing one step ahead you are indeed calculating total expectations).
The brute force was just to show that the overall problem size was small when n is 6, in spirit of the original comment, and that brute force was just fine.
That is the standard interpretation of x^y^z. Interpreting it as
(x^y)^z
x^(yz)
You can also put four spaces in front of the line to automatically escape all formatting characters.
*this has four spaces in front of it and no escape characters*For one thing, the factor noted as "ignored for the sake of simplicity" where a player can carry his un-lost lives into the next round (and the opponent gets a chance to proactively choose who to go up next) seems to me like the far and away #1 most important factor in why order would matter or what the best possible order would be. If you have a lop-sided player who doesn't perform very well, but does really well in one specific matchup, you should probably try to save that player for when you can send them into that matchup.
Without any of that that, in a series of perfectly randomized one off matches in a perfect mathematical frictionless vacuum, order might not matter... but that just isn't what a crew battle is.
I think the missing piece from the analysis is whether this model is actually a good fit for SSB matchups.
https://lmsys.org/blog/2023-12-07-leaderboard/
> This model actually is the maximum likelihood (MLE) estimate of the underlying Elo model assuming a fixed but unknown pairwise win-rate.