Would AlphaGo Zero become perfect with enough training time?

Question

Would AlphaGo Zero become theoretically perfect with enough training time? If not, what would be the limiting factor?

(By perfect, I mean it always wins the game if possible, even against another perfect opponent.)

Answer 1

We cannot tell with certainty whether AlphaGo Zero would become perfect with enough training time. This is because none of the parts (Neural Network) that would benefit from infinite training time (= a nice approximation of "enough" training time) are guaranteed to ever converge to a perfect solution.

The main limiting factor is that we do not know whether the Neural Network used is big enough. Sure, it's pretty big, it has a lot of capacity... but is that enough? Imagine if they had used a tiny Neural Network (for example just a single hidden layer with a very low number of nodes, like 2 hidden nodes). Such a network certainly wouldn't have enough capacity to ever learn a truly, perfectly optimal policy. With a bigger network it becomes more plausible that it may have sufficient capacity, but we still cannot tell for sure.

---

Note that AlphaGo Zero does not just involve a trained part; it also has a Monte-Carlo Tree Search component. After running through the Neural Network to generate an initial policy (which in practice turns out to already often be extremely good, but we cannot tell for certain if it's perfect), it does run some MCTS simulations during it's "thinking time" to refine that policy.

MCTS doesn't benefit* from increased training time, but it does benefit from increased thinking time (i.e. processing time per turn during the actual game being played, rather than offline training time / self-play time before the evaluation game). In the most common implementation of MCTS (UCT, using the UCB1 equation in the Selection Phase), we can prove that it does in fact learn to play truly perfectly if it is given an infinite amount of thinking time. Now, AlphaGo Zero does use a slightly different implementation of the Selection Phase (which involves the policy generated by the trained Neural Network as prior probabilities), so without a formal analysis I can't tell for sure whether that proof still holds up here. Intuitively it looks like it still should hold up fine though.

---

*Note: I wrote above that "MCTS doesn't benefit from increased training time. In practice, of course it does tend to benefit from increased training time because that tends to result in a better Network, which tends to result in better decisions during the Selection Phase and better evaluations of later game states in the tree. What I mean is that MCTS is not theoretically guaranteed to always keep benefitting from increases in training time as we tend to infinity, precisely because that's also where we don't have theoretical guarantees that the Neural Network itself will forever keep improving.

Answer 2

Assuming you mean a mathematically perfect player, similar to what we can achieve trivially in Tic Tac Toe, then the answer is "maybe". The underlying reinforcement learning algorithms that it uses do have some convergence guarantees, but there are some caveats:

• Theories of convergence that apply to value and policy functions learned by RL assume unrealistic timescales and decays of learning parameters. If you have actual infinite time and resources then it is possible to explore all board states and learn their values accurately. But then, if you have those resources at your disposal, a brute-force search would work too.

• Using neural network approximations to true value functions can put bounds on how well value functions are learned, as they rely on generalisation, and are characterised by an error metric. The values that they calculate are in fact guaranteed to not be mathematically perfect, and in part that is by design (because you want learning from similar states to apply to new unseen states, and as part of that need to accept the compromise that most state values will be slightly incorrect). This is especially true of the fast policy network used to drive Monte Carlo Tree Search (MCTS).

• Running longer MCTS during play improves performance at cost of spending more time per move decision. Given infinite resources, MCTS can play perfectly, even from very crude heuristics.

The difference between AlphaGo Zero and a more traditional game search algorithm is to do with optimal use of available computing resources, as set by available hardware, training time and decision time when playing. It is orders of magnitude more effective to use the RL self-play approach combined with the focused MCTS as in AlphaGo Zero, than any basic search. At least for similar puzzles and games, it is more efficient than any other game playing technique that has been explored. We are likely still more orders of magnitude of effort away from a perfect Go player, and there is no reason yet to suspect that this will ever become practical, and Go become "solved".

Answer 3

Yes AlphaGo Zero could become undeniably perfect.

It has won 100:0 against AlphaGo Lee (which won 4:1 against 18-time world champion (human) Lee Sedol) and 89:11 against AlphaGo Master (which won 60 straight online games against human professional Go players from 29 December 2016 to 4 January 2017).

From the official AlphaGo website:

"AlphaGo's 4-1 victory in Seoul, South Korea, in March 2016 was watched by over 200 million people worldwide. It was a landmark achievement that experts agreed was a decade ahead of its time, and earned AlphaGo a 9 dan professional ranking (the highest certification) - the first time a computer Go player had ever received the accolade.".

From AlphaGo's webpage: "AlphaGo's next move":

"We plan to publish one final academic paper later this year that will detail the extensive set of improvements we made to the algorithms’ efficiency and potential to be generalised across a broader set of problems. Just like our first AlphaGo paper, we hope that other developers will pick up the baton, and use these new advances to build their own set of strong Go programs.

...

Since our match with Lee Sedol, AlphaGo has become its own teacher, playing millions of high level training games against itself to continually improve.".