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!