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!