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".