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.

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.