Berlekamp Memorial Workshop Talks, Day 1

Aaron Siegel: "Elwyn Berlekamp and Combinatorial Game Theory"

Aaron gave an amazing history of Elwyn's 56 years of publishing about games.  As he later mentioned, probably none of us at the workshop would have been in the field if it weren't for him.  This was such a great talk.  Here are some of the things I learned:

• At 10 years old, Elwyn was allowed to play Dots-and-Boxes with his friends in the back of the room during Math class, as he was bored by the lectures.  Thank goodness for understanding teachers!  In 2002, nearly 50 years later, he published a book on Dots-and-Boxes.  In it there are four theorems.  As Aaron summarized, if you only know theorem n and your opponent knows n+1, it's hopeless.
• As an undergrad at MIT, Elwyn wrote one of the first chess-playing programs and published columns about Bridge in the newspaper.  He would later publish about bridge-playing programs.
• He learned about Nim at Bell Labs, where he spent three summers also during college.
• He lost to a Dots-and-Boxes-playing program created by other students, so he learned more about it, then came back and won.
• He worked at Bell Labs again later and wrote a paper connecting Dots and Boxes to Sprague-Grundy theory.  His supervisors challenged him, asking why this was useful.  He wrote a six-page response, which earned him vindication from the VP.
• Winning Ways took a long time to complete.  It began when Elwyn met Richard Guy in North Carolina in 1967.  Elwyn proposed writing the book, and Guy suggested they team up with John Conway.  The three of them met in 1969 at a conference at Oxford.  They spent the next 13 years working on Winning Ways, which was published in 1982.  I really had known nothing of the history of the creation of Winning Ways before this talk!
• Elwyn got into Go in 1988 while working with David Wolfe.  Elwyn created the 9-dan stumping problem, on which he could defeat some of the best Go players as either Black or White.  As David explained, this position was about halfway between a natural endgame and the completely contrived boards that they had worked out a theory for using infinitesimals.
• In 1996, Elwyn started using Coupon Stacks as a way to get a professional opinion on the temperature of a game.
• In 2018, Elwyn published his final paper, this time about Entrepreneurial Chess, which we played at the game.

Elwyn's amazing career spanned multiple fields, but, as Aaron mentioned, "I think games were always what he loved best."



Svenja Huntemann: "Introduction to CGT"

Svenja gave an introduction to CGT to fill an unexpectedly empty slot.  Svenja covered impartial games, outcome classes, and basic partisan notions explained via Domineering: fractions, switches, and infinitesimals.  Her off-the-cuff version of this introduction is better than my planned and practiced version.



Melissa Huggan: "The Cheating Robot"

Melissa talked about work with Richard Nowakowski that continues her great PhD work on simultaneous games.  In the simultaneous positions, what if Right knows what Left is going to do before they both make their move?  (The name is derived from a Rock-Paper-Scissors robot that can cheat and win by very quickly reacting to what the human player does.)

In this cool model, it turns out that Zero is unique!  It can only occur when both players can only move to zero (causing a draw).  There can be other drawing scenarios, but they don't act like Zero when included in sums!  Melissa took a closer look at Topping Dominoes and used this to show some interesting examples and how to play optimally in these scenarios.



Urban Larsson: "The Fragility of Golden Games"

Urban talked about some joint work with Yakov Babichenko on non-combinatorial games where payoffs (0 or 1) are on the leaves of a binary tree.  Players alternate choosing between the two subtrees at each level, so the value of the game is easily decided recursively.  If the payoffs are assigned at random, how often does the overall value change?  If the Pr[leaf payoff is 1] is the golden ratio, then we call this a Golden Game.

Fragility is then based on the Hamming Distance to change the outcome of the game.  It turns out that Golden Games are very fragile, while non-Golden games are more robust.  As Urban pointed out, "Golden Games are special with high probability."  They want to look at some applications to machine learning with an interfering adversary.  E.g. how many pixels need to be changed until a machine can no longer recognize that a photo is of either a dog or a wolf?  How fragile are these algorithms?



I'm definitely looking forward to the Day 2 talks!