Sprouts 2024 was on Saturday, and it was excellent! Here are my summaries of the talks:
Pritika Raj, "Red-Blue Hackenbush and the Construction of Real Numbers"
Pritika covered the basics of Hackenbush and showed how to create integers from mono-colored stalks: path graphs with one end on the ground. Then she got to dyadic rationals, and showed that they can also all be created from finite stalks. After that, Pritika explained how to use infinite stalks to create non-dyadic-rational real numbers. For example, she showed that 2/3 is equal to an alternating Blue/Red/Blue/Red/... infinite path from the ground.
Vivaan Daga, "Nim and Base 2"
Vivaan explained the rules of Nim and gave a good example of a playthrough. He showed how to use the binary XOR to figure out the outcome class of a position. Then he got into the details of the proof that XOR works. Vivaan explained that binary is the important operation because, due to the mex rule, Grundy values are as small as they can be.
Keynote: Mike Fisher, "Octal Games: Old and New"
Mike introduced impartial games and the basis of Sprague-Grundy theory. Then he explained the rules of Kayles and showed the table of the first 84 Kayles values. He showed the same with Dawson's Chess, explaining the rules and giving a table of values that showed the periodicity. Then he covered Treblecross in the same way, but showed a graph of the Grundy values, since it's unknown whether the Grundy values are periodic.
Mike then explained the coding of octal games. Each game is represented as d0.d1d2d3d4... with d0 = 0 or 4, and all other di being between 0 and 7 (inclusive). Each digit di is the sum of up to three components:
- 1 if you can remove i when the pile has exactly i,
- 2 if you can remove i when the pile has more than i, and
- 4 if you can remove i and split the remaining items into two piles, when the pile has more than i+1
Mike showed that Kayles is 0.77, Dawson's Chess is 0.137, Treblecross is 0.007, and Nim is 0.3333... He then showed off Achim Flammenkamp page of known octal game properties.
He continued by describing Wythoff's Nim, Beatty Sequences, and the Golden Mean, then explained what the Silver and Bronze means are. He used that to lead into the three octal games he created from sequences based on each of these means. The Olympic Games, as they are known: The Golden Game, the Silver Game, and the Bronze Game. Mike ended with a new result to me: the Plastic Game, based on the plastic sequence, which is generated by Van der Laan numbers.
Ethan Saunders, "Misère Cricket Pitch"
Ethan explained Cricket Pitch, themed around a bumpy field that must be leveled out by a huge roller. The game is described by a list of non-negative integers with the roller inserted somewhere. A move consists of moving the roller in your direction (left/right) over as many piles as you want, but you can't cross a zero-sized pile. Every pile you roll over in your turn gets decremented. Ethan showed how to calculate some basic games, then used this to discuss group representations.
Sean Pye, "Fighting Fires on Infinite Grids"
Sean researched the fire-fighting problem on graphs: where fires break out on vertices then fire fighters are sent to defend them. The fire fighters prevent the vertices they visit from burning as the fire spreads out from its initial location each round. Sean studied solutions on hexagonal grids and strong grids. He showed the known strategies for hexgrids that use only 2 firefighters to contain a fire and that strong grids need only 4 firefighters.
Devan Burke, "Reinforcement Learning with Super Mario Bros."
Devan talked about how he worked towards training an AI player to beat level 1-1 of Super Mario Bros. He talked about the formulas he used to reward the AI player using reinforcement learning. He explained that the player can see four snapshots of the screen to use as input. In order to keep the size reasonable, they used grayscale images. Devan described the design of the neural networks used by his player. His algorithm included a double-deep Q network.
Raymond Riddell, "Monte Carlo Tree Search"
Raymond talked about the MCTS algorithm he wrote for my HTML-(and JS-)based combinatorial games. He explained the difference between heuristic and aheuristic algorithms. He showed a demo of the algorithm applied to Connect Four. He described a bunch of details of his code, including how the tree is structured and all of the UCB1 values of the nodes based on their win records. These values are used to determine which node to traverse when exploring more of the tree.
Max Fierro, "Computational Methods Uniformly Pushing the Solving Horizon"
Max talked about exhaustive searches for solving deterministic games. In order to do this, he employs the notion of histories, sets of states that include a utility function. His team created a 4-tuple to represent vertices in a graph that works for any sort of deterministic game. Max described a minimax implementation to search and make decisions. His group uses multiple threads and a custom database system to speed up his code.
Tomasz Maciosowski, "The Temperature of a Snort Position can be Infinitely Larger Than its Degree"
Tomasz explained the game of Snort and described a game simplification that removes unplayable vertices and tints vertices that can only be played by one player. He described the notion of temperature and showed how it applies to star graphs. He then talked about using a genetic algorithm to search for positions with higher temperature than the max degree of the graph. This led to the discovery of caterpillar graphs that led to unbounded differences between the temperature and degree.
One of our scheduled presenters got sick and couldn't present, but otherwise this was an immensely successful edition of Sprouts! Thank you to everyone who came and especially thank you to everyone who presented! See you next year!
