MCTS Data Flow

In last week's post, Monte Carlo Tree Search (MCTS), I featured a video to explain the fundamental concepts of MCTS. Here's a diagram that takes the explanation several steps further. Note that it's based on AlphaGo Zero, but the concepts apply largely to AlphaZero as well.

Extracted from:
AlphaGo Zero Cheat Sheet
(applied-data.science; big PNG: 8333 x 7500)

I added the red numbers in parentheses to connect the left portion of the diagram, an inverted tree structure ('How AlphaGo Zero chooses its next move'), with the right portion, a step-by-step explanation of the left portion ('First, run the following simulation 1600 times...'). The following text is (mostly) copied from the 'cheat sheet'.

(1) Start at the root node of the tree (the current game state). Choose the action that maximizes 'Q + U'. Continue until a leaf node is reached

(2) The game state of the leaf node is passed into the neural network [NB: the tall stack of blocks; explained elsewhere on the 'cheat sheet'], which outputs predictions about two things:-
      • P - Move probabilities
      • V - Value of the state

(3) The move probabilities (P) are attached to the new feasible actions from the leaf node.

(4) Backup previous edges. Each edge that was traversed to get to the leaf node is updated.

'After 1600 simulations'

(5) The move can either be chosen:-
      • Deterministically (for competitive play)
      • Stochastically (for exploratory play)

Values like 'N', 'W', 'Q', and 'P' are explained in the notes to the diagram. After studying the diagram, I felt that I was finally starting to understand the basic concepts of MCTS. How do they work with AlphaZero? That will require further study.

February Amazon Yahoos

For the third consecutive month, my Yahoo news feed served no chess news. Of celebrities and sports, there was plenty to choose from; of chess there was nothing. Is the problem perhaps an overall deterioration in the Yahoo news feed itself?

Maybe yes, maybe no, but Yahoo doesn't have a problem following me around the web to watch what I am doing. For the second consecutive month -- I documented the first in January Amazon Yahoos -- and lasting for several days, it served me an ad echoing what I had browsed on Amazon.

'Sponsored --$-- Amazon.com'

The three books shown are:-

• 'Better Thinking, Better Chess: How a Grandmaster Finds his Moves'; Joel Benjamin
• '300 Most Important Chess Positions'; Thomas Engqvist
• 'Chess for Life'; Matthew Sadler, Natasha Regan

Those are certainly three noteworthy books, but I only recall looking at the last one. That was while preparing the first post of last month, 'Game Changer' Interview. As for the other two books, I've heard about them, but don't remember browsing their pages on Amazon. Did I click on the Yahoo ad to look at any of the books? Of course not. Why encourage creepy web behavior?

Since I don't have any mainstream media chess stories to fill out this post, I get to select my own. I'll start with a theme I introduced in 'January Yahoos', titled 'Weird Chess News'. What's weird for me is not necessarily weird for you, and vice versa, but as long I'm writing the post, I get to pick. Both of these stories are about chess in school and both are from Texas:-

• [San Benito CISD] places chess coach on administrative leave (valleycentral.com) • 'Thousands of dollars spent on the chess club in San Benito has landed their after school program director in hot water.'
• Chess: Coach faces allegations of throwing matches, could be banned (usatoday.com) • 'A coach for an award-winning chess team from El Paso, Texas, could be banned for life following allegations he instructed players to lose games on purpose.'

If there was one single story this month that I would have liked to see get a wider audience, it was this one:-

• Magnus Carlsen On The Ancient Appeal Of Chess And The Opportunities Of A More Modern Game (forbes.com; 'Guest post written by Magnus Carlsen') • GM Carlsen ended his essay saying, 'The excitement of playing a game of chess over a physical board -- feeling the tension as your opponent sits two feet in front of you, studying your every move -- cannot be beaten. Yet nothing would make me sadder than losing the essential benefits of chess because of a righteous refusal to adapt to change.'

Other events might have interested a wider audience. Without too much thought I came up with the Gibraltar Open; the Champions Showdown and the Cairns Cup (for women), both in St.Louis; and even the Stockfish - Leela TCEC match, an engine handcrafted by humans vs. a rapidly improving AI/NN challenger. Maybe we'll see some mainstream coverage of chess in March, but I'm not optimistic.

'On Anderssen'

My recent post Down the Rabbit Hole mentioned,

I discovered the magazine Schachzeitung, 'von der Berliner Schachgesellschaft', Volume 1, 1846 (starts in July).

Since then I've been searching the Google Books digital collection of 19th century chess literature, looking for the most relevant files. Schachzeitung is just one example of many periodicals available.

So far I've collected 23 of the first 26 annual editions of Schachzeitung (1846-1871). My main objective is to locate information about the early, unofficial World Championships, where the German master Adolf Anderssen played a central role for many years.

Starting in 1851 Anderssen was listed on the annual cover page as one of the two editors of Schachzeitung. In fact, his name always appeared first. This lasted for nine years, but the Di Felice extract that I quoted in the 'Rabbit Hole' post doesn't even mention him.

Anderssen was also the winner of the 1851 London Tournament (London, V-VII, 1851). The 1851 edition of Schachzeitung (vol.6) has many stories on the event, but it will be some time before I'm able to understand them correctly.

One of the features of 19th century chess magazines that you don't see much in the 21st century is the importance of poems -- sometimes long poems, stretching for many pages. Shown above is a short poem from the last page of the August 1851 issue, titled 'An Anderssen'. That would have been a month or so after the 1851 London tournament ended. When I fed the OCR output, line by line, into Google Translate, it gave me the following translation.

You beat Albion for Germany
In a people's struggle, the best-humored;
You have defeated the proud island son,
And England fell in his master Staunton.

That was a fight, a glory at the right time;
Recently we were not bedded on laurel,
We were Matt before Christendom,
Since you have saved us from the checkmate.

But if your victory raises you to the hero,
Be he the dove with the green branches,
Who brings us hope and animates,
That this victory would only lead to the round

That's not too bad; the software choked only on the word 'Matt'. How would it do on a longer poem? I'll never find out unless I find a poem so compelling that I just have to know what it says. As for AI/NN translation of poetry in general, that would be a different area of research. I doubt there is much overlap with chess literature.

Stockfish Wins TCEC S14; CCC6 S2 Underway

TCEC: 'Stockfish wins TCEC S14' -- shouldn't that be followed by 'Ho-hum'? After all, Stockfish has won the last three TCEC seasons and we have to go back to season 10 to find a different winner. Here are the posts on this blog that signalled the TCEC winners:-

• 2017-12-11: Houdini, Komodo, Stockfish, and AlphaZero • S10: 'With the score at +14-9=73 after 96 games, Houdini was declared the winner' (over Komodo)
• 2018-04-16: Stockfish Wins TCEC Season 11
• 2018-07-16: Stockfish Wins TCEC Season 12
• 2018-11-12: Stockfish Wins TCEC Season 13 (and Everything Else)

In season 14, Stockfish almost lost. As I wrote in last week's report, TCEC S14 Final, CCC5/-6; Part 2/2:-

The TCEC S14 final match between Stockfish and Leela has seen 72 games completed. Leela leads by one game, +9-8=55. If Leela can maintain this slim lead through the full 100 games, it will signal a major shift in chess engine dominance.

Of the next 28 games in the 100 game match, Stockfish won two games and the rest were drawn, making the final score +10-9=81 (50.5-49.5) in Stockfish's favor. That's as narrow a match win as exists in chess, much to the delight of Stockfish fans and the chagrin of Leela fans. Congratulations to both open source teams for a thrilling superfinal!

CCC: In the other major, ongoing engine competition, the 'CCC6: Winter Classic' completed stage 1. Eight engines qualified to stage 2, as shown in the following crosstable.

For a readable version of the same crosstable see the tab for 'TCEC/CCC Links' at the top of this page and follow the link for 'CCC #tournament-results'. Those eight qualifying engines were joined by the big four -- Komodo, Leela (Lc0), Stockfish, and Houdini -- for a total of 12 engines in the stage 2 'Playoffs'. Two of those engines will qualify for the 200-game final.

Dagmar and Strange Ebbesen

In this ongoing series on The Sociology of Chess (November 2016), one of the themes I haven't explored is chess as an accessory to legend. Take the following drawing, for example.

If the drawing looks familiar, it might be because I've also used it on my page Chess Through the Artist's Eye. In fact, the image shown above is cropped to show only the principle characters, while the 'Artist's Eye' page includes the many onlookers to the left and right of the scene. That same page informs,

Brozik, Václav (Czech, 1851–1901) • 'Dagmar and Strange Ebbesen at the Chess Table' (1880?), Illustreret Tidende

The Wikipedia page, Vaclav Brozík, says,

Václav Brožík (French: Vaclav de Brozik; 6 March 1851, Tremošná - 15 April 1901 Paris) was a Czech painter who worked in the academic style.

One of the subjects of the drawing is described in another Wikipedia page, Dagmar of Bohemia:-

Dagmar of Bohemia (also known as Margaret of Bohemia; c. 1186 – 24 May 1212 in Ribe) was queen consort of Denmark as the first spouse of King Valdemar II of Denmark. She was the daughter of King Premysl I Ottokar of Bohemia and his first wife, Adelheid of Meissen.

That's all very nice, but in the words of the 11th World Champion, 'What's that got to do with chess?' The pieces of the story come together in a series of poems, Full text of "The Mermaid's Prophecy and Other Songs Relating to Queen Dagmar" (archive.org; Project Gutenberg eBook). The poems are titled...

I. King Valdemar's Wooing
II. Queen Dagmar's Arrival in Denmark
III. The Mermaid's Prophecy

...where the 'Wooing' starts in the first verses,

Valdemar King and Sir Strange bold
     At table sat one day,
So many a word 'twixt them there passed
     In amicable way.

"Hear Strange, hear! thou for a time
     Thy native land must leave;
Thou shalt away to Bohemia far
     My young bride to receive."

...After reaching Bohemia, Strange Ebbesen announces the reason for his visit and is challenged to a game...

"Hail to thee, King of Bohemian Land,
     Thou sittest a prince in state;
To you sends Valdemar, Denmark's King,
     With your daughter he would mate."

[...]

Then they bore in the playing board,
     Was wroughten all of gold;
Sir Strange should with the princess play,
     And private converse hold.

The third game they together played
     Upon that red gold board,
Sir Strange won the noble maid
     For Valdemar his lord.

...In fact, there is nothing here to confirm that the game is chess. That must be artist Brozík's imagination, but why not?

Monte Carlo Tree Search (MCTS)

Since the answer to last week's post, AI/NN: 'Here to Stay?', is a resounding 'Yes!', it's time to learn a little more about the subject. One aspect on which I'm particularly fuzzy and which is important to understanding AlphaZero is the Monte Carlo Tree Search, aka MCTS. The following video is not specific to chess, but explains the concepts better than any other video I reviewed while working on this post.

Monte Carlo Tree Search (15:49) • 'Published on Mar 5, 2017'

The description explains,

This is a video I [John Levine] made for my class "CS310: Foundations of Artificial Intelligence" at the University of Strathclyde. The video has a brief description of the Monte Carlo Tree Search algorithm and includes a worked example.

The 'worked example', which starts at 3:30 into the clip, is particularly useful and helps to understand better the material that precedes it. For more about MCTS specific to chess, see Monte Carlo Tree Search (chessprogramming.org).

Chessable and 'Game Changer'

Chessable appeared on my radar twice during the past month. The first time was in connection with the 'Game Changer' book; see my recent post 'Game Changer' Excerpts for my next-to-last word on that. The second time was John Hartmann's book review in the January 2019 issue of Chess Life. The Chessable portion of the review started,

Chessable is a new website/"webservice" gaining quite a bit of mindshare with tech-savvy players. Part of this has to do with its association with IM John Bartholomew, one of chess' leading streaming personalities, who also serves as Chessable's Chief Communications Officer and co-founder. Bartholomew is a big draw in the streaming/esport landscape and his involvement with the platform has undoubtedly aided in its rise to prominence.

I make no claim to being particularly tech-savvy, which is confirmed by my having never visited the Chessable site. Hartmann's mention that the site was 'free to use' meant that it was high time to rectify the oversight.

Chessable.com describes itself as 'Learn chess online: openings, tactics & more'. Since taking up chess960 I'm no longer interested in studying traditional chess openings and since tactics trainers are a dime a dozen, I wasn't sure that the site had much to offer me that was both interesting and free. Luckily for me, the '& more' portion includes endgames.

Free access to the site requires an id and a password (entry no.248 according to my system for managing passwords), undoubtedly used to track progress on the Chessable material. I quickly located the free 'Basic Endgames' course and started using the service immediately. The key to the training is in repeating the material, an exercise which I found a bit tedious after a few minutes, but which probably works for anyone who has the necessary patience. The underlying theory is explained on the page The science that makes chess learning easier (chessable.com). Like most theories about learning, I imagine there is considerable controversy here, but I'll look into that some other time.

As for the material based on the 'Game Changer' book, see The game has changed! GM Matthew Sadler on how Game Changer can benefit YOU (ditto; 31 January 2019) by Leon Watson, who is described on the About Us page as responsible for 'PR & Marketing'. That promotional page points to Game Changer: AlphaZero's Groundbreaking Chess Strategies and the Promise of AI - MoveTrainer™ Course (chessable.com). The comments include a couple of positive reviews by competent chess players who are also knowlegeable about MoveTrainer. All in all, the course looks promising.