4 ms·

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 rand

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?

ex3ndr 9y ago
I suppose, yes. This is called "reinforcement learning".
- seanwilson 9y ago
  Can you elaborate? What are the input and outputs of the neural net?
svantana 9y ago
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.
- dvdkhlng 9y ago
  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 https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
soVeryTired 9y ago
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 :)
eutectic 9y ago
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.
- soVeryTired 9y ago
  I think the separation of value and policy networks was a feature of the older AlphaGo systems, but not AlphaGo Zero
- seanwilson 9y ago
  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?
  - eutectic 9y ago

ex3ndr 9y ago

I suppose, yes. This is called "reinforcement learning".

seanwilson 9y ago
Can you elaborate? What are the input and outputs of the neural net?

svantana 9y ago

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.

dvdkhlng 9y ago
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 https://en.wikipedia.org/wiki/Monte_Carlo_tree_search

soVeryTired 9y ago

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 :)

eutectic 9y ago

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.

soVeryTired 9y ago
I think the separation of value and policy networks was a feature of the older AlphaGo systems, but not AlphaGo Zero
seanwilson 9y ago
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?
- eutectic 9y ago