4 ms·

One falsehood in the article is that Go is the only game where computers "don't stand a chance." In fact, computers are substantially worse than the best human

One falsehood in the article is that Go is the only game where computers "don't stand a chance." In fact, computers are substantially worse than the best humans at Go, Arimaa, Hex and maybe Havannah [1], to take some games that I know. Arimaa is underexplored for both humans and computers, but there are several programmers working on it, and there is a modest prize available. Hex and Havannah are less explored, but they also have academic work done on them, and their human communities are also small, which means that we're not getting the best humans can do. [1] Havannah has a pretty good bot, Castro, but I think it's still quite beatable.

rockdoe 12y ago
One of these games was designed to be hard for computers, the others are way less popular than go and have far less history, and hence competition/interest. It's an exaggeration but a pretty minor one.
- hyperpape 12y ago
  Yes, but as I pointed out, there's also less human interest in those games. That affects both humans and computers. No one is a grandmaster at Arimaa, Hex or Havannah. If those games were more popular, then both computers and professionals would be better. As far as the quality of the exaggeration, I think it is misleading. Shogi programs are just catching the best humans in 2013-2014. Go may not resist artificial intelligence for another ten years. That's a noticeable difference, but also not that grand of one. I'd just like a little accuracy: we may not be dealing with more than moderate differences in difficulty.
  - hajile 12y ago
    Shogi programs only match up in the standard 9x9 board. They fall far behind the moment you introduce a larger variant. As to go, computers have a hard to time with 9x9 and a handicap. 13x13, 19x19, or larger is even further out of the question. The fundamental issue is that the problem must be solved entirely with heuristics. We have trouble modeling cat brains. We are a long way away from human-level pattern recognition heuristics.
    - hyperpape 12y ago
      Your knowledge of the situation in Go seems out of date. On the 9x9 board, bots are perhaps equal with professionals, or just behind them. On 19x19, they regularly win with 4 stone handicaps. See: http://www.computer-go.info/h-c/index.html http://www.computer-go.info/h-c/index.html
      - RBerenguel 12y ago
        Bots are still somewhat behind pros (last February pros scored 4-0 agains bots in 9x9... I love 9x9 so I try to keep up with this :) )
      - rtpg 12y ago
        4 stone is a pretty big handicap (though I can't win against pros with 9 so I guess there's that :))
VLM 12y ago
From the article a criteria often missed in the discussion is "...of all the world’s perfect information games..." Virtually all tabletop grognard games are perfect information games. I say virtually because there might be one I can't think of at this time, maybe a card driven game. I suppose the COIN series is partially imperfect information... Even a noob player can crush an AI trying to play grognard games so usually the computer cheats or is given a massive handicap, like, say, your human controlled division is up against two, maybe three AI divisions. I've played a lot of grognard games both computer and tabletop and I've never found a worthy evenly matched AI opponent although humans can kick my butt. Some computer implementations implement a fog of war which would certainly be imperfect information, but not tabletops or faithful reimplementations of tabletops. A "good" grognard scenario/game doesn't depend on FoW anyway, or at least many people share that belief. You can model a stereotypical grognard game as "chess with a large hex board, more pieces, and wider variety of pieces". I guess that gives some idea what a computer-proof abstract game would look like. "GO" on a 171x171 grid, perhaps, or chess with 50 kinds of pieces.
- icegreentea 12y ago
  I'm not sure what exactly a grognard game is - but if it's just wargames, off the top of my head Stratego is a game without perfect information. A lot of fun too. The traditional board version takes three participants to play, but computer/electronic versions gets ride of the referee.
  - lazyant 12y ago
    I've played lots of board/classic Stratego, you just need the two participants, I don't know what the referee would be for.
    - dllthomas 12y ago
      Apparently there is a related game where battles are decided without revealing the identities of the pieces involved.
- gwern 12y ago
clusterfoo 12y ago
Heh, my first thought reading the article was designing a game that is simple, yet inherently difficult for an AI player. Thanks for introducing me to Arimaa!
- hyperpape 12y ago
  It's quite chesslike, and not really my taste, but it's a good game.
SilasX 12y ago
Depending on your definition of "game", there's also captchas.
- dllthomas 12y ago
  ... and Spin The Bottle!
  - notduncansmith 12y ago
    You clearly have outdated software, my computer is a pro at that one.
  - SilasX 12y ago
    Captchas are (like Go and the other games) a legit information processing distinguisher between humans and computers; unlike spin the bottle, it's not just an issue of having the right peripherals or social standing. (I know you were probably joking; this is just in case anyone gets the idea that the "captcha game" is just as trivial in this respect as spin-the-bottle.)
    - dllthomas 12y ago
      Certainly the case. I was obviously joking, but thank you for making this distinction more salient - it deserves to be.

rockdoe 12y ago

One of these games was designed to be hard for computers, the others are way less popular than go and have far less history, and hence competition/interest. It's an exaggeration but a pretty minor one.

hyperpape 12y ago
Yes, but as I pointed out, there's also less human interest in those games. That affects both humans and computers. No one is a grandmaster at Arimaa, Hex or Havannah. If those games were more popular, then both computers and professionals would be better. As far as the quality of the exaggeration, I think it is misleading. Shogi programs are just catching the best humans in 2013-2014. Go may not resist artificial intelligence for another ten years. That's a noticeable difference, but also not that grand of one. I'd just like a little accuracy: we may not be dealing with more than moderate differences in difficulty.
- hajile 12y ago
  Shogi programs only match up in the standard 9x9 board. They fall far behind the moment you introduce a larger variant. As to go, computers have a hard to time with 9x9 and a handicap. 13x13, 19x19, or larger is even further out of the question. The fundamental issue is that the problem must be solved entirely with heuristics. We have trouble modeling cat brains. We are a long way away from human-level pattern recognition heuristics.
  - hyperpape 12y ago
    Your knowledge of the situation in Go seems out of date. On the 9x9 board, bots are perhaps equal with professionals, or just behind them. On 19x19, they regularly win with 4 stone handicaps. See: http://www.computer-go.info/h-c/index.html http://www.computer-go.info/h-c/index.html
    - RBerenguel 12y ago
      Bots are still somewhat behind pros (last February pros scored 4-0 agains bots in 9x9... I love 9x9 so I try to keep up with this :) )
    - rtpg 12y ago
      4 stone is a pretty big handicap (though I can't win against pros with 9 so I guess there's that :))

VLM 12y ago

From the article a criteria often missed in the discussion is "...of all the world’s perfect information games..." Virtually all tabletop grognard games are perfect information games. I say virtually because there might be one I can't think of at this time, maybe a card driven game. I suppose the COIN series is partially imperfect information... Even a noob player can crush an AI trying to play grognard games so usually the computer cheats or is given a massive handicap, like, say, your human controlled division is up against two, maybe three AI divisions. I've played a lot of grognard games both computer and tabletop and I've never found a worthy evenly matched AI opponent although humans can kick my butt. Some computer implementations implement a fog of war which would certainly be imperfect information, but not tabletops or faithful reimplementations of tabletops. A "good" grognard scenario/game doesn't depend on FoW anyway, or at least many people share that belief. You can model a stereotypical grognard game as "chess with a large hex board, more pieces, and wider variety of pieces". I guess that gives some idea what a computer-proof abstract game would look like. "GO" on a 171x171 grid, perhaps, or chess with 50 kinds of pieces.

icegreentea 12y ago
I'm not sure what exactly a grognard game is - but if it's just wargames, off the top of my head Stratego is a game without perfect information. A lot of fun too. The traditional board version takes three participants to play, but computer/electronic versions gets ride of the referee.
- lazyant 12y ago
  I've played lots of board/classic Stratego, you just need the two participants, I don't know what the referee would be for.
  - dllthomas 12y ago
    Apparently there is a related game where battles are decided without revealing the identities of the pieces involved.
gwern 12y ago

clusterfoo 12y ago

Heh, my first thought reading the article was designing a game that is simple, yet inherently difficult for an AI player. Thanks for introducing me to Arimaa!

hyperpape 12y ago
It's quite chesslike, and not really my taste, but it's a good game.

SilasX 12y ago

Depending on your definition of "game", there's also captchas.

dllthomas 12y ago
... and Spin The Bottle!
- notduncansmith 12y ago
  You clearly have outdated software, my computer is a pro at that one.
- SilasX 12y ago
  Captchas are (like Go and the other games) a legit information processing distinguisher between humans and computers; unlike spin the bottle, it's not just an issue of having the right peripherals or social standing. (I know you were probably joking; this is just in case anyone gets the idea that the "captcha game" is just as trivial in this respect as spin-the-bottle.)
  - dllthomas 12y ago
    Certainly the case. I was obviously joking, but thank you for making this distinction more salient - it deserves to be.