mfb said:Which other games do you expect next?
...
It will be interesting to see if the AI can be adapted to work with a broader range of problems.
mfb said:Which other games do you expect next?
Chess and Go have no randomness and no hidden information - all players always know the full state of the game. Many card games have hidden information (cards not shown to everyone) and randomness, for example. There is a Poker-AI beating humans but that is a different topic..
Delta² said:No , I am not saying that they lie on how they trained the program , but I don't know if they got some aid from GMs regarding the development of the source code of the program. Conventional chess program developers cooperate often with GMs and that reflects on the source code (mainly the source code regarding its evaluation function) of the conventional chess program. I thought that Alphazero developers may also did the same thing.(in simple words, a GM can tell a programmer how he/she thinks when playing chess and the programmer can somehow incorporate this info into the source code of the program)
Haelfix said:I gather this was done with some form of a RNN.
What's funny about this business is that the general algorithms and structures have been known for well over 30 years. Some tweaking is needed for the particular game of course, but why has it taken this long for results like this to all of a sudden show up. It just seems like a completely obvious thing to try with chess, so I doubt this team were the first to try this approach.
I often wonder if this type of system could be applied to mathematics, giving it basic rules of math and scoring according to deriving known mathematical complexities, seems pretty simple to a layman like me but perhaps I'm missing something obvious as I'm not much of a mathematician.PAllen said:It seems that except possibly for the core neural network itself, huge changes and breakthroughs would be needed to apply their (self learning, with no training data) system to incomplete information, open type problem areas
jerromyjon said:While I find this quite interesting, it also seems quite "unstructured". What I mean is that I assume there are no constraints on repetition, and I wonder how replaying the same series of identical moves affects the weighting of "good play" when there are random repetitions. I would think having some type of iteration scheme to allow it to play through all possible games would give it the power to determine the best possible move out of all options but I don't know if that is out of the range of possible in a finite time.
Many many times greater than the number of atoms in the observable universe.Ryan_m_b said:For chess it certainly isn’t possible as the number of legitimate games is often compared to the number of atoms in the universe.
Okay, now I agree with the title of the post, "mind boggling"!PAllen said:Many many times greater than the number of atoms in the observable universe.
jerromyjon said:While I find this quite interesting, it also seems quite "unstructured". What I mean is that I assume there are no constraints on repetition, and I wonder how replaying the same series of identical moves affects the weighting of "good play" when there are random repetitions. I would think having some type of iteration scheme to allow it to play through all possible games would give it the power to determine the best possible move out of all options but I don't know if that is out of the range of possible in a finite time.
Very good point, I didn't think about it that way. Thanks.phyzguy said:So the games it was learning from were far from randomly selected.
PAllen said:Many many times greater than the number of atoms in the observable universe.
PAllen said:The group was concerned with these rats holes eating up too much processing time, so they added a rule that games over some threshold length were scored as draws (the paper does not specify what value they chose for this cutoff).
anorlunda said:Limiting the number of moves before declaring a draw would let you make the number of possible games more finite. But I think that it is beside the point. These neural nets don't memorize specific games, they remember gain factors (weights) in their neural nets. I think neural nets are fascinating because they are almost the antithesis of logic.
I would guess they cut off after something like 500 or 1000, because these are vanishingly rare even between computers. Games of length 200 or more occur even in human tournaments. I agree the cutoff has nothing to do with minimizing the set of all possible games, and everything to do with maximizing the number of self play games that can be completed in a given training period, without losing much value.mfb said:The number of possible games exceeds the number of atoms in the observable universe even if you stop games after 50 moves of each side - not an unusual length of actual games.
With Go you exceed that number after less than 20 moves per side.
Apart from the Chess endgame (where computers can calculate all relevant moves) the games are too complex to check every option. The algorithms have to decide which options to explore in more detail, and which options to discard. This is not an easy task - sometimes sacrificing the queen leads to a big advantage several moves later, for example.
They is the paper authors. They describe a need, for the case of chess, during self training self play, to add a rule that games longer than some threshold be declared draws. They don’t state what cutoff they used. Note that even though the 50 move rule and 3 fold repetition already ensure that any chess game terminates infinite length, the theoretical worst case is on the order of 5000 moves. My belief is that their fear was that pursuing such implausible games to their natural conclusion before scoring would reduce the number of self training games completed in reasonable time, and that little would be lost training to this modified chess variant.mfb said:Who is “they”? No one calculates hundreds of steps in advance. You cannot. Even 10 moves gives way too many options to explore all of them.
Stockfish evaluated did 70 million positions per second. In a minute that gives you 4 billion positions. At ~20 possible moves for each player that would allow a full search just 7 half-moves deep. AlphaZero with its 80,000 positions per second could only look about 5 half-moves ahead. Even amateurs will explore the most promising moves in more detail - and so do the chess engines.
I think you continue to misunderstand me. There is a self training phase, the result of which then plays games with other opponents. The cutoff only applies to self training and is wholly lrrelevant to look ahead for move making during self training. It applies to scoring a self played game. Scoring occurs after a game ends. They want to keep game length in the hundreds, not thousands. So they add an extra rule that terminates games that go on too long and calls them draws. This makes it a different game than chess, which has no such rule. But they correctly guess that good play of this game is intistinguishable in practice from regular chess.mfb said:Even with 2 move options per side, 50 moves for each side would give you 2^100 = 10^30 possible games, way too many to explore all of them. You need the rule to prevent exploring the value of endless loops. The main point stays the same: The algorithms don't do brute force. They explore only a tiny part of the possible moves, and the strategy which part to examine is the interesting part.
Please read the paper. They discuss exactly this issue, and state that while such techniques were used in the prior Go specific variants, for AlphaZero they explicitly removed all such specializations, and ensured that NO game oriented optimizations or heuristics were present in the initial state of the Neural Network.GTOM said:It is true that even a supercompu can't brute force a game of chess, let alone go. But actually only a small subset of gamespace is needed to find the winner strategy.
One optimalisation method is backpropagation, start from the end, and see how different steps can alter the outcome.
In GO once you realize that you can rotate, mirror the table and get the same outcome, you can drastically reduce the complexity of search tree. I guess with proper similarity functions (that maybe two states arent exactly the same, but similar enough to follow the same strategy) search time can be drastically reduced too.
Since new alphago was developed AFTER the experiments with the first one, not just out of the blue with new super learning algorithm, i find it hard to imagine, that they didnt rely on that kind of knowledge. Programmers are kinda lazy, they don't write something from scratch, when they can copy-paste, use function libraries, existing network structures etc.
Getting back to this interesting point, it occurs to me that since AlphaZero is learning from scratch, a more appropriate comparison would be with the total number of games of chess played by all serious chess players through history. Every chess player learns from the play of the current generation of strong players, who learned from the play of those before, etc. Thus, the comparable human neural net is not one person but the collection of all serious players from the advent of chess, and even reasonably close predecessor games.256bits said:Well, there is the link "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm", PDF, under heading A new paradigm ( third way down ).
If I read Table S3 correctly, it took 44 million training games to learn chess, and 21 million to learn Go and Shogi, to become the best at winning.
Humans hardly play that many games with their slow processing grey matter.
Ok, here is a data point:PAllen said:Getting back to this interesting point, it occurs to me that since AlphaZero is learning from scratch, a more appropriate comparison would be with the total number of games of chess played by all serious chess players through history. Every chess player learns from the play of the current generation of strong players, who learned from the play of those before, etc. Thus, the comparable human neural net is not one person but the collection of all serious players from the advent of chess, and even reasonably close predecessor games.
My guess is that this would still not total 44 million, but I have no data on this. It would certainly less disparate than looking at games of just one human player.
PAllen said:Getting back to this interesting point, it occurs to me that since AlphaZero is learning from scratch, a more appropriate comparison would be with the total number of games of chess played by all serious chess players through history. Every chess player learns from the play of the current generation of strong players, who learned from the play of those before, etc. Thus, the comparable human neural net is not one person but the collection of all serious players from the advent of chess, and even reasonably close predecessor games.
My guess is that this would still not total 44 million, but I have no data on this. It would certainly less disparate than looking at games of just one human player.
Yes, it is very worth reading the whole paper.Andy Resnick said:I finally got a chance to read the arXiv report, which is fascinating- my question is, is there some way to 'peek under the hood' to see the process by which AlphaZero optimized the move probabilities based on the Monte-Carlo tree search, and if during the process of selecting and optimizing the parameters and value estimates arrived at an overall strategic process that is measurably distinct from 'human' approaches to play- could AlphaZero pass a 'Chess version' Turing test?
sysprog said:GM Amanov provides insightful commentary.
Amanov mentions in the video that the majority of the games were not yet released -- that renders at best tenuous any suggested plenary interpretation of the results -- preliminary study of emergents from the program set implementation presumably should avail of unfettered access to every game.GTOM said:Looks like what i said about a simpler brute force and avoid error is rather that Stockfish (which is enough to achieve draw in the majority of cases), than that new program, well it is sure interesting, what are the differences, drop useless combinations faster, more likely start in right direction?
phyzguy said:There is a big push for "Explainable AI", driven by the uses in medicine, law and other places. Here is a New York Times article on the issues. So people are working on being able to ask how these deep neural networks make their decisions. If they make progress, it would be interesting to apply to AlphaZero, to see if we can gain insights on how it chooses the correct move.
phyzguy said:There is a big push for "Explainable AI", driven by the uses in medicine, law and other places. Here is a New York Times article on the issues. So people are working on being able to ask how these deep neural networks make their decisions. If they make progress, it would be interesting to apply to AlphaZero, to see if we can gain insights on how it chooses the correct move.