11 December 2017

Houdini, Komodo, Stockfish, and AlphaZero

Last week's report on TCEC Season 10, Engine-to-engine, Head-to-head, finished with a prediction:-

The engines are slugging it out as I write this and have finished 80 games out of the 100 scheduled for the event. Houdini leads [Komodo] with a score of +13-7=60, meaning that we can project a final score of something like +16-9=75. I'll come back to the event when it's over.

With the score at +14-9=73 after 96 games, Houdini was declared the winner; Houdini is TCEC Season 10 champion! (chessdom.com):-

With its gold medal Houdini becomes the engine with most titles in TCEC history. Robert Houdart shared, "I’ve worked non-stop for the past two years to bring Houdini back to the top level, and I’m really happy that this has resulted in a new TCEC title, which is the equivalent of World Champion status."

Houdini won one more game to achieve a final score of +15-9=76. The match was punctuated by two events. The first was a technical problem; Houdini with a six point lead near the halfway point of TCEC:-

Komodo Team Reports Compiler Glitch – Version Update Rejected [...] At the beginning of the Superfinal many noticed that Komodo’s speed (in nodes per second) was lower than previously seen. Tournament director Anton Mihailov, with the help of the server administrator Martin Thoresen, double- and triple-checked that the engine was installed correctly. The details were sent to the Komodo team and everyone agreed there was no problem during the Superfinal setup.

Statement by team Komodo [...] In summary, there is indeed a slowdown in the version now running in TCEC, which appears to be due to a compiler bug.

In a software development chain, the compiler is the tool that translates the high-level code that the developer writes into the low-level code that the processor understands. The Komodo team asked to submit a substitute executable, but the request was rejected by Houdart and Mihailov. TCEC openings for all games of the superfinal were announced in advance and any new version of an engine introduced mid-match might conceivably take advantage of this knowledge.

The second event, external to the TCEC, was the publication of a paper by Google's DeepMind titled, 'Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm'. The paper appeared a few days before the TCEC's close, when the winner was nearly certain. Its abstract said,

The game of chess is the most widely-studied domain in the history of artificial intelligence. The strongest programs are based on a combination of sophisticated search techniques, domain-specific adaptations, and handcrafted evaluation functions that have been refined by human experts over several decades. In contrast, the AlphaGo Zero program recently achieved superhuman performance in the game of Go, by tabula rasa reinforcement learning from games of self-play.

In this paper, we generalise this approach into a single AlphaZero algorithm that can achieve, tabula rasa, superhuman performance in many challenging domains. Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved within 24 hours a superhuman level of play in the games of chess and shogi (Japanese chess) as well as Go, and convincingly defeated a world-champion program in each case.

The phrase 'tabula rasa' can be understood as 'blank slate'. In Tabula rasa, Wikipedia says,

Tabula rasa refers to the epistemological idea that individuals are born without built-in mental content and that therefore all knowledge comes from experience or perception.

In other words, starting with only the rules of chess, AlphaZero progressed in a few hours of computational time to a level where it 'convincingly defeated a world-champion program'. For chess, its opponent was '2016 TCEC world-champion program Stockfish' (TCEC season 9). In the season 10 semifinal, Stockfish finished a half point behind the two eventual finalists. Informed observers consider the three engines to be of approximately equal strength, comfortably ahead of the competition. The DeepMind paper continued,

We evaluated the fully trained instances of AlphaZero against Stockfish, Elmo and the previous version of AlphaGo Zero (trained for 3 days) in chess, shogi and Go respectively, playing 100 game matches at tournament time controls of one minute per move. AlphaZero and the previous AlphaGo Zero used a single machine with 4 TPUs. Stockfish and Elmo played at their strongest skill level using 64 threads and a hash size of 1GB. AlphaZero convincingly defeated all opponents, losing zero games to Stockfish and eight games to Elmo (see Supplementary Material for several example games), as well as defeating the previous version of AlphaGo Zero.

We can quibble about whether the AlphaZero - Stockfish match was indeed a fair fight -- 1 GB hash size is a severe restriction -- but the final score of +28-0=72 for AlphaZero was more than convincing to all but the most vehement skeptics. The new TCEC champion expressed his thoughts just after the TCEC finished; Interview with Robert Houdart, author of the champion engine Houdini (chessdom.com):-

Q: AlphaZero just defeated last year’s champion Stockfish 8. Your opinion on the paper published and the match that took place?

A: It’s fascinating and amazing, and at the same time very much expected! We even discussed this during the interview with Nelson and the Komodo authors. It opens entirely new, astonishing possibilities for chess engines! I do hope Google will publish more details about their approach, so that the chess world in general and the computer chess world in particular can benefit from their achievement.

Q: Now that Houdini is the reigning champion, would you issue a challenge for AlphaZero? Under what conditions?

A: It’s normally up to the challenger to issue a challenge, not the reigning champion :) A big discussion point about a possible match between a "normal" engine and AlphaZero would be the hardware to use -- how can you make sure that hardware is comparable? If I can run Houdini on 2000 cores it will be a lot stronger than when running on 64 cores. That said, I’m not sure how Google is viewing their project -- is it a research/marketing project (like Deep Blue was for IBM), or do they intend to use AlphaZero competitively or as an analysis engine available to the general public?

The 'interview with Nelson [Hernandez] and the Komodo authors', which appeared two weeks before the end of season 10 was Interview with Robert Houdart, Mark Lefler and GM Larry Kaufman (chessdom.com). Now that the TCEC event has finished, I would like to look a little more at the technology behind AlphaZero. I started with yesterday's post Giraffe and AlphaZero, which included a link to the DeepMind paper, and will spend the next few Mondays following up.

10 December 2017

Giraffe and AlphaZero

Start with the sociology of chess, last seen two weeks ago in FIDE's Social Commissions 2017, and add artificial intelligence, as in the previous post, A New Style of Chess, about Google/DeepMind’s AlphaZero. What have you got? I didn't know, so I asked Google.

The first answer it gave me (in fact, the first three answers) was a paper by Nathan Ensmenger: Is chess the drosophila of artificial intelligence? A social history of an algorithm. (ncbi.nlm.nih.gov/pubmed; February 2012):-

Abstract: Since the mid 1960s, researchers in computer science have famously referred to chess as the 'drosophila' of artificial intelligence (AI). What they seem to mean by this is that chess, like the common fruit fly, is an accessible, familiar, and relatively simple experimental technology that nonetheless can be used productively to produce valid knowledge about other, more complex systems. But for historians of science and technology, the analogy between chess and drosophila assumes a larger significance.

As Robert Kohler has ably described, the decision to adopt drosophila as the organism of choice for genetics research had far-reaching implications for the development of 20th century biology. In a similar manner, the decision to focus on chess as the measure of both human and computer intelligence had important and unintended consequences for AI research.

This paper explores the emergence of chess as an experimental technology, its significance in the developing research practices of the AI community, and the unique ways in which the decision to focus on chess shaped the program of AI research in the decade of the 1970s. More broadly, it attempts to open up the virtual black box of computer software -- and of computer games in particular -- to the scrutiny of historical and sociological analysis.

A little further down the list of Google's results was An AI computer learned how to beat almost anyone at chess in 72 hours (qz.com; September 2015):-

Matthew Lai, a computer scientist at University College London, recently published his master’s thesis, which demonstrated a machine learning system -- called Giraffe, after this cartoon about evolution -- that can learn to play at the International Master level of chess in just 72 hours. According to MIT Technology Review, Lai’s machine is a deep neural network -- a computer system that’s inspired by the structure of the brain and attempts to learn and make decisions in a similar way. According to Lai’s paper, Giraffe performs "moderately better" than contemporary computer programs that analyze every possible move at once, as opposed to the few that might actually lead to success.

Matthew Lai and Giraffe. Where have we seen those names recently? They were in the paper that announced AlphaZero to the world: Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (PDF). Matthew Lai was listed as one of the 13 authors of the paper and received a mention in the references:-

Matthew Lai. Giraffe: Using deep reinforcement learning to play chess. Master’s thesis, Imperial College London, 2015.

Giraffe was mentioned again in the section titled 'PriorWork on Computer Chess and Shogi':-

Giraffe evaluated positions by a neural network that included mobility maps and attack and defend maps describing the lowest valued attacker and defender of each square. It was trained by self-play using TD(leaf), also reaching a standard of play comparable to international masters.

Looks like we're on the right track:-

Chess + Sociology + AI => Matthew Lai + Giraffe => AlphaZero

Where to take the subject from here? That will have to wait for another post.

08 December 2017

A New Style of Chess

Historical moments in chess are few and far between. Here are a half dozen events from the past 50 years that made a big impression on me. Almost all were World Championship matches.

Add to these significant career events in the lives of the greatest players.

  • 2005 Kasparov retires
  • 2008 Fischer dies

Twenty years ago, chess engines started to take over as the best players.

This week we learned of another historical event.

  • 2017 Google's AlphaZero - Stockfish

One of the best known chess channels on Youtube is Agadmator's. Of the five games he analyzed from the match, here's his first.

Google Deep Mind AI Alpha Zero Devours Stockfish (13:22) • 'Published on Dec 6, 2017'

Although it's still too early to measure the impact of AlphaZero's accomplishment on the future of chess, it will be profound. Earlier this year, in another episode of Video Friday, we saw Kasparov with DeepMind’s CEO Demis Hassabis: Kasparov Talks at Google (June 2017). There will certainly be more discussions to come.

07 December 2017

1959 Yugoslavia Candidates

With the last two editions of 'Top eBay Chess Items by Price' dominated by big-ticket auctions from Sotheby’s -- A Six-Figure Chess Item at Auction and A Chess Painting and a Namesake -- I haven't had the chance to feature any of the lesser auctions. The item shown below would have made the cut on any average eBay day for 'Top Chess Items'. Titled 'Chess book signed by eight masters, incl. Fischer, Keres, Petrosian, Smyslov and Tal', it sold for around $1500, 'Best offer accepted'.

Top row: Keres, Petrosian, Smyslov, Gligoric
Bottom row: Fischer, Olafsson, Benko, Tal

The description said,

A chess book signed by Benko, Fischer, Gligoric, Keres, Olafsson, Petrosian, Smyslov and Tal: "Kandidatenturnier für Schachweltmeisterschaft" by S. Gligoric and V. Ragozin/Ragosin (Belgrade, 1960). In German. A 320-page hardback in good condition, although the cover is worn (especially on the corners).

The eight participants in the world championship candidates' tournament in Bled, Zagreb and Belgrade all signed this book on the event. Fischer signed it on the front fly-leaf (which also has the name and address of a previous owner, Alan Benson, whose signed book label is on the inside front cover). The book has eight full-page photographs of the participants, and Benko, Gligoric, Keres, Olafsson, Petrosian, Smyslov and Tal -- though not Fischer -- signed their respective photographs (the pages of which already featured a printed signature). Tal signed the book a second time, on page 153, at the end of a combinational win against Fischer

Ignoring the autographs, several of the photos are well known on their own, e.g. Fischer and Tal, and it's useful to know their source. The wall boards are the same in the background of five photos, indicating that they were taken at the same time. For more about the tournament, see 1959 Yugoslavia Candidates Tournament.

05 December 2017

December 1967 'On the Cover'

For the first time since I started this 'On the Cover' series in 2014, the December edition does not feature a scene reminding us of the year end holidays.

Left: 'Interzonal Qualifiers'
Right: 'Manhattan Chess Club President'

Chess Life

The following players have emerged from the Interzonal Tournament at Sousse, Tunisia, just completed, as those who will join Spassky and Tal (already seeded) in a series of matches to determine which of them will play Tigran Petrosian for the World Championship. Reshevsky, Stein and Hort, who finished with identical scores, will participate in a playoff in February to determine the sixth qualifier. A full report follows soon.

That full report will recount a dark moment in American chess. My page on the tournament, 1967 Sousse Interzonal Tournament ('Sousse, X-XI, 1967'), says, '[Bobby] Fischer withdrew while leading the tournament after playing ten games of his schedule.' The event was, however, a bright moment in Bent Larsen's career. The 'Doughty Dane', who was featured on the CR side of the November 1967 'On the Cover', finished first with a score of +13-3=5.

Chess Review

On the cover this month is Manhattan Chess Club President Jacques Coe. His speech on the 90th anniversary of the club appeared [in November].

That speech started,

In the summer of 1877, while people were still talking about whether Hayes or Tilden should have been President, and the Civil War was fresher in memory than World War II is for us, the Manhattan Chess Club was born.

Its members met at the Cafe Logeling, 49 Bowery, between Bayard and Canal Streets, where over their beards they drank lager beer, and under their beards they played chess. The proprietor, Mr. Logeling, kept on hand one of the greatest selections of German, American, English and French newspapers. He was also a chess enthusiast, and eventually built a room over the garden at the back of the cafe which was set aside for the players.

The rest of the speech, which covered nearly a full CR page, was a recap of the club's New York residences. A query on this blog (see the search box in the right column) reveals its importance to the history of American chess.

04 December 2017

Engine-to-engine, Head-to-head

Let's wrap up the series on Engine Trouble (September 2017; 'investigate what sort of engine setup I would need to improve my [chess960] result'), last seen in Improve Engine Software - Tablebases, and look at a couple of engine-to-engine tournaments -- a veteran and a newcomer -- that were taking place in parallel with the series. In the few months since I posted about the veteran, TCEC Season 10 Kickoff (September 2017; 'Top Chess Engine Championship'), the competition has reached the final stage.

2017-11-20: Komodo – Houdini is the Superfinal of TCEC Season 10 • 'Komodo and Houdini are the two finalists in this years edition of the premier event for computer chess. The two engines finished top of the table at the Candidates stage with equal score 18.5/28, half a point ahead of Stockfish.'

The engines are slugging it out as I write this and have finished 80 games out of the 100 scheduled for the event. Houdini leads with a score of +13-7=60, meaning that we can project a final score of something like +16-9=75. I'll come back to the event when it's over.

The newcomer was Chess.com's Computer Chess Championship. The announcement, preliminary results and, final results are all stuffed into a single article, which first appeared in September, but carries the date of its last update:-

2017-11-16: Chess.com Announces Computer Chess Championship, 'Updated With Results' (chess.com) • 'The world's strongest computer engines will compete in a first-of-its-kind speed chess tournament on Chess.com this November, the site announced today. As computer engines have claimed the undisputed title as the best chess-playing entities on earth, interest in the machines has risen among chess fans. The first annual Chess.com Computer Chess Championship (CCCC) will decide which engine is the best at the format of chess most played online: speed chess.'

Chess.com navigation has always been unusual. For this event, if you want to understand it chronologically, you first have to scroll to the bottom of the page then work your way back up, instead of reading the article from top to bottom.

The Computer Chess Championship is scheduled for Nov. 13-16, with all four days featuring full live coverage on Chess.com/TV with master commentary and high production values to promote computer chess as a fun viewing experience for the modern gaming audience. The top-two scoring engines in the round-robin will face each other in a thrilling super-final, where time controls will transition from rapid to blitz and finally to bullet chess as the match proceeds. Chess.com will provide four days of live coverage with master commentary, broadcasting all 90 games of the round-robin and all 20 games of the super-final.

According to Norm Schmidt, the author of the computer engine Fire and Chess.com's advisor for computer chess, the technical details for the tournament are below. The tournament will be run from an Amazon Web Services server farm located in Northern Virginia. Each engine will utilize its own dedicated AWS virtualized instance of a hyperthreaded Intel Xeon E5-2666 v3 2.90 GHz (two processors each with 18 cores) with 60.0 GB RAM running on Windows Server 2016 Data Center Edition.

That 'announcement' includes coverage of the event's two stages: Round Robin Crosstable & Final Standings, plus Superfinal Crosstable. Those results are also summarized in classic top to bottom reporting in a follow-up piece.

2017-11-18: Stockfish Wins Chess.com Computer Championship (chess.com) • 'The powerful, open-source chess engine Stockfish narrowly beat out two strong commercial engines to win the first Chess.com Computer Chess Championship this week. Stockfish placed clear first in the 10-engine round robin to reach the superfinal, and then edged the second-place Houdini in the rapid, blitz, and bullet finals to win the championship.'

The entire event is summarized in a series of live shows, now available on Chess.com's Youtube channel under the title 'Computer Chess Championship':-

One of these days I hope someone explains to me the difference between a superfinal and a final. In the meantime, I'll continue to admire the likes of Houdini, Komodo, and Stockfish as they go head-to-head in the chess version of core wars.

03 December 2017

A Chess Painting and a Namesake

Two weeks ago, in the previous edition of Top eBay Chess Items by Price, we saw A Six-Figure Chess Item at Auction, featuring a Sotheby’s live auction for 'Marcel Duchamp : Pocket Chess Set'.

After a starting price of US $160.000, the auction lasted two minutes, with the bid rising by increments of $10.000 every ten seconds or so. The winning bid was $340.000 after 13 bids.

By some odd coincidence, this edition of 'Top eBay Chess Items' also features a Sotheby’s live auction for a six-figure painting. The item pictured below was titled 'Edwin Lord Weeks : A Game of Chess', and sold for US $110.000 after 20 bids. Although the item had a starting price of $40.000, the first four bids were under that amount. Once the bidding reached $50,000, the price climbed in increments of $5.000.

The description informed,

After years of travel through Europe, North Africa, the Middle East and India, the American artist Edwin Lord Weeks remained captivated by the sights he encountered abroad. Toward the end of his career he began an ambitious series of paintings based on A Thousand and One Nights.

Having documented his travels through sketches, paintings and photographs, Weeks was well equipped with the source material for the present scene, and was careful to render the architecture, complete with its delicately carved stone latticework, as well as the costumes of the two figures. The lounging woman is swathed in elaborately embroidered silks, reminiscent of the Nautch dancing girls whom Weeks had painted in India.

For the complete description, see the Sotheby’s page, weeks, edwin lord; a game of chess. There we learn that the painting was part of an auction for European Art that took place on 21 November 2017 in New York, that its estimate was 50.000-70.000 USD, that the lot sold for '137.500 USD (Hammer Price with Buyer's Premium)', and that the work is an oil on canvas (55 1/4 by 73 1/4 in., 140.3 by 186.1 cm).

Is Edwin Lord Weeks a distant relative? Wikipedia has a page Edwin Lord Weeks, that says,

Weeks was born in Boston, Massachusetts in 1849. His parents were affluent spice and tea merchants from Newton, a suburb of Boston, and as such they were able to finance their son's youthful interest in painting and travelling. As a young man Weeks visited the Florida Keys to draw, and also travelled to Surinam in South America.

The page also mentions, 'In 1872 Weeks relocated to Paris, becoming a pupil of Léon Bonnat and Jean-Léon Gérôme.' The painter Gérôme executed two well known works of caissart titled 'Arnauts playing chess' and 'Almehs playing chess in a cafe', although I'm not convinced that the game pictured in both is indeed chess. A work similar in composition to those two is 'A game of chess in a Cairo street' by Weeks.


Later: Re the sentence 'Although the item had a starting price of $40.000, the first four bids were under that amount', a note at the top of the eBay page says, 'Live auction bidding may start higher or lower'. I assume this means 'higher or lower than the starting price'. A link at the bottom of the page leads to: How live auctions work (at Sotheby’s).