Category: Programming

Google’s AlphaGo Beats Professional Go Player

Two weeks ago SmartGo sponsored the Core Intuition podcast, and I encouraged listeners to learn Go before computers conquer the game. Little did I know that Google’s AlphaGo had already beaten a professional player in a five-game match back in October; they were just waiting for their paper to get published.

I had expected this day to be at least five years away, more likely a decade; this is an amazing accomplishment by Google’s DeepMind team. In my previous thoughts on Facebook and Google entering the race, I was right about tree search being essential, wrong about more Go-specific approaches being necessary.

So how did Google do it? They build on Monte Carlo Tree Search (MCTS), but refine and extend it, and combine it with neural networks. Their paper is full of interesting details; here’s my initial take on the most important factors contributing to their success:

  • Extending MCTS with position evaluation: At each node where they perform a Monte Carlo simulation (a rollout or playout), they also evaluate the position using a value function. The results from the simulations and the value function are combined; the combination performs better than either alone.
  • Improved rollout policy: They create a deep neural network for the rollout policy using supervised learning, then refine it with reinforcement learning. A neural network implementing this rollout policy takes 3 ms to select an action; they also trained a rollout policy that is 1000 times faster but less precise (based on a linear combination of pattern features instead of a neural net). They use the more accurate one during learning, the faster one during actual play.
  • Using rollouts to learn value function: Position evaluation has not worked well for computer Go in the past, but here they just need a reasonably good guess at how likely a position will lead to a win. They trained it with 30 million distinct positions (each sampled from a separate game to avoid overfitting), and used their best rollout policy to play to the end and determine the winner. This resulting value function is more accurate than a playout using their fast rollout policy, and while it’s less accurate than using their best rollouts using neural nets, it takes 15000 times less computation. (The paper also mentions truncated rollouts, not quite clear on those yet.)

The AlphaGo team has also found good solutions for an asynchronous MCTS algorithm, for combining fast MCTS operations with slow neural networks, and for hashing local moves during the playouts. Massive amounts of hardware are helpful too.

The match against Lee Sedol in March is going to be tremendously exciting. There’s still time to learn Go now so you can follow along and share in the excitement.

My Path to Swift

After some experiments with Swift, I’ve been spending an increasing amount of time on a new project written completely in Swift. (Project to be revealed in due time.) Faster development, fewer bugs, and more fun — I’m hooked, and I don’t want to go back.

With the open source announcement of Swift delivering everything I wanted and more, there’s no reason to go back. Swift will be my main language for the next decade.

My programming language history

Most of my career has been focused on two large code bases, PowerPoint and SmartGo, and just a few programming languages. These languages have paved my path to Swift.

6502 assembler: After the TI-59 pocket calculator, my first real computer was a KIM-1. With a blistering speed of 1 MHz and a whole 1KB of RAM, that was an amazing machine. I squeezed my first Othello program into that computer, and learned a lot about performance and knowing every bit.

Modula-2: After some Pascal on Apple II, my time at ETH Zürich and UNC Chapel Hill was spent with Modula-2, first on the Lilith and then on the Mac. The original Smart Go Board for Macintosh was written in Modula-2. With the strong influence of Niklaus Wirth, I got drilled in the fundamentals of strong typing and modularity.

C++: When I started at Microsoft in 1991, most of the PowerPoint code was in C, with some Pascal in Mac-specific files (PowerPoint originally started as a Pascal program on the Mac). Over the next several releases, piece by piece, we successfully rewrote the whole program in C++, completely object-oriented. Both speed and memory usage were critical, and we learned how to use a subset of C++ to achieve high performance. (At one time, six of the twenty developers on PowerPoint had a connection to ETH Zürich — the Swiss influence was strong on that team. Still is.)

Once I left Microsoft in 1999 to work on SmartGo, C++ on Windows was the natural choice. C++ worked really well for Go, from fast low-level bitset operations to object-oriented UI code. But Vista pushed me over the edge and back to the Mac.

Objective-C: The Mac version of SmartGo got interrupted when Apple opened the iPhone for development. Keeping the base code in C++, I added the UI for SmartGo on iOS as I learned Objective-C. Seven years later, I’ve written a lot of Objective-C code, but it’s not my language of choice. The lack of type safety, the convenience of nil objects hiding potential errors, the need to avoid dynamic allocations and message passing in tight loops: these all worked against my nature. And having to interface with Go-specific code in C++ kept me from taking advantage of the full power of Objective-C.

Swift: With just a few months of Swift experience, it’s already clear that it gives me the building blocks for writing fast, high-quality software for the game of Go. It has strong typing and performance rivaling C++. It supports operator overloading (useful for bitset operations in Go) and generics (useful for arrays indexed by .Black and .White). Unicode string handling is a godsend for a game that originated in the Far East. Value semantics. Returning tuples. No crazy block syntax. Functional programming. And good riddance to semicolons.

I’m still in the early stages of learning Swift, and I’m already writing code better and faster than with the subset of C++ I had been using for 20 years. Did I mention it’s more fun too? So to me, it’s a clear choice.

Moving forward

I know where I’m going: my apps are transitioning to Swift. I know the first step: a separate Swift project to help me master the language and build up some base modules. After that? It will take me a while, but I will figure it out.

Transitioning a large code base is risky and never easy. I have no illusions that this will be simple. (Moving PowerPoint to C++ was good practice, but also a warning.) The fact that Swift doesn’t interoperate with C++ makes it harder. And it all has to be done while keeping the existing apps healthy and customers happy and dealing with any other curve balls Apple throws my way.

Yes, this will slow down development on my Go apps for the next years. It’s a risk I have to take: I’ve worked on these apps for fifteen years, and plan to work on them for many more. As an indie developer, I need to invest in my apps and in myself.

Go at Facebook

Before I left Microsoft in 1999 to pursue SmartGo full-time, I tried to convince them to start a computer Go project. No luck. It appears my timing was off by a decade: Microsoft released Path of Go for Xbox in 2010. Now Facebook and Google are getting into the game. Will they have a chance against the top programs?

We don’t know much about Google yet, just a hint from Demis Hassabis about a surprise from their DeepMind project. But researchers at Facebook (Yuandong Tian and Yan Zhu) have written a paper with more details.

Facebook researchers built a Deep Convolution Neural Net (DCNN) that they trained with games from KGS and GoGoD to predict good moves to play. They’re achieving an impressive 1 dan in ranked games on KGS, which beats any previous pattern-based approach. However, when they combine their approach with Monte Carlo Tree Search (MCTS), the results are a mixed bag. Evaluating a position with a DCNN is computationally expensive (their paper mentions about 3,000 MCTS playouts for every DCNN board evaluation); it’s not clear that using a neural net to generate moves for tree search is the best use of computing power.

Neural nets can be a powerful solution for pattern recognition problems, and many such problems are relevant to Facebook, so I understand why they have chosen to focus on improved move prediction using DCNN. My guess is that Google will take a similar approach. However, pattern recognition works well for shallow problems; Go is a deep problem, lookahead is essential.

As long as Facebook and Google stick with trying to find general solutions to general problems, I don’t think top Go programs like Zen and Crazy Stone have anything to worry about. But once these giants decide to beat the strongest human players and are willing to focus on Go-specific solutions, it will get interesting.

Monte Carlo Tree Search

Go-playing programs have made remarkable progress over the last decade. I want to give a brief overview of what has changed and how today’s top programs work.

Chess programs are based on tree search and position evaluation: look some moves ahead, evaluate the position, and select the move that leads to the position with the best evaluation (assuming best opponent defense). Do this well enough and fast enough, and you can beat anybody.

Go programs tried variations on that approach, and made very slow progress. The high number of legal moves at each position was one obstacle, but the main issue was the lack of a simple evaluation function. In chess, the material on the board is a good first approximation, and you can add adjustments to get a solid evaluation. In Go, you have to solve many separate tactical problems to find out what’s happening on the board and who is ahead. Those tactical problems include life and death, captures, and connections; once you have computed those, you can figure out territories, make assumptions about boundaries and open areas, and get a halfway reasonable evaluation. Unreliable and hard to scale; not a recipe for success.

Today’s top programs like Zen and Crazy Stone use Monte Carlo Tree Search (MCTS). The two components of that approach:

  • Monte Carlo: Play thousands of semi-random games (playouts) from the current board position. Play all the way to the very end of the game, where evaluation is trivial.
  • Tree Search: Build a tree of moves, and explore more promising moves more deeply.

This sounds crazy at first, but the reason it works is that it completely bypasses the difficult problem of evaluating the current position. Our goal is simply to choose the move that gives us a better chance of winning. With thousands of playouts from the current position, better moves tend to lead to more wins.

Monte Carlo programs are stronger when they just optimize their chance of winning, not the number of points they win by. This leads to good risk management: play safe moves that assure a win when you’re ahead, take risks when you’re behind.

The playouts are not completely random: they use heuristics to respond to standard patterns. The heuristics need to be carefully balanced to avoid bias. There are many refinements in MCTS, but the principles are simple, and properly implemented, this approach yields a scalable program where quality of play improves with added computing power.

While current top Go programs are approaching top amateur strength, they still exhibit a weakness when dealing with multiple tactically complicated situations on the board. The global search may be powerful enough to solve each life and death problem separately, but not together. Improvements in handling local fights without losing the benefits of global MCTS are needed.

You can find more details at:

SmartGo for Macintosh

It’s been a long road. But today you can download an early beta version of SmartGo for Macintosh.

I know a lot of you doubted this day would ever come. I’ve been promising a Mac version since practically forever, and it kept not happening. Sorry about that. Some history is in order.

Smart Go Board for the Macintosh was released in 1987, with frequent updates until I joined Microsoft in 1991, where I worked on PowerPoint until 1999. SmartGo for Windows was released in 2002; Windows Vista finally pushed me over the edge and I switched back to the Mac in 2007.

So in early 2008 I had made good progress on the Mac version, but was running into issues with the cross-platform approach I had started with (using wxWidgets). When Apple announced the iPhone SDK, it seemed like a great way to gain experience with Objective-C development before getting back to building a fully native Mac version. I knew I wanted thousands of pro games in my pocket, and figured other Go players would too; I had no clue it was going to take off as it did.

So in 2009 I added computer play, and more games, and then had some time to work on the Mac version again. And what does Apple do in 2010? They announce the iPad. SmartGo Kifu was born, available on day one. A big success, but that first iPad version demanded a lot of rethinking and refinement.

The iPad also inspired a new way to visualize annotated games: book view. That gave me this crazy idea of putting Go books on the iPad. Basically, I wanted to read “Invincible” on the iPad; I had no clue that a few years later I would end up with a new file format and 100 Go books. (And no time to work on the Mac version.)

Turned out it made sense to split off Go Books for the Mac as a separate app, and that actually shipped a few months ago. Which finally left some time to make significant progress on SmartGo for Macintosh.

So is the Mac version done yet? No. But it has gotten to the point where it’s useful to me. Getting it to a 1.0 release will take time, as there are many big and lots of small issues to work on, and I still need to keep updating the iOS versions as well as Go Books. Meanwhile, I want to give you the opportunity to use what I have so far.

As promised, the Mac version is free if you already own the Windows version. The two platforms are bundled: buy one, get both. So if you’re already using SmartGo for Windows, and now have access to a Mac, just download the Mac version and start using it. (If your email has changed, let me know.) If you’re new to SmartGo, take the 15-day free trial for a spin.

The Mac version inherits the GoGoD game collection and the problem collection from SmartGo for Windows and SmartGo Kifu. It inherits the tree view and joseki matching from SmartGo Kifu. It adds built-in access to Kogo’s Joseki Dictionary. However, there are still significant holes; for example, there’s not even a way to edit game info yet. Over time, those holes will be filled, and more of the advanced functions from the Windows version will make their way to the Mac. (Some, like playing on IGS, will remain Windows-only.)

It’s still a long road ahead. But now you can join me for the rest of the journey.

SmartGo in 2013

“It always takes longer than you expect, even when you take into account Hofstadter’s Law.” – Douglas Hofstadter

Another year without a Mac version of SmartGo. Progress, but not there yet. While that’s disappointing, both to you and to me, looking back at 2013 makes me feel much more confident about 2014.

SmartGo Kifu: Step by step, this app is approaching what I envision it to be. It got a fresh look with new icons, more logical layout, and less clutter. Then it went through another big change for iOS 7.

New features this year included Airdrop and Bluetooth keyboard support, and some large additions:

  • Tree view: The tree view reveals the structure of annotated games and makes navigation easy.
  • Matching games: When I introduced joseki matching last year I had to punt two features: dynamically switching to the corner with the most recent move, and showing the list of games that match a given position. Those are now done. Still many ways to make joseki matching even more useful; stay tuned.
  • GoGoD game collection: Switching to the GoGoD game collection took it from 40,000 games at the start of the year to over 76,000. The onomasticon (names dictionary) by John Fairbairn is also included, with a mini-biography of many professional players.

SmartGo Books: The 35 books added this year (for a total of 86) include out-of-print books as well as SmartGo Books exclusives, and several series are now complete: Elementary Go Series, Workshop Lectures, So You Want to Play Go, and Graded Go Problems. SmartGo Books now includes four books in German, one Japanese, one Spanish – more translations coming in 2014. See for a complete list.

SmartGo Player: It got an updated design, the tree view, and the ability to email the game record. More radical changes planned for next year.

Mac and Windows: The Mac version made progress, but is not ready for a beta yet. The Windows version was suspended for a while until I could upgrade the game collection; a beta version is now available.

Website: This year brought a completely new design for and, created by Scott Jensen, as well as more and better translations of the website. (Who else maintains their website in nine languages?)

Code: The health of the code determines how fast I can implement new features, how stable I can make the app, and how swiftly I can react to a curveball like iOS 7. This year included a complete rewrite of the gobook file format code, converting the whole code base to 64-bit and ARC (Automatic Reference Counting), integrating Crashlytics into SmartGo Kifu and Books, and significant performance improvements.

While I don’t know exactly what 2014 will bring, I’m confident that looking back there will be similarly good things to write about. Thanks for being a SmartGo user and recommending the apps to your friends. I wish you all the best for 2014!

SmartGo Books File Format

In SmartGo Books you can replay moves in diagrams, solve problems interactively, and export board positions. This means you need much more than just images of diagrams: you need a way to represent all the Go positions and moves as well as the text.

At first, I was using SGF with some extensions to specify book text and Go data. However, it soon became obvious that the tree structure of SGF and the linear structure of a book were not a good match. I ended up creating a new file format to simplify the creation, review, and display of digital Go books. It still takes a lot of work to convert printed Go books to digital form, but this format helps.

You can download the gobook format description (PDF). While this is work in progress, it has proven its value in over 70 Go books, representing a wide variety of challenges, from the Elementary Go Series to Invincible. I hope other people will find this format useful.

Tools for this file format are still pretty limited; for now, you can open files in this gobook format in the upcoming version of SmartGo Kifu. And the Mac version of SmartGo that I’m working on knows how to handle this file format, of course, but that’s for another time.