9 ms·

I'm surprised how slow the press has been to pick this up. This seems like an amazing step forward to me. AlphaZero played only against itself as training and i

I'm surprised how slow the press has been to pick this up. This seems like an amazing step forward to me. AlphaZero played only against itself as training and it beat one of the best chess AIs in the world that has been finely tuned with decades worth of human knowledge. 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?

sanxiyn 9y ago
> Are there any other interesting complete information games? 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.
- Filligree 9y ago
  Well, there's math. Mapping it to AZ and finding a decent "win" function might be hard, but it's a complete information something, certainly.
  - sanxiyn 9y ago
    Quick, someone apply AlphaZero algorithm to this MCTS prover for math: https://arxiv.org/abs/1611.05990 https://arxiv.org/abs/1611.05990 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 https://arxiv.org/abs/1705.08439
animal531 9y ago
The interesting thing for me (apart from the very short training period) is that this seems to be a more generalised version of their previous AlphaGo engine, which means that in future it should be even easier to adapt and use for other tasks.
317070 9y ago
> Are there any other interesting complete information games? 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.
- seanwilson 9y ago
  > How about axioms of logic as legal moves, and asking it to go from a set of axioms to open mathematical 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.
- rhaps0dy 9y ago
  >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. 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.
  - fmap 9y ago
    Theorem proving in intuitionistic logic is a two-player game and maps perfectly to the kind of Monte-Carlo Tree Search that's employed here. Except that it is far more difficult than Chess/Go/etc., since the branching factor is essentially unbounded.
    - seanwilson 9y ago
thomasahle 9y ago
There is always Infinite Chess https://en.wikipedia.org/wiki/Infinite_chess https://en.wikipedia.org/wiki/Infinite_chess and other games with complete information, but unbounded state. (Or even just bounded, but finite, such as Hex.) Monte Carlo + NN seems like a good approach, so maybe it'd be worth a go. Imperfect information games seem like a much more interesting challenge though.
username223 9y ago
> Now that Go and Chess are efficiently solved for AI...what's next? 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?
- ouid 9y ago
  they're better than humans but they aren't solved.
- joefkelley 9y ago
  Menial labor robots will come whether YC funds them or not, so they better work on UBI to prepare for that.
VikingCoder 9y ago
Relevant XKCD: https://xkcd.com/1002/ https://xkcd.com/1002/
- TulliusCicero 9y ago
  I question whether the author has actually played Starcraft. It's clearly vastly more complicated from an AI perspective than games like Chess or Go, and this has been obvious for some time.
  - forgot-my-pw 9y ago
    It is, but these real time strategy games are also vastly difficult for human players. The bar is just to beat human pros, not to play perfectly.
TulliusCicero 9y ago
DeepMind has partnered with Blizzard to work on Starcraft 2 AI. That will probably take a long time to get something that can defeat professionals.
- b4lancesh33t 9y ago
  Probably. On the other hand, it wasn't five years ago where a majority of randos on the internet thought that AI would never defeat top humans at Go. (Sorry for citing such an unimportant population, but it is the one I'm a part of and whose opinions I have access to.)
  - d3ckard 9y ago
    While I wouldn't exclude possible breakthrough, it's definitely a different case. Go was feared because of an enormous number of possible states, but AlphaGo circumvented the issue by not caring about it. It didn't "solve" Go, it just plays it better than humans. 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.
    - alphydan 9y ago
      Could a similar strategy apply then? > state is much bigger. Can AlphaGo not care about it and just play better and faster?
      - Raidion 9y ago
        In SC there are time constraints in that you're getting resources at a certain rate. You have to grow your capacity to pull resources and at the same time be building units to defend yourself. If you allocate resources poorly, you'll find yourself losing. AlphaGo can't ignore that, but... 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?
barkingcat 9y ago
Get these AI working on P=NP.
dmitriid 9y ago
I guess Starcraft and other video games, especially procedurally generated games where the ruleset may bi fixed, but the playing field is not.
- oneweekwonder 9y ago
  > especially procedurally generated games 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?
  - tudelo 9y ago
    Imagine how extremely frustrating it would be to have a bad base position in comparison to your enemy, or your enemy having an island-like terrain when you build all ground units and could not scout quick enough...
    - oneweekwonder 9y ago
      True. But I was thinking in the context of sc where the maps is normally mirrors of each other. 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.
      - RepressedEmu 9y ago
        Procedurally generated but still symmetrical maps would actually be really interesting. It would be like having a new battleground to explore every match without giving an advantage to either side.
        kilburn 9y ago
        Symmetry is not the only map characteristic that gives advantages to one race over another. Terran is really good at sieging, Zerg is good at expanding early, Protoss is very bad at defending open bases, etc.. The pro-played maps are carefully designed to balance all that, and when they fail the players themselves limit their strategies according to what works and what doesn't on each map. 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...
king07828 9y ago
Still need to solve the game model development problem and the I/O problem. 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.
tzs 9y ago
> Now that Go and Chess are efficiently solved for AI...what's next? 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.
- thatcat 9y ago
  Transfer learning is the name of this concept. [0] It seems like one approach is to use markov networks to establish statistical relationships between models. https://en.wikipedia.org/wiki/Transfer_learning https://en.wikipedia.org/wiki/Transfer_learning http://www.cs.utexas.edu/users/ai-lab/?Transfer http://www.cs.utexas.edu/users/ai-lab/?Transfer
- dkonofalski 9y ago
  Does it really matter that it views bughouse as a new game? If it can still learn it in a matter of hours as an entirely new game then, although there's probably efficiency that could be gained from knowledge transfer, I can't really imagine it would need to figure that out until after it's done. I would think that, once it's figured out how to play a few games from scratch, it can check to see what commonalities those have and then apply them to even more games/ideas/processes.
oneweekwonder 9y ago
Another poster already mentioned deepmind and starcraft2[0]. I want to mention it uses python and is a pip package. > 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 https://github.com/deepmind/pysc2 [1]: http://www.starcraftai.com/wiki/Main_Page http://www.starcraftai.com/wiki/Main_Page [2]: https://www.digitaltrends.com/computing/facebook-cherrypi-ai-bit-loses-starcraft-brood-war/ https://www.digitaltrends.com/computing/facebook-cherrypi-ai...
CodesInChaos 9y ago
I'd like to see a game where each player can take a variable number of actions each move. For example, Risk. (Probably not too difficult an enhancement) 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.
RockofStrength 9y ago
One idea is Bongard problems, because they are purely creative categorization, so it's interesting for AI. http://www.foundalis.com/res/bps/bpidx.htm http://www.foundalis.com/res/bps/bpidx.htm
mulmen 9y ago
That's not why humans play games so why should it be for AI? We didn't consider running "solved" after the first Olympic games. AlphaZero is just better than any other algorithm at this time. A year ago that wasn't the case, in a year it may also not be the case. We learned something about developing AIs here which we can apply to the next. That doesn't mean Chess and Go are of no value to AI researchers, it shows that they are fertile ground for discovery.
carc 9y ago
Neither go nor chess are solved
supermdguy 9y ago
Life
WoodenChair 9y ago
>Now that Go and Chess are efficiently solved for AI...what's next? 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.
wglb 9y ago
Neither Chess or Go are solved. Checkers is solved.
on_and_off 9y ago
It seems that Alpha Go is now aiming Starcraft 2. 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)
chongli 9y ago
I'd like to see an AI figure out how to beat Zelda for the NES without being given any information specific to the game. This is something pretty much any human can do yet it appears daunting for AI.

sanxiyn 9y ago

> Are there any other interesting complete information games? 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.

Filligree 9y ago
Well, there's math. Mapping it to AZ and finding a decent "win" function might be hard, but it's a complete information something, certainly.
- sanxiyn 9y ago
  Quick, someone apply AlphaZero algorithm to this MCTS prover for math: https://arxiv.org/abs/1611.05990 https://arxiv.org/abs/1611.05990 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 https://arxiv.org/abs/1705.08439

animal531 9y ago

The interesting thing for me (apart from the very short training period) is that this seems to be a more generalised version of their previous AlphaGo engine, which means that in future it should be even easier to adapt and use for other tasks.

317070 9y ago

> Are there any other interesting complete information games? 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.

seanwilson 9y ago
> How about axioms of logic as legal moves, and asking it to go from a set of axioms to open mathematical 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.
rhaps0dy 9y ago
>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. 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.
- fmap 9y ago
  Theorem proving in intuitionistic logic is a two-player game and maps perfectly to the kind of Monte-Carlo Tree Search that's employed here. Except that it is far more difficult than Chess/Go/etc., since the branching factor is essentially unbounded.
  - seanwilson 9y ago

thomasahle 9y ago

There is always Infinite Chess https://en.wikipedia.org/wiki/Infinite_chess https://en.wikipedia.org/wiki/Infinite_chess and other games with complete information, but unbounded state. (Or even just bounded, but finite, such as Hex.) Monte Carlo + NN seems like a good approach, so maybe it'd be worth a go. Imperfect information games seem like a much more interesting challenge though.

username223 9y ago

> Now that Go and Chess are efficiently solved for AI...what's next? 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?

ouid 9y ago
they're better than humans but they aren't solved.
joefkelley 9y ago
Menial labor robots will come whether YC funds them or not, so they better work on UBI to prepare for that.

VikingCoder 9y ago

Relevant XKCD: https://xkcd.com/1002/ https://xkcd.com/1002/

TulliusCicero 9y ago
I question whether the author has actually played Starcraft. It's clearly vastly more complicated from an AI perspective than games like Chess or Go, and this has been obvious for some time.
- forgot-my-pw 9y ago
  It is, but these real time strategy games are also vastly difficult for human players. The bar is just to beat human pros, not to play perfectly.

TulliusCicero 9y ago

DeepMind has partnered with Blizzard to work on Starcraft 2 AI. That will probably take a long time to get something that can defeat professionals.

b4lancesh33t 9y ago
Probably. On the other hand, it wasn't five years ago where a majority of randos on the internet thought that AI would never defeat top humans at Go. (Sorry for citing such an unimportant population, but it is the one I'm a part of and whose opinions I have access to.)
- d3ckard 9y ago
  While I wouldn't exclude possible breakthrough, it's definitely a different case. Go was feared because of an enormous number of possible states, but AlphaGo circumvented the issue by not caring about it. It didn't "solve" Go, it just plays it better than humans. 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.
  - alphydan 9y ago
    Could a similar strategy apply then? > state is much bigger. Can AlphaGo not care about it and just play better and faster?
    - Raidion 9y ago
      In SC there are time constraints in that you're getting resources at a certain rate. You have to grow your capacity to pull resources and at the same time be building units to defend yourself. If you allocate resources poorly, you'll find yourself losing. AlphaGo can't ignore that, but... 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?

barkingcat 9y ago

Get these AI working on P=NP.

dmitriid 9y ago

I guess Starcraft and other video games, especially procedurally generated games where the ruleset may bi fixed, but the playing field is not.

oneweekwonder 9y ago
> especially procedurally generated games 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?
- tudelo 9y ago
  Imagine how extremely frustrating it would be to have a bad base position in comparison to your enemy, or your enemy having an island-like terrain when you build all ground units and could not scout quick enough...
  - oneweekwonder 9y ago
    True. But I was thinking in the context of sc where the maps is normally mirrors of each other. 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.
    - RepressedEmu 9y ago
      Procedurally generated but still symmetrical maps would actually be really interesting. It would be like having a new battleground to explore every match without giving an advantage to either side.
      - kilburn 9y ago
        Symmetry is not the only map characteristic that gives advantages to one race over another. Terran is really good at sieging, Zerg is good at expanding early, Protoss is very bad at defending open bases, etc.. The pro-played maps are carefully designed to balance all that, and when they fail the players themselves limit their strategies according to what works and what doesn't on each map. 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...

king07828 9y ago

Still need to solve the game model development problem and the I/O problem. 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.

tzs 9y ago

> Now that Go and Chess are efficiently solved for AI...what's next? 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.

thatcat 9y ago
Transfer learning is the name of this concept. [0] It seems like one approach is to use markov networks to establish statistical relationships between models. https://en.wikipedia.org/wiki/Transfer_learning https://en.wikipedia.org/wiki/Transfer_learning http://www.cs.utexas.edu/users/ai-lab/?Transfer http://www.cs.utexas.edu/users/ai-lab/?Transfer
dkonofalski 9y ago
Does it really matter that it views bughouse as a new game? If it can still learn it in a matter of hours as an entirely new game then, although there's probably efficiency that could be gained from knowledge transfer, I can't really imagine it would need to figure that out until after it's done. I would think that, once it's figured out how to play a few games from scratch, it can check to see what commonalities those have and then apply them to even more games/ideas/processes.

oneweekwonder 9y ago

Another poster already mentioned deepmind and starcraft2[0]. I want to mention it uses python and is a pip package. > 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 https://github.com/deepmind/pysc2 [1]: http://www.starcraftai.com/wiki/Main_Page http://www.starcraftai.com/wiki/Main_Page [2]: https://www.digitaltrends.com/computing/facebook-cherrypi-ai-bit-loses-starcraft-brood-war/ https://www.digitaltrends.com/computing/facebook-cherrypi-ai...

CodesInChaos 9y ago

I'd like to see a game where each player can take a variable number of actions each move. For example, Risk. (Probably not too difficult an enhancement) 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.

RockofStrength 9y ago

One idea is Bongard problems, because they are purely creative categorization, so it's interesting for AI. http://www.foundalis.com/res/bps/bpidx.htm http://www.foundalis.com/res/bps/bpidx.htm

mulmen 9y ago

That's not why humans play games so why should it be for AI? We didn't consider running "solved" after the first Olympic games. AlphaZero is just better than any other algorithm at this time. A year ago that wasn't the case, in a year it may also not be the case. We learned something about developing AIs here which we can apply to the next. That doesn't mean Chess and Go are of no value to AI researchers, it shows that they are fertile ground for discovery.

carc 9y ago

Neither go nor chess are solved

supermdguy 9y ago

Life

WoodenChair 9y ago

>Now that Go and Chess are efficiently solved for AI...what's next? 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.

wglb 9y ago

Neither Chess or Go are solved. Checkers is solved.

on_and_off 9y ago

It seems that Alpha Go is now aiming Starcraft 2. 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)

chongli 9y ago

I'd like to see an AI figure out how to beat Zelda for the NES without being given any information specific to the game. This is something pretty much any human can do yet it appears daunting for AI.