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:
- 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.
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?
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?
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.
