7 ms·

Andrew Ng posted a comment about this on facebook: "I'm thrilled about Libratus' Poker triumph--this is a huge step for AI. Othello/Checkers/Chess/Go were theor

Andrew Ng posted a comment about this on facebook: "I'm thrilled about Libratus' Poker triumph--this is a huge step for AI. Othello/Checkers/Chess/Go were theoretically solvable with minimax tree search and sheer computation; but poker, which requires bluffing, needs sophisticated modeling of your opponents and new algorithmic principles. CMU's Tuomas Sandholm has also (in a private email) promised to publish their algorithms, which I look forward to. Congrats CMU!!!" https://www.facebook.com/andrew.ng.96/posts/1260889373966967 https://www.facebook.com/andrew.ng.96/posts/1260889373966967

andrewprock 10y ago
I'm surprised that Andrew Ng made this claim. The strategy that was built for Libratus' predecessor did not do sophisticated modeling of the opponents, or use new algorithmic principles. Poker is solved using a very large game tree, just as with the other games. The structure of the tree is modified to support the notion of hidden state, but beyond that it is essentially the same as the other games. The structure for representing hidden nodes was developed in the 1950s by Von Neumann. Most of the algorithmic innovations related to how to update the game tree. My guess is that the primary innovation for the Libratus strategy was that of scale.
- leeleelee 10y ago
  This was my thought too. Poker is quite "solvable" meaning, whenever you're confronted with a decisions -- there is always a "correct" answer which does not have to depend on the other players' behavior or style. And you can find that answer by simulation, or game trees, and other methods. It's also important to keep in mind that the best AI can still lose, and the worst AI can still win (and everything in between). Poker involves randomness, obviously whereas chess/go/etc does not.
  - mormegil 10y ago
    That depends on what you mean by "correct". Sure, you could theoretically find Nash equilibrium of poker and by playing the equilibrium strategy, you can ensure you won't lose. But that does not mean this is the best strategy to use at a given table against the given opponents, who (being imperfect humans) almost certainly do not play the equilibrium strategy themselves. And, by playing a proper nonequilibrium strategy, suited to the specific players, you can win more.
    - andrewprock 10y ago
      The usual way these games are solved is to create an "abstract" game which is tractable, find the Nash equilibrium, and map state in the real game back to the "abstract" game. In the limit, the solutions for a well designed "abstract" game will converge to that of the real game.
      - mormegil 10y ago
        You are explaining how current algorithms try to find the (approximate) Nash equilibrium (and those algorithms are far from perfect; as noted in the recent DeepStack paper, current abstraction-based programs are beatable by over 3000 mbb/g, which is four times as large as simply folding each game). But my point is that even the (exact) equilibrium strategy would not necessarily be the best strategy against given non-equilibrium-playing players.
        andrewprock 10y ago
        Yes, you are correct on every point. Opponent modeling and exploitation is significantly more difficult than coming up with a Nash equilibrium to an abstract game.
  - yAnonymous 10y ago
    >there is always a "correct" answer That's wrong. Even when you're holding a good hand, your opponent could hold a better one and reading them is a key element of poker. The opponent's hand is an important variable to decide whether you hold the winning hand or not. If you look at the experiment in detail, you'll find that it was set up in the AI's favor. >When a hand was all-in before the river no more cards were dealt and each player received his equity in chips. While all that is less important when you can avoid all-in situations, the main statement -that the other player's behavior is irrelevant- is still wrong.
    - yazr 10y ago
      >>If you look at the experiment in detail, you'll find that it was set up in the AI's favor. Could you elaborate on this ?
      - yAnonymous 10y ago
        Links were posted here: https://news.ycombinator.com/item?id=13535714 https://news.ycombinator.com/item?id=13535714 As expected, the AI is good at making technically correct decisions and "draining money" from a table by playing hands with sufficient data almost perfectly. However, in decisive all-in situations with little information available, it supposedly wouldn't do so well, regardless of all the learning, but that's what it often comes down to. >Nash Equilibrium is a strategy which ensures that the player who is using it will, at the very least, not fare worse than a player using any other strategy. How do you make this work for situations that can cost you the game in one hand, with little information available? Without observing the opponent's behavior you can't, and for the AI that means it can be forced into making bad calls by playing aggressively, unless the game mode allows for avoiding such decisions, which was the case in this test.
- DennisP 10y ago
  The no-limit hold'em game tree has over 10^160 states. Even limit poker is too large to solve directly. In 2015, limit poker was essentially solved with a new technique in game theory that allowed them to find a simplified model. http://spectrum.ieee.org/automaton/robotics/artificial-intelligence/ai-learns-from-mistakes-to-defeat-human-poker-players http://spectrum.ieee.org/automaton/robotics/artificial-intel...
  - paulddraper 10y ago
    Chess has a lot of possible states too. (Yeah, I know that's different.) Heuristics make analysis practical, and well chosen ones make the difference. This isn't to minimize the accomplishment, but rather to say it has strong similarities to other AI games.
- RivieraKid 10y ago
  You have to model opponent's behavior though. For example, the probability opponent will fold when AI bets a certain amount.
  - andrewprock 10y ago
    This is sort of correct. In a Nash equilibrium, the other player is modeled as also playing a Nash equilibrium strategy. Nothing more.
- xapata 10y ago
  > Poker is solved using a very large game tree You mean Libratus' strategy used a very large game tree. That is not the only strategy. Take a look at research from the University of Alberta [0]. Also, I'm not certain Libratus' strategy can be simplified to "very large game tree" as I haven't seen the paper, yet. While finding a Nash equilibrium means no other player can beat you, it doesn't mean you're going to make the most money in a big ring game. A different strategy might lose money to an equilibrium player, but exploit a different, weak player so much that it's worth the loss. [0] http://poker.cs.ualberta.ca/publications.html http://poker.cs.ualberta.ca/publications.html
  - __s 10y ago
    Key example of that Nash point is Rock Paper Scissors. You can't exploit anybody playing 100% random, yet that's the Nash Equilibrium. RPSAI competitions tend to have 100% random players perform quite poorly
    - thefalcon 10y ago
      Do you mean to say that 100% random RPSAIs have a lower winrate vs humans than RPSAIs that learn and exploit human patterns? Surely a 100% random RPSAI doesn't have a poor win rate against any other RPSAI?
      - T-hawk 10y ago
        A 100% random RPS AI doesn't have a poor 1-on-1 win rate against any other RPS AI, but it absolutely can have a poor rate of winning tournaments, if "poor" is defined broadly enough. For a tournament that pays cash to the top 10%, most human players would consider anything in the bottom 90% to be poor, which would include a 50% win rate from a random AI. This happens because some entrants aren't 100% random, and the worse of them can be exploited by the better of them. What happens is that the results involving any random AI essentially degenerate into noise, while the tournament is really contested between the nonrandom entrants and will be won by the one of them with the best strategy. Put another way: to win or place highly in a tournament, you don't just want expected win-rate, you want variance. If there is no difference in reward between a 50% win-rate versus a 10% win-rate (both are far out of the money), but there is a big difference between a 50% win-rate and a 90% win-rate (the latter wins the tournament), you will seek the 90% at the cost of potentially ending up at 10%.

andrewprock 10y ago

I'm surprised that Andrew Ng made this claim. The strategy that was built for Libratus' predecessor did not do sophisticated modeling of the opponents, or use new algorithmic principles. Poker is solved using a very large game tree, just as with the other games. The structure of the tree is modified to support the notion of hidden state, but beyond that it is essentially the same as the other games. The structure for representing hidden nodes was developed in the 1950s by Von Neumann. Most of the algorithmic innovations related to how to update the game tree. My guess is that the primary innovation for the Libratus strategy was that of scale.

leeleelee 10y ago
This was my thought too. Poker is quite "solvable" meaning, whenever you're confronted with a decisions -- there is always a "correct" answer which does not have to depend on the other players' behavior or style. And you can find that answer by simulation, or game trees, and other methods. It's also important to keep in mind that the best AI can still lose, and the worst AI can still win (and everything in between). Poker involves randomness, obviously whereas chess/go/etc does not.
- mormegil 10y ago
  That depends on what you mean by "correct". Sure, you could theoretically find Nash equilibrium of poker and by playing the equilibrium strategy, you can ensure you won't lose. But that does not mean this is the best strategy to use at a given table against the given opponents, who (being imperfect humans) almost certainly do not play the equilibrium strategy themselves. And, by playing a proper nonequilibrium strategy, suited to the specific players, you can win more.
  - andrewprock 10y ago
    The usual way these games are solved is to create an "abstract" game which is tractable, find the Nash equilibrium, and map state in the real game back to the "abstract" game. In the limit, the solutions for a well designed "abstract" game will converge to that of the real game.
    - mormegil 10y ago
      You are explaining how current algorithms try to find the (approximate) Nash equilibrium (and those algorithms are far from perfect; as noted in the recent DeepStack paper, current abstraction-based programs are beatable by over 3000 mbb/g, which is four times as large as simply folding each game). But my point is that even the (exact) equilibrium strategy would not necessarily be the best strategy against given non-equilibrium-playing players.
      - andrewprock 10y ago
        Yes, you are correct on every point. Opponent modeling and exploitation is significantly more difficult than coming up with a Nash equilibrium to an abstract game.
- yAnonymous 10y ago
  >there is always a "correct" answer That's wrong. Even when you're holding a good hand, your opponent could hold a better one and reading them is a key element of poker. The opponent's hand is an important variable to decide whether you hold the winning hand or not. If you look at the experiment in detail, you'll find that it was set up in the AI's favor. >When a hand was all-in before the river no more cards were dealt and each player received his equity in chips. While all that is less important when you can avoid all-in situations, the main statement -that the other player's behavior is irrelevant- is still wrong.
  - yazr 10y ago
    >>If you look at the experiment in detail, you'll find that it was set up in the AI's favor. Could you elaborate on this ?
    - yAnonymous 10y ago
      Links were posted here: https://news.ycombinator.com/item?id=13535714 https://news.ycombinator.com/item?id=13535714 As expected, the AI is good at making technically correct decisions and "draining money" from a table by playing hands with sufficient data almost perfectly. However, in decisive all-in situations with little information available, it supposedly wouldn't do so well, regardless of all the learning, but that's what it often comes down to. >Nash Equilibrium is a strategy which ensures that the player who is using it will, at the very least, not fare worse than a player using any other strategy. How do you make this work for situations that can cost you the game in one hand, with little information available? Without observing the opponent's behavior you can't, and for the AI that means it can be forced into making bad calls by playing aggressively, unless the game mode allows for avoiding such decisions, which was the case in this test.
DennisP 10y ago
The no-limit hold'em game tree has over 10^160 states. Even limit poker is too large to solve directly. In 2015, limit poker was essentially solved with a new technique in game theory that allowed them to find a simplified model. http://spectrum.ieee.org/automaton/robotics/artificial-intelligence/ai-learns-from-mistakes-to-defeat-human-poker-players http://spectrum.ieee.org/automaton/robotics/artificial-intel...
- paulddraper 10y ago
  Chess has a lot of possible states too. (Yeah, I know that's different.) Heuristics make analysis practical, and well chosen ones make the difference. This isn't to minimize the accomplishment, but rather to say it has strong similarities to other AI games.
RivieraKid 10y ago
You have to model opponent's behavior though. For example, the probability opponent will fold when AI bets a certain amount.
- andrewprock 10y ago
  This is sort of correct. In a Nash equilibrium, the other player is modeled as also playing a Nash equilibrium strategy. Nothing more.
xapata 10y ago
> Poker is solved using a very large game tree You mean Libratus' strategy used a very large game tree. That is not the only strategy. Take a look at research from the University of Alberta [0]. Also, I'm not certain Libratus' strategy can be simplified to "very large game tree" as I haven't seen the paper, yet. While finding a Nash equilibrium means no other player can beat you, it doesn't mean you're going to make the most money in a big ring game. A different strategy might lose money to an equilibrium player, but exploit a different, weak player so much that it's worth the loss. [0] http://poker.cs.ualberta.ca/publications.html http://poker.cs.ualberta.ca/publications.html
- __s 10y ago
  Key example of that Nash point is Rock Paper Scissors. You can't exploit anybody playing 100% random, yet that's the Nash Equilibrium. RPSAI competitions tend to have 100% random players perform quite poorly
  - thefalcon 10y ago
    Do you mean to say that 100% random RPSAIs have a lower winrate vs humans than RPSAIs that learn and exploit human patterns? Surely a 100% random RPSAI doesn't have a poor win rate against any other RPSAI?
    - T-hawk 10y ago
      A 100% random RPS AI doesn't have a poor 1-on-1 win rate against any other RPS AI, but it absolutely can have a poor rate of winning tournaments, if "poor" is defined broadly enough. For a tournament that pays cash to the top 10%, most human players would consider anything in the bottom 90% to be poor, which would include a 50% win rate from a random AI. This happens because some entrants aren't 100% random, and the worse of them can be exploited by the better of them. What happens is that the results involving any random AI essentially degenerate into noise, while the tournament is really contested between the nonrandom entrants and will be won by the one of them with the best strategy. Put another way: to win or place highly in a tournament, you don't just want expected win-rate, you want variance. If there is no difference in reward between a 50% win-rate versus a 10% win-rate (both are far out of the money), but there is a big difference between a 50% win-rate and a 90% win-rate (the latter wins the tournament), you will seek the 90% at the cost of potentially ending up at 10%.