Google reveals secret test of AI bot to beat top Go players • Hacker News Board

Re: Google reveals secret test of AI bot to beat top Go players

#181

Post by inimino » Thu, Jan 05, 2017, 5:02 PM UTC

malteof wrote: post #149

inimino wrote: post #141

Earlier quoted context omitted.

Games like go and chess are necessarily solveable by definition, right? If you mean solveable in our lifetimes, by current technology, that's something else entirely, and much less likely. Beating human players in go is like finding a good heuristic for an NP-complete problem. Solving 19*19 go is like proving P!=NP, i.e. we don't even have tools that can approach the problem.

Not sure if this is true for Go. I'm not sure, but it seems to me that at some point a problem becomes "too complex" to solve. I.e. Go has about 2.08168199382×10^170 legal positions [1] and the number of atoms in the observable universe is only up to ~4×10^81. I don't know if there are some theorems, thoughts, philosophies about whether this means it can't be solved, but at least it must be extremely difficult. [1] h…

In a theoretical sense, Go is certainly solvable, as we can easily construct a Turing machine that plays out every possible move, and provably terminates (given an appropriate ruleset). Practically, the universe will certainly be expected to terminate first.

There may be other ways to solve the game, but we don't know what they are. Because we know it is theoretically solvable, we cannot rule out a practical approach to solving it by some mathematical magic even if we have no idea what that would look like.

By analogy, we can prove many things about infinitely many integers by mathematical induction, but if we didn't have that technique, such proofs might seem impossible.

Re: Google reveals secret test of AI bot to beat top Go players

#182

Post by conanbatt » Thu, Jan 05, 2017, 5:04 PM UTC

thomasahle wrote: post #152

conanbatt wrote: post #127

Earlier quoted context omitted.

As a semi-pro player I can assure you thats not how you play Go.

Interesting. From chess it seems that, for important matches, players will deeply study each other's games and try to get the other player into positions that they may be less used to playing and less comfortable with. Is this not done in go?

Its more important to smoothen out your own weaknesses than looking for your opponents. A weakness in your style of play is going to make you lose way more many games than your ability to find some weaknesses in some other player.

To become a pro you have to go through insane levels of competitions, you need to be strong, not find a weakness in the 100's of players you will face to just have a shot to become the lowest level of professional.

Re: Google reveals secret test of AI bot to beat top Go players

#183

Post by hyperpape » Thu, Jan 05, 2017, 5:35 PM UTC

stouset wrote: post #78

dfan wrote: post #7

One thing that isn't made clear in this writeup is that Master plays in a very nonhuman style, as opposed to the version of AlphaGo that beat Lee Sedol, which mostly played like a strong human except for a few surprising moves. My first guess when I saw Master's games was that it was a program like AlphaGo that had its policy network trained from scratch rather than being bootstrapped by being given the goal of imita…

As computers are able to evaluate positions faster (and therefore deeper), the "godlike" tactics are dominating over human-style strategy. It used to be that computers played "computer-like" moves because they didn't understand the position. Now, they play computer-like moves because "understanding" the position isn't as important as just being able to see 25+ moves ahead. In a nutshell, positional play in chess is s…

I would not describe the moves dfan is talking about as tactical. Rather, they appear to exhibit a very different positional judgment from what humans use/different strategic aims.

What you say sounds plausible, but I do not believe it is backed up by any analysis of the games.

Re: Google reveals secret test of AI bot to beat top Go players

#184

Post by hyperpape » Thu, Jan 05, 2017, 5:37 PM UTC

Radim wrote: post #154

ogrisel wrote: post #150

Earlier quoted context omitted.

Maybe it does not use the same opening style when it plays against a version of itself. It would be very interesting to have pro-players comment on published records of alphago self-play. Maybe alphago has discovered a new balance between black and white (that is a new optimal value of the komi) but when playing with the human defined of the value of the komi its optimal style is also different than what it would be…

You mean, like these three AlphaGo self-play games from September? ;) https://deepmind.com/research/alphago/alphago-games-english/ (analysis by Gu Li and Zhou Ruiyang, two top pros; standard komi)

Note that these games look much more human than the ones dfan was describing. There are surprising ideas, but they are still much more normal.

Re: Google reveals secret test of AI bot to beat top Go players

#185

Post by fryguy » Thu, Jan 05, 2017, 5:46 PM UTC

btilly wrote: post #124

fryguy wrote: post #123

Earlier quoted context omitted.

Complex is being used in a different context here though. You are meaning complex as in strategic complexity. The parent (I think) is using it in terms of the games rules. Go is pretty simple in principle: place stones on the board one at a time, and remove enemy pieces completely surrounded by your own. But it's fairly complex to know what exactly constitutes being surrounded. Chess has 6 different kinds of pieces t…

Checkers has adjusted its Elo system over time. I believe that it now matches chess except with a floor of a 1000 rating. From http://icheckers.net/ratings/ , the current ratings range goes from 1000 to 2297 among active players, and up to 2510 among inactive players. Even if you use the larger range of inactive players, that's a range of 7.5 times the standard deviation. Which is considerably less than chess.

Tinsley isn't on that list, and I saw it claimed that his rating was 2700: https://en.wikipedia.org/wiki/Marion_Tinsley

Chess has a floor of 1200 for novices. So I'm not sure your point.

Re: Google reveals secret test of AI bot to beat top Go players

#186

Post by xapata » Thu, Jan 05, 2017, 5:51 PM UTC

dfan wrote: post #7

One thing that isn't made clear in this writeup is that Master plays in a very nonhuman style, as opposed to the version of AlphaGo that beat Lee Sedol, which mostly played like a strong human except for a few surprising moves. My first guess when I saw Master's games was that it was a program like AlphaGo that had its policy network trained from scratch rather than being bootstrapped by being given the goal of imita…

The same thing has happened in poker. The computer plays moves that are "obviously bad" according to human heuristics -- frequent limp opening and donk(ey) betting -- yet the computer is able to incorporate those moves into its strategy successfully.

Re: Google reveals secret test of AI bot to beat top Go players

#187

Post by xapata » Thu, Jan 05, 2017, 5:57 PM UTC

spurgu wrote: post #61

EGreg wrote: post #53

Earlier quoted context omitted.

They solved heads up poker in this manner recently. They claim that the chances anyone can beat this computer in the long run are now infinitesimal. http://poker.srv.ualberta.ca/about

Still a good way to go to beat no limit holdem I'd assume.

A group from CMU appears to have solved no-limit heads-up hold-em. It's only a matter of time (and compute power) for a full ring game.

No-limit is far more difficult than limit due to the risk of catastrophic failure. A Nash equilibrium robot won't make any money. A robot must identify a weakness in you, then deviate from equilibrium to exploit your weakness. So long as you're playing deep stack, you could simply play the Bertrand Russel chicken story (echoing David Hume): The farmer feeds it every day, so the chicken assumes that this will continue indefinitely. One day, though, the chicken has its neck wrung and is killed. It's the "maniac" style. Pretend to be an idiot that plays too many hands. Don't lose your shirt. The robot will learn that you're always bluffing. Eventually you have the nuts and you take everything.

Re: Google reveals secret test of AI bot to beat top Go players

#188

Post by visarga » Thu, Jan 05, 2017, 6:21 PM UTC

pmontra wrote: post #30

MR4D wrote: post #2

This is impressive. According to the article, the bot has not yet lost. I think at the end of 2017, we may have to say that computers have conquered Go. Interesting that the timing is 20 years after mastering chess.

The series is over with a score of 60-0. You can find all the games at http://tieba.baidu.com/p/4922688212?pn=1 It's chinese but the pictures are universal and the comments don't really matter much. By the way, Google Translate makes a pretty horrible work at translating those pages. I think they need to add some more DeepMind to it :-) To be fair, they probably don't have much training data for the jargon of the gam…

> By the way, Google Translate makes a pretty horrible work at translating those pages. I think they need to add some more DeepMind to it :-)

I think they made an announcement about that.

> Found in translation: More accurate, fluent sentences in Google Translate

https://blog.google/products/translate/found-translation-mor...

So it doesn't seem to work so well.

Re: Google reveals secret test of AI bot to beat top Go players

#189

Post by btilly » Thu, Jan 05, 2017, 6:22 PM UTC

fryguy wrote: post #185

btilly wrote: post #124

Earlier quoted context omitted.

Checkers has adjusted its Elo system over time. I believe that it now matches chess except with a floor of a 1000 rating. From http://icheckers.net/ratings/ , the current ratings range goes from 1000 to 2297 among active players, and up to 2510 among inactive players. Even if you use the larger range of inactive players, that's a range of 7.5 times the standard deviation. Which is considerably less than chess.

Tinsley isn't on that list, and I saw it claimed that his rating was 2700: https://en.wikipedia.org/wiki/Marion_Tinsley Chess has a floor of 1200 for novices. So I'm not sure your point.

The Elo system for Checkers has changed over time. Tinsley had a rating around 2700, but he would not get that rating today.

Chess ratings from the USCF have a floor of 100. What you are thinking of is that they start people at a provisional rating of 1200 and then let them drift to where they belong. But a person who just knows how the pieces move will quickly head down towards that floor.

Re: Google reveals secret test of AI bot to beat top Go players

#190

Post by visarga » Thu, Jan 05, 2017, 6:26 PM UTC

codehotter wrote: post #167

rdlecler1 wrote: post #84

I'd like to see if a small team of the worlds best go players could beat AG.

How much stronger is a team of top players than its strongest member? I wonder what the best way of coordination would be. Perhaps they can identify several promising lines and each player chooses one variation to calculate more deeply. From my own experience playing (as a weak amateur), I feel I'm rarely able to think so systematically -- often ideas I discover while contemplating one line are tried in entirely diff…

> I wonder what the best way of coordination would be.

They would have to use a software to divide the search tree between them and collect their judgements.

I'm wondering how would a mixed team of AIs and humans fare? For example, a team of 1 AI and 4 humans against a team of similar setup. Humans could be assigned to judge parts of the search tree and their inputs aggregated by the AI.