## Friday, November 9, 2012

### 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 fL and fR, 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".

1. Where can I find more information on the Konane result? A quick Google search only turns up information about the talk, but not any details of it itself. Apparently it is "generalized" Konane, but I cannot find anything on its rulset.

2. Also, I have a ruleset I came up with for a game played on graphs that I highly suspect is succinet. I can make any number, nimber, switch-value, and tiny/miny value with it, but I don't know how to proceed from there to prove further values.

3. Mingy,

I think that Carlos Santos' paper has not yet been published. I'm not sure that the publication from Integers 2011 is out, though I could certainly be wrong.

I do know that the "generalization" of Konane allows two pieces of the same color to occupy adjacent boxes. This is not the case in traditional Konane.

I don't know much about proving the habitat of a game, but it must be a very interesting research direction!

4. Hi

The paper will appear in next GONC. It was presented in BIRS (fist time). But i can send you the paper if you want.

Best, Carlos Santos

1. I would love to read the paper. My email is mjongo@gmail.com