Monte Carlo instead of Alpha-Beta?

by Stephan Oliver Platz
1/30/2019 – Until now, chess programs mostly worked according to the so-called alpha-beta pruning search algorithm. The spectacular Deep Mind project Alpha Zero is based on the Monte Carlo Tree Search (MCTS). The Komodo developers, too, are now increasingly relying on this method — with success. STEPHEN OLIVER PLATZ explains the difference and shows the progress. | Photo: (Komodo Dragon) Ryan Vaarsi, CC BY 2.0

Komodo 12 Komodo 12

In computer chess there is no getting past Komodo, a two-time ICGA Computer World Chess Champion. Find out how Komodo can take your game to the next level!

More...

Lessons from Alpha Zero

Just over a year ago, the Alpha Zero chess program made headlines by sensationally defeating Stockfish 8. In the published games the playing style was really impressive, reminiscent of Anderssen and Morphy with positional sacrifices of pawns and pieces. Many chess aficionados would like to buy Alpha Zero if it were available and could be run on conventional computers. While that's not an option, fortunately, Komodo MCTS is a chess program available for an affordable price that uses similar techniques as Alpha Zero and can be installed on consumer PCs. This version has made great progress since its first release, as can be seen from two remarkable games played in December 2018.

A tactical masterpiece

In the first round of Division 2 of the current TCEC 14 tournament, which is regarded by many as the actual, albeit unofficial World Chess Computer Championship, Komodo MCTS defeated Nirvana 2.4 in a spectacular way. Playing with the white pieces against a Sicilian Defence, Komodo sacrificed a pawn, then the exchange and finally a bishop, but Black was already lost after grabbing the pawn:

 

In this game, the open-minded approach of the program is particularly impressive as a result of the Monte Carlo tree search used by Komodo MCTS.


The Sicilian Tajmanov-Scheveningen

The Sicilian has been known for decades as the most reliable way for Black to obtain an unbalanced but good position. Among the most popular Sicilians at the top level the two that certainly stand out are the Najdorf and the Paulsen.

More...


Monte Carlo tree search (MCTS) — what is it?

In contrast to the conventional alpha-beta pruning search algorithm, no chess knowledge is required in this procedure, apart from the rules of the game and the possible outcomes of a chess game: win, defeat or draw. Roughly speaking, this is what happens: In a given position, a bunch of possible moves are tried out by the program playing against itself until a result is obtained: 1, 0 or 1/2. What the move that achieves the best result looks like does not matter. Whether the move abandons a pawn, a piece or the queen, allows a double or triple pawn, or violates any iron principle formulated by great chess teachers, is irrelevant as long as it is successful. You could call this an open-minded approach.

By playing out a large number of games to the end, conclusions are drawn about the best moves in a particular position. The program deals with the most successful moves in more detail than with the unsuccessful ones. The result is a "search tree", which at the end allows the choice of a move which is purely based on the best performance.

This method is particularly effective combined with "neural networks". It is well known that Alpha Zero played countless games against itself for nine hours and learned from the results. However, enormous computing capacities were made available for this, because otherwise, nine hours would hardly have been enough.  Afterwards Alpha Zero was able to beat Stockfish 8, one of the best chess programs in the world. In a nutshell, this means: AI (artificial intelligence) learns by trial and error purely from its experience.

Effective = aesthetically attractive?

In this context, I would like to mention the discussion between world champion Dr Emanuel Lasker and his archrival Dr Siegbert Tarrasch about the "aesthetic" value of a move.

Just before his World Chess Championship match against Tarrasch in 1908 (pictured via Wikimedia Commons), Lasker made these remarks:

Lasker and Tarrasch

"Dr Tarrasch is a thinker who loves deep and complex considerations. He is willing to acknowledge the effectiveness and usefulness of a move if he considers it both beautiful and theoretically correct. But I accept this kind of beauty only if and when it is appropriate. He admires an idea for its depth, I admire it for its effectiveness. My opponent believes in beauty, I believe in strength. I think that a move is also beautiful in that it is powerful." (a)

From this, it becomes clear that world champion Dr Emanuel Lasker's considerations were guided by the attempt to achieve the best results. This is exactly the approach Komodo MCTS also pursues.

Will alpha-beta pruning algorithms soon be exhausted?

In an interview published in December 2018, Komodo developer IGM Larry Kaufman stated that Komodo MCTS is making ten times faster progress than the "normal" Komodo version, which is known to rely on the proven alpha-beta pruning. (b) In a very simplified way, the following can be said about this:

AlphaThe alpha-beta pruning is about excluding as many moves and variations as possible because their results are obviously unfavourable. The alpha value indicates how much player "A" will reach at least if a certain move is played. The beta value, on the other hand, describes the maximum amount that player "B" will achieve by his best countermove. So if I check a move that wins a knight and find out that the opponent gets at most one pawn by playing the best continuation, I could assign a value of +2.00 to this move, if all other conditions are the same. Now I look at another move in the same starting position and notice that although I can capture an adverse rook, my opponent will get at least my queen and three pawns by proper counterplay so that the final result is -7.00.

BetaIn this way, all possible moves are assigned certain values. Those moves with the best values come right to the top and are immediately examined closer and deeper, while those with the worst values come last and usually don't give better results even at greater search depths. If nevertheless, this case should occur, then immediately a re-evaluation takes place, and a move evaluated so far with -2.55, for example, suddenly moves with a plus value to the first, second or third place.

In contrast to the Monte Carlo method, however, the positions are not played out (unless a mate is found), but are followed up to a search depth that increases over time and the resulting positions are evaluated according precisely to previously defined criteria. Here, not only the values of the pieces and pawns are important, but also positional factors such as king safety, pawn weaknesses, open lines, space advantage, control of the centre, etc.

This ingenious method has been refined more and more in recent years and has proven to be extremely successful. Nevertheless, it is possible that the scope for increasing playing strength may be exhausted at some point. Think of the latest Stockfish version 10, in which the programmers and their countless volunteer testers invested about ten months of development work, to gain just 15 ELO points compared to its predecessor version Stockfish 9 (64-bit, 1CPU, according to CCRL Elo list 40/40, dated January, 12th, 2019). 

Let's compare the three previous versions: Stockfish 7 was released on January, 2nd, 2016 and has an Elo rating of 3246. Stockfish 8 from November, 2nd, 2016, just 10 months later, jumped to 3301, a plus of 55 Elo points. This is equivalent to an increase of 5.5 points per month of development. Stockfish 9 from January, 31st, 2018, came out about 15 months later and reached a rating of 3367, 66 points more than the previous version, which means 4.4 Elo increase per month of development. Then ten months went by before the latest version Stockfish 10 was released on November, 30th, 2018. This new version has an Elo rating of 3382, only 15 points more than Stockfish 9. This shows that the curve suddenly flattens out with only a 1.5 point increase per month.

These observations might indicate that the development potential of the chess programs with the conventional alpha-beta pruning search algorithm has, in fact, already been largely exhausted. But of course one should not judge hastily. So let's wait for the next generation of popular programs. Only then we'll know whether this trend is consolidating or not. Anyway, from the above it becomes clear why the Komodo developers Larry Kaufman and Mark Lefler believe that their MCTS version will make the greatest progress. In the current Top Chess Engines Championship (TCEC 14) Komodo MCTS could already sensationally work its way into the "Premier League", and thus into the class of the best eight chess programs.

Komodo's positional masterpiece

It is remarkable that the new program with the Monte Carlo tree search was already able to win some games against a giant like Stockfish 10. The following game was played on December, 21st, 2018 with a time control of 40 minutes per 40 moves each. Both programs could use four processors. By a surprising pawn sacrifice, Komodo MCTS succeeded in positionally outmanoeuvring its formidable opponent. It's kind of weird that after White's 26th move, all three knights are placed on the edges of the board:

 

Komodo 12

In computer chess there is no getting past Komodo, a two-time ICGA Computer World Chess Champion. Find out how Komodo can take your game to the next level!

More...


Komodo MCTS is available together with the conventional Komodo version in the ChessBase shop. You can advantageously use the Monte Carlo tree search without abandoning the time-proven alpha-beta pruning. By using the two search algorithms alternately, you will get deeper insights into complicated positions which is useful both for the analysis of games and for the computer-aided preparation of opening variations.

References

(a) Quoted according to Harold C. Schonberg, "Die Grossmeister des Schach", Frankfurt 1976, p. 119




Stephan is a passionate collector of chess books and for yours has been successfully playing as an amateur for his German club. The former musician and comedian works as a freelance journalist and author in Berlin and in the Franconian village Hiltpoltstein.
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Discuss

Rules for reader comments

 
 

Not registered yet? Register

marialorca marialorca 4/15/2019 03:20
I am new with Komodo 12 (from yesterday :-) ) YUPPIIIIEEEE. Than I try Komodo MC....after Komodo 12 one of positions evaluate 11,87 for white in 96 minutes. I can understand that Komodo MC playing this position with himself manytimes for evaluate 2,97 to white in 517 minutes. Output in graphis is miserable.... I want to know HOW MANY games, WHAT WAS the results in main line, WHAT IS second best line and WHY .....
AhmetBurak23 AhmetBurak23 3/24/2019 08:39
Komodo MCTS has only 2 wins against Stockfish but Stockfish wins 12 games against Komodo MCTS...
JoshuaVGreen JoshuaVGreen 2/1/2019 01:50
What, no mention of the LeelaChessZero project (https://github.com/LeelaChessZero/lczero) which aims to "build a strong UCT chess AI following the same type of techniques as AlphaZero" ?
celeje celeje 1/31/2019 04:58
@ ICCF Grandmaster:

Thanks for the link. I put here your conclusion:

"With a bit more computing power (eg with the setting "permanent brain") maybe Stockfish 8 would have been able to avert the worst and save himself in a happy draw. This is not excluded. On the other hand, Stockfish 10 would probably have been able to draw the game under the given match conditions (hardware, time mode etc.)."

"But it would be desirable to consider the hardware disadvantage on the part of the traditional engines that do not have AlphaZero's TPUs, more than before."
ICCF Grandmaster ICCF Grandmaster 1/31/2019 12:04
For more insight into one of the most crucial games between AlphaZero and Stockfish 8 look up this article (sorry, only in German language til now):
https://de.chessbase.com/post/wie-stockfish-alphazero-ins-neuronale-netz-ging
It's a simulation of what Stockfish 8 probably did evaluate under the given match conditions, what it saw and what it missed, also checked with Stockfish 10. The latter engine would probably not have lost that game, which followed the English opening.
TMMM TMMM 1/31/2019 11:18
For those seriously considering buying Komodo 12 based on this advertisement, do check out http://www.computerchess.org.uk/ccrl/4040/. There it shows Komodo 12.3 MCTS is ranked even *lower* than Komodo 11.3.1, and of course way lower than Stockfish 10, which is free and open-source. Not to mention that AlphaZero completely crushed Stockfish, i.e. Komodo is nowhere near the level of AlphaZero.

And I agree with jajalamapratapri, MCTS is only a small part of what AlphaZero is doing and it is not the reason why it performs so differently from other engines.
WildKid WildKid 1/31/2019 11:10
VERY roughly (I am only commenting at all because the ATL article says nothing sensible): 'alpha beta' looks for the move that gives the best result assuming the opponent also plays optimally, 'pruning' lines where either side's choices seem sub-optimal. 'Monte Carlo' examines a wide range of alternative moves without discounting any of them, and produces a 'compound' evaluation. Alpha Zero has the special feature that it doesn't have an 'evaluation function' (e.g. 'I am two pawns ahead'); it is simply trying to maximize the probability of a win vs. a loss. Alpha Zero thus does not assume that the opponent will necessarily play optimally in a logical sense. This may (wild speculation here) be why it has such an attacking style.
Pionki Pionki 1/31/2019 09:55
Alpha Zero may have shown a new way. Perhaps in future other programs, which are currently on the market, will become better than Alpha Zero, if they adopt the same way. Perhaps human chess players will adopt a new way of playing the game. In future a new generation of players may not study openings (which in itself must be a tedious excercise), but simply play chess. Things may change after first a romantic era, and then a century of conventional wisdom of the centre of the board. Every century or so everything turns upside down.
benedictralph benedictralph 1/31/2019 09:40
@TMMM: Of course they are nowhere near what AlphaZero showed because the latter had Google's resources behind it. Just like it took IBM's resources to beat Kasparov back in 1997.
Tom Box Tom Box 1/31/2019 05:58
Alpha Zero vs Stockfish was not a fair match as Stockfish was not playing at full strength.
jajalamapratapri jajalamapratapri 1/31/2019 02:00
Saying "Alpha Zero is based on the Monte Carlo Tree Search (MCTS)" is like saying self-driving cars are based on rubber tires.
chessgod0 chessgod0 1/31/2019 01:06
Fully agree with TMMM--these games do not remotely rise to what AlphaZero showed in it's match. Comparing this to what AlphaZero did is like comparing boys to men--laughable.
TMMM TMMM 1/30/2019 09:16
These games are nowhere near what AlphaZero showed, with e.g. his Bg5!! or Ng4!! moves against Stockfish. This just sounds like a desperate attempt by ChessBase/Komodo to profit from the AlphaZero deep learning hype.
fixpont fixpont 1/30/2019 06:49
Rybka used Monte/Carlo as far as 10 years ago. There were article about it in this exact site.

https://goo.gl/tR6YF5
https://goo.gl/tHULuc
RayLopez RayLopez 1/30/2019 04:42
The author I think is mistaken: Alpha Zero uses Monte Carlo for the evaluation function in addition to alpha-beta pruning, as well as the minimax algorithm, rather than as a mutually exclusive alternative to alpha-beta. I'll let more experienced programmers than myself comment further.
1