Supercomputing and Thanksgiving, Back Next Week

Last week I came down with an unexpected case of Lack-of-Wireless-Internet-Access while at the Supercomputing 2012 conference.  Unfortunately, I think this is more a case of my own machine having trouble than lack of access provided at the conference.  The result (as far as you care) is that there is no post for last week.

This week is American Thanksgiving, so I will probably not have something for you on Thursday.

Posts resume next week for the last two weeks of the semester. :)

Succinct Games

One year ago, at Integers 2011, Carlos Santos presented his awesome result about Konane and short games: any possible short game value can be realized as a Konane position.  This seemed like a tremendous result to me, but to be sure, I asked Neil McKay whether there were any other known games with this property.  He responded: "Yes, 'Tree'."

"What's th-... oh." is probably something similar to what I actually said.  "Tree" is just the ruleset where any position is the root of a game tree.  He was entirely correct, of course, because any other position in a short game can be represented by that position's game tree.  It wasn't until later that I realized why this answer wasn't satisfying.

I wanted a Succinct Game. 

I've been very informal so far.  The word "game" is dangerous, as it is often used to either mean a position in a game or (maybe more common) a ruleset to determine what the next possible move options for either player are.  A ruleset is actually a pair of functions, say f_L and f_R, each of which takes a position and returns all the options for Left or Right respectively.  What I meant earlier is that I wanted a Succinct Ruleset.  This means that the positions can be described with a small amount of information.  More rigorously: less than proportional to the size of the game tree.

Tree does not fit this definition, since the input positions have to contain a description of the entire game tree.  To know what to do next, the entire game tree needs to be represented, which can certainly have variable size.  The Konane ruleset, on the other hand, just explains what the possible moves are based on where the stones are.  It does not require a description that has each input-output pair "hardcoded". 

I'm probably revealing my computational background again.  What I am actually saying is: I know that I can write a succinct program representing the function pair for rulesets such as Konane.

So, the revised question is: Are there any other succinct rulesets that have possible positions for any short game value?  Errr.... short ruleset value.  (Avoiding "game" is hard!)

Postscript note: my industrious aide Ernie found that economic game theory uses the term Succinct Game to refer to the analagous property!  This is not too surprising, since this is exactly how succinct is used: there is a way to more concisely describe a system by using a program to determine the "state".

Graphs for Graph Games

There are lots of fun graph games: Kayles, Col, Snort, etc.  When people go to play these games, how do you decide which graph to use?  How does that work?  Does anyone know of any good graph generators for combinatorial games?

One could consider the game Fjords as a graph game, with some vertices initially painted red and others blue.  Then on your turn, you paint an uncolored vertex that is adjacent to a vertex already containing your color.  This is the game you play during the second stage of Fjords.  The first stage is a longer, somewhat random process that creates the graph and assigns the initial colors.  This stage does require the players to make decisions and is likely the "more fun" part of the game. 

How else can graphs-for-games be generated?  What other board games have processes like this?