There were great talks again on Day 2!
Miloš Stojaković: "Strong Avoiding Positional Games"
Joint work with Jelena Stratijev. Positional games are played on a finite set X where the Winning Sets are given subsets. Players take turns claiming elements until all are taken. Then the winner is determined based on different classes of the positional games (e.g. the Strong Maker-Maker condition for Tic-Tac-Toe). Miloš talked about Strong Avoider-Avoider: the first player who claims an entire Winning Set (now the "losing set") loses. If no one does, then the game is a draw.
Sim, for example, is played on K_c with triangles as the Winning Sets. (Ramsey Theory tells us that a draw is not possible.) It turns out there is a winning strategy for the first player on 3^3 Tic-Tac-Toe! (The potential name Tic-Tac-No was mentioned.) No draws are possible here either.
Miloš's team found winning strategies for the second player for different Winning Sets of complete graphs. The proofs use a lot of cool techniques including strategy stealing!
Daniella Popović: "A New Approach to Equivalence of Games"
Joint work with Nikola Milosavljević and Bojan Bašić. Daniella began by reminding us of the equivalence of games. She then presented a new idea: partitioning game DAGs into classes where two positions share a class if they all have options to the same other classes. This is called "Emulational Equivalence" and is flexible because it does not require knowledge of the play convention (Normal/Misere). Her team defined Hackenforb: players alternate deleting edges from a graph. If any component matches a forbidden set of subgraphs, it is also deleted.
Daniella then showed that Hackenforb and Nim are emulationally equivalent. They were also able to show equivalence from Hackenforb to Chomp! More importantly, they showed there are games that cannot be related to Hackenforb in this way!
Michael Fisher: "Olympic Games: Three Impartial Games with Octal Codes"
Joint work with Keith Hazen and Craig Tennenhouse. Mike reminded us about Wythoff's Nim and Beatty sequences: using irrationals to define partitions on the natural numbers. He then reminded us about Octal Games, Kayles, Dawson's Chess, and Nim. Then Mike tied this in to Number Theory and Metallic Means: the Golden Ratio and Silver mean based on Pell Numbers. Bronze numbers exist as well, so Mike's team made an octal game based on each. E.g. the Golden Game uses the infinite octal code .1211212112112... (non-repeating!). The P-positions are at 0 = F1, F3, F5, F7, ... (the odd elements of the Fibonacci sequence). The Silver game does the same thing: each index is 1 or 2 depending on which side of the Silver-based Beatty sequences the index lands on. Mike showed graphs of Grundy values, but these did not reveal any obvious formulas.
Richard J Nowakowski: "The Game of Flipping Coins"
Joint work with Anthony Bonato and Melissa Huggan. This talk came about from teaching CGT to a non-CGT faculty member. They tried using Turning Turtles, but then wanted something to include partizan games as well. To do that they created Flipping Coins. This game is played on a string of 1s and 0s: Left can change two 1s into 0s (no matter what is between them) and Right can change a 0...1 to 1..0 (yes, the order matters). Thus, for example, the strings 11 = integer value 1 and 01 = -1. His group found integers and fractions. They discovered that Left has a serious advantage, but that all values are numbers. (That last bit uses the conditions from Alda's talk the previous day!)
It turns out that both players want to play usually at the right-end of the string, meaning it looks like the analysis could be related to ordinal sums. Richard's team found a complete way to evaluate positions!
Tomoaki Abuku: "A Multiple Hook Removing Game Whose Starting Position is a Rectangular Young Diagram with Unimodal Numbering"
This is Joint Work with Masata Tada. In this new impartial game, the players play on a Young Diagram and remove one box and the corresponding hook: the boxes directly below and to the right. Then the remaining boxes are shifted up and to the left. This is a very interesting Chomp variant! Tomoaki then described a variant with a unimodal numbering on the boxes. After a move that removes a hook, the player has to go again if they can remove a book with the same multiset. This continues until no such matching multiset move exists. Tomoaki's team found a diagonal expression to classify positions, which they used to calculate many of the nimbers. Tomoaki described an equivalence to a version with shifted Young Diagrams that helped reduce game sizes.
Kanae Yoshiwatari: "Complexity of Colored Arc Kayles"
Joint work with Tesshu Hanaka, Hironori Kiya, and Hirotaka Ono. Colored Arc Kayles is the partizan version of Arc Kayles where edges are colored by the player (or green/gray for either) who can play on that edge. Kanae reminded us about the relationship between Arc Kayles and Cram and Domineering. Kanae's team showed that Colored Arc Kayles is NP-hard, as well as some parameterized algorithms (still exponential) to solve it that improved on multiple previous results. Some of the parameters they use include the vertex cover and neighborhood diversity.
Eric Duchêne: "Partizan Subtraction Games"
Joint work with Marc Heinrich, Richard J Nowakowski, and Aline Parreau. Eric next presented his result on Partizan Subtraction games, which is just like impartial subtraction, but with separate subtraction sets. Eric's team showed that this game is NP-hard via a clever reduction from Generalized Knapsack. Then they showed the game is quite easy from some small sets and talked about the different styles of sequences of outcome classes. They showed that computing the length of the preperiod of the sequence is NP-hard using the Frobenius problem! Then they looked at the effects of set sizes between the players.
Aline Parreau: "Maker-Breaker Domination Game"
Joint work with: Guillaume Bagan, Eric Duchêne, Valentin Gledel, Tuomo Lehtilä, and Gabriel Renault. In this game, one player (the Maker) is trying to build a dominating set on the vertices of a graph while the other player tries to prevent that. Aline pointed out that you can swap the roles by thinking of the Breaker as trying to created closed neighborhoods. Aline's team showed that the game is PSPACE-complete, even for bipartite and split graphs. They also showed a property that implies a Maker win, then showed that the property is NP-hard to detect, but not in trees! Trees are one of few graph families Aline found to be solvable in Polynomial time. The hardness remains open for interval graphs. There are really interesting relationships between matchings.
Hikaru Manabe: "Four-Dimensional Chocolate Games and Chocolate Games with a Pass Move"
Joint work with Aditi Singh, Yuki Tokuni, and Ryohei Miyadera. Hikaru is a high-school student in Japan! He spoke about Chomp games (on chocolate) but also using only horizontal and vertical cuts. His team looked at staircase functions that result in different board shapes and the nimbers you can get. Then Hikaru generalized to 3-d and then to 4-d! His team continued to use stair-shaped functions to grow boards out from the bitter (poison) square. Then they looked at the relationship with adding a pass move and how that could be modeled by shifting dimensions.
Amazing talks! Then we had a great conference dinner until way too late. (That's why these weren't out last night.) One more day to go!
No comments:
Post a Comment