Komodo MCTS: the boa constrictor approach

by Albert Silver
6/15/2018 – The inclusion of the new Monte Carlo Tree Search (MCTS) version of Komodo has had many users surprised, confused, and even describing it as a gimmick. However, its value is not to be underestimated, and it allows the astute user to find resources the very best engines are completely blind to. GM Karsten Mueller has helped illustrate this with some finely chosen examples in the following article. Read on to see what makes Komodo MCTS so special!

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

Testing Monte Carlo Tree Search

When Deep Mind unveiled their AlphaZero, it broke the chains of status quo irrevocably on a variety of fronts. On the one hand, there was their self-learning neural network, and on the other, there was their use of the MCTS search system, which is vastly different from the hitherto ubiquitous alpha-beta search system that ruled the day.

Because of how new it is, very little advanced development has been made to fine-tune it, and as a result, it still performs worse on a pure Elo level. However, Mark Lefler, the chief programmer of Komodo, has been working hard with nearly daily breakthroughs, and promises to release updates soon (“but [we] are waiting for the rather significant daily Elo gains to slow a bit.”), available for free to owners of Komodo 12.

That said, what is the value of this new MCTS system, and does it work even when not coupled to a neural network? The answer is a very vocal ‘yes’.

Have you ever watched a game of Magnus Carlsen, as he does his unique boa constrictor act on his opponents, and wondered how he seemed to be able to win these ‘drawn’ endgames? Perhaps you are watching with one of the top engines, and it invariably says the position is dead drawn until all of a sudden with the snap of a finger Magnus is winning. Is it Voodoo? Hypnotism? Or was the engine just wrong? It is actually none of these things.

What a player such as Carlsen does is to outplay his opponents, even though the evaluation by the engines is a big fat 0.00. How can he be outplaying them if the evaluation never changes? Behind the curtains of that game, he is slowly reducing the number of available moves to his opponent. At first, they might have three or four perfectly viable choices, all of which draw, but as the game proceeds, they now only have two or three viable choices, until before long they are walking a tightrope act with only one move to keep it together or lose.

For classic engines, as long as there is one single move that can save, they will declare it a draw. Objectively, they are not wrong, since that one saving move does save, and it is there, but that doesn’t begin to tell the story. MCTS search looks at the various options, some losing, some winning, and some drawn, and chooses the move that offers the best chances to win or save. Naturally, if there is only one right move, it must choose it, but if given a fork in the road, then much like Carlsen, it will choose the continuation that presents the most practical chances.

In order to illustrate this, GM Karsten Mueller has shared a few examples that show the difference, and value, of this sort of analysis:


Tricky to the end — Part 1

[Event "27th EY BU16 2017"] [Site "Mamaia ROU"] [Date "2017.09.14"] [Round "9.3"] [White "Gaifullin, Artur"] [Black "Van Foreest, Lucas"] [Result "1/2-1/2"] [ECO "D35"] [WhiteElo "2413"] [BlackElo "2485"] [Annotator "Mueller,Karsten"] [SetUp "1"] [FEN "8/8/8/1p1p4/3P2p1/4q1P1/1R4R1/2k3K1 w - - 0 71"] [PlyCount "19"] [EventDate "2017.09.05"] [EventType "swiss"] [EventRounds "9"] [EventCountry "ROU"] [SourceTitle "Komodo 12 Monte Carlo"] [Source "ChessBase"] [SourceDate "2017.09.13"] [SourceVersion "1"] [SourceVersionDate "2017.09.13"] [SourceQuality "1"] {[#]} 71. Rbf2 $6 {Komodo 12} ({Komodo 12 Monte Carlo chooses the trickier} 71. Kh1 $5 {though it too fails to the correct} b4 $1 (71... Qh6+ $2 72. Rh2 Qe3 73. Rhc2+ Kd1 74. Rf2 Qh6+ 75. Kg1 Kc1 76. Rbe2 Kd1 77. Ra2 $18) (71... Qe1+ $2 72. Kh2 b4 73. Ra2 Kb1 74. Rgb2+ Kc1 75. Ra1+ Kxb2 76. Rxe1 Kc3 77. Kg2 b3 78. Kf2 Kxd4 79. Ke2 Kc3 80. Rc1+ $18) (71... Qxd4 $2 72. Rbf2 Qh8+ 73. Rh2 Qxh2+ 74. Kxh2 b4 75. Rf5 b3 76. Rxd5 b2 77. Rc5+ Kd2 78. Rb5 Kc1 79. Kg2 $18) 72. Rxb4 (72. Rbf2 Qxf2 73. Rxf2 b3 $11) 72... Qh6+ (72... Qe1+ $2 73. Rg1 $18) 73. Kg1 (73. Rh2 Qe3 $11 {And White is unable to coordinate his rooks properly.}) 73... Qe3+ 74. Kh2 Qh6+ $11) 71... b4 $1 {Black's counterplay comes in the nick of time.} 72. Kh1 Qh6+ 73. Rh2 Qxh2+ 74. Kxh2 b3 75. Kg2 b2 76. Rf1+ Kc2 77. Kf2 b1=R 78. Rxb1 Kxb1 79. Ke3 Kc2 80. Kf4 (80. Kf4 Kd3 81. Kxg4 Kxd4 82. Kf5 Ke3 83. g4 d4 $11) 1/2-1/2

In the next example, we see the MCTS search play like a grandmaster, not because of 'perfect' moves, but for making it as hard for the opponent as possible to keep control.


Tricky to the end — Part 2

[Event "Helsingor Xtracon op"] [Site "Helsingor"] [Date "2017.07.29"] [Round "9"] [White "Goh, Wei Ming Kevin"] [Black "Bosiocic, Marin"] [Result "0-1"] [ECO "B48"] [WhiteElo "2446"] [BlackElo "2616"] [Annotator "Mueller,Karsten"] [SetUp "1"] [FEN "8/8/p4R2/P3p3/1p1bk3/1r3R2/6PK/8 b - - 0 50"] [PlyCount "11"] [EventDate "2017.07.22"] [EventType "swiss"] [EventRounds "10"] [EventCountry "DEN"] [SourceTitle "Komodo 12 Monte Carlo"] [Source "ChessBase"] [SourceDate "2017.09.13"] [SourceVersion "1"] [SourceVersionDate "2017.09.13"] [SourceQuality "1"] {[#]} 50... Rxf3 $5 {is the astute choice by Komodo 12 Monte Carlo.} (50... Ra3 $6 {Komodo 12} 51. Rxa6 b3 52. Ra8 b2 53. Rb8 Rxa5 54. Rfb3 $11) 51. gxf3+ Kd3 {And the bishop strikes back after} 52. Rxa6 $2 {after which the rook is dominated.} (52. Rb6 $1 {was the only move that held the fort together. For example,} Kc4 (52... Bxb6 $2 53. axb6 b3 54. b7 b2 55. b8=Q $18) 53. Rxa6 b3 54. Rc6+ Kb5 55. Rc1 Kxa5 56. Kg3 Be3 (56... Kb4 57. Kg4 b2 58. Rb1 Kb3 59. Kf5 Kc2 60. Rxb2+ Bxb2 61. f4 $11) 57. Rc3 Bf4+ 58. Kg4 Kb4 59. Rc8 b2 60. Rb8+ Kc3 61. Rc8+ Kd2 62. Rb8 Kc2 63. Rc8+ Kb1 64. Kf5 $11) 52... b3 53. Ra8 ({It is too late for} 53. Rb6 {since it runs into} Bxb6 54. axb6 b2 55. b7 b1=Q $19) 53... e4 $1 {This opening of the h2-b8 diagonal is deadly.} 54. Kg2 (54. fxe4 b2 55. Rb8 Be5+ $19) (54. a6 b2 55. Rb8 Be5+ $19) 54... e3 55. a6 (55. Kf1 e2+ 56. Ke1 Bc3+ $19) 55... e2 (55... e2 56. Re8 b2 57. a7 Bxa7 58. Rd8+ Bd4 $19) 0-1

In the following position, White exploits some tactics to give Black more trouble than he had imagined.


Unexpected troubles

[Event "31st Belgrade Trophy"] [Site "Belgrade SRB"] [Date "2017.11.25"] [Round "2.4"] [White "Blagojevic, Dr"] [Black "Sahin, Oz"] [Result "1-0"] [ECO "E62"] [WhiteElo "2495"] [BlackElo "2226"] [Annotator "Mueller,Karsten"] [SetUp "1"] [FEN "8/4r2k/6Rp/5KbP/6P1/3B4/8/8 w - - 0 88"] [PlyCount "9"] [EventDate "2017.11.24"] [EventType "swiss"] [EventRounds "9"] [EventCountry "SRB"] [SourceTitle "Komodo 12 Monte Carlo"] [Source "ChessBase"] [SourceDate "2017.09.13"] [SourceVersion "1"] [SourceVersionDate "2017.09.13"] [SourceQuality "1"] {[#]} 88. Rxg5 $5 {A fascinating choice by Komodo 12 Monte Carlo that promises no end of mines to avoid.} (88. Bc4 $6 {Komodo 12}) {This dance of the rook is fraught with danger, and the extensive tactical questions asked of Black are common in endgames.} 88... Rd7 $2 {A careless move that allows White to set up an indirect threat to the black rook, while saving his own otherwise.} ({After } 88... Re3 $1 {There woould be no win available. Ex:} 89. Kf6+ (89. Be4 hxg5 $11) (89. Kf4+ Rxd3 $11) 89... Rxd3 90. Rg7+ Kh8 91. Rg6 Kh7 $11) (88... Rf7+ $2 89. Ke6+ Kh8 90. Kxf7 hxg5 91. Kg6 $18) (88... hxg5 $2 89. Kf6+ Kh6 90. Kxe7 Kg7 $18) 89. Be4 $1 hxg5 (89... Rf7+ 90. Ke6+ Kh8 91. Kxf7 hxg5 92. Kg6 $18) 90. Ke6+ {A deadly discovered check.} Kh6 91. Kxd7 Kg7 92. Ke6 (92. Ke6 Kh6 93. Kf5 Kg7 94. Kxg5 $18) 1-0

As the grandmaster explains, it is a mistake to just push one's pawns blindly forward in an endgame with passed pawn by both sides.


When the knight trumps the bishop

[Event "CHN Team Men 2017"] [Site "Beijing CHN"] [Date "2017.06.14"] [Round "9.3"] [White "Zhao, Yuanhe"] [Black "Huang, Renjie"] [Result "1-0"] [ECO "D30"] [WhiteElo "2401"] [BlackElo "2156"] [Annotator "Mueller,Karsten"] [SetUp "1"] [FEN "6b1/8/6P1/8/5P1N/4p3/4k1K1/8 w - - 0 78"] [PlyCount "13"] [EventDate "2017.06.06"] [EventType "team"] [EventRounds "9"] [EventCountry "CHN"] [SourceTitle "Komodo 12 Monte Carlo"] [Source "ChessBase"] [SourceDate "2017.09.13"] [SourceVersion "1"] [SourceVersionDate "2017.09.13"] [SourceQuality "1"] [WhiteTeam "Chengdu"] [BlackTeam "Shandong"] {[#]} 78. Nf5 $5 {Komodo 12 Monte Carlo} (78. f5 {Komodo 12}) {In an endgame with both sides pushing passed pawns, caution and great precision are often required. Just blindly pushing one's pawns would be a grave mistake.} 78... Kd3 $2 {The king goes to chase the knight, but this is a mistake since White's knight is in time to stop the e-pawn while being free to march his own pawns forward.} ({The intermediate move, AKA Zwischenzzug,} 78... Bd5+ $1 {saves the day:} 79. Kg3 (79. Kh3 $6 Be6 80. Kh4 (80. Kg4 $2 Kd3 $19) 80... Bxf5 81. Kg5 $11) 79... Kd3 (79... Be6 {is also playable. For example,} 80. g7 Kd3 81. Nxe3 Kxe3 82. f5 Bg8 83. Kg4 Ke4 84. Kg5 Ke5 85. Kg6 Kd6 86. f6 Ke6 $11) 80. Nxe3 Kxe3 81. f5 (81. Kg4 Ke4 82. Kg5 Bc4 83. g7 (83. f5 Ke5 84. f6 Ke6 $11) 83... Bg8 84. f5 Ke5 85. f6 Ke6 86. Kg6 Bf7+ $1 $11) 81... Be4 $1 {The only move that holds the pawns in check.} 82. Kg4 Kd4 83. Kg5 Ke5 84. f6 Ke6 85. f7 Ke7 $11) (78... Be6 $2 79. Nd4+ (79. Ng3+ Kd3 80. Kf3 Kd4 81. f5 Bd5+ 82. Kf4 Bc4 83. f6 $18) 79... Kd3 80. Nxe6 e2 81. g7 e1=Q 82. g8=Q $18) (78... Kd2 $2 79. Ng3 e2 80. Nxe2 Kxe2 81. f5 Bd5+ 82. Kg3 Be4 83. Kf4 $18) 79. Ng3 Bd5+ ({Nach} 79... e2 80. Kf2 Be6 (80... Kd4 81. Kxe2 Kd5 82. Kf3 Ke6 83. f5+ Kf6 84. Kf4 $18) {The pawns are stopped personally by the his majesty.} 81. Ke1 $1 Bc4 82. f5 Kd4 83. f6 $18) 80. Kh3 e2 (80... Kd4 81. Kg4 $18) 81. Nxe2 Kxe2 82. f5 Be4 83. Kg4 Ke3 84. Kg5 1-0

In the next and final example, the grandmaster cannot help himself as his teaching instincts take over and he serves up a highly illustrative example of Rauser's Drawing zone. Most readers will be familiar with the concept of the h-pawn and the wrong bishop to ensure a win, but there are exceptions, as below:

As GM Mueller explains: "Black wins, if he can force White's king to leave the zone illustrated by the green squares, permanently."

Almost counterintuitively, White played 98.Kb4?? and lost. See the game to know how and why.


The exception confirms the rule

[Event "Gibraltar Masters 2018"] [Site "Caleta ENG"] [Date "2018.01.26"] [Round "4.114"] [White "Chibnall, Alana"] [Black "Gonzalez Gonzalez, A."] [Result "0-1"] [ECO "B28"] [WhiteElo "1906"] [BlackElo "2192"] [Annotator "Mueller,Karsten"] [SetUp "1"] [FEN "8/8/p1bPk3/P1P5/1P6/6p1/8/5K2 w - - 0 62"] [PlyCount "90"] [EventDate "2018.01.23"] [EventType "swiss"] [EventRounds "10"] [EventCountry "ENG"] [SourceTitle "Komodo 12 Monte Carlo"] [Source "ChessBase"] [SourceDate "2017.09.13"] [SourceVersion "1"] [SourceVersionDate "2017.09.13"] [SourceQuality "1"] {[#]} 62. Ke2 $5 {Komodo 12 Monte Carlo} (62. b5 $6 {Komodo 12}) (62. Kg1 $5 { Komodo 12 Monte Carlo}) 62... Kf5 $2 (62... Kd5 63. Kf3 Kc4+ 64. Kxg3 Kxb4 65. Kf4 Kxa5 66. Ke3 Kb4 67. Kd2 Kb3 68. Kc1 Ka2 $19) 63. d7 Bxd7 64. Kf3 Ke5 65. Kxg3 Kd4 66. Kf2 Kd3 67. Ke1 Kc2 68. Ke2 Bc6 69. Ke1 Bb5 70. Kf2 Kd2 71. Kf3 Bc6+ 72. Kf2 Bb5 73. Kf3 Ba4 74. Kf2 Kc3 75. Ke3 Kxb4 76. Kd2 Kb3 77. Kd3 Bb5+ 78. Kd2 Kb2 79. Kd1 Bc6 80. Kd2 Be4 81. Kd1 Bd5 82. Kd2 Bf3 83. Ke3 Bg2 84. Kd2 Kb1 85. Kd1 Bc6 86. Kd2 Ba4 87. Kc3 Kc1 88. Kb4 Bc6 89. Ka3 Kb1 90. Kb3 Bd5+ 91. Ka3 Ka1 92. Ka4 Ka2 93. Kb4 Kb2 94. Ka4 Bc6+ 95. Kb4 Bb5 96. c6 Bxc6 97. Kc4 Bb5+ {It is essential that White's king remain in the drawing zone. If he fails to return to it, he is lost.} 98. Kb4 $2 {White moves his king outside the drawing zone and is unable to return. As such he loses the game.} (98. Kd4 Kb3 99. Ke3 Kc3 100. Kf2 Kb4 (100... Bd3 101. Ke3 Bg6 102. Ke2 $1 $11 {With Black's bishop unable to control the promotion square, or prevent the king from entering, he is forced to accept the draw.}) 101. Ke3 Kxa5 102. Kd2 Kb4 103. Kc2 Ka3 104. Kb1 $11) 98... Be2 99. Ka4 Bd1+ 100. Kb4 Bb3 101. Kc5 Kc3 102. Kb6 Bc4 103. Kc5 Bf1 104. Kd5 Bg2+ $2 (104... Bd3 $1 105. Ke5 Kb4 106. Kd4 Bh7 107. Ke3 Kxa5 108. Kd2 Kb4 109. Kc1 Kc3 $19) 105. Kc5 $2 (105. Ke5 $1 Kc4 106. Kf4 Kb4 107. Ke3 Kxa5 108. Kd2 Kb4 109. Kc2 Ka3 110. Kb1 $11) 105... Bb7 106. Kb6 Kb4 0-1

As you can see, the MCTS search has valuable insights to offer by its very own nature. Hopefully it will also help you make the most of your resources.

Correction June 19th: GM Dr Karsten Müller agrees that the definition as originally given above for "Rauser's drawing zone" was not correct, and it has been amended.


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!


Links


Born in the US, he grew up in Paris, France, where he completed his Baccalaureat, and after college moved to Rio de Janeiro, Brazil. He had a peak rating of 2240 FIDE, and was a key designer of Chess Assistant 6. In 2010 he joined the ChessBase family as an editor and writer at ChessBase News. He is also a passionate photographer with work appearing in numerous publications, and the content creator of the YouTube channel, Chess & Tech.

Discuss

Rules for reader comments

 
 

Not registered yet? Register