From “readymade” works to surreal hash table wildness in chess programs fooled by him

 Toutfait.com source

Marcel Duchamp was a leading French chess player whose career was sandwiched between two forays into the art world. He played for the French national team in five chess Olympiads from 1924 to 1933. He finished tied for fourth place out of fourteen players in the 1932 French championship.

Today we look afresh at some of his coups in art and chess and find some unexpected depth.

We say “unexpected” because Duchamp was famous for art that consisted of common objects tweaked or thrown together. He called them readymades in English while writing in French. An example is his 1917 Fountain, which Dick and Kathryn saw in Philadelphia last weekend:

 SFMOMA replica, Wikimedia Commons source

Duchamp first submitted this anonymously to a New York exhibition he was helping to organize. When it was refused, he resigned in protest. He then ascribed it to a person named Richard Mutt. Richard means “rich person” in French while “R. Mutt” suggests Armut which is German for “poverty.” A magazine defended the work by saying that whether Mr. Mutt made the fountain—which came from the J.L. Mott Iron Works—has no importance:

He CHOSE it… [and thus] created a new thought for that object.

The new thought led in 2004 to a poll of 500 art professionals voting Fountain “the most influential artwork of the 20th century.” This was ahead of Guernica, Les Demoiselles d’Avignon, The Persistence of Memory, The Dance, Spiral Jetty, just to name a few works of greater creation effort. It was ahead of everything by Alexander Calder or Andy Warhol or math favorite Maurits Escher for that matter. For Duchamp that was quite a coup—which is also French for a move at chess. Fountain is also a kind of coupe—French for “cup” and also snippet or section.

Michelangelo Buonarroti famously declared that “every block of stone has a figure inside it and the sculptor’s task is to discover it.” Dick and I feel most of our peers would disagree with this about sculpture but agree with the same remark applied to mathematics. As Platonists we believe our theorems had proofs in “the book” from the start and that our chipping away at problems is what discovers them.

The paradox is that we nevertheless experience theoretical research as being as creative as Michelangelo’s artwork or Duchamp’s original painting, Nude Descending a Staircase. What accounts for this? We have previously alluded to “builders” versus “solvers” and the imperative of creating good definitions. Builders still need to sense where and when proofs are likely to be available.

Finding a new proof idea is reckoned as the height of creativity despite the idea’s prior existence. This is however rare. Most of us do not invent or re-invent wheels but rather ride wheels we’ve mastered. They may be wheels we learned in school, as pre-fab as Duchamp’s 1913 Bicycle Wheel. The creativity may come from learning to deploy the wheels in a new context:

 David Gómez (c) “Duchamp a Hamburger Bahnhof” source, license (photo unchanged)

## Replicas and Memes

Neither of the works pictured above is the original version. The originals were lost, as were second versions made by Duchamp. Duchamp’s third Bicycle Wheel belongs to MoMA, which is adjacent to Dick and Kathryn’s apartment in Manhattan. The Philadelphia Art Museum has the earliest surviving replica of Fountain, certified by Duchamp as dating to 1950. Duchamp blessed fourteen other replicas in the 1960s.

For contrast, Duchamp spent nine years making the original artwork shown behind the board in this crop of an iconic photo:

 Cropped from Vanity Fair source

The nine-foot high construction between glass panes lives in Philadelphia under its English name The Bride Stripped Bare By Her Bachelors, Even. The “even” translates the French même, which is different from mème meaning “meme.” Richard Dawkins coined the latter term in his 1976 book the Selfish Gene. Modern Internet “memes” diverge from Dawkins’s meaning but amplify his book’s emphasis on replication. Both the isolation of concepts and the replication were anticipated by Duchamp.

A wonderful Matrix Barcelona story has the uncropped photo of Duchamp playing the bared Eve Babitz. It also has a film segment with Duchamp and Man Ray which shows how they viewed the world. Duchamp could paint “retinally” as at left below, but this page explains how his vision of the scene shifted a year later. Then his poster for the 1925 French championship abstracts chess itself:

 Composite of sources collected here

## Duchamp’s Chess

Duchamp’s high-level chess activity stopped before the Second World War broke, but he kept up his interest during it. In 1944-45 he helped organize an exhibition The Visual Imagery of Chess at the Julien Levy gallery in midtown Manhattan. One evening featured a blindfold simultaneous exhibition by the Belgian-American master George Koltanowski:

 Composite of src1, src2

This composite photo with leafy allusions shows left-to-right Levy (standing), artist Frederick Kiesler, Duchamp executing a move called out by Koltanowski (facing away), art historian Alfred Barr, Bauhaus artist Xanti Schawinsky, composer Vittorio Rieti, and the married artists Dorothea Tanning and Max Ernst. Plus someone evidently looking for a new game. My “assisted readymade” skirts the edge of fair use (non-commercial) with modification. The works I combined each have higher creation cost than the objects Duchamp used. Yet there’s no restraint on combining other people’s theorems—of whatever creation cost—with attribution.

Koltanowski kept the seven games entirely in his head, winning six and drawing one, and performed similar feats well into his eighties. Yet Duchamp once beat him in a major tournament—in only 15 moves—when Koltanowski was in his prime and looking at the board.

So how strong was Duchamp? It is hard to tell because Arpad Elo did not create the Elo rating system until the 1950s and because the records of many of Duchamp’s games are lost. Twenty of Duchamp’s tournaments are listed in the omnibus Chessbase compilation but only four have all his games, only four more include as many as five games, and most including the 1923 Belgian Cup lack even the results of his other games. For these eight events, my chess model assesses Duchamp’s “Intrinsic Performance Ratings” (IPRs) as follows:

The error bars are big but the readings are consistent enough to conclude that Duchamp reached the 2000–2100 range but fell short of today’s 2200 Master rank.

My IPRs for historical players have been criticized as too low because today’s players benefit from greater knowledge of the opening, middlegame dynamics, and endgames. My model does not compensate for this—it credits moves that go from brain to board not caring whether preparing with computers at home put them in the brain. However, a comparison with Koltanowski is particularly apt because Elo himself estimated Koltanowski at 2450 based on his play in 1932–1937. My IPR from every available Koltanowski game in those years is 2485 +- 95. When limited to the major—and complete—tournaments that would have most informed Elo’s estimate, it is 2520 +- 100. The latter does much to suggest that Koltanowski might have merited back then the grandmaster title, which he was awarded honoris causa in 1988. Koltanowski had 2380 +- 165 in the year 1929, including his loss to Duchamp.

Still, Duchamp’s multiple IPR readings over 2000 earn him the rank of expert, which few attain. Duchamp gave himself a different title in 1952:

I am still a victim of chess. It has all the beauty of art—and much more.

Duchamp loved the endgame but is only known to have composed one problem. Fitting for Valentine’s Day, he embellished it with a hand-drawn cupid:

 Composite of diagrams from Arena and Toutfait.com source

Yet unrequited love may be the theme, for there is no solution. Analysis by human masters has long determined the game to be drawn with the confidence of a human mathematical proof. All the critical action can be conveyed in one sequence of moves: 1. Rg7+ Kf2 2. Ke4 h4 3. Kd5 h3 4. Kc6 h2 5. Rh7 Kg2 6. Kc7 Rg8 (or 6…Rf8 or …Re8 or even …Rxb7+ if followed by 7. Kxb7 f5!) 7. b8Q Rxb8 8. Kxb8 h1Q (or 8…f5 first) 9. Rxh1 Kxh1 10. Kc7 f5 11. b6 f4 12. b7 f3 13. b8Q f2 14. Qb1+ Kg2 15. Qe4+ Kg1 16. Qg4+ Kh2 17. Qf3 Kg1 18. Qg3+ Kh1! when 19. Qxf2 is stalemate and no more progress can be made.

The cupid and signature were on one side of the program sheet for an art exhibition titled “Through the Big End of the Opera Glass.” The other side had the board diagram, caption, and mirror-image words saying, “Look through from other side against light.” The upshot arrow was meant as a hint to shoot White’s pawns forward. But by making a mirror image of the position instead, I have found the second of two surprising effects.

The first surprise is that when it comes to verifying the draw with today’s chess programs—which are far stronger than any human player—Duchamp’s position splits them wildly. This is without equipping the programs with endgame tables—just their basic search algorithms.

The Houdini 6 program, which has just begun defending its TCEC championship against a field led by past champions Komodo and Stockfish, takes only 10 seconds on my office machine to reach a “drawn” verdict that it never revises. Here is a coupe of its analysis approaching depth 40 ply, meaning a nominal basic search 20 moves ahead. That’s enough to see the final stalemate, so Houdini instead tries to box Black in, but by move 4 we can already see Black’s king squirting out. Its latent threat to White’s pawns knocks White’s advantage down to 0.27 of a pawn, which is almost nada:

Komodo stays with the critical line but churns up hours of thinking time while keeping an over-optimistic value for it:

The just-released version 9 of Stockfish, however, gyrates past depth 30, seemingly settles down like Houdini, but then suddenly goes—and stays—bananas:

When Komodo is given only 32MB hash, it gyrates even more wildly until seeming to settle on a +3.25 or +3.26 value at depths 31–34. Then at depth 35 it balloons up to +6.99 and swoons. After 24 hours it is still on depth 35 and has emitted only two checked-down values of +6.12 and +4.00 at about the 8 and 16 hour points.

Now for the second surprise. The mirror-image position at right above changes absolutely none of the chess logic. But when we input it to Stockfish 9, with 32MB hash, it gives a serene computation:

What’s going on? The upshot is that the mirrored position’s different squares use a different set of keys in a tabulation hashing scheme. They give a different pattern of hash collisions and hence a different computation.

There are two more mirror positions with Black and White interchanged. One is serene (from depth 20 on) but the other blows up at depths 36–40. This is for Stockfish 9 with 32MB hash, “contempt” set to 0, and default settings otherwise. With 512MB hash, both blow up. Since both Stockfish 9 and the Arena chess GUI used to take the data are freely downloadable, anyone can reproduce the above and do more experiments.

There is potential high importance because the large-scale behavior of the hash collisions and search may be sensitive to whether the nearly-50,000 bits making up the hash keys are truly random or pseudorandom. I detailed this and a reproducible “digital butterfly effect” in a post some years ago.

Thus unexpected things happen to computers at high depth in Duchamp’s position. It is not in the Chessbase database, but he may have gotten it “readymade” from playing a game or analyzing one. In all cases we can credit the astuteness of his choosing it.

## Open Problems

What will be Duchamp’s legacy in the 21st Century? Chess players will keep it growing. Buenos Aires (where he traveled to study chess in 1919), Rio de Janeiro, and Montevideo have organized tournaments in his honor. It was my pleasure to monitor the 2018 Copa Marcel Duchamp which finished last week in Montevideo. This involved getting files of the games from arbiter Sabrina de San Vicente, analyzing them using spare capacity on UB’s Center for Computational Research, and generating ready-made statistical reports for her and the tournament staff to view.

Tid-bit: delicacy, dainty, snack, nibble, appetizer, hors d’oeuvre, goody, dipper, finger food

Adam Engst is the publisher of the site TidBITS. This is a site dedicated to technical insights about all aspects of Apple machines: from nano to servers.

Today I want to talk about mathematical tidbits not Apple devices, but look at the above site for information about Apple stuff of all kinds.

Variations on Montgomery’s trick

Peter Montgomery is a cryptographer at Microsoft. Just recently, Joppe Bos and Arjen Lenstra have edited a book titled Topics in Computational Number Theory Inspired by Peter L. Montgomery. The chapters range to Montgomery’s work on elliptic curves, factoring, evaluating polynomials, computing null-spaces of matrices over finite fields, and FFT extensions for algebraic groups. Bos and Lenstra say in their intro that most of this was “inspired by integer factorization, Peter’s main research interest since high school.” Factoring, always factoring…

Today we discuss one of Montgomery’s simpler but most influential ideas going back to a 1985 paper: how to compute mod ${N}$ when you can only do operations mod ${R}$.

An almost exponential improvement in bounds against ACC

 Source from previous paper

Cody Murray is a PhD student of Ryan Williams at MIT. He and Ryan have a new paper that greatly improves Ryan’s separation of nonuniform ${\mathsf{ACC}}$ circuits from uniform nondeterministic time classes. The previous best separation was from ${\mathsf{NEXP}}$, that is, nondeterministic time ${2^{n^{O(1)}}}$. The new one is from ${\mathsf{NQP}}$, which is nondeterministic time ${2^{(\log n)^{O(1)}}}$. The ‘Q’ here means “quasi-polynomial,” not “quantum.”

Today we discuss the new ideas that led to this breakthrough on a previous breakthrough.

Facing the awful truth that computers are physical machines

 As moderator of RSA 2016 panel

Paul Kocher is the lead author on the second of two papers detailing a longstanding class of security vulnerability that was recognized only recently. He is an author on the first paper. Both papers credit his CRYPTO 1996 paper as originating the broad kind of attack that exploits the vulnerability. That paper was titled, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems.” Last week, the world learned that timing attacks can jeopardize entire computing systems, smartphones, the Cloud, everything.

Today we give a high-level view of the Meltdown and Spectre security flaws described in these papers.

With wishes for a memorable New Year 2018

Muhammad Afzal Upal is Chair of the Computing and Information Science Department at Mercyhurst University. He works in machine learning and cognitive science, most specifically making inferences from textual data. In joint papers he has refined a quantitative approach to the idea of postdiction originally suggested by Walter Kintsch in the 1980s.

Today we review some postdictions from 2017 and wish everyone a Happy New Year 2018.