14 December 2018

DeepMind Videos

Last week's post, AlphaZero Is Back!, ended with a request for more time to understand what had just happened.

This is too much new material to digest in the time available for a simple blog post, so I'll come back to the subject as soon as I can.

This video from Google's DeepMind is partly a restatement of what we learned from their first announcement a year ago, partly a statement of what they have been doing since then, and partly a declaration about where they want to go with the technology.

AlphaZero: Shedding new light on the grand games of chess, shogi and Go (4:38) • 'Published on Dec 6, 2018'

The description explains,

DeepMind's AlphaZero is the successor of AlphaGo, the first computer program to beat a world champion at the ancient game of Go. It taught itself from scratch how to master the games of chess, shogi and Go, beating a world-champion program in each case and discovering new and creative playing strategies that hint at the potential of these systems to tackle other complex problems.

A DeepMind blog post, AlphaZero: Shedding new light on the grand games of chess, shogi and Go (deepmind.com/blog), bearing the same title and publication date as the video, goes into more depth. One paragraph explains the essence of the technology.

An untrained neural network plays millions of games against itself via a process of trial and error called reinforcement learning. At first, it plays completely randomly, but over time the system learns from wins, losses, and draws to adjust the parameters of the neural network, making it more likely to choose advantageous moves in the future.

In other words, an NN plays a few million games, compares its predictions about the outcome of its moves against the result of those games, adjusts its internal NN parameters to eliminate discrepancies between its predictions and its results, then starts the process over with the new parameters. Eventually it reaches a level where the predictions and the results almost coincide. DeepMind has also put together a couple of video courses on the underlying technology:-

I now know what I'll be doing during the year-end holidays.

13 December 2018

Endgame Studies with Timman

GM Jan Timman is best known as a player. Last year, in 1967 World Juniors (October 2017), I gave a brief overview of his career as a World Championship candidate, stopping just before his ill-fated participation in the 1993 Karpov - Timman FIDE Title Match.

After being a player, GM Timman is also well known as an author. His Wikipedia page, Jan Timman, currently lists nine book titles and I am certain that the list is not complete. The last book listed is 'The Art of the Endgame', subtitled 'My Journeys in the Magical World of Endgame Studies' (New in Chess, 2011). The book brings us to a third aspect of his dedication to chess : as a composer of endgame studies. Chapter 1 of the 2011 book, titled 'Miniature Studies', starts,

A miniature study is a study with no more than seven pieces in the starting position. With minimal material, the composer must weave the maximum amount of finesses into the position. A classical example is the following study by the brilliant Russian composer Mark Liburkin.

Any study with seven pieces or less is solved by current tablebase technology, which we saw a few months ago in Seven-piece Tablebase on Lichess (August 2018). The Liburkin study is the first position in the first chapter of Timman's book.

Liburkin, '64' 1933
White to play and win

I'll continue to explore 'The Art of the Endgame' and will report any findings worth further research. I've already discovered that seven-piece tablebase positions are paricularly fruitful for further investigation.

11 December 2018

Null Moves

In yesterday's post, Kasparov vs. the Early Engines, one of the encounters mentioned by GM Kasparov in his book Deep Thinking was:-

1992-12 Match vs. Fritz 2, Cologne; +26-11=3 (?)

Of the two mentions of the match in the book, the first (loc.1880 using the Kindle location attribute) starts like this:-

In 1992, I played a long casual blitz match against one of this new generation of PC programs, one that would go on to become nearly synonymous with PC chess engines. Fritz was published by ChessBase, which explains the sardonic German nickname. Its creator was a Dutchman, Frans Morsch, who had also written programs for tabletop chess machines like Mephisto. As such, he was used to having to cram tightly optimized code into very limited resources. He also helped pioneer several of the search enhancements that allowed chess machines to keep improving despite the increasing branching factor that was supposed to slow them down.

This introduction to Fritz and its search heuristics continues with a discussion of the 'null move' concept:-

One of these is worth a brief technical detour because it's an interesting example of how machine intelligence has been augmented in ways that have nothing to do with the workings of the human mind. Called the "null move" technique, it tells the engine to "pass" for one side. That is, to evaluate a position as if one player could make two moves in a row. If the position has not improved even after moving twice, then it can be assumed that the first move is a dud and can be quickly discarded from the search tree, reducing its size and making the search more efficient. Null moves were used in some of the earliest chess programs, including the Soviet Kaissa. It's elegant and a little ironic that algorithms designed on the principle of exhaustive search are augmented by being less exhaustive.

Humans use a very different heuristic when making plans. Strategic thinking requires setting long-term goals and establishing milestones along the way, leaving aside for the moment how your opponent, or business or political rivals, might respond. I can look at a position and think, "Wouldn't it be great if I could get my bishop over there, my pawn up there, and then work my queen around to join the attack." There are no calculations involved yet, only a type of strategic wish list. Only then do I begin to work out whether it's actually possible and what my opponent might do to counter it.

The first point that caught my attention here was the assertion that a null move has 'nothing to do with the workings of the human mind'. When I'm using an engine to evaluate a position, I often inject a null move to identify the opponent's threats, like threatening mate in four or threatening a Knight fork. It's a useful technique that simulates a mental process that occurs after nearly every move in a game between humans: 'What's the threat?'

The following diagram illustrates the null move at the earliest stage of the game, the start position. It shows the position arising after two possible sequences, both of which use the null move (represented by '--').

1.e4 -- 2.d4 // 1.d4 -- 2.e4

As an added bonus, the diagram shows White's main threat after both 1.e4 and 1.d4, which is to advance the other center Pawn and make a strong central position with plenty of space behind the Pawns to develop the other pieces. After either of those moves, Black's objective is to prevent White from achieving that strong center unhindered. This is the underlying idea behind many of the most common opening variations after either 1.e4 or 1.d4.

As for the last paragraph I quoted from Kasparov's book, it starts 'Humans use a very different heuristic when making plans'. In fact, this type of strategic thinking is also possible using an engine by injecting a series of null moves, thereby preventing the opponent from making any moves at all. Here's an example, again using an engine on the traditional start position:-

1.e4 -- 2.d4 -- 3.Nf3 -- 4.Bd3 -- 5.O-O -- 6.c4 -- 7.Nc3 -- 8.Re1

After that sequence of opening moves, the engine I was using gave White's position a value of +3.00. In other words, White's advantage after eight straight developing moves is nearly the same as the value of a minor piece. With a series of null moves, the engine is helping the human to answer the question, 'What's the plan?'

One concept that applies mainly to engines is called 'Null Move Pruning', which I once covered in Chess Engines : Pruning (September 2015). Even here, the concept is similar to what humans do when they avoid looking at a move because it doesn't address the main threat.

10 December 2018

Kasparov vs. the Early Engines

Last week's post, Defending the Human Race?, about Garry Kasparov's two matches against IBM's Deep Blue computer, reminded me that I had an open follow-up from an earlier post this year: Kasparov vs. Hsu (February 2018). That post compared milestones in the evolution of Deep Blue that are found in both Kasparov's book Deep Thinking and Feng-hsiung Hsu's book Behind Deep Blue. The post closed by saying,

Kasparov's book also gives details about his games/matches against other chess computers. I should compare this to my page Garry Kasparov's TMER.

That cryptic acronym 'TMER' stands for Kasparov's Tournament, Match, and Exhibition Record (1973-; Last updated 2014-08-11), a record of Kasparov's career that I've been maintaining on-and-off since the year 2000. The following chart merges references in Kasparov's book with the corresponding data in the TMER.

The 'LOC' references, like the first one '>>> LOC0038', refer to locations in the Kindle version of the book, which is the version I've been working from. I suppose they can be translated to page numbers in the hardcopy version of the book, but I don't know how to do that easily. For explanations of the other codes in the chart, see the TMER page.

The chart shows that Kasparov's book mentions six events where he played against computers before the two famous matches against Deep Blue. If I find any more references in the book, I'll update this current post. In any case, I'll come back to the chart in another post.

09 December 2018

Puzzle Rush

Our featured November video on this blog was 'The World Is Watching', about the start of game one of the 2018 Carlsen - Caruana match for the World Championship. For the December video, let's skip ahead to the match tiebreak.

Puzzle Rush #1: World Chess Championship edition! (7:47) • 'Published on Nov 27, 2018'

The video from the John Bartholomew channel starts,

This is John! I'm back from London. The tiebreaker for the 2018 World Chess Championship is tomorrow, Wednesday, November 28. I'm very much looking forward to it and I'm sure you are as well. What does that have to do with Puzzle Rush? It's been sweeping the chess community and is a new feature on Chess.com where you try to solve as many puzzles as possible in a five minute spin.

The answer to the question 'What does the World Championship have to do with Puzzle Rush?' lies in the following tweet.

While that idea has as much chance of being realized as having all regulation games in the next WCC match end decisively, we can still dream. For more about the new speed game, see Puzzle Rush - Compete to solve Chess Puzzles (chess.com).

07 December 2018

AlphaZero Is Back!

Ding, ding, ding! As I made my way through this morning's reading list on chess topics, the bells were sounding everywhere. Almost a year to the day after their first shock announcement, Google's Deepmind had just released more news about AlphaZero, by all reports the strongest chess player ever.

The news was propagated via Science magazine -- see Table of Contents : December 07, 2018 (sciencemag.org; cover shown on the left) -- which included three articles by world class authorities on computer chess:-

The description for the cover of Science said,

Starting from random play and given no domain knowledge except the game rules, the AlphaZero program taught itself to play chess, shogi, and Go, defeating a world champion program in each game. Blue translucent pieces represent AlphaZero's possible moves; percentages indicate the predicted outcome. A single algorithm that can master several complex problems is an important step toward creating a general-purpose machine learning system to tackle real-world problems. • Image: DeepMind Technologies Limited

This is too much new material to digest in the time available for a simple blog post, so I'll come back to the subject as soon as I can.

06 December 2018

Breaking the 2800 Barrier

A few months ago I opened Breaking the 2700 Barrier (June 2018), by saying,

No, I'm not talking about achieving a 2700 rating. I'm talking about post no.2700 on this blog.

I continued by discussing the history of chess players rated 2700 or more, then closed the post saying,

To break 2800, all I have to do is write another 100 posts.

Post no.2800 was A Conversation with Demis Hassabis a few weeks ago, but given the flurry of posts on this blog for the 2018 Carlsen - Caruana match that finished last week, I'm only finding spare time now. In a nutshell, the following chart shows the history of players rated 2800 or more.

The first column shows the evolution of top ratings during the second half of the 1980s, taken from the January list for each year. Throughout that period there were only two players rated over 2700, and Garry Kasparov was the first to break the 2800 barrier at the end of that decade.

The second column shows the top players after further intervals of five years: 1995, 2000, and 2005. Kasparov continued to head the list, but the number of 2700 players expanded steadily.

A little 'i' after a player's name means 'inactive'. FIDE hasn't always been consistent with the 'i' flag and Bobby Fischer made a sudden appearance in 2005, perhaps because he was in the news for having been detained in Japan.

A little 'w' means 'woman'. It appears only once on the chart, in 2005, when Judit Polgar made the top-10 list of all players. Note that there are not separate rating systems for men and women. All tournaments, even when restricted to women (where Judit Polgar never participated), are rated using the same methods and criteria.

The last column shows top-10 lists for the current decade: 2010, 2015, and 2018. For the first time we see players other than Kasparov rated over 2800.

I'll be back in another 100 posts to write 'Breaking the 2900 Barrier'. It promises to be a short post.