Now that Go and Chess are efficiently solved for AI...what's next? Are there any other interesting complete information games remaining? What's the next milestone for incomplete information games?
I'd like to see an AI that can learn things related to what it already knows with very little training, like humans can do.
Take chess. There's a chess variant that is popular between rounds at tournaments, called "bughouse". It's played by two teams of two, using two chess sets and two clocks. One member of the team plays white on one of the boards, and the other plays black on the other board.
For the most part, the game on each board follows the normal rules of chess. Whichever individual game ends first determines the outcome of the combined game. The teammates may talk to each other and collaborate during the game.
The big difference between the game on each board and a regular game of chess is that on your turn you can, instead of making a move on the board, pick up any piece that your partner has captured, and drop it anywhere on your board (with some restrictions, such as pawn cannot be dropped on the first or eight rank).
If you take a human who has learned to play chess to a certain level, and who has never played (or even heard of) bughouse, and explain the rules to them and then have them start playing it only takes them a little while to get about as good as they are at normal chess.
The human quickly figures out what chess knowledge transfers directly to bughouse, which needs tweaking, and which needs to be thrown out. As far as I know, current AI cannot do that--to it bughouse is a completely new game.
It seems like one approach is to use markov networks to establish statistical relationships between models.
https://en.wikipedia.org/wiki/Transfer_learning http://www.cs.utexas.edu/users/ai-lab/?Transfer
How about axioms of logic as legal moves, and asking it to go from a set of axioms to open mathematical problems?
Or chemical procedures and components as moves, and asking it to tackle a disease with a known molecular structure?
It is not as straightforward as I make it sound, but these are complete information problems.
I'm not sure how you could train it against itself. The branching factor would be infinite as well so I don't know how you'd constrain the legal moves. For example, maybe rewriting (a * 2) to (a + a) or (a * 4 - a * 2) and so on for every theorem you know would be useful in a proof, plus you can invent your own theorems as intermediate steps.
>Or chemical procedures and components as moves, and asking it to tackle a disease with a known molecular structure?
>It is not as straightforward as I make it sound, but these are complete information problems.
However they are not adversarial games. Self-play only works for adversarial games. Also each mathematical problem is different and needs to be solved only once, and likewise for molecular structures. Additionally, they only need to be solved once, so there is no "gradient of skill" that we know to climb.
You can extend this idea to full first-order intuitionistic logic and probably also to higher-order logics, as well as many different modal logics. There are also formulations of classical logic as a single player game, but that doesn't seem to be very useful here.
While chess if very complicated to play, the state can be represented by (at worst) an 8x8x6 boolean array (board, one of 6 possible pieces), for go a 17x17x2 boolean array. There is nothing similar for logic and and deep learning breaks down (in my experience) once you don't have that nice regular input space.
Chess is not "solved." Solving chess would mean knowing with absolute certainty the best move in any position. It would also mean knowing the best first move. We do not have technology with the computational capability to "solve chess." We have technology that can play chess better than any human, but that's not the same as solving it.
I think the best current Poker AI (which can beat good humans) doesn't use neural networks, but expect that combing counterfactual risk minimization with neural networks shouldn't bee too hard.
RTS games should be the next bigger challenge. Not only do they have incomplete information, you also have to handle widely different scales (both space and time) and have a large number of units. I expect this to require an interesting new approach to integrate large scale strategies with small scale tactics without getting stuck in local strategy optima.
Cleaning toilets? I would love to see AI doing degrading but useful work. Sadly, all we get is computers playing board games.
EDIT: YC is doing UBI experiments now. How about funding startups building menial labor robots, then passing the savings on to the humans who used to do the work?
Imperfect information games seem like a much more interesting challenge though.
> pip install pysc2
StarCraft BroodWar also has a more mature AI scene[1].
Facebook even tried their hands at a bot this year ending 6/28. Only 2 teams made the top 10, with 15 entries being from independent developers[2].
[0]: https://github.com/deepmind/pysc2
[1]: http://www.starcraftai.com/wiki/Main_Page
[2]: https://www.digitaltrends.com/computing/facebook-cherrypi-ai...
Starcraft 2 state is much bigger than Go's and requires real time action. Also, actions have to be performed in parallel in real time, which probably requires different techniques and probably puts a way lower bound on number of iterations doable in given time.
> state is much bigger.
Can AlphaGo not care about it and just play better and faster?
I think AI does have an advantage once it starts to be competent, especially if it's interacting through APIs exclusively and not the interface, which means that it's actions per minute could be astronomically higher than a human player, with unheard of levels of micro. At the same time, I think machine learning is almost an idea solution to figuring out build orders. It's gonna be fast and smart. Question just is how long?
There's no way they'll compete under unlimited APM rules, it wouldn't even be remotely interesting. We're trying to match wits with the AI, not the inertia and momentum of super slow fingers, keys, and mouse.
I'm sure they'll come up with an "effective APM" heuristic which compares similarly to top pros, and feed it as a constraint to the AI.
For AI vs AI it could be interesting to see what strategies develop with two opponents with the ability to perfectly microcontrol their units.
[0]Zerglings vs Siege Tanks when controlled by AI with perfect micro.
Otherwise, you make a fair point and that video is amazing. AI vs AI strategy with unlimited APM would be very exciting to watch.
For example the "All ravens, all the time" Terran player Ketrok just responded to the surge in popularity of Cannon Rushes by making a tiny tweak to his opening worker movement. The revised opening spots the Cannon Rush in time to adequately defend and thus of course win.
I'd be interested to see if it can "plan ahead". Maybe a Chess variant where you have to submit your next move before the current player moves, or something like that.
As far as I understand (and I am no expert at all), AlphaGo basically creates a heuristic of what move to play in a given situation (which heurisitic is created by playing against itself many, many times). Instead of trying to "break" the game, they just decided to simulate playing and results were good enough to outmatch humans, but we have no idea how close to the "perfect game" AlphaGo actually got.
But - whole input to a network is 19x19 array with 3 possible states per cell, plus maybe turn count and one bit for determining whose next move is. S2 network should process graphic stream (lets say 1280/720), needs spatial awareness(minimap), priority setting and computational resource management. And it has to be fast enough in the first place just to follow the game.
I'm not saying that won't happen (who predicted Go breakthrough?), but it at least seem like a much bigger challenge.
When AlphaZero plays Go with itself, it can basically go as fast as it can calculate next move. With Starcraft that's not the case - both networks have to work in sync, probably need some temporal awareness and probably will have some limit of actions per time fraction, which basically requires a whole new approach. Of course, I can be gravely mistaken, but I would like to now how they can circumvent this.
It will probably lead to interesting challenges.
I would love to see it tackle my favorite RTS (Supreme Commander) but really, what would be interesting would be to have it attack 'real life' problems :
-logistics
-subway circulation
-city planning
-detect diseases
-optimize the energy efficiency of a building.
(just armchair opinion, I don't know how well suited AZ would be to these problems. I do know that AI has already helped with some of these though)
Not really, given that they already tried Shogi too. Personally I would love to see AlphaZero playing Arimaa, but it is probably not as interesting because of its short history.
I actually prefer "expert iteration" and "tree-policy target" term instead of "AlphaZero algorithm", because they emphasize what is novel about it among the entire system. Terms are from https://arxiv.org/abs/1705.08439
The game models for each Alpha Zero (Chess, Shogi, and Go) look to have been created by a human, as well as the input and output translation (e.g., a human would need to intervene[1] to help AZ Chess to play and win Atari 2600 Video Chess).
[1] Intervene by doing the translation by the human or by writing a program to convert AZ I/O to Atari 2600 I/O.
Checkers is solved.
mmm, this gives me a idea. Do anybody know of a procedurally generated rts.
Something like Starcraft 2; multiplayer action-rts, massive army coordination, with mikro, makro and meta game mechanics. On a randomly generated map?
So you will still have a good idea where the guy spawn. But your now forced to scout to see where to take engagements and not.
The players even get to choose which maps they'll play (by eliminating some map if they feel it's unfair) and in which order...