The reason behind using MCTS over Alpha Beta Pruning in Alphazero

Question

I am not really satisfied with the available analysis of why AlphaZero uses MCTS instead of Alpha Beta search. Some analysis claim that its because MCTS is a lot more humanlike. I disagree because I don't think AlphaZero was really concerned about becoming humanlike. The fact that it ended up playing like humans was just a coincidence but it was never the goal behind its design choice.

In the AlphaZero paper,

MCTS and Alpha-Beta Search

For at least four decades the strongest computer chess programs have used alpha-beta search (18, 23). AlphaZero uses a markedly different approach that averages over the position evaluations within a subtree, rather than computing the minimax evaluation of that subtree. However, chess programs using traditional MCTS were much weaker than alpha-beta search programs, (4, 24); while alpha-beta programs based on neural networks have previously been unable to compete with faster, handcrafted evaluation functions. AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation used in typical chess programs. This provides a much more powerful representation, but may also introduce spurious approximation errors. MCTS averages over these approximation errors, which therefore tend to cancel out when evaluating a large subtree. In contrast, alpha-beta search computes an explicit minimax, which propagates the biggest approximation errors to the root of the subtree. Using MCTS may allow AlphaZero to effectively combine its neural network representations with a powerful, domain-independent search.

What do they mean by

approach that averages over the position evaluations within a subtree, rather than computing the minimax evaluation of that subtree.

What does it mean to average over position evaluations within a subtree?

Also in the next part,

AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation used in typical chess programs.

How is alphazero's evaluation non linear and how are the typical programs linear?

Could someone dumb these down?

My own guess behind MCTS over AB is because MCTS returns visit counts for each of the moves, and this data can be used to train the Policy Network in Alphazero. A minimax(AB) would return just that one best move, which could be used to train value network, but it cannot be used to train Policy network. So MCTS exists to train policy network in Alphazero. Is this a good or a bad guess?

Also, please do not mark these as multiple questions, I believe all these are a part of the same question.

Answer 1

Let's begin with what position evaluation means, as it is the core of everything.

AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation used in typical chess programs.

In beginner Chess we are probably taught that pawn is worth 1 point, 3 for knight and 9 for Queen. This is a quick way to evaluate how good/bad our situation is. Similarly in Bridge, we count Ace as 4 points, King as 3 and etc.. This is the position evaluation function, indicates how advantage/disadvantage a side is given a certain board situation.

Obviously, the above-mentioned evaluation methods are very elementary and do not account for all the complexity. Say I can be a Queen and a Rook less but can surely checkmate (win) in 20 steps. Or I have a hand with only 10 points (A,K,Q,J) but with all 13 cards of Spades and thus easily make a 7S major slam.

To accommodate these situations, human experts invent a lot of 'patches' to the evaluation: e.g. 2 pawns on same line gives a -1, a long suit adds +2 points etc.. All in all, these are handcrafted features create manually via careful engineering. 'Typical chess programs' e.g. Stockfish use them under the hood.

Regardless, these position evaluations are linear: they are composed of a bunch of if-else statements, e.g. 'if I have a Pawn, adds 1 point', 'if I have no card in a suit, adds 4 points'. This is what the paper means by linear function approximation.

In contrary, AlphaZero's position evaluation function does not rely on any hard-coded rules, but directly evaluate the board position. For example in Go, the function takes the position of all pieces on the board as input, feeds through a deep neural network (with a lot of layers e.g. convolution, residue blocks, max-pooling etc.) and returns a score of position advantage (e.g. 60% chance Black is leading).

Notice that:

1. The DNN is not static - it keeps updating during training and (hopefully) improves.
2. The evaluation function is non-linear; this is where the non-linear function approximation based on a deep neural network comes from.

approach that averages over the position evaluations within a subtree, rather than computing the minimax evaluation of that subtree.

The 'averages over' part is essentially how MCTS works - compute the positional evaluations of all subtrees of a branch, and (weighted) average the results as the score of the branch. While in Alpha-Beta, there is no 'average' - only the best is kept else pruned.

MCTS returns visit counts for each of the moves

AFAIK, visit counts is used to approximate the confidence of position evaluation (similar to the role of sample size and confidence level in statistics). The actual scores combines both visit counts and evaluation scores of subtree.

Finally,

why AlphaZero uses MCTS instead of Alpha Beta search?

[Updated]

There are at least 2 reasons as per this reference papar:

(section 3.2) In some games of interest, e.g., in the game of Go, it has proven hard to encode or learn an evaluation function of sufficient quality to achieve good performance in a minimax search.

It claims that minimax is more sensitive to evaluation function vs. MCTS, and for complex games it makes a significant impact. The fundamental reason probably lays between the statistic used: max/min vs. mean.

(section 4.3) Classical game-tree-search algorithms, such as minimax search with α − β pruning, are notoriously difficult to parallelize effectively. Fortunately, MCTS lends itself much more easily to parallelization.

A practical consideration: MCTS is easier to parallelize.

Finally, I recommend going over the AlphaGo paper first as it spells out more details (especially the value and policy network part), then AlphaGo Zero (which merges the value and policy network) before jumping into AlphaZero. Things should get a lot clearer this way as the authors skip some details in later papers.