[HN Gopher] Solving Crew Battle Strategy with Math
___________________________________________________________________
Solving Crew Battle Strategy with Math
Author : alexmolas
Score : 43 points
Date : 2024-03-25 17:12 UTC (5 hours ago)
(HTM) web link (www.alexirpan.com)
(TXT) w3m dump (www.alexirpan.com)
| k2enemy wrote:
| I'm not familiar with Smash, but it seems like the author might
| enjoy reading about the Blotto game:
| https://link.springer.com/article/10.1007/s00199-005-0071-5
| kibwen wrote:
| _> 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. :)
| dmoy wrote:
| Ah this is Super Smash crew battle. Not BOTY (breakdancing)
| crew battle. Which makes a whole lot more sense.
| jvanderbot wrote:
| 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.
| alexirpan wrote:
| 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
| ;)
| jvanderbot wrote:
| > O(n^24^n)
|
| 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.
| alexirpan wrote:
| It's not a typo - specifically the time complexity is
| O(n^2 _2^n_ 2^n) = O(n^24^n). This is faster than your
| O(N! _N!) proposal.
|
| https://www.wolframalpha.com/input?i=plot+%28n%21%29%5E2+
| vs+...
|
| To be more specific - you get to O(n^2_2^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.
| jvanderbot wrote:
| 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.
| Someone wrote:
| > Oh shit I read that as n^{24^n} I was like what are
| these kids smoking nowadays
|
| That is the standard interpretation of _x^y^z_.
| Interpreting it as (x^y)^z
|
| doesn't make sense as that is equal to the simpler and
| shorter x^(yz)
|
| (https://math.stackexchange.com/a/1633800)
| jvanderbot wrote:
| Well, he was saying n^24^n = (n^2)(4^n) which makes sense
| when rendered in latex, but not here. Clearly, I saw
| n^(24^n)
| dmurray wrote:
| "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.
| alexmolas wrote:
| maybe it's better to use a standard Elo system?
| blueblimp wrote:
| The Bradley-Terry model is essentially the same thing as Elo.
|
| 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.
| loganfrederick wrote:
| 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.
|
| [1]: https://luminosity.gg/news/smash-ultimates-2nd-official-
| tier...
| based_basis wrote:
| 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.
| lofatdairy wrote:
| 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.
| tz18 wrote:
| >For the sake of simplicity, I will ignore that Smash games
| have stocks, and assume each match is a total win or loss.
| cool_dude85 wrote:
| 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.
| naet wrote:
| 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.
___________________________________________________________________
(page generated 2024-03-25 23:00 UTC)