Tag: AlphaGo

Using Strong Go Programs on Macintosh

SmartGo for Mac is not playing strongly, as computer play is using my own pre-AlphaGo engine. However, like SmartGo for Windows, you can use GTP (Go Text Protocol) to connect to strong engines to play against.

The most recent version of SmartGo for Macintosh (0.8.18) includes some improvements in how it handles GTP engines. It’s not perfect, there’s much more to be done, but hopefully it will tide you over while I keep my focus on the new SmartGo for iOS.

The first step is downloading and installing the computer go engines you want to connect to. Here are three I’ve tested with SmartGo for Mac, from easy to hard to install. All assume that you’re somewhat comfortable using the Terminal app; check out this iMore guide if you’re new to the command line.

Pachi

The easiest way to install Pachi on the Mac is using Homebrew (which you probably have to install first). Follow these instructions:

https://brewinstall.org/Install-pachi-on-Mac-with-Brew/

Leela Zero

Find Leela Zero on Github, scroll down to I just want to play with Leela Zero right now, and follow the Homebrew instructions. You’ll also have to download a file with network weights; the link is in that same section.

KataGo

Installing KataGo is more complicated, as you have to compile it yourself. Follow the instructions for Linux at https://github.com/lightvector/KataGo.

smartgo-mac-gtp-preferences

Setting Parameters

Once you’ve installed an engine, you need to add it to SmartGo. Choose SmartGo > Preferences in the menu and click on GTP. Then click on the + icon and navigate to the executable of the engine you want to add. SmartGo uses the engine name to guess reasonable parameters, then tries to run the engine to get its name and version. If you see a green checkmark with the name and version, you’re all set. Otherwise, edit the parameters sent to the GTP engine (the third column in the table). The following basic settings work for my setup:

Leela Zero: -g –playouts 1000 –noponder -w /usr/local/Cellar/leela-zero/0.17/best-network/40b_257a_64k_q

KataGo: gtp -model /Users/anders/work/katago/cpp/models/model.txt.gz -config /Users/anders/work/katago/cpp/configs/gtp_example.cfg

Leela Zero and KataGo take a while to initialize, so even just getting name and version initially can take a minute, and SmartGo may time out. If it does, just try starting a game against the engine anyway (File > New Game, specify the engine in the dropdown for Black or White), and see if it works.

I hope these instructions get you pointed in the right direction. I’m sorry none of this is as easy as it should be.

Highest Possible Pinnacle?

DeepMind announced that AlphaGo will no longer compete: “This week’s series of thrilling games with the world’s best players … has been the highest possible pinnacle for AlphaGo as a competitive program. For that reason, the Future of Go Summit is our final match event with AlphaGo.”

This reason is rubbish. Could AlphaGo repeat its string of 60 victories in no-komi games? Could it win a match giving handicap stones? If AlphaGo wanted to keep competing, there are many more challenges left for it to conquer.

DeepMind used Go as a very successful testbed for its deep learning algorithms: a testbed that has measurable outcomes and can generate its own test data. Winning against the world’s best doesn’t make that testbed obsolete. DeepMind said that this year’s version was using ten times less computing power than last year’s AlphaGo. Could they improve the algorithms by another factor of ten? Hundred? Thousand? Yes, by all means push into other domains and apply what you’ve learned, but don’t abandon the testbed. You have ideas on how to improve your learning algorithm for medical diagnosis or self-driving cars? Testing the effectiveness of those improvements will be a lot harder than in Go.

I’m glad the DeepMind team is publishing a set of 50 AlphaGo self-play games, and that they’re working on a teaching tool. But not pushing AlphaGo forward competitively is a mistake.

Moves to Unique Game

The Ke Jie vs. AlphaGo games quickly reached a position that was not in the GoGoD game collection of almost 90,000 professional game records: Game 1 was unique at move 5, game 2 was unique at move 7. To me, this seemed very early, and @badukaire on Twitter got me to wonder: How soon does a pro game usually reach a position that’s different from any previously played game?

Number of moves to unique game

Time for some data: I ran SmartGo’s fuseki matching on the whole GoGoD game collection (excluding handicap games). In that data set, the highest probability for a move to become unique is at move 8; the median is between move 11 and 12; the average is about move 13. Games are unique by move 7 in about 16% of games; by move 5 in only about 4%.

So it’s somewhat unusual to diverge from standard play that early, but there’s more variety of play early in the game than I expected. Also, I’m sure that a lot of games will soon be copying those moves by AlphaGo and Ke Jie, and those opening moves will be unique no more.

Wishful Thinking

Lee Sedol’s strategy in game 4 worked brilliantly (well explained in the excellent Go Game Guru commentary). It took AlphaGo from godlike play to kyu-level petulance. When it no longer saw a clear path to victory, it started playing moves that made no sense.

AlphaGo optimizes its chance of winning, not its margin of victory. As long as that chance of winning was good, this worked well. When the chance of winning dropped, AlphaGo’s quality of play fell precipitously. Why?

Ineffective threats

The bad moves that AlphaGo played include moves 87 and 161: threats that just don’t work, as they can easily be refuted, and either lose points, or at least reduce future opportunities. When AlphaGo plays such a move, it’s smart enough to find the correct local answer and figure out that the move doesn’t actually work. However, the Monte Carlo Tree Search component (MCTS) will also look at other moves that don’t answer that threat, as there is always a chance that the opponent plays elsewhere. Thus AlphaGo sees a non-zero chance that this threat actually works, and the way MCTS calculates the statistics it thinks that this increases its chance of winning.

Of course, the opposite is true. Playing a threat that can easily be refuted is just wishful thinking. The value network would figure out that such an exchange actually makes the position worse, but it doesn’t know that it should override the Monte Carlo simulations in this case.

Adjusting komi

One way to avoid this effect is to internally adjust the komi until the program has a good chance of winning. This causes the program to play what it thinks are winning moves, while in fact it will lose by the few points you artificially adjusted the score. If the opponent makes a mistake, the program might regain a real winning position later. (SmartGo uses this technique; it also helps play more reasonable moves in handicap games.)

For AlphaGo, that technique won’t work well: as I understand it, the value network is trained to recognize whether positions are good for Black or for White, not by how many points a player is ahead.

Known unknowns

Another idea is to look at the source of uncertainty in MCTS. The Monte Carlo winning percentages are based on statistics from the playouts, and there are many uncertainties in that process due to the random nature of the playouts and the limited nature of the search. The more moves you look at, the smaller the unknowns become, and the statistical methods used to figure out which moves to explore more deeply and how to back up results in the search tree try to minimize these uncertainties.

However, whether the opponent will answer a threat is a yes-or-no decision; it should not be treated like a statistical unknown. In that case, you want to back up the results in the tree using minimax, not percentages. Something for the DeepMind team to work on before they challenge Ke Jie, so AlphaGo won’t throw another tantrum.

AlphaGo Don’t Care

AlphaGo is badass. Like the honey badger, AlphaGo just don’t care.

Lee Sedol may have underestimated AlphaGo in game 1, but he knew what he was up against in game 2. I watched Michael Redmond’s commentary during the game, then Myungwan Kim’s commentary this morning. The Go Game Guru commentary is also very helpful.

The tenuki at move 13: Professionals always extend at the bottom first? AlphaGo don’t care. It builds a nice position at the top instead.

The peep at move 15: This is usually played much later in the game, and never without first extending on the bottom. AlphaGo don’t care. It adds 29 later, and makes the whole thing work with the creative shoulder hit of 37. It even ends up with 10 points of territory there.

With 64 and 70, Lee Sedol made his group invulnerable to prepare for a fight at the top. AlphaGo don’t care, it just builds up its framework, and then shows a lot of flexibility in where it ends up with territory.

Lee Sedol threatens the territory at the top with 166? AlphaGo don’t care, it just secures points in the center instead. Points are points, it doesn’t matter where on the board they are.

What can Lee Sedol do in the next games? I think he needs to get a complicated fight going early in the game, start ko fights, in general increase the complexity. But I fear AlphaGo just won’t care.

Four More Games

AlphaGo’s victory over Lee Sedol last night was stunning. I’m still gathering my thoughts and trying to figure out what happened.

The game analysis at Go Game Guru has been very helpful. But I have to wonder whether I can trust the commentary — maybe AlphaGo knew what it was doing?

Move 80 was described by Younggil An 8p as ‘slack’. I wonder whether AlphaGo at that point already calculated that it was winning, and that eliminating the aji (latent possibilities) in that area would be the best way to reduce the risk of losing. I would love to know more about AlphaGo’s evaluation of that move.

AlphaGo demonstrated that it’s good at fighting, and would not back down from a fight. It also showed excellent positional judgement and timing, managing to invade on the right side with 102, get just enough out of that fight, and end with sente to play the huge move of 116 to take the upper left corner. And it’s not letting up in the endgame once it sees a path to victory. We have not seen any ko fights yet, but there’s no reason to believe AlphaGo couldn’t handle those well.

For the remaining games, I think Lee Sedol must establish a lead by mid game at the latest to have a chance of winning. As the game gets closer to the end, there are fewer moves to consider, and there are fewer moves for the Monte Carlo playouts to reach the end of the game, so AlphaGo will just get stronger.

Move 7 was a new move. At least, it’s not in the GoGoD database of 85,000 professional game records. With SmartGo’s side-matching, only two games (both played in 2013) match that right-side position. He probably tried to make sure AlphaGo couldn’t just rely on known patterns, but that gambit didn’t pay off. I don’t think Lee Sedol will try a similar move tonight.

There are four more games; I would not count Lee Sedol out yet. He now knows what AlphaGo can do, and won’t underestimate it again. We have some very exciting games to look forward to.

Late Nights with AlphaGo

Google has announced times and time limits for Lee Sedol’s match against AlphaGo. Games start at 13:00 (UTC+9), which means they’ll start in the evening the day before in the US:

  • Tuesday March 8: 8 p.m. PST, 11 p.m. EST
  • Wednesday March 9: 8 p.m. PST, 11 p.m. EST
  • Friday March 11: 8 p.m. PST, 11 p.m. EST
  • Saturday March 12: 8 p.m. PST, 11 p.m. EST
  • Monday March 14: 9 p.m. PST, midnight EST (DST!)

And Michael Redmond 9p will be commenting in English. Mark your calendars and stock up on popcorn.

Time limits are two hours per player, plus 3×1-minute byo-yomi. Thus after basic time is up, players can use up to a minute for every move; three times they can spend an extra minute. The article says each game is thus expected to last 4-5 hours, but if AlphaGo uses its full two hours (instead of playing very fast as in the Fan Hui match), it could easily go longer. Be prepared for some late nights.

I’m glad they increased the time limits from the Fan Hui match; this should be a very exciting match. Just one new tidbit since my Lee Sedol vs AlphaGo blog post — on the Computer Go mailing list, Aja Huang commented today: “We are still preparing hard for the match. … AlphaGo is getting stronger and stronger.”