29

Very recently, the news came out that Alphabet's DeepMind research team have extended their machine learning engine to play both Shogi and chess. Apparently, after only a few hours of self-learning, meaning by only playing against itself given the rules of the games, its performance in chess has already surpassed that of top current engines such as Stockfish 8. I personally don't know yet how exactly the matches were set up, as in under what condition Stockfish was set to perform, since if the calculation times are limited engines are able to perform very poorly. In any case, this is a very impressive achievement, because even if it turns out that one could have set up Stockfish more optimally, with few additional hours of training, AlphaZero would surpass again the level of play, meaning AlphaZero's fundamentally stronger than any current standard chess engine based on heuristic evaluation functions.

Now in the light of this news, it would be great if someone could elaborate on the main differences in the workings of a machine learned chess engine compared to the standard engines we are all accustomed to using. More concretely:

  1. Isn't the evaluation function that AlphaZero uses, trained by machine learning methods, at the end just another heuristic evaluation function? If yes, would it be fair to say that the fundamental difference between evaluation functions of the two engines, is the fact that Stockfish has an optimized evaluation function hand-tuned by humans, meaning the definition of the function to optimize is fixed, whereas for AlphaZero, the target evaluation function is constantly being redefined through additional training (for instance through self-play)? Making the latter a far more dynamic of an approach.
  2. Ultimately, vaguely speaking, an engine like Stockfish, applies its evaluation function to the tree of possible moves, deciding which branches to keep and which ones to drop, then through a deeper concrete analysis of each branch, again through its evaluation function, it figures out which branch yielded the highest value, and that becomes the principal variation (of course there are many advances techniques around this process to efficiently prune this large tree). Meaning, for each position, this extremely concrete routine has to be repeated for Stockfish to make a decision. In contrast, I imagine AlphaZero does something very different, namely, it does not rely on a concrete analysis of the tree of possible moves at a given position, instead its evaluation function essentially assigns a value to that position (which intuitively is similar to putting the current position in analogy to all the other positions that it has been trained for), without ever having to perform concrete analysis in the way that Stockfish, or even a human player does. Is this at all a sound picture of the workings of AlphaZero or similarly trained machine learning engines?

  3. We know that the space of chess positions is large enough that any attempt at sampling all the positions in it would be even in principle completely in vain (EXPTIME complexity), that would suggest that no amount of training through self-play would be enough to have explored all positions, so then how can the end result be good despite having potentially explored a small fraction of positions of the space via self-play? What is the key idea here at play?

  4. My guess is that, AlphaZero has a very optimal way of comparing any given position, even if new, to a previously visited one in its training set, the closer the comparison, the more valid the evaluation one can draw from the comparison. For instance, when it played the move Bg5 in game 5, it must have explored a similar structure during its training, i.e. it is able to recognize that this position is essentially equivalent to (a possibly completely) different one studied in its training, in analogy to how face recognition is achieved through machine learning, and as a result it concludes Bg5 should be the best move, as was in that (or those) other similar positions. Is this at all a correct guess? I have no idea how this comparison is done, as surely it's not possible to store all trained position and parse through them each time.

This is merely an attempt to get so insights into the workings of AlphaZero and how it comes to a decision given a position.

20
  • How does AlphaZero select a move in the search?

This is very obvious from the paper.

Each simulation proceeds by selecting in each state s a move a with low visit count, high move probability and high vale selecting ...

What does that mean? AlphaZero has trained probabilities for each move (end of page 2 in the paper) from a deep neural network. During the search, it picks a move proportional to that probability, and also nodes that have low count (to ensure the sampling space is explored). This is not a new concept, Monte Carlo Tree Search has been in the literature before Google existed.

------ (Very) Rough example ------

We have a position, and we have two legal moves.

  • Move 1 is good and reasonable
  • Move 2 puts your own king in danger for no compensation

According the paper, a trained deep model might estimate the probabilities as (0.90, 0.10). Let's say AlphaZero uses 4 iterations in Monte Carlo. The iterations could look like:

Iteration 1: Pick move 1 because it has the highest probability. Do a simulation from move 1. Iteration 2: Pick move 1 because it has the highest probability. Do a simulation from move 1. Iteration 3: Pick move 1 because it has the highest probability. Do a simulation from move 1.

Now, we're at iteration 4. Although move 1 has the higher estimated probability but move 2 has not been searched ("low visit count" in the paper), now AlphaZero would pick move 2, and do simulation.

Both moves would be considered, but AlphaZero would put more computing resources on move 1 (good thing).

AlphaZero would then pick the move with the best expected outcome.

------------------ Your questions: ------------------

Isn't the evaluation function that AlphaZero uses, trained by machine learning methods, at the end just another heuristic evaluation function?

The trained evaluation function is a deep neural network, it is not a set of heuristic rules, like what you see in Stockfish. Nobody understands fully about (not even the Google team) the trained network, it just works. This is how NN works generally.

whereas for AlphaZero, the target evaluation function is constantly being redefined through the target evaluation function is constantly being redefined through additional training.

The evaluation function in AlphaZero is a set of trained neurons (bias + weights). The Google team used very powerful machines to train the parameters. Generally, the more resources you can invest in training a deep learning model, the better parameters you get.

(2).

Stockfish uses alpha-beta, while AlphaZero uses Monte-Carlo. They are two very different algorithms. The alpha-beta algorithm assumes a lower/upper bound, while Monte-Carlo creates simulations from the root to leaf.

to have explored all positions, so then how can the end result be good despite having potentially explored a small fraction of positions of the space via self-play? What is the key idea here at play?

Google didn't claim they had solved chess, not even their powerful machines could possibly enumerate all chess positions. But they didn't have to ... that's the point for machine learning, the model "learns" from the training set. In this case, the training set come from self-playing. The key idea is to play as many as good quality games against itself as possible and quickly.

For instance, when it played the move Bg5 in game 5, it must have explored a similar structure during its training,

I don't think AlphaZero encountered the exact same position in the training games. I think a quick read of Monte-Carlo is a good idea:

https://chessprogramming.wikispaces.com/Monte-Carlo+Tree+Search

AlphaZero was able to play the move by reaching sufficient depth. The algorithm estimates the expected probability of winning for each move, apparently, the move Bg5 gave the highest expected probability.

You can think like, AlphaGo was able to search so well that it saw the probability of winning is highest after Bg5, while Stockfish didn't consider the move seriously (and thus lost).

  • 2
    "Monte Carlo Tree Search has been in the literature before Google existed" I can only trace MCTS back to about 2006. – CodesInChaos Dec 7 '17 at 16:57
  • 2
    @CodesInChaos MCTS is not a new technique. Google certainly didn't invent Monte Carlo. – SmallChess Dec 7 '17 at 17:00
  • 4
    Brügmann 1993 is clearly only MC. MC Go Dev. (2003) combines MC and trees, but in a primitive way. Chang (2005) is pretty close, but in a different context and I think it still lacks proper choice of the node to expand and propagation of estimations. Efficient Selectivity and Backup Operators in MCTS Remi Coulom (2006) is a proper MCTS, as far as I can tell, the first one. – CodesInChaos Dec 7 '17 at 18:25
  • 1
    @SmallChess Parts of your answer seem to be contradictory: "now AlphaZero would pick move 2, and do simulation. Both moves would be considered, but AlphaZero would put more computing resources on move 1 (good thing)." contradicts the statement Each simulation proceeds by selecting in each state s a move a with low visit count... as, in your example, that would be 2 rather than 1. To be honest the paper does not contain any piece of useful information for the understanding, as they show no way to reproduce the experiment or give any insight on the actual way they train the networks. – gented Dec 16 '17 at 19:46
  • 1
    What they do is essentially stating "we used algorithm X and it works" - which provides little to no understanding on the methods itself, so I wouldn't focus too much on the paper itself to try to figure out what it really does. – gented Dec 16 '17 at 19:48
0

I guess my question would be how the neural net "learns" what to do in a position it hasn't encountered. Saying the actual AZ executes an MCTS using the bias + weights from the trained neural net just pushes it back a step to how the neural net calculates these values. If it was through random self-play, with no human knowledge, then how does it decide how to weight a position it has never seen?

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.