6 ms·

Is there any remaining logic game which AI hasn't become superhuman? IIRC Monte Carlo tree search has done wonders in this area.

pclmulqdq 5y ago
Contract Bridge is still untouched. I'm not sure if it's because of lack of resources, but it has a lot of difficult elements: cooperation, huge search trees due to imperfect information, and information theoretic aspects of bidding.
btheshoe 5y ago
Imperfect information games that require agents to cooperate with each other haven't been solved yet. (multiagent cooperation is still a hard problem) Hanabi is a big(ish) research area. Contract bridge has had some work done on it.
- HWR_14 5y ago
  I'm surprised that Hanabi is such a huge research area. Compared to bridge or poker, it seems like a far more simple game.
  - ska 5y ago
    > I'm surprised ... it seems like a far more simple game. This probably shouldn't surprise you. If you are researching how to attack a new/difficult class of problems, typically you look for the simplest versions of that class first.
    - HWR_14 5y ago
      I would agree with that. I just tended to assume that Hanabi would be a solved problem by now.
      - noambrown 5y ago
        Bots are superhuman in self-play Hanabi: https://ai.facebook.com/blog/building-ai-that-can-master-complex-cooperative-games-with-hidden-information/ https://ai.facebook.com/blog/building-ai-that-can-master-com... The remaining challenge is getting it to play well with human partners. Doing that requires modeling human conventions rather than learning weird bot conventions. That's hard because while you can collect essentially unlimited data through self play, it's hard to collect a lot of data playing with humans using reinforcement learning. AI algorithms are really bad at sample efficiency.
isaacg 5y ago
As far as I know, in Magic: the Gathering, the best bots are far worse than most players. Part of the difficulty is that the rules are so complicated that there are only a couple of complete rules implementations. Beyond that, it's an imperfect information game with far more actions per game than poker, so optimal-solver techniques haven't seen success.
- golergka 5y ago
  Have people tried using GPT-3 for this?
- dwohnitmok 5y ago
  I think this is purely a resource issue, e.g. if Google Brain decided to make an MtG bot I would be fairly confident it would be superhuman. Even real time strategy games like Starcraft are looking like they're on the cusp of superhuman bots (Alphastar was competitive as Protoss against elite players, but did not consistently beat them).
  - jdmoreira 5y ago
    The search tree is huge in mtg. It has to be the largest of any game. You can take actions all the time. There are triggers all the time, you can stack your actions on top of your opponent actions. Huge space really. And then of course it's also imperfect information both in the sense of your opponent hand but also his deck. The cardpool is also very large for some formats. I actually don't think it's solvable just by throwing MCTS at it with todays hardware but would love to know more about this, if someone else has more insight please reply. EDIT: Oh and there is also the meta-game / deck building aspect. If you are going to win a tournament you have to have favorable matchups against most players in the room.
    - ogogmad 5y ago
      MCTS is usually paired up with Deep Learning. This doesn't appear to have any problems with games with even larger branching factors. Look up AlphaZero and AlphaStar.
splonk 5y ago
Here's a recent paper from DeepMind about their recent efforts towards generalized game solving (caveat: I haven't actually read it yet). https://arxiv.org/pdf/2112.03178.pdf https://arxiv.org/pdf/2112.03178.pdf Abstract: "Games have a long history of serving as a benchmark for progress in artificial intelligence. Recently, approaches using search and learning have shown strong performance across a set of perfect information games, and approaches using game-theoretic reasoning and learning have shown strong performance for specific imperfect information poker variants. We introduce Player of Games, a general-purpose algorithm that unifies previous approaches, combining guided search, self-play learning, and game-theoretic reasoning. Player of Games is the first algorithm to achieve strong empirical performance in large perfect and imperfect information games — an important step towards truly general algorithms for arbitrary environments. We prove that Player of Games is sound, converging to perfect play as available computation time and approximation capacity increases. Player of Games reaches strong performance in chess and Go, beats the strongest openly available agent in heads-up no-limit Texas hold’em poker (Slumbot), and defeats the state-of-the-art agent in Scotland Yard, an imperfect information game that illustrates the value of guided search, learning, and game-theoretic reasoning"

pclmulqdq 5y ago

Contract Bridge is still untouched. I'm not sure if it's because of lack of resources, but it has a lot of difficult elements: cooperation, huge search trees due to imperfect information, and information theoretic aspects of bidding.

btheshoe 5y ago

Imperfect information games that require agents to cooperate with each other haven't been solved yet. (multiagent cooperation is still a hard problem) Hanabi is a big(ish) research area. Contract bridge has had some work done on it.

HWR_14 5y ago
I'm surprised that Hanabi is such a huge research area. Compared to bridge or poker, it seems like a far more simple game.
- ska 5y ago
  > I'm surprised ... it seems like a far more simple game. This probably shouldn't surprise you. If you are researching how to attack a new/difficult class of problems, typically you look for the simplest versions of that class first.
  - HWR_14 5y ago
    I would agree with that. I just tended to assume that Hanabi would be a solved problem by now.
    - noambrown 5y ago
      Bots are superhuman in self-play Hanabi: https://ai.facebook.com/blog/building-ai-that-can-master-complex-cooperative-games-with-hidden-information/ https://ai.facebook.com/blog/building-ai-that-can-master-com... The remaining challenge is getting it to play well with human partners. Doing that requires modeling human conventions rather than learning weird bot conventions. That's hard because while you can collect essentially unlimited data through self play, it's hard to collect a lot of data playing with humans using reinforcement learning. AI algorithms are really bad at sample efficiency.

isaacg 5y ago

As far as I know, in Magic: the Gathering, the best bots are far worse than most players. Part of the difficulty is that the rules are so complicated that there are only a couple of complete rules implementations. Beyond that, it's an imperfect information game with far more actions per game than poker, so optimal-solver techniques haven't seen success.

golergka 5y ago
Have people tried using GPT-3 for this?
dwohnitmok 5y ago
I think this is purely a resource issue, e.g. if Google Brain decided to make an MtG bot I would be fairly confident it would be superhuman. Even real time strategy games like Starcraft are looking like they're on the cusp of superhuman bots (Alphastar was competitive as Protoss against elite players, but did not consistently beat them).
- jdmoreira 5y ago
  The search tree is huge in mtg. It has to be the largest of any game. You can take actions all the time. There are triggers all the time, you can stack your actions on top of your opponent actions. Huge space really. And then of course it's also imperfect information both in the sense of your opponent hand but also his deck. The cardpool is also very large for some formats. I actually don't think it's solvable just by throwing MCTS at it with todays hardware but would love to know more about this, if someone else has more insight please reply. EDIT: Oh and there is also the meta-game / deck building aspect. If you are going to win a tournament you have to have favorable matchups against most players in the room.
  - ogogmad 5y ago
    MCTS is usually paired up with Deep Learning. This doesn't appear to have any problems with games with even larger branching factors. Look up AlphaZero and AlphaStar.

splonk 5y ago

Here's a recent paper from DeepMind about their recent efforts towards generalized game solving (caveat: I haven't actually read it yet). https://arxiv.org/pdf/2112.03178.pdf https://arxiv.org/pdf/2112.03178.pdf Abstract: "Games have a long history of serving as a benchmark for progress in artificial intelligence. Recently, approaches using search and learning have shown strong performance across a set of perfect information games, and approaches using game-theoretic reasoning and learning have shown strong performance for specific imperfect information poker variants. We introduce Player of Games, a general-purpose algorithm that unifies previous approaches, combining guided search, self-play learning, and game-theoretic reasoning. Player of Games is the first algorithm to achieve strong empirical performance in large perfect and imperfect information games — an important step towards truly general algorithms for arbitrary environments. We prove that Player of Games is sound, converging to perfect play as available computation time and approximation capacity increases. Player of Games reaches strong performance in chess and Go, beats the strongest openly available agent in heads-up no-limit Texas hold’em poker (Slumbot), and defeats the state-of-the-art agent in Scotland Yard, an imperfect information game that illustrates the value of guided search, learning, and game-theoretic reasoning"