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.
No comments:
Post a Comment