Is AlphaZero really a breakthrough in AI?
medium.com
medium.com
Firstly, a major challenge in training an AI of this sort is getting enough labelled data. They played 300,000 games from memory. Under normal circumstances, that requires access to 300,000 games played by experts so the AI can learn to copy what the export does. That is how Alpha Go did it.
AlphaZero neatly side steps this by generating it's own training data by playing itself. If how to do this was "obvious", it would have been done a long time ago.
Secondly, they parallelised things. Alpha Go trained the AI from the results of each game as it is played. AlphaZero played 1,250 games simultaneously, and feed the results into the AI as they became available. The result is it took well over an order of magnitude less elapsed time to train AlphaZero than Alpha Go, even though the CPU cycles may have been roughly similar.
Finally, he overstates how hard it is to customise the engine (Markov algorithm + AI) to a game. There are two pointers to this. Firstly, it took them over 2 years to create Alpha Go. It became the world champion on 23 May. Now, 7 months later we have AlphaZero. But AlphaZero didn't to play just one game in those 7 months: is the best player on the planet for 3 games: Go, Chess, and Shogi.
I don't know whether they customised the AI for each game, but I suspect if the input and output layers were wide enough to accommodate the largest game they could use the same one for each. The Markov engine does have to know how to make all legal moves from any game position, but coding that isn't rocket science or particularly time consuming. The AI does _not_ start out knowing those rules - it learns them from the Markov engine. It's all very DRY.
This sort of engine only works are a particular style of game - one where their is only a smallish set of well known moves at each step, and the playing board is also smallish (19x19 in the case of Go, with three possible states for each position: empty, black, white). Most board and card games fit this description. AlphaZero can teach itself to play any of them to a standard higher than any human can play them, and do it within a few hours, not the decades it takes to create a human grand master. The net result is Homo sapiens reign of supremacy at playing this style of game is now over. For this entire niche our brains have been firmly relegated to a 2nd class intelligence.
I don't know whether you would call pulling this off a breakthrough, but I do know the techniques they applied will be copied by man+dog for years if not decades to come.
Learning by self-play is nearly as old as AI itself. TD Gammon, one of the very first algorithms to reach superhuman levels in a nontrivial game, learned by self play. The basic ingredients for AlphaGo Zero, Monte-Carlo tree search and use of a convnet to evaluate board positions, were known already.
The major contribution of the AlphaGo Zero and AlphaZero was IMO the realisation that MCTS acts as a "policy improvement operatior", and that reinforcement learning becomes far more stable when it's used in conjunction with MCTS.
It's a major contribution and could represent a big shift in the field. But we won't be able to judge how big of a contribution until the research is more reproducable.
Thank you for mentioning this! Neural-nets self-trained bots have been a thing for quite a while in backgammon. Chronologically, from my memory: TD Gammon, Jellyfish, Snowie, GnuBG [1], XG (eXtreme Gammon) [2]
(Disclaimer: I had a sign flip bug in the Reinforcement Learning step of the Lines of Action bot that made it worse every generation! After a few thousand iterations it was _really_ bad at playing lines of action)
(Acton is a suburb of London and has more railway stations bearing its name than any other place in the UK)
They are, of course, still likely to struggle against an advanced player experienced with the Abingdon Gambit.
It was done a long time ago. Arthur Samuel's chequers program (1959) improved by playing against itself in thousands of games.
People can and do improve that way too: https://www.chess.com/forum/view/general/playing-against-you...
When learning Chess or Go, playing whole games with myself would be too tedious. Do people really do this?
But I have played countless opening sequences in chess and many many joseki lines in go, I have practised various piece mating combos in chess and different yose techniques in go, one does chess problems from newspapers or books and of course everyone knows you do go problems (tsumego) to get strong at go – this means I only ever play small subsets of both games against myself. Never whole games. It is this ability that the machines have over us.
The only whole games I've played are both sides of grandmaster level competitive-games in each board-game. But then, that's not really playing against myself where I choose each move. Some expert has chosen the move for me. Interestingly, AlphaZero does not need to learn this way because it can play itself so many times. Because that amount of times would be too tedious (possibly even unfeasible) for a human we will always continue to learn from expert play.
When AI is smart enough to know what expert play _is_ it may go back to using that technique.
Chess World Champions Robert Fischer and Magnus Carlsen notoriously did as children. Magnus Carlsen even recommended it as one of his top 13 tips to improve :
Coding a set of rules for chess may not be a big deal. Encoding it into a neural network architecture, so that the network only explores valid game states, _is_ a big deal, like the article says.
The paper itself clarifies that the network architecture is matched to the game board grid. Each position and each move are represented by features described as sets of "stacked" planes (i.e. 2d feature vectors). So for example, in chess, the board is a set of 8 x 8 planes, and the movement of a piece is represented by a set of 56 planes for "queen moves" (continuous moves in any direction) and another 8 for "knight moves" (jumping over pawns). How they constraint specific pieces to subsets of those planes, is not explained, or I missed it.
That's not an obvious setup, neither is it a trivial one. More to the point, it's absolutely not something you can just copy and paste to an arbitrary other game- it can only be applied to a game that uses the same board and same pieces as chess. So, for example, no, you couldn't use that same architecture to represent a game of poker.
I think you're imagining some setup in which a neural net is directly communicating with an external rule engine that generates a set of legal moves for each piece in each board configuration. That's not how it works. You know how people say that Neural Nets are "black boxes"? That's what they mean. You can't just plug into arbitrary steps of their training with arbitrary external processes. You have to setup everything right at the input and then wait patiently at the output, until what you want comes out. Then you can plug that in to whatever reasoning loop you want to set up.
So like I say, it's not a trivial thing and it doesn't generalise very well to arbitrary problems. You need to match the architecture to the problem. For example, that's why ConvNets have been studied extensively for vision- their architecture is specifically tailored to vision problems.
Hence also the doubts expressed in the article about the claims to general game-playing ability. Yeah, you might imagine that it's possible to create a specialised architecture to play any particular game (or even sets of games with similar setups, like chess and shogi)- but it's not clear how exactly you'd do that automatically. Handcrafting a thousand architectures for a thousand different games is not very "general purpose", is it?
> Most board and card games fit this description.
Most card games don't, because they are not perfect information games.
David Silver himself, who led AlphaGo project, wrote in 2016 in "Deep Reinforcement Learning from Self-Play in Imperfect-Information Games" https://arxiv.org/abs/1603.01121 "While many machine learning methods have achieved near-optimal solutions to classical, perfect-information games, these methods fail to converge in imperfect-information games".
For Heads Up (two players) Limit (bet sizes are fixed) Hold Em (a popular modern variant with two hole cards and five community cards) such a strategy was developed and you can view it online, it's essentially unbeatable. Its name is Cepheus.
Instead of the output of the neural network being the move to make then, couldn't you make the output be the weight/probability you should fold, call or raise?
On the timeline issue of course, I don't it's reasonable to make any assumptions about what that implies about the algorithms. It may be that Chess was solved, the dev team went on a 6 month binge, then shoved a Go board in front of the machine and it learned it in a weekend. Alternatively they may have gotten to a point where 5 of their top target games had special cases to learn before they were ready to show off the Chess engine, and that it took 7 months to get the other applications over the line.
No one knows how Stockfish behaves with that many search threads, since no one tested it. I don't know if there is any data on how Stockfish scales with number of CPUs but I seem to remember that being one of the weaknesses of the engine, and that commercial engines like Komodo scaled better with larger number of CPUs.
Anecdotally on 2.8 GHz 8 core 64bit CPU with 8 threads and 16 GB hash size it calculates about 7-8 million ply per second at the beginning of the game, and much more later when there are less peaces on the board. AlphaZero's setup, with 64 threads on 32 physical CPU cores, calculated about 70 million ply per second, with tiny 1 GB hash (i.e. the engine could remember less of what it calculated previously).
But my Stockfish on computationally weaker setup clearly flags some of the moves in the match as mistakes on the 64 threaded Stockfish. I would really like to understand why. Is it because if you have more resources to see deeper you see how hopeless the situation is, or is it something else?
I am sure we will see more of these matches. It would be nice if Google volunteered some computing resources and entered TCEC regularly.
Also read this comment from Stockfish author: https://www.reddit.com/r/chess/comments/7igro1/alphazero_rea...
Turns out that there is a good reason for 1GB of hash : it is an easy way to get a high number nodes searches per second (ie high kn/sec) on many threads.
http://support.stockfishchess.org/discussions/questions/655-...
Stockfish is a major PIA to configure to use correctly and I do not blame AlphaZero for taking the easy way out..
I turned on 30 threads for Stockfish 8 on my 2x Xeon 2670 with 64GBs of RAM and tried to adjust hash memory.
When going past 1GB hash my kn/sec dropped from 25kn/sec to less than 10kn/sec
It might have to do with how 2x CPU configurations work, locality, who knows.
A0 should have let Stockfish use its opening book though.
> A0 should have let Stockfish use its opening book though.
Has it been confirmed that it didn't? As far as I can tell, DeepMind never said that Stockfish didn't use an opening book or endgame tablebase, only that AlphaZero didn't: https://twitter.com/demishassabis/status/938347604462542849
The only time opening books are mentioned in the arxiv paper is when they are described as standard components of chess engines; while it doesn't explicitly state whether Stockfish was allowed to use them in the tests, I would think it likely: https://arxiv.org/abs/1712.01815
The rumor that Stockfish didn't have an opening book seems widespread but unsourced.
The value network is simply updated to match the real outcomes of games of self-play.
The policy network is updated to match the results of a tree search; for each board position many thousands of lines are explored using the value and policy networks, and then the policy is updated to match (a somewhat 'sharpened' version of) the number of lines in which each move was chosen.
When exploring each lines, at each step the move 'a' is chosen from the current board state 's' which maximizes Q(s, a) + P(s, a) / (1 + N(s, a)), where R is the policy network, Q is the average value network evaluation for lines where 'a' was picked from 's' (with the appropriate signs to match the current player at 's'), and N is the number of simulations in which 'a' was picked. When we reach an unseen board state, it is evaluated with the policy network and a new line is explored from the root.
This is less circular than it may seem because:
a) The value network is trained using real outcomes. b) Towards the end of the game, the tree search sees real outcomes.
This training procedure allows the network to 'bootstrap', learning progressively more complex knowledge about how to play effectively.
> and a policy network which estimates the probability that each move should be played.
So for this network, the input is the before and after board state and the output is the probability that this move should be played?
* evaluate a position by playing lots of random games until the end using "likely" moves (in their order of likelihood). this gives you a "win rate" (i.e. empirical probability of winning) that is used as a position's score.
* train a neural net to predict that win rate based score (without having to play random games).
* use that neural net to predict which moves are "likely", thereby making the playing of random games more efficient, yielding more expressive scores, which in turn again improve the accuracy of the network.
* use the above described algorithm to self-play games, where every move is determined by looking at the win-rates given by the neural-net-driven quasi-random games, continuously training the score-estimating neural net.
This is just my high-level understanding without knowing too much about the topic. Monte Carlo Tree search is a little more complex than what I try to explain here.
1/ Initialise a random neural network.
2/ For any given position, use the neural network to estimate the probability of win (or draw).
3/ Play multiple branches out to the end, to get an estimate of the 'real' probability of win (for the current skill level)
4/ Modify the neural network so its estimate of the probability of win more closely matches the actual probability of win
5/ Goto 2 :)
When working in academia, I found it very common for research papers to not come with source code or enough information to allow you to replicate experiments yourself. You usually have to pester the author. I don't find the (valid) criticisms here that unusual. I'm not sure why they wouldn't release the moves for all the test games played though seeing is that should be simple to do.
As for Stockfish and AlphaZero running on different hardware...AlphaZero's approach is built around taking full advantage of what TPUs can do quickly and Stockfish doesn't utilise TPUs so how are you meant to make this fair? Does Stockfish eventually level out when you throw enough hardware at it? Doesn't DeepMind's claim about AlphaZero evaluating significantly less moves per turn invalidate the criticism about the hardware used?
It’s always been a trade off between using more expensive heuristics on fewer moves or cheaper heuristics on more moves. The “number of moves” thing only says that they went all-in on the better heuristics angle. In fact, there was something posted recently about test games where they played go by just using the first move suggested by the search heuristic and that was pretty strong.
OK, but AlphaZero essentially runs on different hardware so how are you suppose to make the comparison fair? You could give Stockfish access to the TPUs but wouldn't do anything with them.
I'm sure they're saving some stuff for the full paper. Don't know how many games that will include, but hopefully it'll have some shogi game records too.
It's like they don't understand the exponential nature of depth search in chess…
That does sound fishy,
In some of the games vs AlphaZero, Stockfish makes errors that it _itself_ appears to be able to judge as huge blunders. In game 3 (which people view as a masterpiece of long term strategic thinking by AlphaZero) one of these is at least a +10 swing to AlphaZero as white. That's about the same as throwing away your queen. Without the weird time controls put in place, it seems unlikely that we'd be seeing blunders like that. As I said before, I'd still expect AlphaZero to win, and in many cases it was already ahead before these mistakes, but it's worth mentioning in any analysis.
To me, what follows does not seem to justify this claim, but it is not my field. In addition, some of his arguments seem to be beside the point - for example, he asks "Does AlphaZero completely learn from self-play?", and while saying generally, yes, he objects that encoding the rules was a non-trivial matter. While that certainly seems to be true, it does not seem to have much bearing on the claim that AlphaZero apparently learned to win through self-play. That, to me, seems to be its singular achievement: the absence of human-written tactics and strategy (unless the encoding of the rules somehow prefigured them, which is not being claimed here, and which seems highly unlikely.)
The fact alone that DeepMind is making such a big todo about self-play is a bit iffy in and of itself. It's probably a sign that they're more interested in catching the attention of the popular press and the general public, than of anyone who has at least read through Russel and Norvig [i.e. a popular AI textbook that mentions TD Gammon (in the Adversarial Search chapter)].
In any case- that's a claim in the paper and it's just as valid to scrutinise it as any other claim. But even more so if it's repeated in the lay press without anyone bothering to do their homework...
Btw, if I may be a bit nosy- what is your field?
The author can certainly scrutinize whatever claims he likes, but does he make his case? I suppose he can certainly say that without further information, the outcome simply cannot be independently evaluated.
I'm actually not joking. I wonder how much different it would be to teach an AI like this how to play more complex games. I imagine Axis and Allies wouldn't take much, but Third Reich is notoriously complicated. The quickest war-length game I've played took a week of playing 3-4 hours per day and games like that seem to me to be much more similar to real world problems, with multiple different sorts of trade offs that interlock with each other.
Are neural AIs like this actually feasible to train for problems like that or are other AI techniques better suited to it? What about games with multiple different game systems, like board games with a card game element to them like Settlers of Catan? Would you need to use several different types of AI to optimize different parts of the game?
OpenAI's gym is probably a good place to start, as you can crib how they do it for a whole bunch of games. https://github.com/openai/gym
In a lifelike situation the AI will not have access to the inner state of the game, but instead has to gather the information via the same (restricted) mechanisms as other players.
edit: I should probably clarify that the above is about competitive StarCraft. I should probably learn to play GO, too.
Even if we all agree that AlphaGo is the DeepBlue of Go, we are still having a few more layers to take before humans need to worry.
https://www.wired.com/story/googles-ai-declares-galactic-war...
(Aug 2017)
Edit: this is an oversimplification
Edit: https://github.com/glinscott/fishtest http://tests.stockfishchess.org/tests