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.