The Curious Case of Col's Computational Complexity

Col is one of three basic placement games on graphs along with Snort and Node Kayles.  In all three, players take turns painting vertices their color, with a restriction based on what colors are neighboring.  In Col, you can't paint a vertex adjacent to another vertex that already has your color.  In Snort, you can't paint adjacent to a vertex in your opponent's color.  In Node Kayles, you can't paint adjacent to either color.  (That's not usually how Node Kayles is described, but this is equivalent.)

Winning Ways mentions these in its discussion of the computational complexity of games.  (It's in Volume 1, chapter 7, "Hackenbush", under "NP-Hardness" as part of the chapter's Extras.)  From Page 224 of the second edition:

"Even & Tarjan have shown that Generalized Hex is PSPACE-complete and Schaeffer [sic] has done the same for Generalized Geography, Generalized Kayles, Col and Snort."

Winning Ways is a fundamental work.  In 2009, Alessandro Cincotti referenced this to state that Col was PSPACE-complete in his paper on a 3-player Col variant.

The sentence in Winning Ways is a reference to Thomas J. Schaefer's 1978 paper On the complexity of some two-person perfect-information games, which is probably the most important paper in Algorithmic CGT.  In that paper, Node Kayles ("Generalized Kayles") is shown to be PSPACE-complete.  And the same for Snort.

And not Col.

Like the others, Col is certainly in PSPACE: on a graph with n vertices and m edges, the height of the game tree is at most n and each player has at most n options on their turn.  We can do an exponential-time traversal of the game tree using polynomial (in terms of n and m) bits to keep track of our work (Polynomial Space, PSPACE, sized) and determine the outcome class of the position in question. 

The hardness was tricky, however.  It seemed like an easy enough game, but Col is quite cold.  Each position is equal to a number or a number plus *.  For each player, the options might toggle the inclusion of that * and/or push the number towards the opponent's direction.  There are no switches or otherwise hot positions where it is a significant benefit to play first.  The lack of heat made it hard to find a reduction from another partisan games.  Impartial games are automatically cold games, but reducing from impartial to partisan is a pretty tough paradigm shift.  (It's not as bad to go the other way, e.g. the reduction from QSAT to Generalized Geography from Schaefer's paper.)  

These inherent difficulties combined with the Winning Ways typo meant that Col's computational complexity went unsolved for a long time, despite the simplicity of its rules. 

In 2009, Bob Hearn and Erik Demaine adapted Hearn's thesis into the book Games, Puzzles and Computation, which became a catapult to resolving the complexity of many other games that had eluded categorization, including Amazons and Konane.  (This led to the coining of the term Algorithmic Combinatorial Game Theory, i.e. ACGT.)  I met Bob Hearn a few years later and we agreed that solving Col was a big prize.  Not only was it a long standing open problem, but the game seemed computationally hard and proving it would "cure" the hole and make the Winning Ways sentence true. 

In 2013, 35 years after Schaefer's foundational paper, we got to work.  Bob explained Constraint Logic, the main tool from his thesis, to me.  We got the gadgets (mostly him) and everything slowly came together.

And then we got scooped.  In early 2015, a team with Steve Fenner showed that Col was PSPACE-complete in Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. 

The Col result is only a small part of Fenner, Grier, Messner, Schaeffer, and Thierauf's excellent paper, but it's an absolute gem of a proof.  The reduction goes straight from Positive CNF and yields uncolored graphs!  That means that these can be considered starting positions that are shown to be hard, an impressive feat!  Finally, the question of Col's complexity was resolved, joining its cousins Node Kayles and Snort as PSPACE-complete. 

We did continue our work.  Part of the benefit of using Constraint Logic is that our reduction produced Col instances on planar graphs (though they certainly weren't uncolored).  We also showed planar PSPACE-hardness of Fjords, NoGo, and Snort, which was an improvement on Schaefer's original non-planar case.  With those additions, we got our paper out in 2018, one of my best publications.

Col remains an interesting ruleset in the short-lived history of ACGT.  For a long time it was accidentally understood by many to be solved.  Over 35 years after Node Kayles and Snort were solved, it was finally shown to be hard in two separate scenarios, independently proven in a short span.  I'm very lucky that I got to be a part of such a cool "academic moment".

Currently the remaining "biggest" rulesets with unknown complexity are probably Clobber and Domineering.  I know that advances are being made towards the complexity of at least one of these.  Perhaps one day we'll see another race to the finish on another of the most highly-regarded games in CGT.

Edit notes: I originally had an image of the quote from Winning Ways, but it wasn't displaying properly, so I replaced the image with the quote.

Sprouts 2024 Talks

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!

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!

 

 

 

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. 

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!

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.