Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

AlphaGo Zero: Learning from scratch

deepmind.com

Post reply on HN
Print view View original

301–310 of 324 posts

Re: AlphaGo Zero: Learning from scratch

#301

Post by YeGoblynQueenne »

otabdeveloper1 wrote: post #299
YeGoblynQueenne wrote: post #237

Earlier quoted context omitted.

About those claims- this is from Russel and Norvig, 3d ed. (from 2003, so a way back): Go is a deterministic game, but the large branching factor makes it challeging. The key issues and early literature in computer Go are summarized by Boozy and Cazenave (2001) and Muller (2002). Up to 1997 there were no competent Go programs. Now the best programs play most of their moves at the master level; the only problem is tha…

> the last holdout where humans can still beat computers in board games was GO False, because nobody ever bothered to study modern boardgames rigorously. Modern boardgames have small decision trees but very difficult evaluation functions. (Exactly opposite from computational games like Go.) Modern boardgames can probably be solved by pure brute force calculation of all branches of the tree, but nobody knows if things…

In AI, "board games" generally means classical board games (nim, chess, backgammon, go etc) and "card games" means classical card games (bridge, poker, etc). Russel & Norvig also discuss some less well-known games, like kriegspiel (wargame) if memory serves, but those are all classical at least in the sense that they are, well, quite old.

I've seen some AI research in more modern board games actually. I've read a couple of papers discussing the use of Monte Carlo Tree Search to solve creature combat in Magic: the Gathering and my own degree and Master's dissertation were about M:tG (my Master's was in AI and my degree dissertation was an AI system also).

I don't know that much about modern board games, besides collectible card games, but for CCGs in particular, the game trees are not small. I once calculated the time complexity of traversing a full M:tG game tree as O(b^m * n^m) = 2.272461391808129337799800881135e+5564 (where b the branching factor, m the average number of moves in a game and n the number of possible deck permutations for a 60 card deck taking into account cards included multiple times). And mine was probably a very conservative estimate.

Also, to my knowledge, Neural nets have not been used for magic-playing AI (or any other CCG playing AI). What has been used is MCTS, on its own, without terrible success. The best AI I've seen incorporates some domain knowledge, in the form of card-specific strategies (how to play a given card).

There are some difficulties in using ANNs to make an M:tG AI. Primarily, the fact that a truly competent player should be able to pick up a card it's never seen before and play it correctly (or decide whether to include it in a deck, if the goal is to also address deck-building). For this, the AI player will need to have at least some understanding of M:tG's language (ability text). It is my understanding that other modern games have equal requirements to understand some game context outside of the main rules, which complicates the traditional tactic of generating all possible moves, pruning some and choosing the best.

In any case what I meant to say is that people in AI have indeed considered other games besides the classical ones- but when we talk about "games" in AI we do mean the classics.

Re: AlphaGo Zero: Learning from scratch

#302

Post by Spare_account »

kndyry wrote: post #104
aeleos wrote: post #52

The fact that they only used self play with no outside input here is really interesting. I wonder if this system produced more new styles of play. While I am not that familiar with Go, I know in some of the other articles they talk about things like Chinese starts that are specific to certain cultures. I wonder if the fact that it had no outside reinforcement made it produce movements that we have already seen that a…

I don't think it's an overstatement to say that, since playing Lee Sedol in 2016, AlphaGo has completely revolutionized professional and amateur go. It's certainly not unprecedented — the last major revolution happened in the early 20th century (often called the 'Shin Fuseki' era [0]) — but AlphaGo has demonstrably surpassed any previous high-water mark. > I wonder if this system produced more new styles of play. Abs…

With respect to your very interesting comment (I genuinely appreciate your input), you appear to have mis-understood the comment you were replying to.

You've commented on the differences in the style of play that AlphaGo introduced, but the post you were replying to (by aeleos) was going a step further and hypothesising about the potential for a newer, completely 'non-human' style that AlphaGo Zero may have created.

Your comments definitely contribute to the discussion but it was bugging me that there appeared to be a tangent forming about AlphaGo that was overlooking AlphaGo Zero which would be the more interesting area to explore.

Re: AlphaGo Zero: Learning from scratch

#303

Post by otabdeveloper1 »

YeGoblynQueenne wrote: post #301
otabdeveloper1 wrote: post #299

Earlier quoted context omitted.

> the last holdout where humans can still beat computers in board games was GO False, because nobody ever bothered to study modern boardgames rigorously. Modern boardgames have small decision trees but very difficult evaluation functions. (Exactly opposite from computational games like Go.) Modern boardgames can probably be solved by pure brute force calculation of all branches of the tree, but nobody knows if things…

In AI, "board games" generally means classical board games (nim, chess, backgammon, go etc) and "card games" means classical card games (bridge, poker, etc). Russel & Norvig also discuss some less well-known games, like kriegspiel (wargame) if memory serves, but those are all classical at least in the sense that they are, well, quite old. I've seen some AI research in more modern board games actually. I've read a cou…

> but when we talk about "games" in AI we do mean the classics

Only because of inertia. There's nothing inherently special about "classics". Eventually somebody will branch out once Go and poker are mined out of paper and article opportunity.

Once we do then maybe some new, interesting algorithms will be found.

In principle, every game can be solved by storing all possible game states in a database. Where brute-force storing is impractical due to size concerns, compression tricks have to be used.

E.g., Go is a simple game because at the end, every one of the fixed number of board spaces is either +1, -1 or 0. Add them up and you know if you won. This means that every move is either "correct" or "incorrect"; the problem of classifying multidimensional objects into two classes is a problem that we're pretty good at now, and things like neural networks get the job done.

A slightly more complex game like Agricola has no "correct" and "incorrect" moves because it's not zero-sum; you can make an "incorrect" move and still win as long as your opponent is forced to make a relatively more "incorrect" move.

Not sure how much of a difference that makes, but what's certain is that by (effectively) solving Go we've only scratched the surface. It's not the end of research, only the beginning.

Re: AlphaGo Zero: Learning from scratch

#304

Post by YeGoblynQueenne »

otabdeveloper1 wrote: post #303
YeGoblynQueenne wrote: post #301

Earlier quoted context omitted.

In AI, "board games" generally means classical board games (nim, chess, backgammon, go etc) and "card games" means classical card games (bridge, poker, etc). Russel & Norvig also discuss some less well-known games, like kriegspiel (wargame) if memory serves, but those are all classical at least in the sense that they are, well, quite old. I've seen some AI research in more modern board games actually. I've read a cou…

> but when we talk about "games" in AI we do mean the classics Only because of inertia. There's nothing inherently special about "classics". Eventually somebody will branch out once Go and poker are mined out of paper and article opportunity. Once we do then maybe some new, interesting algorithms will be found. In principle, every game can be solved by storing all possible game states in a database. Where brute-force…

Sure. Research in game playing AI doesn't end with Go, or any other game. We may see more research in modern board games, now that we're slowly running out of the classics.

I think you're underestimating the amount of work and determination it took to get to where we are today, though (I mean your comment about "inertia"). Classic board games have the advantage of a long history and of being well understood (the uncertainty about optimal strategies in Go notwithstanding). Additionally, for at least some of them like chess, there are rich databases of entire games that can be used outright, without the AI player having to generate-and-test them in the process of training or playing.

The same is not true for modern games. On the one hand, modern board games like Agricola (or, dunno, Settlers or Carcassonne etc) don't have such an extensive and multi-national following as the classics so it's much harder to find a lot of data to train on (which is obviously important for machine-learning AI players). I had that problem when considering an M:tG AI trained with machine learning: I would have liked to find play-by-play data on professional games but there just isn't any (or where there is it's not enough, or it's not in any standardised format).

Finally, classic board games have cultural significance that modern board games dont' quite match, despite the huge popularity of CCGs like M:tG or Pokemon, or Eurogame hits like Settlers. Go, chess and backgammon in particular have tremendous historical significance in their respective areas of the world- chess in Eastern Europe, backgammon in the Middle East, Go in SE Asia. People go to special academies to learn them, master players are widely recognised etc. You don't get that level of interest with modern board games- so there's less research interest for them, also.

People in game playing AI have been trying for a very long time to crack some games like Go and, recently, poker (not quite cracked yet). They didn't sit around twiddling their thumbs all those years, neither did they choose classical board games over modern ones just because they didn't have the imagination to think of the latter. In AI research, as in all research, you have to make progress before you can make more progress.

Re: AlphaGo Zero: Learning from scratch

#305

Post by mdemare »

otabdeveloper1 wrote: post #298
geofft wrote: post #28

Earlier quoted context omitted.

... yeah, before reading that link my position was "Wow, that's super neat, but Go is a pretty well-defined game," and after reading it I remembered that my position maybe a year or two ago was "Chess is a well-defined game that's beatable by AI techniques but Go is acknowledged to be much harder and require actual intelligence to play and won't be solved for a long while" and now I'm worried. Thanks for posting that…

> Go is acknowledged to be much harder and require actual intelligence to play No, Go is a much less intelligent[1] game. It has a huge decision tree and requires massive amounts of computation to play, but walking trees and counting is exactly what computers do well and what humans do poorly. [1] 'Intelligence' here means exactly that which differentiates humans from calculators: the ability to infer new rules from…

Nobody was saying that before AlphaGo beat Lee Sedol. So this feels like moving the goalposts.

Re: AlphaGo Zero: Learning from scratch

#306

Post by gliptic »

YeGoblynQueenne wrote: post #292
gliptic wrote: post #282

Earlier quoted context omitted.

So you don't think they're doing anything worthwhile at https://intelligence.org/ . I'm going to guess you actually have no idea and are just extrapolating from some articles you read. What are _you_ doing to make legitimate concerns heard then? Did you even read the article you were complaining about?

Yes, I did and it's very bad form to go around asking people if they read the article. Try to remember that different people form different opinions from similar information.

Well, then you should have noticed what the article was about, which was not to detail a research program about AI safety. Different articles can address different aspects of a problem without being accused of advocating "random action". That's just ridiculous.

Re: AlphaGo Zero: Learning from scratch

#307

Post by fjsolwmv »

Houshalter wrote: post #259
ollin wrote: post #212

Earlier quoted context omitted.

>As far as we know the brain is just a "linear algebra blackbox"...Likely they use similar principles. I'm not an expert, but my impression is that this is not really a reasonable claim, unless you're only considering very small function-like subsystems of the brain (e.g. visual cortex). Neural nets (of the nonrecurrent sort) are strict feed-forward function approximators, whereas the brain appears to be a big mess o…

There are some parts of the brain we have no clue about. Episodic memory or our higher level ability to reason. But most of the brain is just low level pattern matching just like what NNs do. The constraints you mention aren't deal breakers. We can make RNNs without maintaining a global state and fully unrolling the loop. See synthetic gradients for instance. NNs can do unsupervised learning as well, through things l…

A pattern matcher can learn high level reasoning. Reasoning is just a boolean circuit

Re: AlphaGo Zero: Learning from scratch

#308

Post by fjsolwmv »

aeleos wrote: post #123
ionforce wrote: post #108

Earlier quoted context omitted.

Is there meaningful information in what one observes?

Yes, it turns out you can find meaningful information. etiam provided this https://arxiv.org/pdf/1312.6034.pdf The main issue is making sure what you are looking for is actually what the network is doing. You have to correctly interpret and visualize a jumble of numbers, which usually requires a hypothesis about how it worked in the first place. But assuming both go well you can gain meaningful information.

Can I train an NN to visualize the numbers?

Re: AlphaGo Zero: Learning from scratch

#309

Post by fjsolwmv »

derefr wrote: post #229
pmontra wrote: post #159

Earlier quoted context omitted.

Agreed. I know I'm winning by 4 points but I have no idea about my probability of winning. However if I'm winning I know that I should play low risk moves and refrain from starting complicated fights. That increases the probability of winning. IMHO the exact value is out of reach for human beings.

It would be interesting to play human go, assisted by a go computer that doesn't say anything about moves, but rather just spits out, for each player, their current likelihood of victory if all further moves by both players were "what it would do." That way, each player could know, at all times, (one major factor that goes into) their probability of winning. They'd still have to mentally adjust it for the likelihood…

Ha, like watching someone play a game and moaning or cheering at their plays.

Re: AlphaGo Zero: Learning from scratch

#310

Post by fjsolwmv »

hasenj wrote: post #203
roenxi wrote: post #138

Earlier quoted context omitted.

The Go community learned to understand that the margin of victory is meaningless along time ago. The most famous game of Honinbo Dosaku, a famous Go player from the late 1600s, is arguably a game where he gave a handicap to his opponent and lost by one point. Lee Chang-Ho, who was the reigning champion in the late 90s, had a style that consistently tried to win by small margins. AlphaGo now appears to be better than…

I think if AlphaGo foresaw it was losing by one point, it would start playing reckless moves, as it did against Lee-Sedol in the only match it lost against him.

Risky, not reckless.
Post reply on HN