Yesterday was Sprouts 2025. In the afternoon session, we had our keynote by Matt Ferland of Dickinson College and six student talks. Here are my (likely lacking) summaries of those talks.
Matt Ferland, Keynote: "Supernim is Much Harder than Nim"
Matt covered the Nim basics, then talked about superstars: games where all options are to nimbers. Supernim is, then, the ruleset of any sums of superstars. Matt talked about reductions to help relate computational problems. (He described this using curing cancer to show the potential impossibility of solving hard problems.) Matt covered NP and 3-SAT, then looked for a relationship from those to Supernim. Unfortunately, an attempt at XORSAT did not yield a reduction. Matt then described MXOR: Multi-state XOR, where variables can have one of many values instead of just boolean. Then the literals each indicate for which of those assigned values they will evaluate to true. Matt showed that MXOR is NP-hard, then showed the subset of Supernim positions and the reduction of MXOR to Supernim.
Nakul Srikanth: "GamesmanROS - A Generalized Game Playing Robotics Software Stack"
Nakul talked about his work with GamesCrafters, a long term (25+ years) project run by Dan Garcia at UC Berkeley. Nakul's contribution has been to incorporate robotics into their automated players. He talked about the physical constraints they deal with in general and then for specific rulesets. He showed how the robots use string representations of positions to perform some of the logic. Different types of games (Placement vs Capture) present different problems that they need to overcome. He showed a great demo of it in action!
Jake Andersen & Cam Jefferys: "Developing Online Martian Chess"
Jake and Cam talked about creating a playable JavaScript Martian Chess program. They described Martian Chess, a scoring game where control of the pieces changed hand depending on which side of the board they're on. They showed the rules using screenshots, then did a quick demo. They talked about how they trained a neural net player by reimplementing the game in python, then ported the model back to JavaScript. They gave a high-level description of how the player model works.
Ethan Saunders: "Paintbucket and Paintbucket on Graphs"
Ethan talked about a partizan flood-fill game called Paintbucket. The game started from being played among Dalhousie students using MSPaint. Each turn you use the flood fill tool on a black-and-white image to change one contiguous color of your opponent's to your own. He then talked about the generalization on graphs. He was able to show that this version is PSPACE-complete. One cool part about this presentation is that he used MSPaint to give the talk!
Caleb Aukeman: "Partial Jenga"
Caleb continued research from a previous study of Jenga by looking at a partizan version where the blocks are colored Blue and Red. He talked about conditions for when layers are unplayable based on which blocks are missing. He also categorized levels based on which blocks were red and blue. (He had great graphics in his talk!) He found switches with heat of 1/2 and showed families of positions that are in P.
Brendan Whitmire: "Gomoku in JavaScript"
Brendan talked about his JavaScript implementation of Gomoku. He showed that he added the Pie Rule to his program, which took some tricky coding in the JS framework he is working with. He talked about the AI "Evolved Player" he's creating. He generated it by pitting the players against each other using an evolutionary learning algorithm using the Python NEAT library.
Brenden Gray: "Cops and a Destructive Robber"
Brenden talked about his work on a pursuit-evasion game on graphs. His is a variant of Cops and Robbers where the Robber damages the vertex they start their turn on. The cop's goal is to minimize the number of damaged vertices, with a secondary goal of capturing the robber. (Damaged vertices do not prevent movement by either player.) This can change the strategy from the original version because the cop may be content to not capture the robber if it will drop the amount of damage. He showed a graph where the cop's best strategy is to stand still.
No comments:
Post a Comment