Advertisement
nodthenbow

fight game solver alg proof

Mar 31st, 2021
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.63 KB | None | 0 0
  1. Solving a fighting game!!!
  2. This isn't going to be super rigorous, it's a "see, this probably exists because like it pretty much is definitely at least probably covered by this setup" proof.
  3. Not gonna prove or explain min-max or Nash equilibriums and what not, others have done that better than I can so go get those. Also not going to explain like, sub game equilibriums or how randomness works, or any other things that I use really. I'm not publishing this to a journal or anything, so if you want to use it for anything of note you'd need to add some rigor to it first.
  4. I'm not using normal symbols or terms because it's harder to read and write that way.
  5. This isn't proving that fighting games are solvable, it's proving an algorithm that solves fighting games. It's trivial to show that a fighting game is solvable.
  6.  
  7. 1) A strategy in some form is doing an act that include either involves preparing for something or doing something, or both.
  8. Peeps are able to prep their thinking and choose what to prep, there is a cost to prepping more actions in reactions, so faster reactions for less things the person want to react to. There is also a limit to how fast contexts can be switched, and how much that effects accuracy and what not. A bunch of stuff really, but essentially through measurable things people can choose to do and are able to do that impacts how much they can try to do at once. The other player can do the same, so by picking actions that beat the choices the other player picks means they could get some reward (unless it's a 10-0 or blah blah).
  9. That whole thinking thing I'll be calling an action, it will count for a dynamic amount of time between forced changes in the environment. For example, if both players are in a stare down then the window would be from once the stare down was realized to when something happens and the player realizes it. Nothing happening doesn't count as a new action even if the thinking set changes, same with how the reaction to new situations isn't synced between players. This is because if you counting the entirety of the waiting period as a sequence like "prepare for X for T time, then prepare for/do Y" and the real diff in timing is imperfect, but still complete information, so it's fine to treat that diff in time as part of the action. With both those considerations, even if the definition of action is wack it still represents the full set of human ability and choices (aka, the definition probs isn't useful in the real world, but it's good for the math parts because it covers the better real world fitting definitions).
  10. 2) Human error is being "ignored".
  11. Expected error rate, estimated error rate, and actual error rate are all bounded and measurable values, so dealing with it can fit into the actions definition. The reason this is brought up is that error means randomness in outcomes, and because they vary the actual error rate changes the rewards structure. That means calculating the NE relies on predicted values that are unknown. The solution to this is to add the meta estimations to the scope of the fighting game that is being solved, and include adjusted error estimations into the actions definition (the most abusable definition ever made).
  12. 3) Ties and rounds are not issues. Ties are assumed to be resolved in some way that determines the winner, so that's part of the game in this context. Rounds can be considered as a full fighting game as a subgame, or ignored completely in the math, so they actually don't matter for the math like they would for determining strategies. This means a game must have a point where it will end regardless of actions.
  13. 4) Assuming people can only think of and do a finite amount of things, then there is a finite amount of possible actions. Assuming games must end with a winner and loser after a finite amount of time, then there is a finite amount of game states and all possible paths lead to a winner and a loser.
  14. 5) Starting state can not be an end state, there must be at least one decision between those points (this action could be choosing to start playing or not for example).
  15. F) This probably is not going to solve any fighting game, and this isn't finding an exploitation strat so it wont max out EV in the real world. Don't get your hopes up, it's just a novel proof.
  16.  
  17. A fighting game has a boolean result, one player wins and the other loses. Say the player who wins gets 1 point and the player who loses gets -1, now it's a zero sum game, therefor it is solvable and has a NE, also min-max applies to it.
  18.  
  19. Given a complete set of action pairs S{A1,A2,...,An}, and a complete set of end states W{E1,E2,...,En} where Em has a value of (1,-1) or (-1,1), a set of action decisions F{D1,D2,...,Dn), and a list of all states where an action decision is made N{N1,N2,...,Nn) and each Nx is made of pairs of possible actions available at the time from S, then for every Em there exists at least one Am that leads to it, by (5).
  20. The set of actions possible when Am was possible will be called Sm, which has the subset of actions {Ai,Aj,...}, the pairs of actions possible there will be called Nm, as it is a member of N.
  21. (i) There exists an Nm where all pairs lead directly to some Em by (3), which has a NE defined by the payoffs that each Am in Nm leads to. The EV for any Sm that has one will be referred to as EVm, it will later be shown that all Sm have an EV.
  22. Side note: due to (2) it's not being covered, but the above still holds with error being considered. I just don't want to explain it. The error rate is at or between 0 and 1, and there are a finite amount of errors you can make, so it's still solvable with this method. It's just not worth explaining with how it's not making the proof wrong, but it is extremely hard to explain.
  23. There are two things the previous node can be, either Sm has a previous decision on the path that leads to it, so the node is a member of N, or the previous node is the start state.
  24. By induction, base case is the Sm described above, it has an EV.
  25. Next,
  26. Case 1, the node leading to Sm is the start state, therefor all N have an EV and the game is solved. (in all the other cases the node is a member of N)
  27. Case 2, the node leading to Sm is some Nm that leads to some subset of S where not all members of that subset have an EV. Due to (5) all paths forwards must lead to some Em, in which case there must exist some Sm with EVm for all leaf nodes that can be reached from Nm, by (i).
  28. Case 3, the node leading to Sm leads to only nodes with EVs, therefor the NE can be found by finding the value of each node that the node leading up to Sm (calling it Sp, because it is a member of S) leads to when it has a value (because it is an end state), or it has an EV to use as a value. The EV of Sp is then that EV
  29. Therefor all N have an EV, and the NE for each node has been defined, so you can find the NE for the start state.
  30. That means the fighting game has been solved! The optimal strategy is to pick an action with the rates defined by the NE of the node you are currently at. All you need to do now is figure out the set of actions a human can do, and then do a lot of calculations.
  31. Yes, I know once I set up fighting games as a zero sum game I showed that they were solvable. This is a proof for a solving algorithm okay?
  32. This is a novel proof that is useful because it shows that any greedy method to calculate part of the tree that does not lead to an end state must know the value/EV of all later nodes to get the correct answer. As far as I know that probably isn't possible, so doing that requires estimation.
  33. It also makes it easier (for me at least) to conceptualize a good heuristic and estimator for solving the game without exhaustive search with this existing.
  34. -nod
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement