4 ms·

One of the researchers on this team gave a great talk at NIPS this year about this work and explained how playing an imperfect information game like poker is fu

One of the researchers on this team gave a great talk at NIPS this year about this work and explained how playing an imperfect information game like poker is fundamentally different from playing a perfect information game like chess or go. A perfect information game has no path dependence --- once you arrive at a state, it doesn't matter how you got there. You only need to consider the current state of the game to figure out the best move to play. In an imperfect information game this is no longer true. Now you need to consider counterfactuals --- how would the opponent have played if I had done something different earlier? They illustrated with a toy game they called "Coin Toss". The idea is that Player A flips a coin, but Player B doesn't get to see the result. Player A then gets to choose whether to end the game there or continue playing. If they end the game, they get $1 from Player B if the coin is heads and lose $1 from Player B if the coin is tails. If they decide to continue playing, then Player B gets to guess whether the coin is heads or tails. If Player B guesses correctly, they get $2 from Player A, and otherwise lose $2. If you spend some time thinking about the strategy, you can figure out that the best strategy for Player B is to guess heads 25% of the time and tails 75% of the time. But if you change the rules to the game for Player A, so that they get $1 if it's tails and lose $1 if it's heads, then the best strategy for Player B reverses as well --- now Player B should guess heads 75% of the time and tails 25% of the time. Yet nothing about Player B's situation has changed --- the only change happened prior to Player B's involvement. Yet this nevertheless changes Player B's strategy because Player B must consider how Player A would have acted given that the coin landed heads vs. tails. So to solve these imperfect information games, you have to be very careful to model these sorts of counterfactuals. If you mess up you will leave yourself with an exploitable strategy --- that is, someone can devise a strategy that causes you to lose the game. Link to the paper here: https://arxiv.org/pdf/1705.02955.pdf https://arxiv.org/pdf/1705.02955.pdf

roenxi 9y ago
I'm going to read the paper carefully and think hard, but going in to it I still have philosophical issues saying imperfect information is 'fundamentally' different. Sure, the specific learning algorithm may not generalise from board games to poker. But to claim that Go is perfect-information is more theoretical than practical. In practice, the 50% of moves your opponent makes are unknowns. Nobody can assess the entire game tree, so the fact that it is theoretically knowable isn't actually relevant in a game. Neither computers nor humans can compute it. Once the tree can be reasonably computed, between high level players the game is over (bar the occasional blunder).
- jpapon 9y ago
  >> Nobody can assess the entire game tree, so the fact that it is theoretically knowable isn't actually relevant in a game. That's not the point though. The point is that you only need to consider current state when considering your next move in Go or Chess. This is not the case in an incomplete information game, since the sequence of moves that led to the current state contains a lot of information. That's not the case in Chess or Go. Basically, Chess and Go satisfy the Markov Property, while Poker does not.
  - roenxi 9y ago
    The current state in Go is the state of the board, the current state of poker includes some historical data. This difference is only significant to humans because we have quite poor memories. An AI has perfect recall, and the fact that a variable is temporal really doesn't make a difference to the theory. (Coincidental aside, this is an issue in Go as well due to the ko rule; but it isn't a major part of the game such as in poker.)
    - jononor 9y ago
      Which AI architecture has perfect recall, in a way that actually makes use of this information? Pretty sure AlphaGo etc does not make use of memory at all.
- antognini 9y ago
  It's true that you can't model the entire game perfectly for any interesting game. But to play a game like Go you only need to know the current state in order to play optimally. If you play poker in a way that only accounts for your current state (i.e., you just take an expected value given the cards on the table, the cards in your hand, and the size of the pot) it won't take long for a competent player to learn how to consistently beat you. (Such a player would get tricked by bluffing, for instance.) In order to play correctly you need to model your opponent's strategy by understanding what their past moves were so that you can guess their probability of bluffing.

roenxi 9y ago

I'm going to read the paper carefully and think hard, but going in to it I still have philosophical issues saying imperfect information is 'fundamentally' different. Sure, the specific learning algorithm may not generalise from board games to poker. But to claim that Go is perfect-information is more theoretical than practical. In practice, the 50% of moves your opponent makes are unknowns. Nobody can assess the entire game tree, so the fact that it is theoretically knowable isn't actually relevant in a game. Neither computers nor humans can compute it. Once the tree can be reasonably computed, between high level players the game is over (bar the occasional blunder).

jpapon 9y ago
>> Nobody can assess the entire game tree, so the fact that it is theoretically knowable isn't actually relevant in a game. That's not the point though. The point is that you only need to consider current state when considering your next move in Go or Chess. This is not the case in an incomplete information game, since the sequence of moves that led to the current state contains a lot of information. That's not the case in Chess or Go. Basically, Chess and Go satisfy the Markov Property, while Poker does not.
- roenxi 9y ago
  The current state in Go is the state of the board, the current state of poker includes some historical data. This difference is only significant to humans because we have quite poor memories. An AI has perfect recall, and the fact that a variable is temporal really doesn't make a difference to the theory. (Coincidental aside, this is an issue in Go as well due to the ko rule; but it isn't a major part of the game such as in poker.)
  - jononor 9y ago
    Which AI architecture has perfect recall, in a way that actually makes use of this information? Pretty sure AlphaGo etc does not make use of memory at all.
antognini 9y ago
It's true that you can't model the entire game perfectly for any interesting game. But to play a game like Go you only need to know the current state in order to play optimally. If you play poker in a way that only accounts for your current state (i.e., you just take an expected value given the cards on the table, the cards in your hand, and the size of the pot) it won't take long for a competent player to learn how to consistently beat you. (Such a player would get tricked by bluffing, for instance.) In order to play correctly you need to model your opponent's strategy by understanding what their past moves were so that you can guess their probability of bluffing.