4 ms·

In my understanding the approach is based on game theoretic principles that do not extend naturally to more than two players. If that's correct then it's not on

• peternilson 10y ago
  Yip, exactly this. The CFR algorithm they speak of is based on finding a nash equilibrium for each strategy-pair in the game tree. Something that I think can only be computed for 2 players, and no more.
  • Tenoke 10y ago
    Surely you can adapt it to compute an approximation of a mixed Nash equilibria. My game theory isnt at a high level, but there are similar computations you can perform, and when I used to play poker, you'd have common calculations based on it for more than 2 players when you are playing with a limited stack. I dont see how that wouldnt be adaptable (abeit more computationally expensive) for more players, but I might be missing something.
    • jumpCastle 10y ago
      I'm not sure Nash equilibrium exists for more than two players in this game.
      • mikebjohanson 10y ago
        Nash equilibria are still guaranteed to exist. But it's only the 2p zero-sum perfect recall case where an equilibrium has useful properties, like being robust against any opponent strategy, including a worst-case opponent who knows your strategy. In a multiplayer (> 2 players) game, opponents can collude against you and playing your part of a Nash gives no useful guarantees on performance. Even if they aren't colluding, in poker games, the presence of a bad player just before you in turn order can hurt your EV worse than their own. And even if all players independently compute their own Nash equilibria (there can be many) and use the piece for their position, then that combination of strategies may not itself be a Nash equilibria.
        • jumpCastle 10y ago
          Thanks for the explanation. I will also appreciate a reference to a good survey paper if you are in the mood :)
          • mikebjohanson 10y ago
            I don't know of a survey paper on CFR for multiplayer, but it's been showing up in conference papers and theses. Here's a link to a shorter conference paper where CFR does converge to a Nash, in 3p Kuhn poker. It describes a family of equilibria, where one player (the second to act, IIRC) has a parameter that can't affect their own EV (...or else it wouldn't be a Nash), but does determine how much the other two players win/lose from each other. This illustrates the problem in equilibria for multiplayer games: if you're players 1 or 3, then even if you are playing a Nash, and everyone else does too (albeit different equilibria), then you can still lose. https://webdocs.cs.ualberta.ca/~games/poker/publications/AAMAS13-3pkuhn.pdf https://webdocs.cs.ualberta.ca/~games/poker/publications/AAM... For a longer read, the best I know of is probably Rich Gibson's PhD thesis. He focussed on CFR for multiplayer games. https://webdocs.cs.ualberta.ca/~games/poker/publications/gibson.phd.pdf https://webdocs.cs.ualberta.ca/~games/poker/publications/gib...
            • jumpCastle 10y ago
              Thanks again. So I guess for multiplayer games a better approach would be reinforcement learning with no game theoretic heuristics?
              • xapata 10y ago
                Game theory is always applicable to games :-) Nash equilibrium is just one aspect of some games.
                • jumpCastle 10y ago
                  Game theory is domain specific. Generic methods in AI tend to dominate domain knowledge over time. Although I agree that other game-theoretic techniques might help here.
  • mikebjohanson 10y ago
    There has been quite a bit of work (and several papers) on using CFR for games with >2 players. It is not theoretically guaranteed to converge to a Nash, and usually doesn't in practice either (there's one case in a toy game, in 3p Kuhn poker, where it does converge). However, even though it doesn't converge to Nash, the algorithm is still well defined, and the resulting strategies appear strong in competitions against other computer adversaries, as demonstrated in the Annual Computer Poker Competition.