Home

Komodo MCTS (Monte Carlo Tree Search) is the new star of TCEC

KomodoMCTSKomodo MCTS (Monte Carlo Tree Search) is the star newcomer to the Top Chess Engine Championship league. It has won Division 4, and qualified from Division 2 and 3 to enter the elite group of the top 16 engines in the world. Currently, it is placed second in Division 1 where after 13 rounds it has collected 8 points (+3 =10 -0) and is in a good position to enter the Premier division.

 

Komodo MCTS – Fritz 1-0 – Sicilian, Najdorf, Byrne (English) attack
Komodo MCTS – Chiron 1-0 – Giuoco Pianissimo, Italian four knights variation
Fritz – Komodo MCTS 1-0 – Sicilian, Najdorf, Byrne (English) attack

The authors of Komodo MCTS share their opinion on the current development of the engine, comparison and contrast to regular Komodo, give their opinion on Alpha Zero and the neural networks, and much more in a detailed interview for Chessdom.com

More about TCEC: TCEC live games / TCEC Season 14 information and rules

Congratulations for winning Div 4, and qualifying from Div 3 and Div 2. This is quite a feat for a newcomer to TCEC. Did you expect the relatively straight forward rise to this elite group level?

Mark Lefler: Thanks. With anything new there are certain issues we had not considered. Some from just learning about how to best use Monte Carlo Tree Search, some from bugs and some from not being able to test on such a large machine. I thought finding a good way to use all the cores was going to be the hardest part of MCTS search. MCTS prefer searching the best lines based on past history, but with many processors, things can get really crowded having them all work on the same tree node, so you have to be a bit clever about encouraging them to search other parts of the tree. But too much searching of the bad line hurts elo. So we have experimented a lot with improving this.

Larry Kaufman: I was pretty confident that we would reach Div 2 once we solved the problem of how to utilize more than a dozen or so threads, but I did not expect it to be by such a large margin over all the other non-GPU engines. There was always the concern about crashes or bad behavior on super hardware.

Judging by the play so far, where do you expect Komodo MCTS to end in the final standings of the season?

Mark Lefler: Larry might be best to answer this, but the playing strength of Komodo MCTS is somewhere between Stockfish 6 and Stockfish 7. So it it pretty strong.

Larry Kaufman: After the “big three” (Stockfish, Komodo, and Houdini) and Lc0, I would expect only one to finish above KomodoMCTS as things stand now. Komodo MCTS is progressing fast, but of course one of the other top few engines could also pull ahead, so sixth place would seem like a fair guess. I don’t rule out the chance that we will make a big breakthrough and contend for a top place.

Komodo MCTS is a newcomer and many do not know the details behind the engine and its innovative approach. Tell us more about Komodo MCTS

Mark Lefler: MCTS searches a tree in a kind of best first arrangement, preferring to expand lines where the win percentage has been good. So you need some estimate of win percentage. We use short alpha-beta search from each MCTS node to estimate these winning changes. But even these alpha-beta short searches are heavily modified from regular Komodo. So these scores get backed up to the root of the tree. A node selection process similar to UCT1 is used, but we heavily modified it, not using a log and not using the scheme in Leela or Alpha Zero, but trying to accomplish the same thing. Explore a lot at first, then narrow the search with more backed up nodes.

There is a new version of Komodo MCTS playing in Div 1. What are the improvements?

Mark Lefler: So many areas of improvement. Better node selection. Better time management. Some speedups. Better handling of positions with lots of terminal nodes like checkmate or 50 move rep. Some Syzygy-related improvements as well.

What is the motivation for splitting the efforts of you and Larry between developing Komodo and developing Komodo MCTS?

Mark Lefler: Well, since we use modified alpha-beta short searches to guide MCTS, work on regular search ends up helping both search modes. We have spent much more time on MCTS lately because it is great seeing a simple change giving 10 elo, and because it is fun to learn new things. We learn a lot every day.

Larry Kaufman: I would add that there does not seem to be a realistic chance for regular Komodo to surpass Stockfish barring some major finding, but it is not difficult to imagine Komodo MCTS doing so since it is progressing more than ten times as fast as normal Komodo.

Are there parts that the two engines share?

M: They share a move generator, and they share some alpha-beta like search functions for the short search winning estimates. But both the search and the eval are modified from the traditional alpha-beta search. I am having to put in too many “if (useMCTS) … else ….;” lines, so we are likely to split the code base soon.

In the chat of TCEC you mentioned, “In this version of Komodo MCTS, once it sees it has a score of 7 pawns ahead (or 7 pawns behind), it uses Syzygy and regular search to finish off the game.” Does that comply with the rules that an engine has to be “unique”?

Mark Lefler: I will leave rule interpretation up to the people running TCEC, but the main reason we do this is that once a game is almost certainly won, alpha beta is just better at coming up with a faster end to the game. In alpha-beta search, win scores are scaled based on the number of moves until mate. In MCTS, a win is a win, and this gets converted to a 100% value, so shortest wins are not always found, so it can take a long time to get there. We thought it was not so interesting postponing the result. We are considering making this “mop up” feature an option people can turn on or off. There is not much of a reason to do the switch when we are totally losing, we may take that out. MCTS may well be better in such cases.

Larry Kaufman: The switch to alpha-beta only occurs when the result is something like 99.9% certain anyway, and for TCEC the effect is much less even than that because such positions are soon adjudicated. If TCEC decides that this very minor overlap with normal Komodo is a problem, we can make it an option you can turn off, or perhaps not do it at all when losing and only do it when winning after several moves, enough to comply with the TCEC adjudication rule.

Mark Lefler: More accurately, when Komodo MCTS sees a score greater than 7 pawns or less than -7 pawns it switches to alpha beta search. It is not exactly the same search as regular alpha-beta would do since time management is very different. It uses the allocated time it would for MCTS mode times a scaling factor.

Larry Kaufman: Aside from not wanting to prolong games unnecessarily, we had some crashes in very long games in the chess.com event, which does not adjudicate won games or even Syzygy position won games. We restored this 7 pawn rule as a temporary solution to avoid these long games which are both boring and prone to problematic behavior. We think the problems were Syzygy-related and have probably been fixed, but we haven’t been inclined to revert the 7 pawn rule. It’s rather silly to wait for say 40 moves to go by in a rook vs king ending and see Komodo MCTS only go for mate when it sees 50 move rule danger! There is much less need for it in TCEC due to adjudication. I’m sure we could make Komodo MCTS win easily won positions more quickly without the 7 pawn rule, but so far we haven’t been motivated to spend our time on this rather than on improving the MCTS engine when the result isn’t yet decided.

Recently, DeepMind’s Alpha Zero published a scientific paper where it detailed the domination over Stockfish. Have you read the paper and can you share your thoughts?

Mark Lefler: Yes I have. Pretty amazing accomplishment. The more complete paper shows more data, but that data seems to be from January 2018, so is pretty old given how much Stockfish has gained since then. They also did not appear to test with Syzygy, they had an unclear opening book in some tests. But they did seem to switch to a more realistic time control.

Larry Kaufman: Based on everything I’ve read, It seems that AlphaZero would probably lose a match to Stockfish 10 under TCEC conditions, as AZ beat an older SF by a rather narrow margin under similar conditions. It’s still rather remarkable that NN could achieve this much this quickly, but as of now I think that beating SF10 will suffice to claim to be the world’s best chess engine.

Now that you have MCTS , can you reveal if you are going towards a Komodo NN model or a hybrid?

Mark Lefler: We are working on a Neural Network for Komodo, which could be used for several things. A replacement of the existing evaluation in alpha-beta Komodo. A replacement for the short searches in Komodo MCTS. Training of this network is going on nearly 24 hours a day, but we have a way to go.

Larry Kaufman: It is pretty clear to me that the only advantage of NN for chess is that it can utilize a good GPU and so whatever it can accomplish is “free” if you don’t care about the cost and power consumption of the GPU. We are making such good progress on Komodo MCTS without NN that the parallel effort we (chess.com and Komodo) are making with NN may never pay off. But most likely some hybrid that can use the GPU will ultimately prove to be best. I think that it is quite unlikely that a pure NN program like Lc0 or AZ will ultimately come out on top. Five centuries of chess knowledge ought to be worth something!