9 ms·

This represents a fairly major milestone in game A.I. doesn't it? I only took one A.I. class in school and had a few that involved games as projects and rememb

by dpeck 9y ago

This represents a fairly major milestone in game A.I. doesn't it? I only took one A.I. class in school and had a few that involved games as projects and remember several times the lecturers/professors (10 years ago) mentioning that Go was a next level target after chess due to extremely high branching factor.

lisper 9y ago
Yes. Of all common games that are deterministic and have no hidden state, GO has the largest search space. It's significantly larger than chess. So this is pretty much the end of that branch of research.
- kibwen 9y ago
  Thank you for mentioning hidden state; I feel like a lot of laypersons have the impression that Go is the hardest game to solve, period, without realizing that it's in a specific class of games where the entire state of the game is evident just by looking at the board (and in addition: is a two-player game, where each player takes exactly one move per turn). I honestly wonder whether a game like Stratego, which is much less competitive than Go but has tons of hidden state, would be harder for current AI techniques to compete at. (EDIT: Specifically last year I was witness to a lot of threads regarding the quality of the AI in the video game Civilization 6 that asserted that poor AI in video games was no longer excusable since computers now beat experts at Go...)
  - lisper 9y ago
    Poker is the canonical example of a hidden-state game and that has already fallen. https://www.wired.com/2017/01/mystery-ai-just-crushed-best-human-players-poker/ https://www.wired.com/2017/01/mystery-ai-just-crushed-best-h... The list of things that humans do better than computers is getting very short very fast.
    - bluetwo 9y ago
      That makes for a good headline but it's not actually true. AI beat humans in two-player, unlimited stakes, no-limit hold-em.
      - lisper 9y ago
        And how does that fact in any way refute my claim?
        bradleyjg 9y ago
        It's not the standard version of the game. If computers were consistently beating the best in the world in blitz chess but not standard tournament rules we wouldn't say that "chess is solved".
        lisper 9y ago
        I didn't say poker was "solved", I said it had "fallen". It's true that poker is not completely solved, but neither is chess. It is still not known whether white has a forced win. It is possible that some day this will be known, and if the answer is yes, then a human playing white may be able to learn the strategy and hence beat any machine. But that will be only marginally more interesting than the fact that a human player can force a draw in tic-tac-toe. The difference between "fallen" and "solved" is just not that interesting. Checkers is solved, but no one cares. I see no reason to believe that the techniques used to beat the best human players in one variant of poker cannot be extended to beat the best human players in any variant of poker, or, for that matter, to any game with randomness and hidden state.
        bluetwo 9y ago
        I would welcome the chance to play you in poker.
        AnimalMuppet 9y ago
        It limits your claim. Putting an AI in a poker tournament with 10 players at the table is not yet a solved problem.
  - joefkelley 9y ago
    It would require a significantly different approach, but good progress is being made in that area as well. Top computers now beat humans at heads-up no limit hold 'em poker, for example: https://www.scientificamerican.com/article/time-to-fold-humans-poker-playing-ai-beats-pros-at-texas-hold-rsquo-em/ https://www.scientificamerican.com/article/time-to-fold-huma.... And that game probably has more hidden state than stratego.
  - bdamm 9y ago
    Not likely. The training of the neural nets adjusts for induced randomness. Witness the high quality AIs for poker or backgammon, where winning a single game isn't needed for the bigger multi-game win. I expect StarCraft will be the next professionally played game to experience destruction at the hands of AI. Then it will be clear that "fog of war" doesn't matter much in the decision tree from a probabilistic perspective. The irony being that faced with a "fog of war" maybe you do want to underestimate your opponent because then, if you end up surviving, you can claim brilliant insight and leadership which bolsters the short-term position, even though in fact you simply were lucky. So in the open-ended problem of tactical maneuvering in business or war, AI might not have an advantage any time soon.
    - SimbaOnSteroids 9y ago
      You'd have to limit its APM.
      - literallycancer 9y ago
        Yeah, I remember this vid with zerglings doding siege tanks shots: https://www.youtube.com/watch?v=IKVFZ28ybQs https://www.youtube.com/watch?v=IKVFZ28ybQs The difference is quite drastic.
  - scarmig 9y ago
    Nit: Go's game state isn't just defined by the board state and whose turn it is, but also by the history of all prior board states (which would still be public knowledge).
    - pmontra 9y ago
      Tewari is a common technique for analyzing go positions. You alter the order of the moves to get to the same final position and, as all the stones (the pieces) are the same, if one sequence ends with a silly move of a player, but there are no silly moves of the other player in any sequence, then the first player made a mistake. This means that the history of the game is pretty much irrelevant. Usually only the last two moves are important because you can't recapture a stone and get to the very same position as two moves before. It's called the ko rule (another unfortunate word clash with English.) There is also triple ko (three linked kos), which requires to remember more moves back, like for repeated positions in chess. A go game with a triple ko has no result: there is no draw so the game must be played again if in a tournament. It's very rare.
      - mrob 9y ago
        >A go game with a triple ko has no result True under Japanese rules. Chinese rules at least theoretically use a superko rule. But many comments online say in practice the game is voided under Chinese rules too. http://senseis.xmp.net/?Superko http://senseis.xmp.net/?Superko
  - ghaff 9y ago
    >I honestly wonder whether a game like Stratego, which is much less competitive than Go but has tons of hidden state, would be harder for current AI techniques to compete at. There don't seem to be good Stratego computer AIs (which actually surprised me a little). But I can easily believe that's at least in part because not a huge amount of effort has been put into it.
  - alasdair_ 9y ago
    I still wonder how well a computer could handle games like magic: the gathering which don't simply include hidden information and randomness, but include cards that change the rules of the games themselves and where the interactions of cards can produce crazy effects that are hard to predict before they occur. Add in the fact that each player needs to build their own deck (choosing from 20,000+ cards) and that new cards are printed regularly, significantly shifting the expected metagame, and building an AI that can routinely win in a larger card pool format like Modern or Vintage seems absurdly difficult.
    - literallycancer 9y ago
      MTG online enforces the rules AFAIK, so I'd assume they are not that complicated.
  - AndyNemmity 9y ago
    I write the current most used AI mod in Civ 6, and have been doing Civ AI since 4. The poor AI in Civ is repeatedly based around smart systems stacked on top of each other. So imagine Software Development, you decide you want to add 10 AI systems to run aspects of the AI. You build all 10 AI systems, each one doing a thing. Then you add them all together, and they all clash. That's Civ AI. It's almost deterministic in that, all the AI systems fight each other in a consistent way, so you could have just ignored writing all your complicated AI, and made the AI just follow a single decision tree, and it would be the same results. Except a single decision tree would follow logic. Random systems competing with each other, has no real logic. Then when AI problems come about, the programmers tweak the systems to fix a single problem, which can maybe work, but will break many other things in the process. So each Civ game, to fix the AI, you start by shutting off all the AI systems one by one. The goal being when I ask the game to do X, X occurs. Once you get all the stuff removed so you can actually make the game do something, you then create actions that make things happen. That can make the game has significantly insanely good AI. The best example of this is a mod in Civ 5 called Vox Popeli which has the most profound Civ AI anyone has come up with, and takes ideas from all the Civ modders. To get the AI to a point where the Human thinks it's good is not particularly hard if you focus on simple, easy to understand concepts, and not large systems that are supposed to cover every possibility organically.
    - ep103 9y ago
      Thank you for your service! The current civ AI team is pointed in such a wrong direction... wish they would hire you guys instead! :)
emtel 9y ago
It's not just the branching factor. It's also the fact that the quality of moves in games like chess can be evaluated relatively quickly, say, within 10-20 turns. In Go, on the other hand, a stone placed at the beginning of the game may be critically important 100 turns later.
gniv 9y ago
The real milestone was achieved last year, when AlphaGo was unveiled, and played (and won) against Lee Sedol.
vorg 9y ago
I wonder if playing Go on a much larger board (e.g. 37 x 37) would limit the ability of AlphaGo to explore branching significantly to tip the advantage back to humans. I'm not sure if A.I. is limited by branching sizes. And would human intuition of strategy on a 19 x 19 board map easily to the strategy of a 37 x 37 board? After all, Go is still Go no matter what size the board, whereas chess can only be called chess when played on the 8 x 8 board.
- deleted 9y ago
  [deleted]
- Florin_Andrei 9y ago
  Board size would hamper old brute force algorithms. Modern Go AI also has "intuitive" components just like we do (large neural networks trained to immediately provide a heat map of what should be the next best move). That NN is not limited by board size. BTW, even when playing by "intuition" alone (no tree search), AlphaGo is still incredibly strong. It would still beat most amateur players that way.
- forgot-my-pw 9y ago
  This game could take forever to finish... AlphaGo should be able to be retrained using different variables/game rules.
- deleted 9y ago
  [deleted]

by dpeck 9y ago

lisper 9y ago

Yes. Of all common games that are deterministic and have no hidden state, GO has the largest search space. It's significantly larger than chess. So this is pretty much the end of that branch of research.

kibwen 9y ago
Thank you for mentioning hidden state; I feel like a lot of laypersons have the impression that Go is the hardest game to solve, period, without realizing that it's in a specific class of games where the entire state of the game is evident just by looking at the board (and in addition: is a two-player game, where each player takes exactly one move per turn). I honestly wonder whether a game like Stratego, which is much less competitive than Go but has tons of hidden state, would be harder for current AI techniques to compete at. (EDIT: Specifically last year I was witness to a lot of threads regarding the quality of the AI in the video game Civilization 6 that asserted that poor AI in video games was no longer excusable since computers now beat experts at Go...)
- lisper 9y ago
  Poker is the canonical example of a hidden-state game and that has already fallen. https://www.wired.com/2017/01/mystery-ai-just-crushed-best-human-players-poker/ https://www.wired.com/2017/01/mystery-ai-just-crushed-best-h... The list of things that humans do better than computers is getting very short very fast.
  - bluetwo 9y ago
    That makes for a good headline but it's not actually true. AI beat humans in two-player, unlimited stakes, no-limit hold-em.
    - lisper 9y ago
      And how does that fact in any way refute my claim?
      - bradleyjg 9y ago
        It's not the standard version of the game. If computers were consistently beating the best in the world in blitz chess but not standard tournament rules we wouldn't say that "chess is solved".
        lisper 9y ago
        I didn't say poker was "solved", I said it had "fallen". It's true that poker is not completely solved, but neither is chess. It is still not known whether white has a forced win. It is possible that some day this will be known, and if the answer is yes, then a human playing white may be able to learn the strategy and hence beat any machine. But that will be only marginally more interesting than the fact that a human player can force a draw in tic-tac-toe. The difference between "fallen" and "solved" is just not that interesting. Checkers is solved, but no one cares. I see no reason to believe that the techniques used to beat the best human players in one variant of poker cannot be extended to beat the best human players in any variant of poker, or, for that matter, to any game with randomness and hidden state.
        bluetwo 9y ago
        I would welcome the chance to play you in poker.
      - AnimalMuppet 9y ago
        It limits your claim. Putting an AI in a poker tournament with 10 players at the table is not yet a solved problem.
- joefkelley 9y ago
  It would require a significantly different approach, but good progress is being made in that area as well. Top computers now beat humans at heads-up no limit hold 'em poker, for example: https://www.scientificamerican.com/article/time-to-fold-humans-poker-playing-ai-beats-pros-at-texas-hold-rsquo-em/ https://www.scientificamerican.com/article/time-to-fold-huma.... And that game probably has more hidden state than stratego.
- bdamm 9y ago
  Not likely. The training of the neural nets adjusts for induced randomness. Witness the high quality AIs for poker or backgammon, where winning a single game isn't needed for the bigger multi-game win. I expect StarCraft will be the next professionally played game to experience destruction at the hands of AI. Then it will be clear that "fog of war" doesn't matter much in the decision tree from a probabilistic perspective. The irony being that faced with a "fog of war" maybe you do want to underestimate your opponent because then, if you end up surviving, you can claim brilliant insight and leadership which bolsters the short-term position, even though in fact you simply were lucky. So in the open-ended problem of tactical maneuvering in business or war, AI might not have an advantage any time soon.
  - SimbaOnSteroids 9y ago
    You'd have to limit its APM.
    - literallycancer 9y ago
      Yeah, I remember this vid with zerglings doding siege tanks shots: https://www.youtube.com/watch?v=IKVFZ28ybQs https://www.youtube.com/watch?v=IKVFZ28ybQs The difference is quite drastic.
- scarmig 9y ago
  Nit: Go's game state isn't just defined by the board state and whose turn it is, but also by the history of all prior board states (which would still be public knowledge).
  - pmontra 9y ago
    Tewari is a common technique for analyzing go positions. You alter the order of the moves to get to the same final position and, as all the stones (the pieces) are the same, if one sequence ends with a silly move of a player, but there are no silly moves of the other player in any sequence, then the first player made a mistake. This means that the history of the game is pretty much irrelevant. Usually only the last two moves are important because you can't recapture a stone and get to the very same position as two moves before. It's called the ko rule (another unfortunate word clash with English.) There is also triple ko (three linked kos), which requires to remember more moves back, like for repeated positions in chess. A go game with a triple ko has no result: there is no draw so the game must be played again if in a tournament. It's very rare.
    - mrob 9y ago
      >A go game with a triple ko has no result True under Japanese rules. Chinese rules at least theoretically use a superko rule. But many comments online say in practice the game is voided under Chinese rules too. http://senseis.xmp.net/?Superko http://senseis.xmp.net/?Superko
- ghaff 9y ago
  >I honestly wonder whether a game like Stratego, which is much less competitive than Go but has tons of hidden state, would be harder for current AI techniques to compete at. There don't seem to be good Stratego computer AIs (which actually surprised me a little). But I can easily believe that's at least in part because not a huge amount of effort has been put into it.
- alasdair_ 9y ago
  I still wonder how well a computer could handle games like magic: the gathering which don't simply include hidden information and randomness, but include cards that change the rules of the games themselves and where the interactions of cards can produce crazy effects that are hard to predict before they occur. Add in the fact that each player needs to build their own deck (choosing from 20,000+ cards) and that new cards are printed regularly, significantly shifting the expected metagame, and building an AI that can routinely win in a larger card pool format like Modern or Vintage seems absurdly difficult.
  - literallycancer 9y ago
    MTG online enforces the rules AFAIK, so I'd assume they are not that complicated.
- AndyNemmity 9y ago
  I write the current most used AI mod in Civ 6, and have been doing Civ AI since 4. The poor AI in Civ is repeatedly based around smart systems stacked on top of each other. So imagine Software Development, you decide you want to add 10 AI systems to run aspects of the AI. You build all 10 AI systems, each one doing a thing. Then you add them all together, and they all clash. That's Civ AI. It's almost deterministic in that, all the AI systems fight each other in a consistent way, so you could have just ignored writing all your complicated AI, and made the AI just follow a single decision tree, and it would be the same results. Except a single decision tree would follow logic. Random systems competing with each other, has no real logic. Then when AI problems come about, the programmers tweak the systems to fix a single problem, which can maybe work, but will break many other things in the process. So each Civ game, to fix the AI, you start by shutting off all the AI systems one by one. The goal being when I ask the game to do X, X occurs. Once you get all the stuff removed so you can actually make the game do something, you then create actions that make things happen. That can make the game has significantly insanely good AI. The best example of this is a mod in Civ 5 called Vox Popeli which has the most profound Civ AI anyone has come up with, and takes ideas from all the Civ modders. To get the AI to a point where the Human thinks it's good is not particularly hard if you focus on simple, easy to understand concepts, and not large systems that are supposed to cover every possibility organically.
  - ep103 9y ago
    Thank you for your service! The current civ AI team is pointed in such a wrong direction... wish they would hire you guys instead! :)

emtel 9y ago

It's not just the branching factor. It's also the fact that the quality of moves in games like chess can be evaluated relatively quickly, say, within 10-20 turns. In Go, on the other hand, a stone placed at the beginning of the game may be critically important 100 turns later.

gniv 9y ago

The real milestone was achieved last year, when AlphaGo was unveiled, and played (and won) against Lee Sedol.

vorg 9y ago

I wonder if playing Go on a much larger board (e.g. 37 x 37) would limit the ability of AlphaGo to explore branching significantly to tip the advantage back to humans. I'm not sure if A.I. is limited by branching sizes. And would human intuition of strategy on a 19 x 19 board map easily to the strategy of a 37 x 37 board? After all, Go is still Go no matter what size the board, whereas chess can only be called chess when played on the 8 x 8 board.

deleted 9y ago
[deleted]
Florin_Andrei 9y ago
Board size would hamper old brute force algorithms. Modern Go AI also has "intuitive" components just like we do (large neural networks trained to immediately provide a heat map of what should be the next best move). That NN is not limited by board size. BTW, even when playing by "intuition" alone (no tree search), AlphaGo is still incredibly strong. It would still beat most amateur players that way.
forgot-my-pw 9y ago
This game could take forever to finish... AlphaGo should be able to be retrained using different variables/game rules.
deleted 9y ago
[deleted]