8 years later: A world Go champion's reflections on AlphaGo

We have more theory for deterministic games. That doesn't mean that it is harder to solve them to a human level.

Computers got to being better than humans in both Go and poker in 2016. The difference is that https://www.deepstack.ai/ was solvable by academics with normal research grants. The training for the final version of AlphaGo is estimated at about $35 million. And who knows how many other versions were created?

Yes, actually solving Go and Civilization are both impossible. But I would be shocked if playing Civilization at a human level was too hard for us to solve with current machine learning techniques.

Every measure of complexity is limited in some way. So they are all poor in various ways. That doesn't make them not worthwhile.

Total game states is one measure. What does it take to solve the game?

You can also look at the branching factor, how many moves are there to make on average. For chess, it's 20. For go, it's something like 300.

You can also look at how long it takes from a move to seeing its negative consequences. A bad move in chess is frequently visible in very few moves. You lose a piece. You lose an exchange. Often these sequences are virtually forced. By contrast, the consequences of a bad move in Go are usually not visible for 50 moves or more. And there is nothing forced about the sequence that gets there.

You can also look at how likely good players are to play similar games. Many chess games have been played over and over again. People sometimes play half the game out of a memorized opening sequence. By contrast, it is plausible that no Go game has ever been played twice on a 9x9 board. It is very unlikely that any Go gamme has been played twice on a 13x13 or 21x21 board.

You can also look at how big the skill gaps between humans get. In my experience, a 1 stone difference in Go is roughly a similar skill gap to 200 points of Elo in chess. A rank beginner who barely moves the pieces may have a 400 rating. No human has ever reached a 2900 rating. That's 12.5 levels. By contrast Go has 30 levels of amateur (kyo), another 9 for serious players (dan), and then the skill range among professionals is about another 3. That's 42 levels of fairly recognizable skill differences between humans. Which speaks to how much more there is to learn about Go than chess. (Even more so when you realize how much of advancing in chess is a matter of making fewer mistakes. By contrast advancing in Go is much more about integrating better principles.)

No matter how you look at it, Go is much more complex than chess.

is it even countable?

Beyond rule complexity, there are at least 5 measures of game complexity in Combinatorial game theory [1]:

    State-space complexity
    Game tree size
    Decision complexity
    Game-tree complexity
    Computational complexity

Take a game where you get to pick a single number between one and a billion. If you pick 10 you win. This has a billion states, but it's trivial. I can increase the bound above a billion, it doesn't matter.

State count gives an upper bound, though, to how complex a game can be, for sure.

Those position counts don't account for blunders or bad tactics which the players will take advantage of in order to simplify and win. In go, any move that lets your opponent cut you off is highly likely a blunder, so counting every other move other than the obvious one you have to play in order to not lose is pretty useless. You can also call it a bad move if you are not under an immediate threat and you are not invading. (this is a guess, I am not a go player) So counting the rest of the moves developing in your territory is also useless.

Yes, for example no limit Rock Paper Scissors where you bet an arbitrary amount and your opponent might call or fold is a game that:

1)has infinitely many legal states/positions

2)imperfect information (another argument often used to argue that game is more complex)

And is:

3)dead simple to play optimally

It's also easy to design a board game with arbitrary number of legal positions that is dead simple to play optimally.

There's a plausible explanation even without ego/emotions:

In the world of go, there was an obsession with finding "the perfect move". This was a significant motivation for the players.

That is now completely gone: if you want to find the perfect move, ask a computer.

Yeah, and plain Q learning is able to iteratively improve a policy in any environment. Every single loop leading to improvement, and yet it hasn't really solved much of anything since the 60s (just some toy problems).

My point being, we don't know where the asymptote lies. Computers have had self improving algorithms since the 60s, and people have been making the same bold claims, like you, that because an iterative process for improvement has been discovered, we're close to super human AI since the 60s too.

Fwiw, I work in home robotics, but have no experience in self driving. My halfway-naive belief is that self-driving is easier than getting useful home robots —in fact I feel it’s not even a close comparison. Some reasons:

- The home is a very unstructured environment, whereas roads have at least _some structure_, and perhaps ~70% of the most useful roads even have clear lane markings and other signs.

- People already know that roads are dangerous, and there’s an expectation that babies won’t suddenly crawl in front of cars. This doesn’t exist in the home

- People are more comfortable being recorded on roads and highways than in their own homes, so you can get training data more easily for self driving.

- to do something useful in the home, imo you need to solve navigation _and_ complicated manipulation problems. For self driving, you only need to solve the navigation problem.

- (this is speculation on my part) Customers will happily pay 10k-20k extra for a self-driving car, and there are industries in which even more cost makes sense. Customers are less likely to pay that for a robot that does your chores

Would be very interested to hear the perspective of someone that works on self-driving

> “Driving” is solved. Driving with humans on the road - doing unpredictable human things - is far off still.

Plus there's serious questions about liability with self driving cars which are still unresolved in most of the world - if the goal is to have vehicles operate themselves with no human supervision, who goes to jail when they kill someone? Despite all of the progress that's been made with AI it's mostly been in low-stakes problems where failure isn't a big deal, so we don't have a consensus on what we're supposed to do when a neural network negligently obliterates a person because some logistics company wanted to save a few bucks on driver salaries.

“Driving” is not solved unless you mean perfectly paved streets in perfect weather on empty streets with no pedestrians. A competent solution like Waymo can handle significantly more complex cases at real world levels of complexity, but it is still unclear how comprehensive and robust that really is across the massive complexity of reality even without other cars on the road. There is simply not enough data, and no independent audits yet.

It is prudent to remain cautiously optimistic that the evidence will bear out in time, but not assert unsupported claims.

I think your guess that home robotics will be solving problems before self-driving cars git gud will be disproven (industrial robotics have been delivering value for five decades at least).

Home robotics has to solve two problems: the robot and operating the robot ~perfectly. Self-driving cars already have cars, which are waldos, if you squint. What sort of sensors should be added is up for debate but the actuation mechanism is a solved problem, and a very simple one, cars have three linear inputs and two binary ones for the turn signals. Technically a few more but none of them are any less trivial.

There's less risk of a fatality when Rosie Robot knocks over the vase you inherited from your grandmother, but people are no more tolerant of that kind of failure in home robots than they are in cars.

Driving the giant death machines costs us billions of manhours every day. Hundreds of billions of manhours per year.

Which small thing puts a similar burden on mankind?

But the average hour is not driven by the average driver, better drivers drive more hours, so it has to be better than the average driver in order to result in fewer incidents.

Musk was wrong. He said specifically and unequivocally that Tesla would be delivering fully autonomous vehicles to customers within a year, every year for the last 8 years.

Just to get ahead of anybody claiming it was not a firm promise, in 2019: “ I think we will be feature-complete full self-driving this year, meaning the car will be able to find you in a parking lot, pick you up, take you all the way to your destination without an intervention — this year. I would say that I am certain of that. That is not a question mark." [1]

See that part where he says: “I would say that I am certain of that. That is not a question mark.” That is called a firm promise.

[1] https://www.businessinsider.com/elon-musk-doubles-down-on-cl...

If Musk was right we would've been there almost a decade ago.

And we're still not really there yet. They work great during some conditions and in certain areas, but they're still nowhere close to making human drivers obsolete.

I think AlphaZero does use MCTS?

I'm not sure one can, from today that is, really understand how huge of a leap was made by AI at this time.

Even going back to the closest analogue, chess, there were good chess engines for a long time prior to Kasparov loosing in 97 to deep blue. Even before Kasparov lost Chess engines were pretty good, just look at the game in 96 when Kasparov won. A grand master would still need to put some thought into how he played.

In Go however even the best engines couldn't hold a candle to a professional player, let alone someone who was the equivalent of a chess grand master. Hell, even as a lowly amateur player I was able to trounce some of the most powerful AIs at the time. Looking at some of the Pro vs AI games back in the early 2010s it's almost painful how bad they were.

It's hard to communicate just how huge of a leap this was, and just how shocking to the whole Go community. It would be like a child one day being unable to speak and the literal next day reciting Shakespeare.

AlphaGo took many AI researchers by surprise. An even bigger surprise came next year, with AlphaZero:

"AlphaZero was a reinforcement learning system that was able to master three different perfect information games - chess, shogi (Japanese chess), and Go - at superhuman levels by just learning from self-play, without using any human expert games or domain knowledge crafted by programmers.

Its predecessor AlphaGo, which defeated the world champion Go player in 2016, was revolutionary but relied on human expert games and domain-specific rules coded by the DeepMind researchers.

AlphaZero started from random play and used a general-purpose reinforcement learning algorithm to iteratively improve its gameplay through self-play, ending up with superior performance compared to the best human players and previous game-specific AI systems.

Many experts were stunned that a general algorithm could rediscover from scratch the millennia-old principles and strategies for these highly complex games, often discovering novel and counterintuitive moves along the way."

In any field.

That would be pretty strange. For a trivial counterexample, you can look up the history of integrated circuits from invention to today.