4 ms·

> 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 salesm

by kibwen 3y ago

> 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 3y ago
Ah this is Super Smash crew battle. Not BOTY (breakdancing) crew battle. Which makes a whole lot more sense.
jvanderbot 3y ago
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 3y ago
  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 3y ago
    > 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 3y ago
      It's not a typo - specifically the time complexity is O(n^22^n2^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+n%5E2+*+2%5En+*+2%5En+for+n+%3D+1+to+30 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.

by kibwen 3y ago

dmoy 3y ago

Ah this is Super Smash crew battle. Not BOTY (breakdancing) crew battle. Which makes a whole lot more sense.

jvanderbot 3y ago

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 3y ago
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 3y ago
  > 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 3y ago
    It's not a typo - specifically the time complexity is O(n^22^n2^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+n%5E2+*+2%5En+*+2%5En+for+n+%3D+1+to+30 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.