Saturday, April 1, 2023

Sprouts 2023 Talks

Sprouts 2023 went great today!  Here are my summaries of the talks.

Shikhar Sehgal, "Playing with Money: Using Symmetry and Combinatorial Game Theory to Solve Simplified Versions of Poker"

Shikhar started by explaining the basics of poker, including the betting and bluffing and versions like Five-Card Stud and Texas Hold 'Em.  He then covered the notion of expected values.  Shikhar broke down all steps of poker into different turns, using expecting values in a scoring-game-outcome fashion.  When the tree is collapsed, the result seems to be very similar to a partizan game.

Isaac Attoh: "Positions of High Temperature in Domineering"

Isaac reminded us about the basics of Domineering.  He showed how some positions are cold (integers) and others are hot (switches).  He covered the basics of temperature including cooling.  Isaac showed the Drummond-Cole temperature 2 position and Berlekamp's conjecture that there isn't anything higher in Domineering.  Isaac was able to find new positions of temperature 3/2 and 7/4.  He used Sage Math and CGSuite in tandem to find those positions.  (During the questions, Isaac revealed that he believes the conjecture.)

Melissa Huggan: "The Cheating Robot" (Keynote)

Melissa talked about her simultaneous CGT model where one player has the advantage of being the Cheating Robot: they can see what move the other player is going to make and choose their best possible counter.  This is still different from alternating play for two reasons:

• The game appears to any observer to be being played simultaneously, so draws can occur.
• The ruleset changes from standard normal play due to moves that interfere with each other.

Melissa then applied her model to Toppling Dominoes.  Although single-color rows of dominoes still maintain their integer "values", rows of two single-color components are already complex: the cheating robot's best strategy isn't necessarily to push back on the same row as the other player, even if that position is traditionally the highest-temperature switch!

Melissa then talked about the Cheating Robot outcome classes (L, R, and D for Draw) and notation: {G^L | G^S | G^R} where G^S are the same round options: what can happen when both players play on that same position.  She also covered CR-game trees and conjugates (instead of negatives) and explained that there are still some fundamental terms getting sorted out.

Melissa finished up by applying the Cheating Robot to Cops and Robbers.  For example, she showed that on a strong grid, four cops are needed to capture a robot-robber.

Harpreet Brar: "Sequences of Grundy Values in Node Kayles"

Harpreet talked about the history of Kayles and Node Kayles (AKA the Domination Game) and covered Grundy values and the mex rule with examples with excellent figures.  She explained very clearly how to apply mex to a list of options by going through each of them.  She then showed her calculations for the Grundy values of paths of length up to 21.

Nadia Bautista-Perez: "Sensing an Invisible Robber"

Nadia described the Localization Game, similar to Cops and Robbers, except that the cop (here the "sensor") doesn't know exactly where the robber is.  The sensor does have more power in that they can move to any vertex on their turn.  After they and the robber move, the sensor then learns how far they are from the robber.  Nadia looked specifically at the case of Broom graphs and she showed that the sensor can capture in moves equal to the number of bristles in the broom.

Andrea Morris: "Exploring AI Techniques on Game of Thrones: Hand of the King"

Andrea explained how the board game Hand of the King works.  This is a kind of impartial scoring game, where both players have the same options each turn, but they keep their own scores.  Andrea employed a minimax algorithm which was useful in the last third of the turns.  To help their early moves, she used a Monte Carlo Tree Search.  The best algorithm they found was a hybrid of the MCTS and Minimax approaches.