Sunday, May 1, 2022

Sprouts 2022: Extra Musings

Sprouts 2022 was awesome!  It was a bit of a bummer to be virtual instead of in person, but there was a bright side to being virtual: we had a bunch of attendees and even talks that we wouldn't have had otherwise!  (We had two attendees from South America!)

Congratulations to our Popping Balloons tournament winners!

  • Craig Tennenhouse won our human tournament.  There were ten participants.  We did four rounds of Swiss, then cut to the top two (Craig and Svenja).  Since one of those two (Svenja) had beaten the other, we decided that Craig would have to win twice in a row in the final to win the whole thing, which he did.
  • Ian Grenville's player, NinePiecesOrLess won the computer tournament as the only participant.
  • NinePiecesOrLess defeated Craig in the "John Henry" match.  Congratulations to Ian Grenville!

Here are some things I learned this year:

  • I need to create a webpage to organize tournaments among humans.
  • "Partizan" vs "Partisan" is not originally a UK English vs American English thing.  Partizan was purposefully chosen for Combinatorial Games because of the political meaning behind partisan.  Partisan may have been accidentally adopted by US gamesters as a misunderstanding.  I guess we have to go update this in the book!
  • We need to manage a mailing list of attendees.  I passed out information to attendees as they signed up, but then didn't email out any reminders as the event drew near.
  • When undergrads are presenting, I think it would be helpful for them to tell their major and year, for context.  We had some great presentations from students outside of Math and CS.
  • I need to figure out how to attract more computer-player submissions.  I'm willing to take any advice on this!  (I know, at least, that we'll need to announce it sooner.)

We don't have any of the details figured out for next year yet.  It may be partially in-person and partially virtual.  No matter what happens, I'm looking forward to future years of Sprouts! 

Thursday, April 28, 2022

Sprouts 2022 Talks, Keynote and Session 2

Svenja Huntemann, Keynote: "Bounding the Boiling Point"

Svenja gave our keynote on Saturday (the first Sprouts keynote ever!) that included an overview of temperature and cooling.  She included hot, tepid and cold games, using switches as a reference.  She then got into thermographs, explaining them from the basics.  She talked about thermic options and confusion intervals, using these to show temperature bounds.

Svenja explained that the boiling point is the supremum of temperatures for a ruleset, then presented Berlekamp's conjecture that the boiling point of Domineering is only 2.  Svenja's team found evidence in this direction, showing that the boiling point of snake-like boards is bounded above by 3.  She explained the difficulties with generalizing this to all boards.


From Session 2:

Vikram Kher, "NP-hardness of a 2D, a 2.5D, and a 3D Puzzle Game"

Vikram talked about the computational complexity of two puzzle-based video games (of the three from his paper).  For both he showed reductions from 3-SAT.  First he showed how to create a Baba Is You board from a 3-SAT formula by using two tokens for each variable.  Next he described the reduction for Fez, which uses rotating rings with the literals implemented as vines for the main character to cling to.


Emma Jones, "Petals"

Emma talked about Petals, a partisan game she created.  A position consists of a ring of petals: Red or Blue.  A turn consists of removing three petals: two of your own color and one of the opponent's right between them.  She found patterns that have value zero as well as some strands that have a variety of other values, including stars, fractions, and Up.


Ian Grenville, "Loopy Game Values"

Ian gave the only talk about Loopy Games.  (This might be the first ever Sprouts talk about loopy games!)  He explained how they work, including the difference between winning and surviving.  He showed some examples of game graphs and the Draw outcome class.  Then he explained the values On, Off, Dud, Over, and Under.  Finally, he talked about how stoppers can be used to simplify analysis, as well as how to deal with some cases where the position isn't a stopper.


This was another great group of talks!

I'll post one more time about other things that came out of Sprouts this year.

Wednesday, April 27, 2022

Sprouts 2022 Talks, Session 1

This past Saturday (April 23, 2022) we held Sprouts for the first time since 2019.  Here's some summaries of the talks from the first session:


Lexi Nash, "Enumerating Distance Games"

Lexi showed how to use a polynomial profile to count the number of positions on a graph with different numbers of colored vertices.  Then she showed how to use Auxiliary Bonds as a better counting method using Cartesian, Strong, and Categorical graph products.  Generating functions can be built from regular expressions of colors of nodes for distance games, and she showed many examples of this technique.


Khoa Bui, "Reinforcement Learning Based Artificial Intelligence"

Khoa talked about Google's AlphaGo player and how he used those characteristics to create an AI to play Ultimate Tic-Tac-Toe.  (This is the game played on a Tic-Tac-Toe board where each of the nine spaces consists of another Tic-Tac-Toe board.  Khoa refers to this kind of recursive game structure as "Stacked".)  He used reinforcement learning combined with a Monte Carlo Tree Search to implement his player.  He wants to apply these techniques to stacked versions of distance games.


Gracie Banning, "Kraken the Numbers!"

Gracie created an impartial game themed around a Kraken attacking people on a row of boats.  Each boat is a Nim Heap, and the Kraken eats from three adjacent piles in the list, taking any triple of this form (floor(k/2), k, floor(k/2)).  She showed values for many three-boat positions and proved that these formulas work by induction.  She also discovered that four-boat positions are zero when all boats have the same size.


Carolyn Curley, "Partisan Peg Solitaire"

Carolyn created a partizan game based off of jumping peg solitaire games.  Players can make jumps in directions based on their identity (Left - Vertical, Right- Horizontal).  She solved on and two-row positions by hand, as well as the 3x3 grid, where she found Up and Down values!  She investigated a bunch of 3x3 sub-boards, as well as what happens when they are surrounded by extra holes.  She looked at many other cases as well.


These were all great talks!  I'm really amazed at what great work undergraduates do in CGT.

The next post will cover the Keynote talk as well as the talks from Session 2.

Sunday, December 19, 2021

Using Spinoza with Python Objects (For in-class exercises)

During the COVID-19 pandemic, I started using Spinoza (https://spinoza.cs.brandeis.edu/) in Intro Programming.  Spinoza lets students try out solving problems in Python.  They get immediate feedback and there's lots of additional pedagogical features.

It uses Brython to run the code.  When it loads each page, parameters for functions are passed as strings.  If you try to create the objects in the Test Generator box, they won't pass correctly when Spinoza executes the tests.  Instead, you have to generate them using additional code that you put in the Solution box.  For example, if you're asking students to write a get_height() method or function for a Monkey class, you have to set things up this way:

  • Use a different name in the Method Name field.  I always just append "_wrapper" to the end.  (E.g. get_height_wrapper.)

  • For the number of parameters, use the total number of primitives you'll need to create any objects for the subject and all parameters.

  • Still put the original function/method header in the scaffolding box.  E.g. def get_height():  If they're writing a method, put it inside the class.  If there are other methods they'll need (__init__ or __str__) then you can include those here too.

class Monkey(object):

    '''Models a monkey.  Attributes: age, height, num_bananas.'''

    def get_height(self):

 

  • In the solution box, there are a bunch of additional things to do:

    • Add a function that creates an instance of the object:

def create_monkey(age, height, num_bananas):

    monkey = Monkey()

    monkey.age = age

    monkey.height = height

    monkey.num_bananas = bananas

    return monkey 

(This will change a lot if they've already created an __init__ and you include that in the scaffolding.)
    • If you didn't create the class above, create it here.  Also include any other classes you might need that you didn't put in the scaffolding.

    • Add the definition of the wrapper.  It should create the objects, then call the function/method that the student is writing.

def get_height_wrapper(age, height, num_bananas):

    monkey = create_monkey(age, height, num_bananas)

    return monkey.get_height()

    • Add your correct version of the requested function.  (E.g. my_get_height().)  If they're writing a method, you'll have to write this as a function instead.

def my_get_height(monkey):

    return monkey.height

    • Add the solution function, which does the same thing as the wrapper, except that it calls your function instead of the student's.

def solution(age, height, num_bananas):

    monkey = create_monkey(age, height, num_bananas)

    return my_get_height(monkey)


It took me a long time to get this working back in 2020, so I hope this is helpful for other people that want to use Spinoza!

Wednesday, August 25, 2021

A CGT Book for Undergrad Math Beginners

Craig Tennenhouse and I have finished the first version of our CGT book.  Here is the book's homepage.  We designed it to be used by undergraduates who may or may not be math majors.  That meant that we needed to include many discrete math concepts as well, to the point where Craig is currently using the text in his Discrete Math class as well.

I wanted this project to be a sabbatical project as early as eight years ago, in the spring of 2013, before I knew when my first sabbatical would be.  At that time I was teaching my third CGT course at Wittenberg University.  All three had been different: the first was as a Math/CS elective, the second was as a first-year college seminar course, and this third time was as an honors course for students with any major.  It was during this third time that I realized I wanted my own thorough notes with lots of exercises in them.  

I actually had some experience with text book exercises.  Nearly a decade prior, I worked with Otto Bretscher on the solution manual for his Linear Algebra text.  I wanted to have a similar large quantity of exercises so students could practice applying the concepts in a structured way.

I met Craig in the fall of 2013, and we have collaborated here and there since.  I had switched schools, which meant my future first sabbatical was far waylaid.  I got my feet under me at a new university, then, just a few years ago, I mentioned that I wanted to write my own book at a CGT event.  I explained that I wanted something at a bit lower level that would be more appropriate for general undergrads.  Craig asked whether we could write it together, which I was definitely on board with.  We both wanted a freely-downloadable book and I was excited to try and adapt my student/instructor dual mode LaTeX code so we could hide some of the exercise solutions.  (At this point, I don't think Craig realized just how many exercises I wanted to write.)

In the summer of 2019, we met and came up with a good outline.  Craig and I were on board with each others' ideas, such as doing impartial games before partisan, so things went very smoothly.  I used that outline in my sabbatical proposal for the spring semester of 2021.  That got accepted, then COVID-19 hit and Craig and I had to collaborate via video calls instead of in person.  (Our universities are about a 2 hour drive apart.)  We started writing in January, and we just finished enough for our first release. 

The result is a text book appropriate for either Discrete Math or Games.  For students who already know the introductory discrete topics, it's easy to skip those sections (laid out as Math Diversions).  There are over 400 exercises in the text, and about half of those have solutions in the back.  There are also some "Computational Corner" pieces with programming examples in Python.  

We aren't done.  We expect to make a bunch of updates as we improve things (and find errors).  The book will continue to get updated on the webpage.  The chaos of the pandemic caused a bunch of delays, so there are definitely many topics we didn't flesh out as much as we wanted.  Nevertheless, we are both very excited and look forward to hearing feedback from teachers, students, self-learners, and even people who just take a quick glance at the PDF.  We have a space in the book to thank contributors who point out errors we need to fix.  All kinds of feedback are very valuable!

I want to give an extra ``Thank You!'' to Craig, without whom this project would never have been completed.  I am so excited that we managed to get this done!

Please feel free to use the comments section here as one avenue to leave us feedback.

Wednesday, October 23, 2019

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.

Tuesday, October 22, 2019

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!