A better yodeling contest

Recently Friedman and Landsberg's experimental results on certain scaling properties in the game chomp has been featured in Science News. (See another take on their work at bit-player.) It has been noted that the classic combinatorial game nim seems to have a "rougher", easier to analyze structure than the "smooth" structure of more complicated games like chomp. In a similar vein, an interesting tidbit is that the limit
\[
\lim_{n\to\infty}\frac{f(\lambda^nx,\lambda^ny)}{\lambda^n}
\]
exists for all integer choices of $\lambda$, $x$, and $y$ if $f$ is the function giving the value of two-rowed chomp positions; whereas if $f$ is the value of two nim heaps, the only values of $\lambda$ which work for all $x$, $y$ are the powers of two.

So, I thought it would be interesting to graph the difference between $f(\lambda x,\lambda y)$ and $\lambda f(x,y)$ for these different functions. There are at least two different ways of taking the difference between two nim-values: simply interpret them as integers and subtract one from the other, or use what is here the more natural operation of nim addition, conveniently provided directly by most CPU's and implemented in C-style languages as the operator "^" - that's right: binary XOR.

Of course, what would be really interesting is whether this kind of scaling behavior extends to more than two dimensions, but I figured that as long as I am getting pretty pictures for 2D scaling, I have a duty to share them.

First up is a look at two heap nim, compared using XOR. Click on the image to download a MPEG movie (warning: each is 3Mb for just a few seconds of video) showing the box with x and y up to 256, for $\lambda<512$. Here black is zero difference, and white is maximum difference in that frame. Notice the many scaling properties associated with the powers of two in both space and time. I believe I have seen this basic idea used in screensavers before, which is appropriate since it is extremely fast.

view - download

Next, comparison using simple subtraction. If the quanitities are equal, they are displayed as black, grayscale representing the absolute difference between them, up to white as the maximum difference.

view - download

Chomp in general exhibits much smoother behavior in terms of time and space. However, the qualitative behavior is quite different depending on whether $\lambda$ is even or odd, so I've separated the data into two movies - the first has all even frames up to 1024 (with unfortunate compression artifacts: the vertical stripes), the second has all odd ones. Notice how the image seems to retract smoothly towards (0,0). (Technical note: I prefer to use "absolute" coordinates for chomp, since these generalize readily to arbitrary poset games, whereas the relativized ones which are frequently encountered in the literature do not do so in any obvious way. Thus, each horizontal line in the top right of the images below actually represents only one distinct position.)

view - download

view - download

When comparing using subtraction for chomp, the scaling is so smooth we don't even need videos! There are only two qualitatively distinct frames depending on whether $\lambda$ is even or odd:

The fact of the matter is most of this is mathematically trivial, even if cool-looking. The next step is to take a look at scaling behaviors on different poset games and for dimensions 3 and more.

This entry was posted on Tuesday, September 5th, 2006 at 11.29 am and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.