A new AI wins at go. Can a similar AI win at chess? Can it achieve pure self-training?

Question

One of the more popular questions asked on this site regards the prospect of a purely self-trained chess AI.

Today, ChessBase is distracted from its coverage of the FIDE Candidates tournament to report that a new AI is, for the first time, beating a leading master of the rather different game of go, which had resisted chess-style AIs for many years. An initial reading of the report suggests that the new go AI is unlike chess AIs, but is more nearly a general-game-playing (GGP) AI. ChessBase's article does not however use the term GGP, but does seem to say that the go AI can win at simple video games.

Is there any reason such a winning go AI could not with minor adjustments also win at chess? If so, does such an AI show promise to achieve the pure self-training the several excellent answers to the earlier question have earlier discussed, which at that time was not yet possible? Why or why not?

I suspect that no really complete, fully informed answer to my question is yet available, so even a partial answer based on related expertise would be appreciated.

For additional reference, see also this related question and answers.

UPDATE

When the above question was first posted five days ago and when some of the fine answers below were given, the first news regarding the victory of the go AI had just appeared. Since then, additional information and commentary have emerged.

Particularly interesting since then has been a quite readable, five-sided roundtable discussion in which one Jonathan Schaeffer remarks:

Learning from human games helps accelerate the program’s learning. AlphaGo could learn to become a strong player on its own, without using the human games. The learning process would just take longer.

According to the roundtable's host, Schaeffer is "[c]omputer science professor at the University of Alberta and the man who solved checkers"; so, presumably, he might be qualified to comment.

For further information, here is the record of another, open discussion, many of whose participants seem better informed than usual. The discussion took place during the match.

Further update, a year and a half later: commenter @MarkS. writes:

This is just a comment because it's about Go, not Chess, but AlphaGo Zero achieved "pure self-training" just from being told who won (and not the final score) and is stronger and vastly more efficient than the AI that beat Lee Sedol. For more information, see deepmind.com/blog/alphago-zero-learning-scratch

Answer 1

Well, well, well! DeepMind have published a paper in which they say they have programmed and trained a neural network computer to beat Stockfish.

With 1 minute thinking time per move their AlphaZero computer beat Stockfish by +25, =25, -0 with white and +3,=47,0- as black.

They "trained" 3 separate computers to play chess, shogi and Go and beat their silicon rivals convincingly.

Here is how the paper describes the training and evaluation -

Self-play games are generated by using the latest parameters for this neural network, omitting the evaluation step and the selection of best player.

AlphaGo Zero tuned the hyper-parameter of its search by Bayesian optimisation. In AlphaZero we reuse the same hyper-parameters for all games without game-specific tuning. The sole exception is the noise that is added to the prior policy to ensure exploration; this is scaled in proportion to the typical number of legal moves for that game type.

Like AlphaGo Zero, the board state is encoded by spatial planes based only on the basic rules for each game. The actions are encoded by either spatial planes or a flat vector, again based only on the basic rules for each game (see Methods).

We applied the AlphaZero algorithm to chess, shogi, and also Go. Unless otherwise specified, the same algorithm settings, network architecture, and hyper-parameters were used for all three games. We trained a separate instance of AlphaZero for each game. Training proceeded for 700,000 steps (mini-batches of size 4,096) starting from randomly initialised parameters, using 5,000 first-generation TPUs to generate self-play games and 64 second-generation TPUs to train the neural networks. Further details of the training procedure are provided in the Methods.

Figure 1 shows the performance of AlphaZero during self-play reinforcement learning, as a function of training steps, on an Elo scale (10). In chess, AlphaZero outperformed Stockfish after just 4 hours (300k steps); in shogi, AlphaZero outperformed Elmo after less than 2 hours (110k steps); and in Go, AlphaZero outperformed AlphaGo Lee (29) after 8 hours (165k steps).

We evaluated the fully trained instances of AlphaZero against Stockfish, Elmo and the previous version of AlphaGo Zero (trained for 3 days) in chess, shogi and Go respectively, playing 100 game matches at tournament time controls of one minute per move. AlphaZero and the previous AlphaGo Zero used a single machine with 4 TPUs. Stockfish and Elmo played at their strongest skill level using 64 threads and a hash size of 1GB. AlphaZero convincingly defeated all opponents, losing zero games to Stockfish and eight games to Elmo (see Supplementary Material for several example games), as well as defeating the previous version of AlphaGo Zero (see Table 1).

Their computer used a new form of chip called a "TPU" (Tensor Processing Unit) developed by Google for machine learning tasks.

They also claim their Monte Carlo tree search algorithm is better and more "human like" than the traditional alpha-beta search algorithms -

We also analysed the relative performance of AlphaZero’s MCTS search compared to the state-of-the-art alpha-beta search engines used by Stockfish and Elmo. AlphaZero searches just 80 thousand positions per second in chess and 40 thousand in shogi, compared to 70 million for Stockfish and 35 million for Elmo. AlphaZero compensates for the lower number of evaluations by using its deep neural network to focus much more selectively on the most promising variations – arguably a more “human-like” approach to search, as originally proposed by Shannon. Figure 2 shows the scalability of each player with respect to thinking time, measured on an Elo scale, relative to Stockfish or Elmo with 40ms thinking time. AlphaZero’s MCTS scaled more effectively with thinking time than either Stockfish or Elmo, calling into question the widely held belief that alpha-beta search is inherently superior in these domains

Here are some of the games -

[FEN ""]
[White "Stockfish "]
[Black "AlphaZero"]

 1. e4 e5 2. Nf3 Nc6 3. Bb5 Nf6 4. d3 Bc5 5. Bxc6 dxc6 
 6. O-O Nd7 7. Nbd2 O-O 8. Qe1 f6 9. Nc4 Rf7 10. a4 Bf8 11. Kh1 Nc5 12. a5 Ne6 
 13. Ncxe5 fxe5 14. Nxe5 Rf6 15. Ng4 Rf7 16. Ne5 Re7 17. a6 c5 18. f4 Qe8 
 19. axb7 Bxb7 20. Qa5 Nd4 21. Qc3 Re6 22. Be3 Rb6 23. Nc4 Rb4 24. b3 a5 
 25. Rxa5 Rxa5 26. Nxa5 Ba6 27. Bxd4 Rxd4 28. Nc4 Rd8 29. g3 h6 30. Qa5 Bc8 
 31. Qxc7 Bh3 32. Rg1 Rd7 33. Qe5 Qxe5 34. Nxe5 Ra7 35. Nc4 g5 36. Rc1 Bg7 
 37. Ne5 Ra8 38. Nf3 Bb2 39. Rb1 Bc3 40. Ng1 Bd7 41. Ne2 Bd2 42. Rd1 Be3 
 43. Kg2 Bg4 44. Re1 Bd2 45. Rf1 Ra2 46. h3 Bxe2 47. Rf2 Bxf4 48. Rxe2 Be5 
 49. Rf2 Kg7 50. g4 Bd4 51. Re2 Kf6 52. e5+ Bxe5 53. Kf3 Ra1 54. Rf2 Re1 
 55. Kg2+ Bf4 56. c3 Rc1 57. d4 Rxc3 58. dxc5 Rxc5 59. b4 Rc3 60. h4 Ke5 
 61. hxg5 hxg5 62. Re2+ Kf6 63. Kf2 Be5 64. Ra2 Rc4 65. Ra6+ Ke7 66. Ra5 Ke6 
 67. Ra6+ Bd6 0-1

Game

 [FEN ""]
 [White "Stockfish "]
 [Black "AlphaZero"]

 1. e4 e5 2. Nf3 Nc6 3. Bb5 Nf6 4. d3 Bc5 5. Bxc6 dxc6 6. O-O Nd7 7. c3 O-O 
 8. d4 Bd6 9. Bg5 Qe8 10. Re1 f6 11. Bh4 Qf7 12. Nbd2 a5 13. Bg3 Re8 14. Qc2 Nf8 15. c4 c5 16. d5 b6 17. Nh4 g6 18. Nhf3 Bd7 19. Rad1 Re7 20. h3 Qg7 21. Qc3 Rae8 22. a3 h6 23. Bh4 Rf7 24. Bg3 Rfe7 25. Bh4 Rf7 26. Bg3 a4 27. Kh1 Rfe7 28. Bh4 Rf7 29. Bg3 Rfe7 30. Bh4 g5 31. Bg3 Ng6 32. Nf1 Rf7 33. Ne3 Ne7 34. Qd3 h5 35. h4 Nc8 36. Re2 g4 37. Nd2 Qh7 38. Kg1 Bf8 39. Nb1 Nd6 40. Nc3 Bh6 41. Rf1 Ra8 42. Kh2 Kf8 43. Kg1 Qg6 44. f4 gxf3 45. Rxf3 Bxe3+ 46. Rfxe3 Ke7 47. Be1 Qh7 48. Rg3 Rg7 49. Rxg7+ Qxg7 50. Re3 Rg8 51. Rg3 Qh8 52. Nb1 Rxg3 53. Bxg3 Qh6 54. Nd2 Bg4 55. Kh2 Kd7 56. b3 axb3 57. Nxb3 Qg6 58. Nd2 Bd1 59. Nf3 Ba4 60. Nd2 Ke7 61. Bf2 Qg4 62. Qf3 Bd1 63. Qxg4 Bxg4 64. a4 Nb7 65. Nb1 Na5 66. Be3 Nxc4 67. Bc1 Bd7 68. Nc3 c6 69. Kg1 cxd5 70. exd5 Bf5 71. Kf2 Nd6 72. Be3 Ne4+ 73. Nxe4 Bxe4 74. a5 bxa5 75. Bxc5+ Kd7 76. d6 Bf5 77. Ba3 Kc6 78. Ke1 Kd5 79. Kd2 Ke4 80. Bb2 Kf4 81. Bc1 Kg3 82. Ke2 a4 83. Kf1 Kxh4 84. Kf2 Kg4 85. Ba3 Bd7 86. Bc1 Kf5 87. Ke3 Ke6 0-1

White: AlphaZero Black: Stockfish

 [FEN ""]
 [White "AlphaZero "]
 [Black "Stockfish"]

 1. Nf3 Nf6 2. c4 b6 3. d4 e6 4. g3 Ba6 5. Qc2 c5 6. d5 exd5 7. cxd5 Bb7 8. Bg2 Nxd5 9. O-O Nc6 10. Rd1 Be7 11. Qf5 Nf6 12. e4 g6 13. Qf4 O-O 14. e5 Nh5 15. Qg4 Re8 16. Nc3 Qb8 17. Nd5 Bf8 18. Bf4 Qc8 19. h3 Ne7 20. Ne3 Bc6 21. Rd6 Ng7 22. Rf6 Qb7 23. Bh6 Nd5 24. Nxd5 Bxd5 25. Rd1 Ne6 26. Bxf8 Rxf8 27. Qh4 Bc6 28. Qh6 Rae8 29. Rd6 Bxf3 30. Bxf3 Qa6 31. h4 Qa5 32. Rd1 c4 33. Rd5 Qe1+ 34. Kg2 c3 35. bxc3 Qxc3 36. h5 Re7 37. Bd1 Qe1 38. Bb3 Rd8 39. Rf3 Qe4 40. Qd2 Qg4 41. Bd1 Qe4 42. h6 Nc7 43. Rd6 Ne6 44. Bb3 Qxe5 45. Rd5 Qh8 46. Qb4 Nc5 47. Rxc5 bxc5 48. Qh4 Rde8 49. Rf6 Rf8 50. Qf4 a5 51. g4 d5 52. Bxd5 Rd7 53. Bc4 a4 54. g5 a3 55. Qf3 Rc7 56. Qxa3 Qxf6 57. gxf6 Rfc8 58. Qd3 Rf8 59. Qd6 Rfc8 60. a4 1-0

Answer 2

Ok, I have to admit that I was wrong. Though I would maintain that it was due to knowledge of the expert opinion, not general obtuseness: To cite the paper: "However, chess programs using traditional MCTS were much weaker than alpha-beta search programs, (4, 24); while alpha-beta programs based on neural networks have previously been unable to compete with faster, handcrafted evaluation functions."

Apparently, chess is strategically deep enough, that you can out strategise somebody, who would be able to out calculate you. To me that's a big surprise because the development in chess engines had been going in the opposite direction. (Apparently there is still a slight caveat as to whether AlphaZero is really stronger than Stockfish: Stockfish played with just 1gb for the hashtables and 64 cores may not really be a match for four TPUs)

It's also a really, really exciting thing to happen, because AlphaZero very likely has very different strengths from traditional engines.

It also means that I update my belief of the significance of AlphaGo as a technological breakthrough by a lot. Basically smashing shogi, Go and chess with one single setup is completely amazing, not to mention dozens of other games that could likely be played on a superhuman level by AlphaZero.

There is a nice explanation as to why MCTS is actually a decent idea even for chess compared to alpha-beta search (from the paper): "AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation used in typical chess programs. This provides a much more powerful representation, but may also introduce spurious approximation errors. MCTS averages over these approximation errors, which therefore tend to cancel out when evaluating a large subtree. In contrast, alpha-beta search computes an explicit mini-max, which propagates the biggest approximation errors to the root of the subtree." (emphasis by me)

Here is my old answer, still containing some valid points, despite the conclusion being superseded by reality.

First of all Alphago is not a general game playing system. It is a program designed purely to play go and nothing else. It is however build from certain building blocks that have a much wider applicability, such as convolutional neural networks, which have been used in image recognition and which have immediate application in medical diagnostics, and reinforcement learning which was used to master the Atari games mentioned in the article.

Also, current engines do "learn" by self-playing: "Overnight, Lefler’s six computers play through over 14,000 games each during an eight-hour period. “Six machines times 14,000 games is a lot of games,” he says. And with every game played, the database gets deeper and richer. There is even sporting interest in watching computers play against one another The result of Lefler’s busily whirring machines is the ever-increasing prowess of Komodo."

To come to the bulk of your question:

There is an important difference between chess and go, at least from a programmer's perspective. Chess is more of a tactical game, whereas go is more of a strategic game. This means that in chess calculation depth trumps positional evaluation. That's basically the key insight that distinguishes the "old" engines like Fritz, Shredder, Junior and the newer generation like Fruit, Rybka, Houdini, Stockfish, Komodo. Because at the end of each line you have to evaluate the position and you want to calculate lot's of lines and the quality of the evaluation isn't as important as search depth, chess engines have lean and fast evaluation functions.

In go on the other hand the tactical complexity is too big even for computers. Consequently evaluating positions and moves accurately is key. What Alphago brings new to the game is this evaluation power, which is based on convolutional neural networks.

To finally get to my point: Whereas chess evaluation functions are lean and fast, neural networks have millions, sometimes billions of parameters. Because "learning" in this context means tweaking parameters, there is much more possible progress for self learning go programs.

So, yes you could use a setup like Alphago to create a chess engine, but it wouldn't be particularly good. Running the evaluation function would take so much time, that you'd have to utilise a huge cluster of gpus to get to necessary search depths (which is what Alphago does). You could create a very good evaluation function, but the speed tradeoff isn't worth it.

Answer 3

There is a project called spawkfish that attempts to do just this. It is a neural network-based engine whose purpose "is to explore how recent advances in computer Go can be applied to the world of computer Chess".

It is a young project and the engine is still quite weak. Playing it is interesting, because its positional play is better than its tactics.

Answer 4

Can a similar AI win at chess? Can it achieve pure self-training?

The short answer is "No!"

Chess and go are radically different in their relative simplicity and relative complexity which derives from their geometry and how you win. These combine to make a program which is good at one useless at the other.

In chess you win by checkmating the opponent, points don't count. Of course a sensible opponent will often resign before you deliver checkmate but the principle is the same. In go you win by having more points at the end of the game. If I have a king and queen and you have a king, rook and pawn but you have built a fortress then it doesn't matter that I have 9 points for the queen and you have just 6 points for your rook and pawn. The game is a draw.

This makes a fundamental difference in the complexity between chess and go. In go you can just keep score and you will know who is winning. In chess the only way you can know who is winning is by pure calculation. In this sense chess is much more complex than go.

At the same time, because of the geometry of the two games, there are orders of magnitude more possibilities in go than in chess. In this sense go is much more complex than chess.

A chess program works by brute force calculation of all the possible moves up to a certain depth which determines its strength. A go program cannot work like this and play anything more advanced than beginner level go.

The basic aim of go is to control more territory than your opponent. At the end of a game it doesn't matter if the difference is 1 stone or 100 stones, both are wins. Every time you place a stone you do two things. You increase your territory, either potential or actual, and you decrease your opponent's.

Sometimes, when it is actual increase or decrease in territory, it is easy to calculate the value of the move, but when it is potential it is very difficult to evaluate. As a weak go player I understand the "actual" much better than the "potential" and a stronger player will beat me by building much greater potential territory in the center while I build smaller actual territory on the edges and in the corners. The stronger player will have built up the ability to judge through intuition and feel from playing lots of games and recognizing how to build "potential" territory.

Earlier I said that every time I place a stone it increases my territory (actual or potential) and decreases my opponent's (actually if it is a stupid move it will do the opposite!). In any given position not all moves are the same. A stone placed in one position can be worth much more or much less than a stone placed in another.

Typically in a game there will be small "fights" where players place their stones near each other, marking out their territory and limiting their opponent's. Meanwhile there are possibilities to start staking out territory in another part of the board or switch to a fight somewhere else where both players already have stones.

What is very important in these situations is knowing when to stop one fight, because the potential gains have diminished, and to either switch to another fight or perhaps strike out into virgin territory. Sometimes this depends on hard calculation but often it is much more nebulous and not subject to calculation. As a weak player this is where a strong payer will crush me every time.

What the computer does in these situations is use probabilistic methods to generate an expected score for a particular move. Sometimes the actual value will turn out to be a little bit less, sometimes a little bit more but over the long haul it will even out more or less. It will keep picking the move with the highest expected value with the expectation that over the long haul of a game small errors will cancel out and its strategy will win.

This is not a strategy which sounds familiar to chess players and is not one which is going to work in chess. It is something which sounds familiar to anybody who follows what goes on in the share markets. It sounds very similar to something called "high frequency trading" where computers will make thousands of small bets or just proposed bets every second to "nickel and dime" the market and perhaps even to move it very marginally in their favor over periods of milliseconds.

Already the financial markets are dominated by these kinds of algorithmic trading which suggests that this kind of program has already triumphed in a far more lucrative area than a board game.

Answer 5

(Anyone how wants a deep technical discussion for AlphaGo can look at my post)

Short answer: No

Long answer:

First, we need to understand why Google didn't implement alpha-beta into AlphaGo. Stockfish and Komodo (and all chess engines) have alpha-beta, why wouldn't AlphaGo?

Reason: there is no easy and cheap way that can accurately evaluates a Go position statically.

In Chess, we can always count the materials, a very effective way to evaluate a position statically. Although not perfect, it's very fast and a very good proxy for chess.

Searching the state space with Monte-Carlo is an inferior method to alpha-beta. Google would have implemented alpha-beta if they could, but they couldn't. Thus, they were forced to use something much slower.

Chess engine would not play better with Monte-Carlo.

Answer 6

I disagree with the other answers. I am computer scientist who works professionally in the area of artificial intelligence and am also a candidate master in chess and 3 dan in igo.

I think it is unclear at this time whether Deep Mind's methods could be applied to chess, but I think it is possible.

Currently, the top chess-playing programs are increasingly relying on heuristics and attempting to use the AlphaGo architecture for chess would in some ways be in the same line of thinking.

One key architectural feature of AlphaGo that would have to be altered is its method of identifying key squares (or heat maps), which is particular to igo-like games and is not directly applicable to chess. Some analog of this method would have to be developed to make the AlphaGo architecture relevant to chess. For example, we could have the concept of "key pieces" rather than key squares.

I think the argument that the AlphaGo architecture is not relevant to chess because chess is more tactical is not a very good claim because ultimately both have search trees which are similar enough in shape that AlphaGo could definitely be adapted to chess.

Answer 7

The answer is Yes! Google just proved this yesterday, when AlphaZero beat the best chess program using only knowledge about the rules and pure self training with no human chess knowledge used. The accepted answer is wrong. The link to the article is here :link

Answer 8

To see AlphaZero in action, follow http://lczero.org/ or play at http://play.lczero.org/