Heaps vs. Heaps

I've been teaching Plymouth State's Data Structures course every semester and hope to keep teaching it for a while.  Each project covers a different data structure... and a combinatorial game that uses that structure.

Unfortunately these two universes conflict over a term: Heaps.  The piles of sticks in Nim are usually referred to as heaps.  However, in CS a heap is a binary tree structure with a specific recursive property: each element is bigger (or smaller in a min-heap) than both child elements.  (There's more to it than just that, but that's the big deal.)  Currently we talk about heaps in class, but I don't have a project that includes just them.

It was brought to my attention last semester that some of my code is confusing for people with CS background.  Many of the games students play are Nim-based, and they often have a getHeaps() method that returns the data structure containing the Nim piles.

Sadly, I've decided against the Combinatorial Games language:  I'll replace the term "heaps" throughout my projects with "piles".  I'll be making these changes over the next two weeks and they'll show up in my projects starting this fall.

Sorry CGT, but people say "piles" anyways.

CGT has a website!

There has been some discussion about having a central resource for CGT material over the past few years.  Just a few days ago at Games at Dal 2015, Aaron Siegel took the initiative to actually get it going at combinatorialgames.org.

Aaron has already posted lots of basic info over there, including some notes on getting started in CGT, some reference materials, and information about upcoming conferences.

Please check it out and continue to check back as more information gets added.  Thanks to Aaron for getting this project started!

Games at Dal 2015: Afternoon Talks

Yesterday (Tuesday) we had two afternoon talks to round out that portion of Games at Dal 2015. 

Simon Rubinstein-Salzedo spoke first.  Simon has recently started a a math institute in California's Bay Area with the goal of teaching advanced math concepts to gifted highschool students.  In the meantime, he and Urban have worked out some interesting results about a multi-pile Nim variant.

The basic variant of the game starts with a heap of n stones.  The first player may take up to n-1 of them.  States are described by the pair (pile size, maximum allowed to take), so the initial position is (n, n-1).  In future turns, removing k stones from any state (a, b) results in the new position (a - k, 2k).  Thus, you can take at most twice as many as were taken last time.  (Naturally, you must take at least one stone.)

The analysis of this game employs a new representation of the positive integers that I was completely unfamiliar with: the Zeckendorf representation.  Apparently, every positive integer can be uniquely represented as a sum of non-consecutive Fibonacci numbers.  For example: 27 = 1 + 5 + 21.  Whoa moments:

• Wow, uniquely!  Awesome!
• Non-consecutive?  Sweet!
• The greedy algorithm works to find the representation.  Given n, choose the biggest Fibonacci number below that, include that in the representation, then recurse on the difference.  (You can kind of see why the elements must be non-consecutive by induction.

Back to the CGT: A position, (a, b), has a winning move exactly when you can take the smallest part of the Zeckendorf representation.  Thus, for (27, x), the winning move is to take 1 stone, so that the result is (26 = 5 + 21, 2).  The next player can't take 5.  In fact, you never have to worry about them taking the next-highest number in the Zeckendorf, because it's non-consecutive and must be more than twice the old smallest value.  This means that a starting position is in P exactly when the size of the heap, n, is in the Fibonacci sequence: the smallest part is the whole thing, which is the only thing you're not allowed to take.  Simon is continuing his analysis by looking at multiple piles and some variants of that.


Craig Tennenhouse, my travel buddy, gave the final talk on some variants of Bogus Nim he's created.  Poker Nim is a well-understood variant of Nim: you keep a bank of the sticks you've removed and if you have a non-zero amount, you're allowed to add some to one pile on your turn instead of taking any.  Unfortunately this doesn't give you any escape from P-positions; your opponent will just snatch up whatever sticks you re-add.

Craig makes two changes to create Non-Loopy Poker Nim:

• First, change this to an impartial game with a shared bank.
• Second, disallow repeated positions to prevent loopiness.  (Positions are recorded using multisets, so order doesn't matter.)

For example, if the game begins at {3, 5, 7} and the first player moves to: {3, 5, 4}, then no one can ever return to {3, 5, 7} by putting sticks back into the last pile (or any other moves that reach this configuration).  The 2-pile version can be represented by a rook on a half-checkerboard with the space at 0,0 being an "automatic" P-position.  Craig further changes the representation to show that for most of the square boards there is an automatic symmetry.   (Post-post-edit: changed the numbers of piles to be correct above.)

If the number of heaps is not fixed, then the game takes on new structure that might best be represented by undirected position graphs.  Since loops are not allowed (by tracking the list of moves) this acts like Undirected Vertex Geography, for which winning positions can be easily detected.

Craig came up with another nice game: Rook Nim.  This game includes a full n x m checkerboard with a single automatic P-position in one corner and with the rook in the far opposite corner.  Here, however, the rook may not move through deleted spaces.  This means that not all games will end with the rook moving to (0,0).


Excellent talks!  After discussing potential problems to work on, we visited the Board Room and enjoyed the Halifax gaming culture.  Today (Wednesday) we worked intensely on the suggested problems: nearly to the point of exhaustion.  This was followed up with some more exploring of Halifax and a bunch of rounds of Hanabi.

I've both learned a ton here and will walk away with new results to write up!  Only two days in and this has been an amazing conference!

Games at Dal 2015: Morning Talks

We just finished the first day of the Games at Dal 2015 conference.  This is my first time at Dalhousie University (my first time in Halifax, in fact) and it's very wonderful here!

Today was the only day of talks; the rest is working sessions.  I'm going to break the talks into two posts: morning and afternoon.  Hopefully I can say something intelligent about everything I saw today.  Things got very deep very quickly!

Carlos Santos started off talking about work with Alda Carvalho on a new variant of Green Hackenbusht: Oak.  Oak includes not only (all-green) pieces growing off the ground (trees/plants), but also underground "roots" for each of the above-ground plants.  These roots are colored with brown edges, and have a more significant impact than the green edges:

• If any green edge is removed, those green edges no longer connected to the ground are removed, as normal.
• If any part of any root is removed, then all of the green edges connected to that root are removed, as well as any root pieces no longer connected to the ground.

Carlos explained a bunch about ordinal sums (this is a topic that probably deserves it's own post) including that for the game G:H, just knowing the value of G is not enough to fully evaluate the sum: the entire form of G is necessary.  (0 behaves differently than *2 + *2 as G in the ordinal sum.)  The same is not true of H; the value is sufficient.

Carlos and Alda found another sum, the gin sum which can be used to efficiently determine the appropriate value of the sums for these Oak positions.  The calculation is similar to the regular XOR sum, though certainly distinct.


Aviezri then spoke about using Fibonacci words in games, work done with Lior Goldberg.  The games they considered are generalized versions of Wythoff's Nim using Beatty sequences to determine the P-positions.  One version of this is: (parameterized by t)

• 2 heaps, as in Wythoff's Nim
• On turn, take either:
• any (positive) amount of sticks from one heap (also as in Wythoff's Nim), or
• k (> 0) from one heap and m (> 0) from the other, where | k - m | < t

The normal Wythoff's Nim, then, is this generalized version with t = 1.  It has been known for a long time that for each value of t, there is a pair of Beatty sequences (increasing sequences that partition the natural numbers) a's and b's that describe the P-positions.  (For each i, (a_i, b_i) is a P-position.)

The more recent work here considers adding invariant moves to the game that don't influence the location of the P positions.  This means adding a pair (x, y) so that the current player can always choose to subtract x and y from the two piles (as long as both piles are big enough) without actually affecting the winning/losing positions.  They proved an algorithm exists to find these in regular Wythoff's Nim.  Conversely, they investigated Forbidden Subtractions: invariant moves that cannot be added without changing the P positions.


Next came Neil McKay, continuing on his presentation from the CMS summer meetings on Hackenbush stalks: paths with green, red, and blue edges.  He got deeper into basics on ordinal sums (again, I should just make a big post on that) and then took off on explaining the nice properties of Hackenbush stalks.  Here his goal is to evaluate sums of stalks.

I'm surprised to learn just how difficult this is!  Unfortunately, sums of stalks are not closed, even though a sum of stalks is equal to a number plus a sum of dicot stalks.  There are some other benefits:

• If x is an integer and H is a dicot, then x : H = x + H
• o (* : G + * : H) = o(G + H) 
• The atomic weight, aw, of a dicot works nicely: aw(G + H) = aw(G) + aw(H).  (I am not keeping up with CGT concepts as they become popular; I don't know what the atomic weight is.)

I'm aware that Hackenbush is known to be NP-hard, but I'm surprised to find that there is no known polynomial algorithm for Hackenbush stalks... or even Hackenbush flowers!  A H.B. flower is *k : z, where z is an integer.


Gabriel Renault got deep into some new Misere conepts looking at invertibility and dead ends in universes with no P-positions: work done with Rebecca Milley.  There are three really big definitions involved here:

• A (Left/Right) End is a position with no moves for Left or Right, respectively.
• A (Left/Right) Dead End is a position where all followers (and the position itself?) are Left/Right Ends.  (Edit: yes, a position is its own follower.)
• A dead ending is a position where all end followers are dead ends.  (Edit: added italicized end.  Thanks, Gabriel!)

Gabriel and Rebecca decided to focus on universes without any P-positions, which allowed them to find some neat properties about equivalence and comparisons.  Conveniently, these P-less universes arise out of sums of dead ends.  (Unfortunately, dead-endings don't automatically work.  E.g. *, which is a dead ending, but is itself a P position.)


I hope to post about the other two talks from the afternoon tomorrow. :)

Portuguese Game Tournaments

Non-Portuguese parents have an excellent reason to be jealous: Portuguese grade schoolers recently competed in the 11th Annual Portuguese Tournament of Mathematical Games.  This big event, put on by Ludus, begins in regional schools for kids ages 7 to 17.  They compete in a wide variety of combinatorial games, then the winners advance to the final rounds as shown in the link above.

The final tournaments were held on March 6 of this year in Vila Real in northern Portugal.  1400 students played one of 6 games (I assume they're combinatorial, but I admit I'm not familiar with them all).

I picked up a copy of Traffic Lights in Lisbon at CGTC1, though I'm not very good at it yet.  It's definitely a nicely-balanced impartial game with easy-to-explain rules.  (I also got to meet João Neto there, without realizing that he's the author of the Trabsact Sagme Diaries.  (Those first two words in the name are anagrams for "abstract" and "game".)

One excellent aspect of the tournaments is that Ludus strives to make them as accessible as possible for all kids.  For example, the pieces for Traffic Lights have different shapes for each color.  This allows blind students to play by feeling the pieces without having to distinguish the colors!

In eighth grade I took an amazing class in mathematical games.  We played a bunch of Nim, Krypto, and Equations.  I wish we had fun tournaments like this to encourage abstract thought outside of the standard curriculum-box.  Unfortunately, I don't see this happening in the US on a large scale anytime soon.

CMS 2015 Summer Meetings, Day 1, Afternoon

(The CGT sessions were only held on the first day, so this is as far as my notes go.)

In the afternoon sessions, I spoke first about placement games on graphs, some variants that could be applied to all of them, and the computational complexity of the resulting games (of which very little is known).

Rebecca Milley went next, and this was the first time I'd ever heard an academic talk about Bowling Kayles!  She introduced a partisan version: Left knocks down 1 pin and Right knocks down 2 neighboring pins.  Rebecca the misere expert naturally considered that angle: who wins under misere play?  (I don't remember if the normal play version is solved.  It seems like it wouldn't be hard to show that Left always wins if there are any pins.) 

Misere games don't have additive inverses, because addition doesn't follow happy group rules.  Specifically, you can have games G and H (G's "inverse") where G + H = 0, but G and H's conjugate don't have the same outcome class when you start adding them to other positions.  (I don't recall how to derive the conjugate; I should learn that!)  In normal play, G+H = 0 means that G = -H, but that's not always the case in misere-land.

Rebecca's Partisan Kayles demonstrates positions with this inequivalence of conjugates and inverses. Consider a single pin (I'll denote this with a capital 'I') added to two single pins (II).  The sum (I + II) is equal to zero. (Playing optimally, both players will get a move, so the first player will win (misere).)  Thus, these two act like inverses.  They don't, however, act like conjugates.  So far, Partisan Kayles is the only known ruleset to fail this misere inverse property!

Richard rounded out the session, speaking more about work with Urban Larsson and Carlos Santos on scoring games.  He introduced DisKonnect, a scoring version of Konane.  (You keep track of the number of pieces you have taken.)  He also considered a method of embedding normal play games into scoring games: just play the game, but at the end, consider the score to be zero.  (I like this!)

Unfortunately, some scoring game positions can't be used to embed normal play games.  The resulting collection of scoring games that can be used, dubbed "guaranteed games", is a well-defined category.  Rulesets here include things such as Blokus, Mancala, and Dots-and-Boxes.

***

As you can see, there are tons of holes in my "reporting" of these talks.  There is much for me to still learn, and many aspects of this field I may never gain a mastery of.  CGT is growing quickly: Misere and Scoring play are taking off, and there are still lots of unanswered questions and lots of new rulesets people are thinking of.  It is definitely a cool time to be a gamester.

CMS 2015 Summer Meetings, Day 1, Morning

Catching up on some quick summaries from the CMS talks from June.  Here's a little thing about the morning talks!

Neil McKay presented a talk about determining whether a game is equivalent to a Hackenbush stalk.  A Hackenbush stalk is a single path of red, blue, and/or green edges (with one of the end vertices being the ground).  This was really interesting, because his talk yields a nice iterative method to do this for any game G. 

Each round, you check whether one of two things is true of G:

• G looks like a hackenbush game connected to the ground by only one green edge.  (G is *-based, meaning it looks like an ordinal sum.)
• G looks like a hackenbush game connected to the groudn by only a red or blue edge.  I believe this part uses the Reduced Canonical Form of G and compares that to G, checking that the difference is dicotic.

If neither is true, then G is not a stalk.  If one or the other is true, then you can reset G by chopping off the bottom of the stalk.  If you ever reach G = 0, then you know G is equivalent to a Hackenbush stalk!

Melissa Huggan next presented work she's done with Brett Stevens on Intersection Restriction games.  The big thing here everyone's excited to hear about is new work on Arc Kayles. She's been working on finding Grundy values on wheel graphs.  (A wheel graph of n spokes is a cycle with n vertices where each vertex also shares an edge with the central hub vertex.)  When some of the outer edges are chosen to be removed, the result is a graph that looks like part of a pizza.

She found a trick to shortcut a bunch of the evaluation: a pizza graph with k vertices has, as options, all of the options of a path graph with k vertices.  Since all nimbers of paths are known, you can use this to bound the nimber of the pizza graph.


Svenja Huntemann talked about some cool work she'd done with Richard N. and Sara Faridi, exploring Doppelganger placement games, specifically strong placement games on graphs.  In a strong placement game, players take turns painting a vertex their color.  This coloring can never be moved or erased, and the strong requirement means that the order of the plays should not matter: each position can be reached by any sequence of painting the colored vertices.

She then goes one step further to talk about distance games: games where the only rule is that vertices can't be painted if they have some distance to other painted vertices.  To specify a distance game, all one needs to do specify the illegal distances of same-colored pieces, S, and the illegal distances of different-colored vertices, D.  For example, Col is the distance game where D = {} and S = {1}; Snort has D = {1}, S = {}; Node Kayles is D = {1}, S = {1}.

For bipartite graphs, we can consider a bipartite flip of the illegal complexes: change the variable for each vertex in one half of the bipartition.  Redefining the game using these rules for illegal states is the same as swapping all odd numbers in the two sets.  If D(G) = {1, 2, 3} and S(G) = {2, 4}, then for H = Bipartite Flip(G), D(H) = {2}, S(H) = {1, 2, 3, 4}.  Doppelganger games, then, are games where the bipartite flip has the same number of legal positions.  I think.  I should ask Svenja again!

CMS 2015 Summer Meeting, Day 0

Over the weekend, I was invited to speak at the summer meeting for the Canadian Math Society at UPEI in Charlottetown, Prince Edward Island!  I got to meet lots of new people and learned about some cool new games as well as work on current things.

Aside from the conference itself, I also had a really nice time traveling to and from PEI.  I drove back and forth from New Hampshire, and that worked great for me.  Also, now that I've eaten poutine, I'm like a new person!

On Friday, the first day of the conference, Richard Nowakowski gave a public lecture, Games: Playing Positions Purposefully.  This was a really nice intro to CGT for mathematicians who didn't have any games background.  He covered all of the basics: strategies, outcome classes, sums, equivalence, numbers, infinitesimals, nimbers, switches, temperature.  I think he got to more of Lessons in Play than I got to teach in some of my courses! 

I was reunited with people I hadn't seen since Integers 2011 and people I met at CGTC1 in January.  I went to bed excited for Saturday's games talks.

Playable Atropos is back... and more usable.

I've been working on building HTML/JS games that can be played in a web browser without the need for Java.  Many years ago, I wrote a Java applet to play the impartial game Atropos, which was great except that it didn't work for non-Java browsers, like most mobile-device browsers.

Last week, I got a working HTML version of Atropos up.  It should work for you, unless you have JavaScript disabled. 

I've been playing recently on boards of size 9, going first against the Hard level "AI".  (It's just a depth-search for a winning move.  Hard goes for a depth of 7 moves, I think.)  Although I usually have to wait for my browser to catch up because it takes a lot of time for the AI to make the first few moves, it starts getting faster pretty quickly.  In this case, I have to try to trap the computer player because if the entire board fills up, I'll have to take the last spot (and lose).

I also rediscovered the Greek-style myth I wrote for the game and added it to the page.

Enjoy!

Schaefer's Boolean Formula Games

For a few years (okay, okay, like, 5 years) I've been working on a paper about boolean formula games.  These are games that include a formula involving some boolean variables.  A turn consists of either assigning a value to an unassigned variable or flipping the value of a variable (depending on the game).

The canonical problem in PSPACE is QBF, which can be phrased as the following game.  There is a boolean formula in terms of some variables x₀ through x_n-1.  The first player (named True) chooses a value for x₀, then the next player (False) chooses a value for x₁, then True assigns x₂, and so on.  Once all variables have been assigned, True wins if the formula has been made true, and False wins otherwise. 

A beautiful and classic paper of Thomas Schaefer defines a bunch of other games (mostly formula games) and shows that they are PSPACE-complete.  (He also shows that Snort and Node-Kayles are PSPACE-complete.)  I've recently updated my ruleset table to include Schaefer's games, and I'd like to add a guide here to translate between Schaefer's technical names and the ruleset names I'm using.  I'm hoping that this can be used as a helpful reference when browsing the paper.  (F used in my notes below refers to the type of formula.  Schaefer often defines separate games for CNF and DNF formulas; I've combined them for brevity.)

Unrestricted QBF:  This is the same game as QBF, except that players may choose any variable they want to assign (instead of needing to choose the next variable).  This is not listed as a game in Schaefer's work mostly because the next one (a special case) is instead.

Positive QBF:  (Schaefer: G_pos(POS F))  This is the same game as Unrestricted QBF, except that the formula must contain no negations.  It is a special case of Unrestricted QBF.

Partitioned Variables QBF: (Schaefer: G_%free(F))  This is the same game as Unrestricted QBF, except that the variables are partitioned in half into two groups, one for each player.  On your turn, you choose any unassigned variable in your partition and assigns a value to it.

Positive Avoid True (Schaefer: G_avoid(POS F))  Similar to Positive QBF, except that all variables are initialized to false and players take turns choosing a variable to flip to true.  The first player to cause the entire formula to be a tautology loses.  Played on positive formulas to enforce that the game will end.

Partitioned Positive Avoid True (Schaefer: G_%avoid(POS F))  Just like Positive Avoid True, except that (as in Partitioned Variables QBF) the variables are partitioned into two equal sets ahead of time.  Each player must choose from their set on their turn.

Positive Seek True (Schaefer: G_seek(POS F))  The same as Positive Avoid True, except that the first player to cause the formula to be a tautology wins.

Partitioned Positive Seek True (Schaefer: G_%seek(POS F))  Just like Partitioned Positive Avoid True, except the first player to cause the formula to be a tautology wins.

These are very useful games to start with to show PSPACE-hardness of other games.  In my table, I've listed which versions of these games are known to be hard, so that the appropriate cases can be covered (if necessary).

CGTC1, Day 3

The third and final day, and the talks were again excellent!  Catia Dias started off by showing off the results of her very thorough Ph.D. thesis.  She discovered and proved many properties of game values and the lattices of their followers, which I think she generated using the generalized Conway construction.  Her talk was extremely thorough as she took on and solved many conjectures.  (I later learned that Richard Nowakowski had proposed three of these conjectures.)  The first conjecture postulated that the lattice of a game is modular exactly when it is distributive, which she showed to be false.  She also proved the Representation Theorem for Games: for every lattice, there is a set of games that generates an isomorphic lattice.  This result holds for both finite and infinite lattices!

She was so complete answering these lattice questions that the biggest open problem (at least, for Thane) is that it's open whether the representation theorem also works for misere play.

Lisa Rougetet spoke next, after having delved into the history of combinatorial games in France.  Her goal was to determine the origins of the French term "Jeux de Combinaisons" (Games of Combinations) and see how it evolved during the 19th and 20th century towards the current CG definition.  At the end of the 18th century, the term "pures combinasons" was used to describe some appropriate games such as draughts and chess.  Then, in the mid 19th century, "Jeux de Combinaisons" shows up, but it is used for games with hidden information.  Later on, it appears again, and is differentiated from games of chance as we would expect, but then goes on to include billiards.  (Perhaps this is as relevant as the bowling version of Kayles.)  Combinatorial games show up in a later text by Edouard Lucas about recreational math, but he uses the term "recreational games".

In the 1900s, William Rivier, a Swiss chess player, divides games into three parts: chance, skill, and Jeux de Combinaisons.  This section includes games with two players and no randomness, but they didn't always have perfect information.  Still, this work is extremely cool because a generalized diagram of a game is included: perhaps the first game tree to make print.

Finally, in 1936, Rene de Passel refers to two alternating player games with perfect information and no randomness as "Jeux de Pure Reflexion".  Hooray, Combinatorial Games!  Lisa's investigation is ongoing, but she notes that the names may have diverged at this point, as Jeux de Combination now refers only to single-player puzzles.

Andre Fabbri spoke next on applying monte carlo evaluation strategies to solitaire versions of games.  He looked specifically at impartial Clobber, but perhaps more interestingly used an additional tactic along with the monte carlo methods: instead of just evaluating game paths to their completion, he included additional heuristic subgoals to help focus the search.  Paths that showed promise with these heuristics were weighted more heavily when being chosen for further exploitation.  In impartial clobber, one of his heuristics involved minimizing the number of remaining pieces in each quadrant of the board.  (For example, the four 4x4 subgrids of an 8x8 board.)

His work did not reveal new results for solitaire clobber; the cases he looked at are all already known.  Instead, he was checking to see whether his player came close to the actual answers.  In the future, Andre is considering using more varied subgoals and using parameterized weights to help determine how much to consider the subgoals during evaluation.  One of the exciting things about this talk was how many suggestions people had for Andre to continue his work.  It was obvious that there is lots more he can do with this nice heuristiced Monte Carlo approach!

Ilan Adler delivered an enlightening approach to finding overlap between the CGT and Classical Game Theory communities.  He attended a conference in the summer of 2013 at Stony Brook, a workshop on computational game theory.  Along with Aviezri and Sam Payne, he defined Economic-Combinatorial (EC) games.  In these games, there is a master combinatorial game, but before each turn the players play an economic game, the decider game, to determine who will make the next move.

The winner of the decider game (the decider) chooses who goes next on the master game.  For example, the two players could be competing in a game of Domineering, with the decider game as a chip-bidding game.  More generally, the decider game can be given as a payoff matrix and can include mixed strategies.  Then the overall game, the Strategic Game, can also be written as a bimatrix one-sum game, which can be solved using linear programming.

One pretty cool result of this analysis is that if there is a bidding game where only the winner spends their bid, then Red and Blue will have pure perfect strategies for the game!

Elan made some great comments about the work done in classical GT in computer science, especially interesting for me since I first presented Atropos at the Workshop on Internet Networks and Economics in 2007.  I got to see first-hand a lot of the really cool results in this field, and got a really good response after playing Atropos with that group!  (This reminds me that I need to get a JavaScript version up and running!)  Thane again had excellent words of wisdom for us, explaining that if we ever talk to someone new who says they work in game theory, the "probability they're part of our community is vanishingly small."

Svenja Huntemann wrapped up the talks with her investigation of game complexes and classification of games using their complexes.  She starts off by talking about (strong) placement games: games where a turn consists of placing a piece which will never be removed or moved, and where the order of moves doesn't matter.  This last point means that games such as Hex and Tic-Tac-Toe are not placement games.  (They can be catagorized as weak placement instead.)  This interchangeability of order allows the use of commutative algebra to analyze further!

The complexes use square-free monomials for each position, and then the edges and faces of these can be seen as either legal or illegal complexes on the graph with vertices as the variables.  Interestingly, for every simplical complex, there exists a ruleset and initial (empty) game board so that the complex is legal for that game.  Surprisingly (at least to me) the same is true of illegal complexes!  Svenja proposes investigating the same question for rulesets with more even more stringent properties. 

There is definitely lots of new exciting avenues for work, and that's true for lots of the talks I saw!  I'm really excited about how these different research directions will be tackled!

Afterwards, we again headed off to take part in some open working sessions.  Unlike Thursday, my group was able to get some new results!  Hooray!  I really liked working with people and I think a lot of new research connections were made between people that had maybe never met before.  This was a great event and I hope to attend CGTC2!

CGTC1 Day 2

First on today's program was Aline Parreau speaking about solving Ricochet Robots puzzles.  Although I've never played this game, I just recently learned of this game from two of my math colleagues at Plymouth State.  I will definitely be requesting them to bring that to game lunch this semester!  Aline and her team found bounds on the number of obstacles that needed to be placed into a grid for robots to visit each square, in both cases of passing through and actually being able to stop in the square.  She took the abstraction a bit further and introduced some bounds for tori (toruses?).

Mike Fisher described a game known as Stirling Shave.  In this game, imagine you have coins in a row.  On your turn, you choose one coin with value lower than all the coins to its right.  Then, you remove the coin and all coins on the right-hand side.  When playing this on a permutation list (instead of coins), he was able to evaluate normal and misere states by doing an interesting ordinal sum evaluation from right-to-left.

Mike's talk is the first time I've heard of tame misere rulesets.  Stirling Shave is tame because each position has either an option to 0 or to 1.  (Unless it has no options, I assume.)  Thane piped up, saying Mike's talk "gets the good housekeeping seal of approval," because Mike had taken the initiative to find the misere quotient monoid.  (I really don't know if I'm using all those terms correctly.)

Tristan Casenave gave a very interesting talk about improving Monte Carlo searches by employing an alpha-beta search to help choose the ordering of moves during evaluation.  When compared to iterative deepening with alpha-beta, this new tactic seems to work quite well!  Basically, the Monte Carlo tree search generates some results, then those numbers are used to order the moves to investigate with alpha-beta.  Indeed, this works for games other than Go, including Hex and NoGo.  I've been a bit curious, however, just how bad these algorithms are at impartial games, so I asked.  Tristan answered that he has a Nim MCTS player, and although he wasn't certain of his recollection of the results, he didn't remember being impressed.  I followed this up by asking about Arimaa, but the MCTS players are apparently not at a very good level there yet.

One interesting approximate stat that Tristan mentioned in response to a question is that Go programs seem to be improving at about the rate of 1 dan each year.  Pretty cool!

I spoke next about boolean formula games, which I also spoke about at Integers just over a year ago.  I don't think I've talked about that here yet; I should probably do that.

Paul Dorbec got up next and spoke about a graph domination game (called DOM-GAME).  This PSPACE complete game is a placement game where each player must choose a vertex that dominates a previously un-dominated vertex.  A collection of vertices dominates all the vertices in it as well as those adjacent to at least one of the collection.  This game is not impartial, however: one player is the dominator, the other the staller.  The dominator is trying to end the game quickly by dominating all the vertices.  The staller is trying to get the game to last as many moves as possible.  The "score" of the game is the total number of moves, so the dominator does better when they force a lower score.

Paul showed that the difference in scores based on which player goes first (and using best strategies, naturally) only differs by at most 1.  He defined a great term: a bluff.  A graph is a bluff for this game if all of your moves are equally good.  Thus you can "bluff" by pretending to handicap yourself and lett your opponent choose the first move.  Double bluffs, then, are graphs where the first two moves are both optimal, no matter where they are made.  In a general bluff game, it doesn't matter at all which move a player chooses at any point; all moves are always equivalent.  For example, that is the case if you play this on a graph with only singleton nodes (and no connections) or only pairs (each node is connected to exactly one other node).

Some open questions he left us with are:  Is this game PSPACE hard on trees?  Are there interesting graphs (probably meaning connected) that have a triple bluff?

Thane Plambeck rounded out the day by talking about some cool geometric Nim variants.  (Who doesn't want more variants of Nim?)  TacTix, invented by Piet Hein, is a misere-played game where there are tokens arranged in a grid.  Each turn the current player chooses a connected orthogonal line (segment) of tokens and removes them all.  Then, even further, in Nim-X you can include diagonal lines as well!  Thane showed the normal play and misere quotients to evaluate Nim-X endgames.  This was actually very helpful for me just as a review of how these quotients work to solve misere sums.  I still need more time to look at it.

In the afternoon we had some pretty deep working groups.  I joined a team interested in the (unknown?) computational complexity of Arc Kayles.  It seemed like something we could resolve, but so far we haven't figured it out.  I went back and forth on this, sometimes trying to show PSPACE hardness and other times trying to find a poly-time algorithm.  It continued to be unsolved on the trip to the dinner as well as our excellent walk back across Lisbon.  It is a really beautiful city to walk around!

That's all for today.  Tomorrow is the last full day; if I don't get a post up tomorrow night, it might not be getting posted until next week.

Happy Gaming!

CGTC1 Day 1

Today was a great day at the conference!  Bonus info: this is the first pure math workshop organized by Ludus, a Portugese organization that promotes math and holds outreach events for kids.  They're well-known for holding an annual game competition for middle schoolers that has regional and final-level parts.

A quick summary of today's talks:

Aviezri Fraenkel spoke about using alternative numeration systems to determine the complexities of games.  He noticed that he could express rulesets for Wythoff generalizations (extremely generalized, so generalizations of generalizations of generalizations of Wythoff) using a numeration system based on continuing fractions.  Aviezri used this to show that one class of games studied by Wei An Liu and Haiyan Li has a polynomial-time solution to differentiate between P and N positions.  Best quote by Aviezri: "33 years ago, I proved..."

Melissa Huggan spoke about Intersection-Restriction games.  She's been studying Arc Kayles, which is just like Node Kayles, except that players choose edges, which are removed along with their neighbors.  She's written code to analyze star graphs with three rays.  (The rays are not restricted to path of length 1; otherwise each star is just equal to *.)  She's also analyzing wheel graphs.  In arc Kayles, playing on a spoke of a wheel turns the graph into a path, while taking an edge on the rim turns it into something that resembles a pizza.

As Melissa said, it's "computationally expensive because we need all subpositions of the pizzas!"

After this, she showed some work on triple-packing and triple-overlapping games.  She has Grundy values for games played on {1, ..., n} up to n = 10.  She's very interested in continuing work on this, but for the 10 case the running time of her code jumped from 8 seconds to 17 minutes!  So far, her data matches the Grundy sequence of arc kayles on complete graphs.  (Edit: I originally read her table as 8 minutes to 17 hours, but I was corrected, and these are the correct times.)

Urban Larsson spoke on some new work on scoring games.  He mentioned the term "Galgemster", which is apparently a gamester who is more interested in algebra. :)

His talk concentrated on finding a subuniverse of scoring games that could be analyzed nicely.  He called these games Guaranteed.

Carlos Santos then spoke about Absolute CGT.  He wants to figure out analytical tools that will work for many universes of games: Normal-play, misere, and scoring games.  He defines the term CG space, which must have nice properties for recursion, order, an operation (e.g. disjunctive sum), and atomic positions.  With this definition, he is able to find "Absolute Theorems" which can then be applied to any space.

Thane was very excited about this joint work by Carlos and Urban and Richard Nowakowski.  As he said, "I love this talk!  Can I now talk, for, like, 30 seconds?"

Gabriel Renault spoke on comparison modulo sets of games.  Unfortunately I don't follow all the monad arguments well, but I did learn some new terms:

* A binary position is one in which each player has no more than one option (and all options are also binary).

* A dicot game is the same as an all-small position.  However, "dicot" is more commonly used under misere play.

Craig Tennenhouse then spoke about his joint work with me on games that use data structures, as described in an undergraduate CS data structures course.  He got lots of interest from people after describing Rotisserie Nim, which is Nim played on a queue.  We noticed that there's an optimal strategy to follow, but the strategy does not actually tell us the outcome class without simulating the entire game.

I played some more great games today!  I'm hoping to test out my Clobbineering skills again tonight!

CGTC1, Day 0

Arrived last night in Lisbon, traveling with Craig Tennenhouse from UNE for CGTC1: CGT Colloquium I.  It's great to see so many people I know and lots of new faces too.

Gathering with gamesters is dangerous.  Last night I chose games over sleep and stayed up a bit too late.  I did get in some games of Amazons (with three players), Clobbineering, Yavalath (also with 3), and FLex (Follow-the-Leader Hex).  Michael Fisher has some beautiful sets from Nestor Games.  Perfect for travel.  They're a bit expensive to get in the US, but they might be worth it!

I'm looking forward to Craig's talk today, as well as others.  Craig and I spent most of the time on the last flight feverishly trying to solve Rotisserie Nim, but it's not clear what our analysis will yield.

There's a chance that Clobbineering will be dubbed the official "game" of this conference.  We'll see!  It was certainly the first time Urban, Tristan, or Svenja had played it, but that keep me from losing most of my games.

After over a year, it's great to be back in the CGT action!