MCTS vs Alpha-beta

[smatovic]

With Lc0 a lot of the attention went on the NN and how it was better than a hand-crafted Evaluation Function.

But I'm trying to understand the search side of things.
I have a basic, layman's, working knowledge of alpha-beta search in chess and virtually no real understanding of MCTS, which I think is used in Lc0 and Komodo MCTS?

Can I ask:
1) Where are details of how the search works, specific to chess?
2) What are the pros and cons of MCTS vs AB?
3) Does the Lc0 MCTS play the game out fully or just to a fixed point? If it is fixed, how deep?

I've heard MCTS is less able to handle tactics but I'm not sure why.

https://www.chessprogramming.org/UCT#Ra ... an_et_al.

UCT has been shown to outperform traditional minimax based approaches in several challenging domains such as Go and KriegSpiel, although minimax search still prevails in other domains such as Chess. This work provides insights into the properties of adversarial search spaces that play a key role in the success or failure of UCT and similar sampling-based approaches. We show that certain "early loss" or "shallow trap" configurations, while unlikely in Go, occur surprisingly often in games like Chess (even in grandmaster games). We provide evidence that UCT, unlike minimax search, is unable to identify such traps in Chess and spends a great deal of time exploring much deeper game play than needed.

MCTS-UCT was used successfully in Go, MCTS-PUCT was used successfully in A0/LC0 with NN Policy/Value head.

--
Srdja

I read the full article you posted which made my head spin, but it was helpful.

So to sum up, Lc0 isn't doing full-game "rollouts", but rather it's building a kindof speculative, highly asymmetric game tree ?

I guess you can say the same about modern AB searches with certain pruning/
reduction/razoring techniques, the question is why plain MCTS-UCT performs worse
for Chess than AB - it is about the nature of the game, Go compared to Chess, as
MCTS-UCT compared to AB, now with MCTS-PUCT, with P as Predicator, they fixed
one part of MCTS a bit, but imo still not enough to get en par with AB in Chess.

I am not sure how the playouts of Leela in Chess/Go work, but in AB for Chess we
have the QS, Quiescence-Search, to handle the horizon-effect, maybe this part is
still missing in MCTS-PUCT to handle end-game and tactic-sequences better?

--
Srdja

[Dann Corbit]

Donald Knuth and Ronald Moore wrote a paper in 1975 titled "An analysis of Alpha Beta Pruning" that showed AB pruning is in some ways optimal.

I think MCTS may approach that, but I do not think it can ever surpass it.

I think MCTS is best for games with such a crazy branching factor that regular pruning methods leave the tree still so big that the memory size is beyond what is feasible. In such cases MCTS is forced. I think also that AB is very difficult to code on GPUs and so GPUs are also a target audience for MCTS. I think it is also possible for MCTS to "get lucky" which is to say that due to having greater randomness than AB search, it might possibly hit the right path early.

On the other hand, I do not know enough about MCTS to know that it is not somehow super-optimal.

As an example of this, Gaussian integration knots are provably optimal. But double exponential integration and Sinc integration are optimal in a better way. The Gaussian integration knots are simply optimal knots. But the technique of double exponential integration is provably optimal in both speed and accuracy.

[chrisw]

With Lc0 a lot of the attention went on the NN and how it was better than a hand-crafted Evaluation Function.

But I'm trying to understand the search side of things.
I have a basic, layman's, working knowledge of alpha-beta search in chess and virtually no real understanding of MCTS, which I think is used in Lc0 and Komodo MCTS?

Can I ask:
1) Where are details of how the search works, specific to chess?
2) What are the pros and cons of MCTS vs AB?
3) Does the Lc0 MCTS play the game out fully or just to a fixed point? If it is fixed, how deep?

I've heard MCTS is less able to handle tactics but I'm not sure why.

What AB has that MCTS doesn’t is B. AB is minimax plus beta B algorithm. Someone realised once upon a time that minimax (the original search algorithm, A) was returning an accurate score for all the ply one moves, but that this wasn’t actually necessary, you didn’t need to know the scores of all the other moves, only that they were worse than the best (to be selected) move. AB algorithm doesn’t tell you how all the other moves score, just the best move. Beta avoids computing all that redundant information (by one line of code) and saves a lot of search time as a result.
MCTS lacks a specific beta-type algorithm, it scores all moves, so MCTS fails to eliminate that redundancy from its search. In practice MCTS manages to spend less time on the secondary moves since its principal move is the one it searches the most, but it still lacks the redundancy-eliminating Beta feature of AB.

On the other side, I guess that MCTS is sort of eliminating some redundancy that AB doesn’t. AB gives you an eval for the principal move, but actually you don’t need the eval, you only need to know the move is best.

[smatovic]

With Lc0 a lot of the attention went on the NN and how it was better than a hand-crafted Evaluation Function.

But I'm trying to understand the search side of things.
I have a basic, layman's, working knowledge of alpha-beta search in chess and virtually no real understanding of MCTS, which I think is used in Lc0 and Komodo MCTS?

Can I ask:
1) Where are details of how the search works, specific to chess?
2) What are the pros and cons of MCTS vs AB?
3) Does the Lc0 MCTS play the game out fully or just to a fixed point? If it is fixed, how deep?

I've heard MCTS is less able to handle tactics but I'm not sure why.

Sorry for digging this up, but I found an description of Komodo (and Dragon?) MCTS on CPW:

https://www.chessprogramming.org/Komodo#MCTS

In Komodo's MCTS mode the search tree is expanded in best-first manner based on winning probabilities determined neither by random playouts nor by a neural network, but a tiny alpha-beta search plus quiescence and static evaluation, also similar to UCT, dealing with the crucial trade-off between exploration and exploitation. While playing strength is lower with MCTS, positional play and judgement may well be better in many positions [27], not to mention a more risky and entertaining playing style.

It works pretty much like BestFirstMiniMax search:

https://www.chessprogramming.org/Best-F ... max_Search

So there are basically three types of top performing engines, Stockfish with selective AlphaBeta, Lc0 with MCTS-PUCT (DAG) and Komodo/Dragon MCTS with some kind of BestFirstMiniMax.

--
Srdja

[JacquesRW]

I wouldn't put Komodo's pseudo-MCTS in a separate category, its just an artificial crippling of its a/b search. I can do some rubbish with <insert random search method> in Stockfish, use the a/b search as helpers for it, and only lose 50-100 elo, much like Komodo MCTS does.

EDIT: Note that Komodo MCTS *is* MCTS much like Leela, but instead of a policy head it uses a/b (and here you can see you are ultimately deferring to your pre-existing, much stronger a/b search).

[smatovic]

I can agree with your statement, but wish to to conjecture, that if you tune BestFirstMiniMax in a similar level as AlphaBeta search it will be at par Elo wise.

--
Srdja