News for hackers. Stuff that matters.
Re:Go master Lee Se-dol says he quits, unable to win over AI... by btilly on Wednesday November 27, 2019 @03:06PM (#21651535)
You're thinking too much like a human.

No, you're thinking too much like someone who understands chess but not Go.

Suppose that we built an opening book with a trillion reasonable courses of action on it. Each one analyzed well. As you have discovered, you will only go a few ply into the game. And all of the positions that you will be directed towards will have only a small edge.

Instead put a tiny fraction of the computing power necessary to build this book into self-training. You will get a better internal model and therefore a significantly stronger computer player. (That is how alpha-go was built in the first place.) This option will produce much better results for far less effort, and again leaves no role for a human to do anything useful.

The fact that a memorized opening book is useless has nothing to do with human vs computer vs cyborg. It has to do with the characteristics of the game. In chess, it is useful to memorize openings and both computers and humans do it. In Go it is a waste of energy, and it is a waste for both computers and humans.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by ammon on Wednesday November 27, 2019 @03:34PM (#21651822)
I want to add that opening books are not THAT effective in computer chess either. Yes, they are significantly more effective than in computer go (because of the smaller branching factor and greater role of tactics). However, exponential increase in game tree size is crazy, even in chess. Thus, opening books really can't take you THAT far into a chess game (10 moves). An engine with a worse book but better search/eval will usually win.
Re:Go master Lee Se-dol says he quits, unable to win over AI... by dragontamer on Wednesday November 27, 2019 @03:48PM (#21651956)
The main purpose of opening books is to beat any player who is strictly relying upon Stockfish (or LeelaZero's) output to play the game. Because these engines play very deterministically, you can beat people who just play's Stockfish #1 (or LeelaZero #1) move over and over.
Re:Go master Lee Se-dol says he quits, unable to win over AI... by bscphil on Wednesday November 27, 2019 @05:30PM (#21652810)
I think the main issue with your initial statement was that you said you could beat someone just taking AlphaGo's advice on every move. Usually when people talk about opening books, they think of the opening book as being part of the engine's decision making process, not an addition to it. Usually this is literally the case, as in chess where I can add an opening book to Stockfish's runtime options.

In my opinion, it's really strange to describe this as an expert "beating" AlphaGo, when really it's just a technique for making AlphaGo stronger than it is without a huge pre-calculated cache of moves.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by DiogenesKynikos on Wednesday November 27, 2019 @08:52PM (#21654020)
I've heard that opening books make Stockfish about 70 Elo better, which is very significant.

10 moves into a chess game is actually pretty far. The directions the game can go are massively narrowed 10 moves in.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by patcon on Wednesday November 27, 2019 @03:29PM (#21651747)
fwiw, I'm with you. Excuse the gratuitous war analogy, but I suspect the approach of OP is akin to talking about which first 8 steps to take (north-east, SW, S) when going into battle -- it's such a small scope of the whole event that it's pointless, and talking about those first steps makes one seem naive to the actual holistic task
Re:Go master Lee Se-dol says he quits, unable to win over AI... by btilly on Wednesday November 27, 2019 @03:35PM (#21651838)
The analogy is a very appropriate one.

If the OP spent a month learning Go, I am sure that it would make sense to him as well. Work through a series like https://senseis.xmp.net/?LearnToPlayGoSeries while playing Go regularly against a variety of opponents. Before book 3 it should be obvious.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by dragontamer on Wednesday November 27, 2019 @03:44PM (#21651911)
I'll have you know that I'm a 15 Kyu Go player.

I'm not an expert by any means, but I'm well past "spend one month" learning the game.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by protomolecule on Thursday November 28, 2019 @09:30AM (#21657584)
I don't mean to offend you, but it seems you've been doing something wrong -- in my opinion, in more than a month you could've advanced much further than 15k.

If you like, I could have a look at several your lost games and maybe suggest how to improve. Just a 3k at kgs, but still.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by xiaodai on Wednesday November 27, 2019 @05:28PM (#21652795)
15kyu? One can easily reach that strength after 1 week. Some ppl become pro age 9
Re:Go master Lee Se-dol says he quits, unable to win over AI... by protomolecule on Thursday November 28, 2019 @09:32AM (#21657597)
And some people by the age of 9 learn how not to be mean to other people.
Re:Go master Lee Se-dol says he quits, unable to win over AI... by dragontamer on Wednesday November 27, 2019 @04:04PM (#21652127)
For the near term future, LeelaZero is the best public engine at computer Go.

This means if you enter a hypothetical "Cyborg" Go competition (computer-assistance allowed), the majority of newbies will simply be playing LeelaZero #1 plays over and over again.

You don't need to build an exhaustive opening book covering all possible moves. You only need to pick say, the top 5 moves LeelaZero ever considers. If you spend ~16-bytes per position and store 1-trillion positions on a 16TB Hard Drive, you'll be able to exhaustively map the top5 moves LeelaZero considers into 17-ply.

From there, you pick the positions that LeelaZero thinks its winning in, but in actuality is losing. You have a map towards 1-trillion positions to choose from, and your opponent (if they only pick from the top5 best moves LeelaZero ever outputs) will walk into your trap.

---------

As long as your opponent picks the top 5-moves from LeelaZero, you'll have the map towards victory. I think you're severely underestimating the abilities of a simple, dumb, opening database.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by conistonwater on Wednesday November 27, 2019 @06:07PM (#21653084)
I think you're missing btilly's point, which is quite valid. Bear in mind that 17-ply is absolutely nothing in go.
Re:Go master Lee Se-dol says he quits, unable to win over AI... by sooheon on Wednesday November 27, 2019 @04:37PM (#21652365)
Time to compile that static dictionary > time for alphazero to play a few million more games against itself to advance the metagame.
Re:Go master Lee Se-dol says he quits, unable to win over AI... by dragontamer on Wednesday November 27, 2019 @03:11PM (#21651592)
> Instead put a tiny fraction of the computing power necessary to build this book into self-training.

Do you believe that AlphaZero could continue to improve dramatically with another 6-months of training? Or if it can improve at another 6-months after that? At some point, the network will reach a local maximum, and it will be unable to improve beyond that.

Characterizing AlphaZero's moves through big-data analysis is innately going to become useful as self-training plateaus. Even Google wasn't able to get more than a few months of training in before the plateau.

At which point, it will be more reasonable to characterize the weaknesses of the network and build an opening book. Avoid the positions that the network was unable to learn about. Etc. etc.

Opening books, at a minimum, would grossly improve AlphaZero's play at competitive levels. Anyone with an opening book of AlphaZero's mistakes will be able to push AlphaZero into a mistaken position.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by btilly on Wednesday November 27, 2019 @03:30PM (#21651762)
AlphaGo spent months training and continued to improve for the whole time. Its improvement slowed, just as it takes more work for humans to get from master to international master than it does from D-level player to C-level player. But it did not stop improving.

And then AlphaZero was better than AlphaGo after around a day of self-training.

Furthermore you are arguing for an opening book without considering how small an advantage an opening book would be. As I have said repeatedly, an opening book takes a tremendous amount of work to generate, will only go a few ply in, and the positions it directs you to will only be a tiny bit better.

Therefore for the foreseeable future, more training and better algorithms will produce better results than trying to create an opening book. Theoretically this could change. But that day will not be today or this year. I would be astonished if it happened during this decade. I would be surprised if it happened in a lifetime.

Your proposed approach is an excellent one for many games. But not for Go.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by dragontamer on Wednesday November 27, 2019 @03:37PM (#21651849)
We have LeelaZero numbers: https://ogs-forums.s3.amazonaws.com/original/2X/2/21de8caa52...

The plateau is real. I'm not sure if continuous self-play will lead to continuous progress for all of eternity. The system is clearly slowing down in self-learning.

AlphaZero's plateau is also well documented: https://i.imgur.com/NMNp6Kq.png

--------

I'm not trying to cast doubt upon reinforcement learning / MCTS / Neural Nets in the game of Go. It is clearly the best methodology we got today.

But anyone who has any experience with neural nets knows about the local-maxima problem. ALL neural nets reach a local maxima eventually. Once this point is reached, you have to rely upon other methodologies to improve playing strength.

Assuming Elo-growth for all time using a singular methodology is naive. We will go very, very far with Deep Learning, but are you satisfied with that limit? Other open questions remain: Go is very far away from being a solved game, even with a magical machine that plays 2000+ Elo stronger than humans.

Re:Go master Lee Se-dol says he quits, unable to win over AI... by jmcgough on Wednesday November 27, 2019 @03:32PM (#21651795)
> Anyone with an opening book of AlphaZero's mistakes will be able to push AlphaZero into a mistaken position.

This only works if AlphaZero never retrains on previous games.