4 ms·

Very happy to see this result. It's like a moral victory for humans, as alphago is more human like (discounting montecarlo search) than stockfish. Maybe deep

Very happy to see this result. It's like a moral victory for humans, as alphago is more human like (discounting montecarlo search) than stockfish. Maybe deep learning will give us the next Euler, Newton, or Einstein.

visarga 9y ago
Shogi, chess and Go are "perfect information games", meaning you can see the whole game state. It's a whole different thing to be able to solve games where you don't see everything (based on uncertainty).
- jacobkg 9y ago
  In 2015 Heads-Up Limit Hold'em was solved: http://science.sciencemag.org/content/347/6218/145.full http://science.sciencemag.org/content/347/6218/145.full
- ucaetano 9y ago
  You mean, like poker? https://www.cmu.edu/news/stories/archives/2017/january/AI-beats-poker-pros.html https://www.cmu.edu/news/stories/archives/2017/january/AI-be... Actually machines can have an even higher advantage in those cases, because they can be much better at estimating probabilities than humans. Think of card counting, for example.
  - grumpopotamus 9y ago
    I disagree. Computers have been outplaying the best humans at chess for two decades, but they only recently beat the top players at 2-player NLHE and only with the aid of massive computational power during training. Furthermore, techniques like monte-carlo tree search used in AlphaGo don't work very well for poker - You can't just try and find the "best move" from the current game state, or you will end up playing a highly-exploitable strategy. You essentially have to solve the entire game every time (or completely in advance) to make sure you are playing a balanced strategy. Only the Counter-Factual Regret Minimization algorithm has been able to achieve this level of play in Heads Up, and right now it looks hard to scale to poker games with more players, like the full-ring games you see at the World Series of Poker, for example. We still have a ways to go in Poker AI.
- roenxi 9y ago
  Is it really though? A big class of imperfect information games can be modeled by having a record of everything the agent has seen so far. Then it has exactly the same, if not more, information available than a human player in the same position. We know that with equal information AIs can make better decisions than humans (see also, AlphaGo :] ) so at that point the AI could reasonably be expected to achieve superhuman performance. The "imperfect information games are harder for AI" crowd are going to be surprised by just how badly humans deal with imperfect information. AIs have a much better memory than humans do, and much more potential to use actual probability which humans are truly shocking at utilising (although neural networks don't seem to utilise this edge; so far).
  - visarga 9y ago
    Could work, but it hasn't been widely demonstrated yet. I really hope we can tackle such games/RL tasks.
  - Cybiote 9y ago
    The difficulty of imperfect information is from cross cutting through information sets and partial observability. With perfect information games like chess or Go, one can solve subgames with guarantees that the equilibrium is the same as for the full game. This is not the case for games like poker, which is why they have been difficult. In addition to that, for n > 2 players, there are no longer theoretical guarantees about converging to a nash equilibrium, which makes designing theory guided algorithms harder. Though empirical performance with n=3 of CFR is encouraging, I know of no results for n > 3. Earlier this year, DeepStack, a system combining neural nets with search, competed live against humans without any side being dominant. Search policy guided training might improve its results, which are impressive compared to even 5 years ago, but this highlights how much more demanding imperfect information games are.
    - deleted 9y ago
      [deleted]
    - sharky6000 9y ago
      Yep, this. Btw there are some encouraging results for n=4 using sequence form replicator dynamics (which are implementing a form of CFR) in Kuhn poker. Toy example but the game gets large fast with n=4. Don't know of any results with n > 4. http://mlanctot.info/files/papers/aamas14sfrd-cfr-kuhn.pdf http://mlanctot.info/files/papers/aamas14sfrd-cfr-kuhn.pdf
- naveen99 9y ago
  Math can be perfect information too if you just start with axioms. Even when starting with conjectures, the rules are transparent for manipulating statements.

visarga 9y ago

Shogi, chess and Go are "perfect information games", meaning you can see the whole game state. It's a whole different thing to be able to solve games where you don't see everything (based on uncertainty).

jacobkg 9y ago
In 2015 Heads-Up Limit Hold'em was solved: http://science.sciencemag.org/content/347/6218/145.full http://science.sciencemag.org/content/347/6218/145.full
ucaetano 9y ago
You mean, like poker? https://www.cmu.edu/news/stories/archives/2017/january/AI-beats-poker-pros.html https://www.cmu.edu/news/stories/archives/2017/january/AI-be... Actually machines can have an even higher advantage in those cases, because they can be much better at estimating probabilities than humans. Think of card counting, for example.
- grumpopotamus 9y ago
  I disagree. Computers have been outplaying the best humans at chess for two decades, but they only recently beat the top players at 2-player NLHE and only with the aid of massive computational power during training. Furthermore, techniques like monte-carlo tree search used in AlphaGo don't work very well for poker - You can't just try and find the "best move" from the current game state, or you will end up playing a highly-exploitable strategy. You essentially have to solve the entire game every time (or completely in advance) to make sure you are playing a balanced strategy. Only the Counter-Factual Regret Minimization algorithm has been able to achieve this level of play in Heads Up, and right now it looks hard to scale to poker games with more players, like the full-ring games you see at the World Series of Poker, for example. We still have a ways to go in Poker AI.
roenxi 9y ago
Is it really though? A big class of imperfect information games can be modeled by having a record of everything the agent has seen so far. Then it has exactly the same, if not more, information available than a human player in the same position. We know that with equal information AIs can make better decisions than humans (see also, AlphaGo :] ) so at that point the AI could reasonably be expected to achieve superhuman performance. The "imperfect information games are harder for AI" crowd are going to be surprised by just how badly humans deal with imperfect information. AIs have a much better memory than humans do, and much more potential to use actual probability which humans are truly shocking at utilising (although neural networks don't seem to utilise this edge; so far).
- visarga 9y ago
  Could work, but it hasn't been widely demonstrated yet. I really hope we can tackle such games/RL tasks.
- Cybiote 9y ago
  The difficulty of imperfect information is from cross cutting through information sets and partial observability. With perfect information games like chess or Go, one can solve subgames with guarantees that the equilibrium is the same as for the full game. This is not the case for games like poker, which is why they have been difficult. In addition to that, for n > 2 players, there are no longer theoretical guarantees about converging to a nash equilibrium, which makes designing theory guided algorithms harder. Though empirical performance with n=3 of CFR is encouraging, I know of no results for n > 3. Earlier this year, DeepStack, a system combining neural nets with search, competed live against humans without any side being dominant. Search policy guided training might improve its results, which are impressive compared to even 5 years ago, but this highlights how much more demanding imperfect information games are.
  - deleted 9y ago
    [deleted]
  - sharky6000 9y ago
    Yep, this. Btw there are some encouraging results for n=4 using sequence form replicator dynamics (which are implementing a form of CFR) in Kuhn poker. Toy example but the game gets large fast with n=4. Don't know of any results with n > 4. http://mlanctot.info/files/papers/aamas14sfrd-cfr-kuhn.pdf http://mlanctot.info/files/papers/aamas14sfrd-cfr-kuhn.pdf
naveen99 9y ago
Math can be perfect information too if you just start with axioms. Even when starting with conjectures, the rules are transparent for manipulating statements.