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...)
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.
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.
"Poker" is a much broader category than "two-player, unlimited stakes, no-limit hold-em."
Particularly, it's usually a multiplayer game at the outset, and has many varieties other than hold 'em (which just happens to be the currently—and this is a fairly recent development—popular form.)
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".
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.
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.
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-huma.... And that game probably has more hidden state than stratego.
>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.
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).
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.
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.
(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...)