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.
Will DeFroscia: "Plinko Nim"
Will described Plinko Nim, which is a Nim game played on (Binary) trees. Each move has to be on the heap on a leaf of the tree. If a leaf's heap is reduced to zero, the piles above it cascade down all the way to the root, which is removed. The path cases are the same as Tower Nim, but the tree case is not yet solved. Will looked at cases with a simple 3-node tree, and even then the formulas are elusive!
I am so glad we had all these great talks! Thank you to all of these great speakers!
