5 ms·

For what is worth, heads-up is a very popular game, and from reading the paper, the approach should more or less be applicable to 6max or full ring, except it w

by Tenoke 10y ago

For what is worth, heads-up is a very popular game, and from reading the paper, the approach should more or less be applicable to 6max or full ring, except it will be way more computationally expensive (but not unfeasibly so like before).

jumpCastle 10y ago
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 only a computational issue. See http://www.nature.com/news/how-rival-bots-battled-their-way-to-poker-supremacy-1.21580 http://www.nature.com/news/how-rival-bots-battled-their-way-...
- 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
  - 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.

by Tenoke 10y ago

jumpCastle 10y ago

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 only a computational issue. See http://www.nature.com/news/how-rival-bots-battled-their-way-to-poker-supremacy-1.21580 http://www.nature.com/news/how-rival-bots-battled-their-way-...

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