I think the conclusion is aligned with tournament player intuition as reflected in the official character tier lists.[1]
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.
> Finding the optimal strategy is at some level similar to picking the optimal order of the N players on each team, which immediately sets off travelling salesman alarm bells in my head.
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. :)
Searching the optimal ordering has at most N! * N! solutions, right?
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.
You can actually do better than O((N!)^2), you can get it in O(n^24^n) because you can reduce the state to finding the next best single player to send in given the unordered set of unused players.
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.
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.
Oh shit I read that as n^{24^n} I was like what are these kids smoking nowadays.
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.
The formatting along this entire thread is so bad due to accidental asterisk-induced italics that I cant follow much of it at all. It would help posters to learn that you can force a * without any risk of italics if you put a backslash in front of the asterisk to escape it.
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*
The authors would like to thank the reviewer for their insightful comments, while the edit window has passed for this particular thread, future work will make use of this trick.
Seems like a lot of fancy math or simulation to justify a conclusion, but that math might not fit the real world situation at all. I feel like I've seen a lot of variations on this theme on HN and it tends to be a pet peeve of mine- maybe showing a ton of math might your result seem more authentic, but I see no evidence that it would be if there's no data to justify the fit of the math.
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 feel like stock counts haven't really been considered in this modeling which is fairly non-trivial as each outcome isn't as binary as rock-paper-scissors. There's an argument to be made that if Zain is locked in and you have both Aklo and Cody on your bench, you should send Aklo in first even if he might not win outright, because if he takes a stock or 2, then it gives better odds that Cody can win with 3 or 4 stocks remaining and sweep the rest of the team.
The issue is that even in the case of RPS-game you should use 3 events model: A-win, draw, B-win. This implies optimization over matrix with 2 component vectors. You can reduce the problem with some measure over this vector, for e.g. favoring wins if you have a strong team, or draws otherwise. But then it's unclear, what is the best measure for your exact case, turning optimization problem into measure study problem.
Very separate question but I've always wondered if there has been any mathematical formalism built up around the structure of tournaments. For instance, can we model how valuable a first-round bye is in a knockout tournament? How valuable is giving an extra game win in a winner bracket / loser bracket tournament to the WB player in the grand final? That kind of thing.
"We picked this model for skill, which is used because it has some nice properties where you can treat a group of opponents as many games against a single opponent with their average rating, and then... [complicated simulation...]amazingly... it turns out the order you face the opponents in doesn't matter!"
I think the missing piece from the analysis is whether this model is actually a good fit for SSB matchups.
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...