Is AlphaZero really a breakthrough in AI?(medium.com)
medium.com
Is AlphaZero really a breakthrough in AI?
https://medium.com/@josecamachocollados/is-alphazero-really-a-scientific-breakthrough-in-ai-bf66ae1c84f2
83 comments
> 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.
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.
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.
> TD Gammon, one of the very first algorithms to reach superhuman levels in a nontrivial game, learned by self play.
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]
[1] http://gnubg.org/
[2] http://extremegammon.com/
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]
[1] http://gnubg.org/
[2] http://extremegammon.com/
Self play reinforcement learning has been a thing for decades it really isn't new. That's how I wrote my Lines of Acton and Dominion AIs years ago.
(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)
(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)
Lines of Acton sounds like an excellent game for Londoners.
(Acton is a suburb of London and has more railway stations bearing its name than any other place in the UK)
(Acton is a suburb of London and has more railway stations bearing its name than any other place in the UK)
Ah yes, a derivative of Mornington Crescent more suitable for computers to play.
It'll be a mark of truly general AI when computers can learn to play Mornington Crescent, and play to win.
They are, of course, still likely to struggle against an advanced player experienced with the Abingdon Gambit.
They are, of course, still likely to struggle against an advanced player experienced with the Abingdon Gambit.
> 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.
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...
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...
> People can and do improve that way too
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.
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.
> When learning Chess or Go, playing whole games with myself would be too tedious. Do people really do this?
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 :
https://www.youtube.com/watch?v=FMaaHd7aFIs
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 :
https://www.youtube.com/watch?v=FMaaHd7aFIs
Huh, that's interesting. I've read up on both of them and didn't know that factoid. Maybe that's what I'm doing wrong in my chess career.
>>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.
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.
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.
>> Finally, he overstates how hard it is to customise the engine (Markov algorithm + AI) to a game.
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?
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?
The question is how much those architectures encode insights about how to play the game well, vs just how to play the game at all. After all, you have to teach general-purpose humans the rules of each specific game.
I agree, but:
> Most board and card games fit this description.
Most card games don't, because they are not perfect information games.
> Most board and card games fit this description.
Most card games don't, because they are not perfect information games.
Is it really impossible to adapt Deepmind's approach to, say, poker? I don't see anything fundamentally impossible, but I'm no RL expert.
I would consider a successful application of AlphaZero algorithm to imperfect information games to be a separate achievement, not a done deal.
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".
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".
Thanks for that paper, very interesting.
Whereas the "correct" way to play chess will consist of knowing always exactly which move to make, most Poker variants will require a statistical model that says things like "In this situation we will fold 4% of the time, call 89% of the time and raise 7% of the time". Then the actual choices you make are random with a specific weighting. So that's hugely different. This truth is why strong poker analysts are always so equivocal. "All options are good here" annoys people but it's often true.
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.
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.
> Whereas the "correct" way to play chess will consist of knowing always exactly which move to make, most Poker variants will require a statistical model that says things like "In this situation we will fold 4% of the time, call 89% of the time and raise 7% of the time". Then the actual choices you make are random with a specific weighting.
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?
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?
Card games are delayed bounded information games. (With one turn lag to one match lag.)
The incomplete information is strictly bounded.
Forgive me if this I'm being waaay too naive, but it doesn't seem like the parallelism side of this is a big deal. Playing N games in parallel and then feeding them back in for training doesn't seem like an incredibly innovative idea?
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.
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.
Playing the games simultaneously is actually innovative in how it let's them learn faster. If you play one game at a time consecutive moves are highly correlated which makes it difficult to make learning updates after each move. If you're playing 1250 parallel games that are starting and restarting so that they're at all at different stages of play, you can do an update after every move in every game and make better progress faster. This is known as Asynchronous Advantage Actor-Critic (A3C) and is a highly cited method discovered by the DeepMind team [1].
[1] https://arxiv.org/abs/1602.01783
[1] https://arxiv.org/abs/1602.01783
I would like to see a rematch with Stockfish configured correctly. I give Stockfish at least 1 GB of hash per thread. In AlphaZero match they had 64 threads and only 1 GB of hash for all of them.
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.
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.
It seems to me that that someone can prove that the configuration mattered by pitting a correctly configured Stockfish against the configuration used by AlphaZero, and see what the outcome is for 100 games.
I haven't read the paper, but some of the constraint choices seem odd to me (1 minute max per move?).
The paper suggest that the more time you give Alphazero, the stronger it becomes too.
Unfortunately, AlphaZero is private and no one has access to either the code (as commercial product) or resources it needs to run (TPUs). So, only Google can do this experiment.
OP is suggesting properly-configured-stockfish versus how-alphazero-configured-stockfish for 100 games.
Don't think Google/Deepmind is interested in TCEC at all. They got bigger and better things to do with the research. Also, current TCEC hardware does not support Alphazero. Eventually people will be able to replicate the results and we'll have a few different versions of Alphazero successors.
Also read this comment from Stockfish author: https://www.reddit.com/r/chess/comments/7igro1/alphazero_rea...
Also read this comment from Stockfish author: https://www.reddit.com/r/chess/comments/7igro1/alphazero_rea...
I too was dissapointed at the 1GB of hash given to Stockfish.
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.
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.
Interesting information on reasons for choosing a 1GB hash size, thanks.
> 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.
> 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.
Can anyone summarise how self play works here if AlphaZero only starts out being told the rules of the game? Does it initially plays games using completely random moves as both players? Is it only told who the winner is with no other feedback? How is it able to learn e.g. that certain moves at the start eventually lead to a win?
There is a value network which estimates the win rate for the current player from a given board state, and a policy network which estimates the probability that each move should be played. As of the more recent iterations, these networks share their bottom layers for greater computational and training efficiency.
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.
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.
Thanks. How does this play out when you're training against a single self played game then? Does it play a whole game with its current networks and then once it knows the winner it goes over each move after to train itself?
> 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?
> 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?
The input is the current board-state and the output is the probability of each move.
I think the separation of value and policy networks was a feature of the older AlphaGo systems, but not AlphaGo Zero
Oops, I obviously meant 'P is the policy'
It is my understanding that the system uses wins to learn to estimate the value of board positions: the position just before the win should be highly valued for the winner and inversely so for the loser. Going back further in time, there will be less confidence, but still a higher value for the winner.
I think the breakthrough is how AlphaZero combines reinforcement learning with Monte Carlo Tree search [1].
* 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] https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
* 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] https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
Very roughly, it works as follows:
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 :)
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 :)
I suppose, yes. This is called "reinforcement learning".
Can you elaborate? What are the input and outputs of the neural net?
Not sure how big breakthrough in Ai domain it is, but after watching some of the AplhaZero games against Stockfish (available at youtube) I'm convinced it's a true revolution in how computers play chess. It plays so much more like humans do, without the usual crazy micro management that other chess engines love to do. It's not boring to watch, makes very little weird moves that only a computer would ever make. If I didn't know what it is, I would presume that it's a real player (and extremely good one).
After some initial successes in computer chess, the defeat of grand masters was declared to be imminent, but human players struck back with strategies that considerably delayed that outcome. I wonder if there is any possibility that a good player could find a weakness in AlphaZero's game, but the way you describe it makes that seem highly unlikely.
Given their track history, I don't think it's likely the DeepMind team are trying to be sneaky here. They'd be found out eventually given how big their claim is.
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?
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?
More hardware still means better results — or there would be no need to cap the time per move.
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.
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.
> More hardware still means better results — or there would be no need to cap the time per move.
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.
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.
They hinted that a full paper will be released in the future.
Yes. And not just a hint; Demis Hassabis (DeepMind founder) explicitly stated "full paper coming soon, will have things like early games": https://twitter.com/demishassabis/status/938347604462542849
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.
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.
[deleted]
It seems weird for someone with experience in both chess and --especially--AI to write, “This improvement on computing power paves the way for the development of newer algorithms, and probably in a few years a game like chess could be almost solved by heavily relying on brute force.”
It's like they don't understand the exponential nature of depth search in chess…
It's like they don't understand the exponential nature of depth search in chess…
"However, the experimental setting does not seem fair. The version of Stockfish used was not the last one but, more importantly, it was run in its released version run on a normal PC, while AlphaZero was ran using considerable higher processing power. For example, in the TCEC competition engines play against each other using the same processor."
That does sound fishy,
That does sound fishy,
It would be good to see a definitive playoff. I've no real doubt that AlphaZero would triumph, but in people's breathless coverage of the games nobody seems to point out Stockfish's various 5-10 pawn blunders (all of which my version of Stockfish finds when annotating the games with 60 seconds per move).
What do you mean by "various 5-10 pawn blunders"? Is that a count of the number of blunders or some sort of score?
Stockfish and other mainstream engines will judge a position in units of centipawns - one hundredth of a pawn. Largely this will be to do with material on either side. For example, if you throw away a pawn with all else being equal, I'd be up 100 centipawns. If I'm white this gets written as "+1.00", and if I'm black it's "-1.00". The score is also based on a strategic evaluation of the position (and positions to come) using (in Stockfish's case) some heuristics. It's worth noting that it's this evaluation of a position at which AlphaZero appears to be three orders of magnitude better than Stockfish.
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.
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.
Got you, thanks for the reply.
The author is actually claiming something more serious than the title suggests: "...all the concerns added together cast reasonable doubts about the current scientific validity of the main claims."
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.)
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.)
As many others have pointed out, self-play in adversarial AI goes back to TD Gammon, in 1992.
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 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?
To a typical insurance salesman, the fact that self-play has been around for a while raises the question of why not until now, for chess? Maybe self-play in chess had already come within a whisker of this result? Has the state of the art reached the point where a bespoke self-play solution for any given chess/go -like game is now unremarkable? Is chess regarded as a sideshow that is given more attention than it deserves from the press and public? Even if this outcome is completely unremarkable from a technical point of view, the question remains, but as a social one.
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.
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.
When can we have an AI that plays Third Reich? But not too well, I want to at least have a chance.
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?
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?
The hard part is probably writing a program to encode the rules of the game. Then, you can figure out how to represent the state (i.e. the board and the player's cards/resources etc) as a matrix or array (i like how this is done in NLP, they tend to represent each character/word/token as a 1-hot vector and then reduce the dimensionality of these (normally really sparse) inputs.
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
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
Engineering breakthrough?
An AI which excels in imperfect information games (card games, Starcraft) would be a real breakthrough. Raw calculation power is bound to win games with a finite set of possibilities. The huge leap would be the ability to handle probabilites: taking guesses, making assumptions and coming into some kind of successful conclusions based on those.
Go cannot be won with raw power though. It has a lot of the constraints of incomplete information problems.
So every move cannot be precalculated? Some of the constraints may be there. The completeness of information available would be the definition of breakthrough for me. In this case, the first state of the game is presented in total with 100% accuracy. So are all the steps from there onward. In my opinion, the challenge for a breakthrough comes when most of the actions of other players happen in dark and no feedback is presented to the AI.
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.
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.
I'm no AI expert, but I won't start to worry about AI being used generally (the last point of the article) until it beats a really complex game like real time strategy title StarCraft.
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.
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.
> Churchill guesses it will be five years before a StarCraft bot can beat a human. He also notes that many experts predicted a similar timeframe for Go—right before AlphaGo burst onto the scene.
https://www.wired.com/story/googles-ai-declares-galactic-war...
(Aug 2017)
https://www.wired.com/story/googles-ai-declares-galactic-war...
(Aug 2017)
Whether it was a breakthrough or not, I have to say, the moves it played were certainly "creative" in a profound sense.
If possible at all, could you give an example for casual chess players?
Seconded. We all want a glimpse of what the "AI" is doing, and see that one step ahead that human minds could never do :)
Not OP, but I highly recommend checking out ChessNetwork's recent videos on the games: https://www.youtube.com/user/ChessNetwork/videos
I would recommend some analysis videos by
agadmator. Here's a good one: https://www.youtube.com/watch?v=lb3_eRNoH_w
International Master Daniel Rensch made a very informative YouTube series about the match, I highly recommend it. Here are the highlights:
https://www.youtube.com/watch?v=6z1o48Sgrck
https://www.youtube.com/watch?v=6z1o48Sgrck
probably a (big) incremental step over a previous breakthrough
Considering how much ai is hyped it is getting harder and harder not to be a skeptic.
From what I recall, DeepMind never mastered Pacman.
No, is an optimization of something already existing. An innovation, but not a breakthrough per se.
Edit: this is an oversimplification
Edit: this is an oversimplification
It could perhaps be said, then, that the Alpha series as a whole is a rolling breakthrough? Each new generation introduces changes that do not seem major compared to the ideas in the foundation of Deep Learning, but this actually allows to surpass state-of-the-art, improving performance on all relevant parameters (and not by a few percent). Dismissing these updates as technicalities is a dubious position.
Isn't that how all newer version of chess engines - including stockfish, improve?
Edit: https://github.com/glinscott/fishtest http://tests.stockfishchess.org/tests
Edit: https://github.com/glinscott/fishtest http://tests.stockfishchess.org/tests
Prior to AZ, some competent people had doubts if self-taught NN could compete at all with a mature chess engine at its strongest setting. You know how that went. The improvement rate of subsequent Alpha revisions is incomparable to what software like chess engines shows. Hence, the tendency to evaluate each one as a breakthrough.
Personally I believe that "breakthrough" is a non-technical word that's hard to define, but "improvement rate surpassing most optimistic expectations for a given field at a given time" could probably qualify as a criteria.
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.