Berlekamp Memorial Workshop Talks, Day 2

On the second (and final) day of the MSRI workshop, we had more talks, which I've attempted to summarize.  As always, please feel free to comment to correct what I got wrong and add things I didn't include!


Carlos Santos: "A Universal Ruleset"

Carlos reprised a talk about a subject Elwyn really enjoyed: finding a universal ruleset.  I didn't know this before, but this was a topic that Elwyn even inspired when he asked the question: What is the habitat of *2?  This means, which rulesets contain *2?  Even more general: which rulesets contain positions that equal all elements of the Short Conway Group?  Any such ruleset can be called "Universal".

Carlos mentioned multiple different procedural strategies he used to try to find such a ruleset.  Although, he could have come up with a new one, as he reasoned, "If I invent something, I am cheating."  So instead he attempted to use Amazons, Traffic Lights, Konane, then found victory with Generalized Konane, constructing everything in the SCG from that.  He was very happy that Generalized Konane already existed in CGSuite, so he could use it without "cheating".

Afterwards, Carlos spoke briefly about the supposed separation between recreational mathematics and "serious" mathematics, finishing with, "The opposite of fun is not serious."



Svenja Huntemann: "Bounding the Boiling Point"

(Joint work with Carlos Santos and Richard Nowkowski.)

Svenja talked about temperature and "How much urgency is necessary to play at a specific position.  This is the first talk where I really got an education about Thermography and thermographs.  Svenja's work uses thermic versions of hot games--which are games with the same temperature but with only one option for each player. 

This thermic version makes it easier to find bounds on the temperature.  The boiling point, then is the suprenum of temperatures of a class of games.  If we can find bounds on the confusion intervals of games in the class, we can use that to find the boiling point!

Svenja discussed the boiling point of Domineering and Elwyn's conjecture that it is 2.  There is a bunch of work on this, including an example position with temperature 2.  A new result here is that long "snakes" cannot have temperature above 3.



Neil McKay: "Yellow-Brown Hackenbush"

Neil presented work on a topic Elywn had published in GONC3.  Yellow-Brown Hackenbush is different than Blue-Red Hackenbush because players cannot play on components where all the edges are yellow or all the edges are brown.  (The three colors of edges: YeLlow edges are takeable by Left, BRown are takeable by Right, and OlivE are takeable by Everyone.)  I felt very lucky that I could distinguish been the three colors in the slides.  Neil stuck to those three colors to preserve the choices, but admitted that it was hard to see the difference on the actual slides.

Unlike B-R Hackenbush, every Y-B Hackenbush position is dicotic.  Thus, all positions are infinitesimals.

Additionally, if playing a restricted version on stalks (path graphs), there are some cool simplifications you can do.  Neil has done work and solved the outcomes for the game, but not yet for the actual canonical form values.  This is something that Elwyn had left as an open problem.  Neil concluded by listing a bunch of open problems remaining with both Yellow-Brown and Blue-Red Hackenbush.



Richard Nowakowski: "Pic Arête"

Richard spoke about Pic Arête, which is Dots & Boxes without the extra move for completing a box.  Though it's actually played like Strings-and-Coins.  The game was solved on the grid by Meyniel and Roudnoff in 1988.  Richard considered playing on a general graph.  It turns out that a French team (Blanc, Duchêne, and Gravier) solved this in 2006, except for some cases.  Apparently these solutions don't always find the optimal move, but find a move good enough to win anyways.

Richard extended this to say that each edge contains a game instead of a single move to cut it so that the edge doesn't disappear until the game there becomes { | }, or exactly zero.  Then the overall game uses the same scoring mechanism as Strings & Coins.  E.g. edge weight games of +1 and -1 give you a Blue-Red version of Pic Arête.  Richard showed some neat examples with simplications.

"I claim I solved it last night in a dream," Richard said of one of the problems he's looking at.


Mike Fisher: "Beatty Games: Big and Small"

(Joint work with Mike Fraboni, Svenja, Urban, RJN, and Carlos)

Mike talked about Beatty Sequences and Games, and actually found the values for positions using different values of alpha.  He then dove into the atomic weights. As Mike kept saying, a lot of this was just personal exercises he gave to himself to see what was going on.  He found a relationship to the atomic weights and the number of consecutive numbers in the Beatty sequences below the number.

Mike then turned his attention to Octal Games, using the octal codes to describe Beatty games.  These infinite octal codes cause interesting patterns of Grundy values that Mike plotted.  Beyond all this, Mike then took Beatty sequences in another direction, investigating a partizan variant of the Beatty game.  He discovered that Richard, Angela, Urban and other had already explained the Golden-Ratio version, so he looked at values and Reduced Canonical Forms of games based on other "Metallic Ratios", e.g. Silver, and Bronze.  (I didn't know these existed!)


David Wolfe: "Distinguishing Gamblers from Investors at the Blackjack Table"

David finished up the talks with some work back from 2002/2003.  He first started by explaining basic Blackjack strategies, then talked about how card counting can enter into the mix.  Counting perfectly can shift the advantage a player has from -.5% to +.5%  David wanted to try to gauge the skill of a player by watching them play.  He catered to us a bit by asking: "How can we assess the skill of people playing combinatorial games?"  He added that the whole thing could be extended to evaluate anyone working in a competitive "gaming" field.

Since the variance is very high, you need to watch a player for a long time in order to try to evaluate this.  Also, instead of awarding points for the money a player actually earns, you instead credit them for the expected value of each play.  This is then compared to the baseline strategy for the game that doesn't include card counting.  This was a really cool approach!


These talks have been an excellent tribute to Elwyn.  I was exposed to so much more about what he accomplished than I had known existed.  I'm really fortunate that I was able to attend this meeting.  I'm very appreciative to MSRI and all of the organizers, especially Aaron Siegel.

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!

Ten Years Professing

Ten years ago today I moved from Massachusetts to Ohio to teach at Wittenberg University.  I was recently hooded, affianced, and ready for my shiny new job.  I realized quickly that I always needed more time to prepare my teaching materials.  A gentle disillusionment that explained why my professors were always so harried.  Somehow keeping up hadn't been too difficult in grad school when I taught three courses over three semesters (instead of 3-4 courses each semester) and had other grad students to handle my grading. 

In the past ten years, the race-against-the-clock to implement new course materials continues.  Luckily, the payoff in appreciation from students is tremendous.  That positive attention from teaching is a fuel that first lent me it's energy in 2001 as an undergrad.  I realized how much I wanted to teach then, a feeling reaffirmed when I taught in grad school at BU from 2007 to 2009.

Being a good teacher does not require your own creation of course materials, however.  I hope my work is actually reusable.  If just one other person gets a jump start because they don't have to create all their own content, that would be worth all the extra effort to make it accessible.

I can't make everything publicly available, because then students can just copy answers and solutions.  Still, I've got student versions of my lecture notes, a LaTeX package for writing lecture notes, publicly-available course pages (with assignments), an automated Python (3) grader, and a Python-to-Java tutorial. 

Ten years has changed a lot.  I'm divorced, a parent, tenured, and have switched schools twice.  As of today, I'm our department chair at Plymouth State.  (This last bit is definitely not going to help me prepare my course materials.)  I've seen a bunch of different students, but I'm still dedicated to their learning.

I got my copy of Games of No Chance 5, which has my Neighboring Nim paper.  (I'm finally published in a GONC!)  Neighboring Nim was something I proved hard back in July 2009, right after that big move to Ohio at the very start of my career.

Summer Software Engineering Reflections

My summer course just ended last week.  I taught Software Engineering, a senior-level course--which is against-the-norm for the summer.  The class was kept intentionally small because I was ramping up a new project and using the very new style of grading I've been going with since last fall.  (I was working on my own project solution concurrently with the students.)

Without revealing too much to my students this fall, here's the DAG for Project 0:

The basic idea behind this is that students can't get points for completing something until they complete the stuff coming before it.  They get the points by showing off their code to me in meetings.  This both lets them redo stuff if it isn't really finished and breaks up the grading so I don't have to find a block of time to get them all done at once.

I also like this because there are extra parts that are not necessary for moving on that students can do to exercise their creative sides.  I can also let students propose new goals to add to the project DAG, then make that available to everyone in the course.

The summer course went really well!  The projects were all really great, and they were each very different even though we were all working in close proximity.  I just barely finished my own version on the last day of class.  (Pedagogically, this is upsetting; realistically, it's rarely feasible for me to complete all my assignments before the students see them on the first run.  Ten years in and I still can't stay far enough ahead.)  These students did amazing work, despite me lagging behind!

Perhaps most important: this is the first time I got all of the students to really implement OO design patterns.  This crop best knows what's going on here.

It took nine tries to get this course right, but I really hope that this means everything will go smoothly starting this fall with the 10th iteration.  (We'll be doing Photo Albums then too, but hopefully they won't get too much of a jump start from this post.)

My current plan is to have the students program some Combinatorial Games again in the Fall of 2020.

I have really good plans for the lecture notes for this course, but that's a ways down the line.

Sprouts 2019 Talks

Sprouts 2019 was yesterday and we had some excellent talks.  Here are my little summaries of them!


Nick Paolini: "Machine Learning in Combinatorial Games"

Nick gave an intro to Machine Learning as a subcategory of AI, including explaining historic data, models, objective functions, and some optimization.  He described Erik Jarlberg's recent work on Nim  (This explored a question I've been really curious about for years!)  Erik's work found that learning players can figure out how to make correct moves in Nim even when trained on a random player.  Nick also talked about developments with AlphaZero, an AI player for Go, Chess, and Shogi.  Nick then talked about his interest in trying to calculate NimSums via machine learning.


Nathan Mozinski: "Displaying Col Moves Online"

Nate showed the current progress on his senior project: displaying the moves in an active Col game being played between two Java players.  That initial code is code I created for my Data Structures class.  He's modified it to write the state of the game to a text file after each move.  He then added a JavaScript-powered webpage to display that game: https://turing.plymouth.edu/~ncm1003/SP/col/.  Right now it displays the current board, the previous board, and the win-loss records of the two players in the on-going match.


Craig Tennenhouse: "Towards an Impartial Short Tafl Variant"

Craig talked about Hnefetafl and some impartial variants he's been exploring.  In his rulesets, there is a King and one or more soldiers (who may or may not be attempting a coup).  To make it short, the King can only move North and West and the game ends when it cannot move.  The different rulesets are each based on a different rule for the movement of the soldiers.  Surprisingly, even with only one soldier and a ruleset such as "The soldier must move closer to the king", P-positions appear in very unexpected places!  For the rule "The soldier can only move south or east and can't go past the king", Craig seems to have solved for all the P-positions. 

CGTC3 Talks: Day Three

More great talks on the final day of CGTC3!  Here are my summaries.


Tomoaki Abuku: "On Nim-like Games Played on Graphs"

Tomoaki investigated NimG with heaps on the edges.  Fukuyama proved a bunch of results about these in 2003.  Tomoaki's team used groups of independent zero-sum-valued vertices to find new results, including for many bipartite graphs.


Svenja Huntemann: "Enumerating Domineering"

Svenja build off work by Oh and Lee that counted independent sets on grids (accidentally) counting Kayles positions--as well as Col.  By considering each square as falling into one of five categories, Svenja and her team found a formula for the number of positions on an m x n board.  Even more complicated is enumerating the maximal positions--in order to build the polynomials, 3x3 matrices are needed instead of 2x2.


Valentin Gledel: "Maker-Breaker Domination Number"

Valentin and his team extended previous work on the Maker-Breaker Domination game.  In the game, the Dominator tries to build a dominating set while the Staller chooses vertices to exclude.  This new work investigates the number of moves the Dominator needs to win; a pair with each case of each player going first.  They found graphs that work for any pair of numbers!


Ravi Kant Rai: "Optimal Play in Duidoku Game"

Ravi found Duidoku--a two-player game based on Sudoku that I had been playing back in 2011 (though under another name).  Ravi found a set of permutation strategies for the second player to never lose (so either win or draw) from the initial position.  Ravi generalizes this to grids of any size, showing that Player two has the advantage exactly when n is even.


Hironori Kiya: "Two Player Tanhinmin and its Extension"

Kiya introduces Tanhinmin as a combinatorial version of a Japanese card game, Daihinmin.  In this game, players play increasing cards (or pass) until one player has emptied their hand (they then win).  Kiya's team found a linear-time algorithm to determine winnability (assuming the cards are already in sorted order).  Kiya extended this to show that it also works when you add in the 8-cut rule from Daihinmin.


Matt Ferland: "Computational Properties of Slimetrail"

Matt presented work he completed with me while an undergraduate at Plymouth State!  Slimetrail is one of the games used by Ludus in their tournaments all across Portugal.  Matt proved that a generalized version (on graphs) is PSPACE-complete.  Matt showed the gadgets in the reduction from QBF.

CGTC3 Talks: Day Two

The second day of talks at CGTC3 were also excellent!  Here are short summaries.


Yuki Irie: "p-Saturations of Welter's Game and the Irreducible Representations of Symmetric Groups"

Yuki confirmed a long-standing conjecture by Mikio Sato (from the 70's!) stating that Welter's Game is related to the representations of groups.  Yuki made the connection by generalizing Welter's game using p-Saturations.  In these versions, the nimber values can be found via a formula using addition without carry in base p and Young diagrams!


Thane Plambeck: "Shotgun Wedding: EGT & CGT"

Thane showed a new potential method for combining EGT and CGT.  In this, he considers some repeatable economic game where players have a set of options to choose from each round.  The application of CGT comes from adding an alternating-turn game to generate those option sets.  Thane's method of choosing includes switches, creating a first-mover advantage situation.


Alda Carvalho: "Combinatorics of Jenga"

Alda and her team considered perfect play in Jenga as a combinatorial game.  Each row low enough in the tower (meaning, it has at least one full row above it) acts as a *2 component.  The total value is not just a simple sum, however, because blocks are added to the top, revealing a new *2 pile after every three moves.  Alda generalized this concept as Clock Nim, then found nimbers by considering it as a type of subtraction game.


Koki Suetsugu: "On a Wythoff-type Extension of the General Subtraction Game"

Koki and his team defined a variant of Cyclic Nimhoff ("Restricted Cyclic Nimhoff") where you can only take up to some given q sticks from a pile.  Like Cyclic Nimhoff, they found a closed-form expression to find the nimber.  He then generalized this further by defining separate subtraction-style sets for each of single-heap-removal moves.  In this game, the nimber evaluation uses the Grundy evaluation functions of the corresponding subtraction games whenever the Grundy sequence is a p-stair.


Fionn McInerney: "The Orthogonal Colouring Game"

Fionn and his group have worked on some cool scoring games using two copies of a graph.  Players can color vertices on either copy, but must adhere to an additional orthogonality restraint: the ordered pair of colors for any vertex and its copy cannot be repeated.  Each graph "belongs" to a single player, but they can color in either; the score is determined by the number of vertices that get painted in the game.  Fionn shows that Player 2 can always force a tie when there's a strictly-matched involution, but determining whether the involution exists can be NP-hard.


Urban Larsson: "Cumulative Games"

Urban took a different tack with combining EGT and CGT using subtraction games.  Similar to Candy Nim, you keep track of how many total elements you've subtracted, hoping to collect more than your opponents.  Unlike Candy Nim, you ignore who gets to play last; you're just concerned about the total collected.  In this way, Urban's team was able to connect to extensive form games in EGT.  To generalize this for other combinatorial games, a reward function is needed on the moves, along with an outcome function for n-player games.


Melissa Huggan: "The Index: a Measure of Equality"

Melissa delivered an update on her team's progress on simultaneous games.  A lot has happened since I last saw this in Lyon.  Here a game called Subtraction Squares is used, where players remove a number of squares from a strip.  A removal can be made from either end.  If we play a continued conjuctive sum, then the index, I(G), is a pair, (x, y), where x is the probability Left can win with a good mixed strategy and y is the same for Right.  They can then show that equality of games happens exactly when the indices are the same.

CGTC3 Talks: Day One

It's so exciting to be back in Lisbon for CGTC3.  Especially after missing it two years ago.

The first day (Tuesday, January 22) started off with some great talks.  Here are some very brief summaries.


Richard Nowakowski: "What's happening in CGT (since 2010)"

Richard opened the meeting by speaking about new branches of CGT that have appeared this decade.  His survey included explaining Misere and Scoring play, simultaneous moves, ties, placement games, and more.  It was best summarized by his statement: "What did they [BCG] not think about because they didn't need to?"


Antoine Dailly: "Connected Subtraction Games on Graphs"

Antoine described a new game inspired by subtraction games.  CSG(S) is a game on a graph where you may remove k connected vertices from G where k is in S and the resulting graph is still connected.  His team has shown some nice periodicity results when appending paths to an initial graph.


Mike Fisher: "Beatty Games Big and Small"

Mike explained Beatty sequences, then talked about some new Beatty-based games, including two partizan subtraction games, octal games, and even infinite octal games.  The talk name is from these subtraction games: big values occur if the subtraction sets are exactly the Beatty sequences and small values happen if you include 1 to both sets.


Carlos Pereira dos Santos: "Extended CGT"

Carlos considers adding infinity and negative infinity to the set of game options as terminal moves: infinity is an automatic win for left (and vice versa), no matter what else is going on in other parts of a game sum.  (He motivated this by Atari Go.)  He calls these types of game Race Games.


Marc Heinrich: "Partizan Subtraction Games"

Marc and his team made nice progress on partizan subtraction games.  I did not know that outcome classes are periodic here, though values are not always!  Marc showed that the sizes of the sets can be much less important that the size of the numbers in the set.


Bernhard von Stengel: "Computational Progress on the Catch-Up Game"

Bernhard described Catch-Up, a kind of scoring game that doesn't use alternating play; instead, whomever has the LOWER score gets to take the next turn.  Bernhard showed a really cool method he found to solve this for big games, using the representation of prior choices as a binary address for the table of values being generated.