Thursday, January 25, 2024

Games at Mumbai: Not the Talks

Games at Mumbai just ended.  In a few hours, I will arrive at the airport and fly home.  My first time in India has been wonderful!  I loved it!  Here are some quick notes about my time here that I think are interesting:

  • The traffic outside the IIT Bombay campus is the wildest I have ever experienced.
  • Learning to look right first when I try to walk across a road is harder than I thought it would be.
  • All of the food was awesome!  I discovered so much!
  • Many bathrooms have a bidet spray nozzle instead of toilet paper.  I attempted to learn to use bidets without using toilet paper, but failed.  I had to rely on stalls that were equipped with rolls of toilet paper.
  • The venue at IIT Bombay, the Victor Menezes Convention Center, was excellent.  There is a great indoor room for presentations and a nice shaded outdoor space for eating and collaborating.  (We also had access to some classrooms.)
  • I got addicted to chai, both with and without masala.

Notes specific to CGT:

  • I talked about what (I think) a ruleset is and this sparked some conversations.
  • Lots of people wanted to talk with me about my research!  That was a (dangerous) ego boost, for sure.
  • I was lucky about the topics I put in my second talk; it addressed many of the questions I got in the two days after the first one.  I barely changed anything from the slides I had before I arrived!
  • Four days of talks about CGT is not too much for me, even being sleep-deprived for three of them.
  • I learned a TON about the pre-history of CGT from Carlos. 

Long, sappy note:

I was very nervous about this trip, because air travel is tough for me.  Mumbai is the furthest east I have ever traveled.  I got quite sick a few weeks ago, and then the day before I left I still had to visit the doctor.  My flights here got cancelled on the morning they were set to depart.  

Nevertheless, I still made it here and I am extremely glad I did.  I learned so much.  Thank you to everyone I met!  Thank you to everyone on the organizing committee!  I feel like I could have jumped into 5 or more new research projects!  (I'm not a research professor, so there's no way I'll be able to do that, sadly.)  

I have been very lucky in my career.  Many times I have not been able to follow through on all the things I wanted to do, and I've had the fortune to continue on anyways.  I received a lot of appreciation here, and it means a ton.  I hope that it is deserved; I did spend a lot of time preparing my talks. 

Just like the Games and Graphs Workshop six-and-a-half years ago and the BIRS meeting in 2011, I really feel like a valuable part of the CGT community.  Thank you to everyone.  There may not be any chance in our rulesets, but I've still been very lucky. 

Games at Mumbai, Day 4 (Final) of Talks

The talks on the final day of Games At Mumbai continued the excellence of the week!  Here are my summaries:

Dhruv Basin, "On ergodicity of a 1-dimensional PCA with parity dependent updation rules" 

Dhruv talked about the site percolation problem--whether there are open clusters on randomly-generated graphs.  In a game version of this, vertices (integer coordinates of the Cartesian plane, so the board is infinite) are randomly either a trap, a target, or open.  Players alternate moving a token along edges that are the same respectively for each vertex.  If you land on a trap, you lose.  If you land on a target, you win.  If both players can force play to continue infinitely, then the game is a draw.  Dhruv showed that, on some loop-free transition choices, how to recursively define the outcome classes.  Then he talked about how this is all related to Probabilistic Cellular Automata.  Dhruv found some range of target/trap probabilities that make the probability of draws become zero.


Anirban Mitra, "A Steckelberg game for cross-channel free-riding"

Anirban discussed multi-channel retailing: the approach of selling goods via multiple platforms.  He described showrooming: looking for products in person, then buying them online as well as the converse: looking for products online, then buying them in person.  Anirban created a Steckelberg model to create an economic game for these phenomena.  He talked about using SPNE (Subgame Perfect Nash Equilibria) to solve the value of Steckelberg games.  He applied SPNE to his showrooming and webrooming model and got meaningful results.


Saraswati Girish Nanati, "Eternal Vertex Cover Game"

Saraswati introduced the Eternal Vertex Cover Game, based on the eternal vertex cover problem.  This is a loopy maker-breaker game.  A position consists of an undirected graph with guards on a subset of the vertices.  Each turn, the attacker selects any edge.  If there are no guards on the vertices incident to that edge, then the attacker wins instantly.  Otherwise, on the defender's turn, they move each guard along up to one edge, one of which must include the edge chosen by the attacker.  (Two guards can cross paths and swap.)  Saraswati related this to the EVC number of a graph.  She showed that finding the smallest necessary set of guards for the defender to win forever is NP-hard by reducing from Red-Blue Dominating Set.  On elementary bipartite graphs, if all guards are in one half of the vertex set, the winning strategy for the defender is to move all guards along the perfect matching.  If not perfect matching exists, then the attacker has a winning strategy.  Saraswati then discussed some variants and open problems she has results for.


Santanu Acharjee, "Scopes of games in bitopological dynamical systems"

Santanu talked about potential applications of CGT to his field: bitopological dynamical systems.  This is concerned with quasi-pseudo-metric spaces when two metrics form a partition on the topology.  (I'm glad I remembered a bit of my college topology class, but I definitely needed to remember more!)  Santanu talked about when many pairwise properties existed across the two metrics.  He then related this to infinite games on topological spaces.  The point of these game, he said, is not to play, but to describe novel infinite strategies.  He talked about Menger, compact, and Alster games (and even more categories beyond these) on bitopological spaces, and many conditions he found for when winning strategies exist.


Matthieu Dufour, "A family of slow exact k-Nim games"

Slow exact k-Nim (SN(n, k)) is a game played on n stacks of tokens.  A move consists of removing exactly 1 token from exactly k different stacks.  Prior results are known for the P-positions on SN(n, 1) (P-positions: when n is even), SN(n,n), SN(3,2), and SN(4,2).  Matthieu has extended this by adding results for many other individual categories.  He started by showing how to identify unplayable tokens to shrink some positions to equivalent smaller stacks.  He called this the NIRB (No stack Is Really Big) condition.  He then listed some other values commonly important to categorize positions.  Matthieu showed his evaluation strategies, explaining when he needed reductions to complete the characterization proofs.

After his talk, Matthieu showed a hilarious "mathematical magic trick" called "Bring the Cat" to close the conference.  He pulled a numerical rabbit from a hat!


Games At Mumbai (Extra Spicy) has been an excellent experience!  I felt really honored to be included, and especially lucky to get to give so many talks.  All of the talks I listened to were awesome and I hope to see many of the new people I met again!  Thank you so much to Urban, Mallik, Prem, Anjali, Ankita, and everyone else who made this happen!

 

 

 

Wednesday, January 24, 2024

Games at Mumbai, Day 3 Talks

Day 3 of Games at Mumbai had more excellent talks!  (I hope you like Wythoff's Nim! :-P)

 

Indrajit Saha, "Subtraction Games in more than one dimension"

Indrajit described a two-pile subtraction game in terms of animals taking from different piles of nuts: either 3 walnuts and 1 peanut or 1 walnut and 2 peanuts.  This generalizes to multi-dimensional subtraction games on tuples.  Indrajit has proven many excellent properties in two dimensions when there are two elements in the subtraction set.  For example, if S = {s1, s2}, then a tuple t is a P-position exactly when t + s1 + s2 is also a P-position!  This is the two move theorem.  When plotting the P-positions, some of the images look like overlapped checkerboards.  Indrajit has also found many results when extending to any dimension.

 

Carlos Pereira dos Santos, "Some open problems in CGT: Not much background required!"

Carlos went directly into impartial games.  He started by talking about Luca Pacioli, who, 500 years ago, wrote a treatise that contained a combinatorial game: a backwards subtraction game (you add instead of subtract and are trying to get up to 30) as well as the solution to the game.  Carlos then talked about basic subtraction games and Grundy sequences.  He did a long example ({1, 3, 6}) and then showed a table of known results from Winning Ways.  Then he gave a first 40-year-old unproven conjecture by Richard Guy about the bounds on period lengths of subtraction games.  Then he listed another open problem directly related to Indrajit's talk: the periodicity of bidimensional finite subtraction games.  Next he talked about pile splitting, starting with Kayles.

Carlos then moved into partizan-land, using Blue-Red Hackenbush.  He explained how to represent dyadic rationals in binary.  He showed the utility of using negatives in the representations to build numbers with no zeroes.  From this, he showed that these are really just Hackenbush strings with that numeric value.


Gandhar Joshi, "Games, puzzles, and automatic proofs"

Gandhar talked about finite state automata and the sequences they generate: automatic sequences.  Gandhar then showed the relationship to games using Wythoff's Nim (he put an Indian spin on the normal names, using Leela and Rajesh).  He showed that Zeckendorf representations can be used with the automata to find Wythoff's Nim P-positions.  Gandhar then talked about using the Walnut theorem solver to find new integer sequences from Upper and Lower Wythoff sets.


Shun-ichi Kimura, "Enforce operation of the disjunctive sum and the continued conjunctive sum"

Kimura talked about two-pile subtraction games as well.  He started by showing plots of his P-positions first, which looked a lot like Indrajik's images, then promised they were the results of easy rules.  In his games he used the continued conjunctive sum, which means players have to make a move on each summand game on their turn, except they can ignore components without moves (unless none of them have moves; then you lose).  Then Kimura explained the enforce operator across sums: the opponent decides which kind of sum the next player will use on their turn.  "Something phenomenal happens", especially because Tweedledee-Tweedledum strategies are much more difficult to implement.  There is also a good theorem by Odawara that shows that some sum rules dominate others.  Combinations of sums create the figures he showed initially, all of which used the same subtraction set {1, 2, 3}.

 

Takahiro Yamashita, "Yama Nim, Triangular Nim, and their Wythoff variations"

Yamashita also talked about two-heap Nim games.  Yama Nim is a variant where you must take at least two from one pile and you also return 1 to the other heap.  The P-positions turn out to be along the diagonal and the two diagonal bands adjacent.  Triangular Nim is a generalization of Yama Nim where you can return more than one token so long as the total number removed is still positive.  Amazingly, the P-positions are exactly the same!  The Grundy values, however, are different and more complicated.  Yamashita then added the "c-Wythoff" twist to triangular nim, allowing players to remove from both piles as long as the difference between the removed amounts is less than or equal to c.  The 0-Wythoff twist changes the P-positons into a list of triangular number pairs!  The 1-Wythoff twist gives square numbers!  Yamashita proved the theorem that the c-Wythoff twist delivers (c+3)-gonal number pairs as P-positions!

 

Hirotaka Ono, "Computational Complexity of Turning Tiles"

Ono described Turning Tiles, which I'd seen Koki, one of his coauthors, present before.  The game is played on a grid of Blue/Red/Black colored tiles and with a token on one of the non-black tiles.  A turn consists of moving the token as a rook so long as all spaces entered are that player's color.  After moving, all tiles that were left get turned to black (never to be used again).  Ono showed that this game is PSPACE-complete, and also showed that the disjoint version is DP-hard.  The hardness reduction is from (Generalized) Geography, restricted to the still-hard max-degree of 3 bipartite graphs.  With those restrictions, Ono was able to create gadgets embedded in the grid.  He then stated that the monochrome disjoint version with one token on each section is DP-hard via a reduction from SAT-UNSAT.  Very cool!  Ono finished by showing an exponential-time dynamic programming algorithm to solve the general version of the game.

 

Hridank Garodia, "Pixel Pummel"

Pixel Pummel is played on an m x n grid, with players placing their own colored dominoes on the grid.  The dominoes are placed standing up, but oriented either vertically or horizontally all in one square.  When a domino's placed with it's long side (from above) directly facing an adjacent opponent's domino's short side, the opponent's domino is replaced by one from the current player (in the same orientation).  These captures cascade recursively.  There are other play configurations that are not allowed.  Hridank, who is a local high school student, has already shown the outcome classes of 1xn boards. 

 

Geremias Polanco, "On the theme of Wythoff's Game"

Geremias warned us that his talk was likely to have a "number theory flavor".  He started off by describing Beatty sequences, then went to Sturmian sequences (new to me) and showed the bijection between them.  He stated that Wythoff introduced the mex function, which I did not know.  He then covered many of the generalizations to Wythoff, including the removal of the monotonicity requirement on the sequences.  Geremias found a Unifying Theorem that states that one of the four properties must be true.  He was also able to find a relaxed version of Wythoff that includes all Beatty solutions.

 

Nikhil Gehlot, "Enabling learning by playing"

Nikhil comes from the side of reality: his company creates educational games to help students learn math and science skills.  He described multiple games that reinforce trigonometric functions.  They also have games for chemical formulas and coordinate systems. 

Tuesday, January 23, 2024

Games at Mumbai, Day 2 Talks

Anjali Bhagat, "Fork positions and 2-dimensional Toppling Dominoes"

Anjali described Toppling Domines, giving some good examples of positions, options, and values.  Her definition included green dominoes, which is not something I'd look at before.  The best part is that she brought in actual dominoes to demonstrate along the edge of the podium.  She then introduced a 2-dimensional variant where one domino is lined up directly next to two dominoes on the same side.  These "fork dominoes" are interesting because they root domino can knock over both other two, but neither of those can topple the other.  She found a bunch of results about what happens when you duplicate one domino in the middle of a string  She proved that when a green stone is added, in many cases the value of the new position is comparable with the old.  Anjali also looked at many other combinations and is interested in solving triangular-number-type structures of all green dominoes.

 

Ankita Dargad, "The temperatures of Robin Hood game"

Ankita explained Robin Hood, a 1-heap game of Wealth Nim with some additional rules: players cannot remove more tokens from the heap than their wealth, and when they take t tokens, it also deducts that same amount from the opponent's wealth.  She also formulated the game in an equivalent way named Ancient Village Story.  She then discovered values (hidden in Sherwood Forest, no doubt) including all integers and all integer switches and switch-like values.  "It's a hot game," she explained.  Ankita then went deeper and looked at the Left and Right stops.  She named the optimal move the "Little John" move, which can be determined easily.  I learned that in India, the Fibonacci sequence is known as a Pingala sequence, which contains all such sequences using different starting pairs.  She showed that the wealth values follow one of these.  She continued by analyzing the temperatures of these positions, which depend on how the Golden Ratio relates to the ratio of wealths.

 

Prem Kant, "Bidding Combinatorial Games"

Prem, who I met last year in the Azores, talked about how to generalize the alternating play part of CGT to create rulesets where players bid to see who plays next.  To handle the bidding process, he uses Discrete Richman Auctions: the players secretly choose their bids, then simultaneously reveal them.  The winner hands over what they bid and (must) take(s) the next turn.  The players each have starting money and bid must be a non-negative integer.  There is additionally one tie-breaker token that one player starts with.  The token can be included in that player's bid, and adds a value of 1/2.  It gets transferred with winning as normal, however if the bids are tied, then it is considered automatically added to that player's bid, so they win and it is transferred to the other player.  There's a lot of space for results here and Prem has covered quite a lot.  In particular, he talked about the different outcome classes based on the budgets each player has compared with the overall total.  For each total budget in the non-negative integers, he found a way to set up the positions so that each one of the possible outcomes in that range is reached.


Johan Wästlund, "Games and optimization on random structures"

On rare occasions, I go to talks at these meetings and then I think "Oh, this one isn't actually about games," and then all of a sudden it is.  This was one of those talks!

Johan started by talking about the geometry of randomly-generated trees and how to determine their independence number--the size of their maximum independent set.  He then showed how that probability distribution comes out.  This was then all used in a simple dice game where players alternate rolling a single n-sided die until the number of throws + the number of distinct values rolled is greater than or equal to n, with the last person winning.  The probability of the game ending after k rolls is exactly equal to the probabilities of the independent set having size k.  Wow!

He used that result to tie into the game Slither, which is equivalent to (directed) Geography on a game tree.  To generate the trees, he uses the same random process as before, but then also randomly chooses the root.  From this he generates a Slither code by writing down the labels of the leaves, from lowest to highest.  Each time he appends these to the ends of the string and works his way in, with P and N-positions going on different sides.  His scheme also includes writing the label of each parent above each digit.  The resulting 2-row code is enough information to completely recreate the tree.  Since the P-positions always consist of a maximum independent set (whoa!) you can also determine the independence number from the string!  He used this to find the Omega constant, though his construction is different from the prior method found in the 1970s.

Johan then switched to talk about putting random edge weights in [0,1] on the complete graph, K_n.  If you consider the minimum matching total weight, that cost tends towards (pi^2)/2 as n goes to infinity.  He talked about a relaxation of the problem that allows you to pay a bailout price instead of paying for the matching for expensive edges.  This is related to a graph game where the players traverse a weighted undirected graph and pay the edge's weight at each move.  (Or pass and pay the bail out price.)  Optimal play can be analyzed by relating back to the matching problem and using that solution.

He also mentioned comply-constraint games, where the opponent picks two options for the current player to select to move to (instead of all available options).  He then surprised me once more by relating this to the Traveling Salesman Problem!  "You never know when Game Theory will come in handy!" 

This was such a cool talk because of how the different results related back to games in amazingly unexpected ways!


Satvik Sharma, "Symmetry in Combinatorial Games"

Satvik, an undergrad student, talked about many cases of symmetry in games.  First he talked about strategy stealing arguments.  He described the 2-move Chess game where each player makes two standard Chess moves in a row instead of one.  There is a very simple strategy stealing argument showing that the second player cannot have a winning strategy (though they may be able to force a Draw): if they did have a winning strategy, then the first player could just move a knight out and back and then use that second player's strategy.  He also talked about the Hex Theorem and the result that the first player has a winning strategy.  Satvik then talked about how to employ Tweedledee-Tweedledum arguments whenever they are available.  Finally he talked about the Game of Queens, a partizan placement game where you alternate placing a queen of your color, but only in a space no other of your queens can attack.  Satvik showed that a symmetry strategy works very well here for any even x even or odd x even size boards.


Today was another great day of talks!  These are excellent!

Monday, January 22, 2024

Games at Mumbai, Day 1 Talks

Today we kicked off a big day of talks at the first "official" day of Games at Mumbai.  Urban taught a CGT course (for grad students) last semester, and I believe that many of the presenters created new combinatorial games in his course, which they spoke about.  There were many very creative games!


Carlos Pereira dos Santos, "A quick journey into Combinatorial Game Theory"

Carlos gave us an intro to all of CGT.  (These talks are very interesting to me because I have heard many different versions and I'm always looking to improve the "Crash Course" talk I give every year at Sprouts.)  

Carlos began with impartial games, using Nim, Cram and Wythoff's Queens to explain Sprague-Grundy theory.  (Carlos was very historically-minded in his talk and started with Bouton.)  He gave lots of good examples to motivate his talking points.  He had a great quote about the omnipresence of nimbers: "This is no longer just a recreational result."  In the end he phrased Sprague-Grundy theory as four facts (this is my simplification):

  • Every impartial game has a nimber value.  (The aforementioned "omnipresence of nimbers")
  • The nimber value can be computed by the mex rule.
  • Sum values use the XOR rule, and 
  • The outcome class is determined by whether the nimber value is zero.

Carlos did not have much time left for the partizan half of his talk.  Nevertheless, he got to integers and 1/2 using Hackenbush positions.  Overall this was a great talk!  I don't think I would be able to fit al the historical context into my talks like he did.  

 

Moumanti Podder, "Graph nim games on graphs with four edges"

Moumanti talked about a Nim variant on graphs with weighted edges.  Each move consists of selecting a vertex and removes tokens from the incident edges in any way that removes at least one token overall.  She showed that a "rectangle graph" is a zero position by explaining a Tweedledee-Tweedledum strategy.  She also showed that star graphs act like single nim heaps, so a galaxy acts like a multi-heap nim position.  Moumanti is looking at trying to characterize the outcome classes of graphs with four edges.  She's found some results on the nim values on triangles, which she got by adding with to a disjoint single edge. 

 

Aaron Siegel, "How to lose at combinatorial games (or at least draw)"

Aaron talked about "standard" CGT and all the different ways the conventions can be broken.  (Transfinite games was a new concept to me!)  He covered breaking normal play (to be misère) and finite game lengths. 

In misère play, Aaron explained that Bouton also found the winning strategy for nim (as well as in normal play).  He went over the Sprague-Grundy basics, and applied it to Kayles, showing off how nice periodicity falls into normal play.  He contrasted this with misère results, which continue to highlight just how elusive these nice patterns are.  "We need an extra condition for outcome classes," he explained--the base case for the set which is an exception to the natural terminal condition.  He gave the Misère Mex Rule, which "becomes almost useless in misère theory."  (As with outcomes, there is an additional condition from the normal play version.)  He explained the "combinatorial explosion" that happens and that the number of possible values born on day five skyrockets to 4,171,780.  

Aaron then talked about tame games: misère impartial games that do reduce to nim.  He also talked about using other algebraic structures to solve different rulesets, including Kayles.  

Shifting to loopy games (under normal play, still impartial), Aaron showed that we no longer have game trees.  He explained the new outcome class: D - draws.  He provided some basic game graphs to show the cases where Draws can occur.  Aaron then dove into values, giving the definition of the loopy mex-rule.  This was very helpful; I think I understood values of impartial loopy games for the first time!


Aditya D. Bhat, "Slamming Toads and Frogs"

Aditya explained how his game differs from traditional Toads & Frogs: no jumping moves are allowed; instead amphibians "slam" other pieces over them.  More concretely: an amphibian with an open space behind it and with an opposing amphibian right in front of them can move that opposing piece to that open space behind, as though that opposing piece had just performed the T&F jump move.  Aditya used CGSuite to find many different game values.  In general, it seems that the values are at least as hot as the same position in Toads and Frogs.  So far he hasn't found a single *-valued position.

 

Deepankar Sehra, "Impartial Game Ruleset: Space Quest" 

Deepankar's game, Space Quest, involves an avatar moving around on a grid, one space horizontally or vertically each turn, to a cell that has not yet been visited.  In addition to that movement, however, the player must also pick another cell anywhere on the board to destroy.  There is a lot of similarity to Undirected Vertex Geography.  Deepankar has done some work on the outcome classes and nimbers of nxn grids up to n=5.  Amazingly, they so far all satisfy: nxn = *(n-1).  (The starting position of the avatar is in the top left cell.)

 

Tanmay Joshi, "3-Annihiliation"  

Tanmay showed off his ruleset, which is played on a string of Ls and Rs, but never three or more of the same letter in a row.  A turn consists of removing one of your own letters, which shrinks and collapses the string.  If this creates any string of 3 or 4 of the same letter in a row, those are removed.  This process is continued until no more 3+ of the same letter remain.  Tanmay has found the integers -2, -1, 0, 1, and 2, switches, but no stars nor fractions.  It seems very reasonable that no other integers exist!  Additionally, the hottest temperature he's found so far is 2, which also makes sense.

 

Vedang Gupta, "Nuclear Battleship and Surround" 

Vedang showed off his two new rulesets: Nuclear Battleship and Surround.  The former is played on a grid with each player having a single ship piece on separate spaces.  Some of the spaces may be destroyed (due to nuclear fallout in the area) and ships cannot move there.  Each turn the current player either leaves their ship alone or moves it, then fires a nuclear missile at another space.  (They can target any undestroyed square, including one that contains an opponent's ship.)  At the end of their opponent's next turn, that space becomes destroyed.  Thus, opposing ships want to move out of a targeted square if they're in one.  Vedang found integers, unbounded switches, and *, and showed thermographs for some positions with multiple ships of one color.

Vedang then talked about his second ruleset: Surround.  In this game, also played on a grid, spaces can contain white or black tokens.  A turn consists of placing tokens of your color in any of the cells that surround the other player's pieces, including the diagonal connections.  If no such cells exist, you're allowed to play one piece along the board's edge.  This creates an all-small ruleset.  Vedang found a lot of infintesimal values, including *, *2, and up.


Harhsvardan Agarwal, "Tokens Partizan"

Tokens Partizan is another game played on a grid.  One way to think of this game is that one player is making Col moves while the other is making Cram moves.  White plays single white stones, but cannot play adjacent to their prior plays.  Black places two adjacent black stones on the board either vertically adjacent or horizontally.  Harhsvardan talked about strategies for the players that involve thinking of the boards colored in a checkerboard style.  With this reasoning, he found general results for all empty grid boards, many of which were proven using induction and reasoning about tiling.


These talks were really good today!  I am really looking forward to see what tomorrow brings.

Sunday, January 21, 2024

Games at Mumbai, Day 0 Talks

On the "unofficial" first day of Games at Mumbai, we had two talks and two tournaments!  This has been a great conference already, but you are here to hear about the talks, so here we go.

Karan Rawat, "All about Go!"

Karan, a member of the Maharashtra Go Association, gave us an overview of Go.  He talked about the history and origins.  He compared it to Chess, which is apparently far more popular in India.  Karan talked about six of the top international Go federations and some of the top tournaments.  He explained many cultural aspects, especially high level tournaments and the pieces used.  (Super fancy Go stones made of shells can cost as much as $150 apiece!)  Karan explained the rules and discussed a bunch of patterns for beginners to look out for.

 

Carlos Pereira dos Santos, "Presentation of Atari Go"

Carlos gave a quick talk to explain Atari Go, which is the same as Go except that the first capture move wins.  (Self-capture moves and passes are not allowed.)  He did give a quick dip into breaking down a complex position into separate independent pieces and use a disjunctive sum to put them back together.  "All components matter" he advised, and then we were off to play an Atari Go tournament.

 

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.


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!