Extracting interest

kw: complexity theory, images, games, analysis

The Shannon Number, Claude Shannon's 1950 estimate of a lower bound on the number of possible games of chess, is 10¹²⁰. More recent estimates indicate the actual number is at least 10¹²³, or 1,000 times as large. This is interesting, in that there are "only" about 5x10⁴⁶ possible board positions. Each position has many possible next moves, so the branching at any point is quite dense.

Very, very few of these games are "good" games, meaning they show competent play, though this can be hard to discern. And whether competent or not, very very few are "interesting". For example, there are huge numbers of games that end abruptly with any of several "fools mate" positions, and a comprehensive computer search would no doubt uncover a great number of "total idiot's mate" positions. Then there are those that quickly lead to a stalemate. The number of possible "interesting" games is impossible to determine, but even if only one game in a quadrillion is interesting, that leaves 10¹⁰⁸ interesting games. Even the square root of this, 10⁵⁴, is a number greater than the number of games that will ever be played on Earth, prior to the loss of its oceans to solar heating about a billion years from now.

Around each possibly interesting game, there will be a number, perhaps a large number, of similar games, that differ by a move here or there, or a few moves taken in a different order, but that in the main cover the same ground and lead to the same final position. There will be a larger number of allied games that lead to a similar but not identical final position.

As I thought about this, I realized that such clusters of similar games are analogous to the cluster of similar images one can produce from any given image by manipulating a pixel here or there, or making wholesale, but subtle, changes. However, the number of possible images, even with a small number of pixels, is much greater than the number of chess games.

Consider this image, a 4x expansion of a familiar icon from Microsoft Windows. The format for these icons is 40x40 pixels, and depending on your screen mode, they can have one byte per pixel (256 colors) or three bytes per pixel (16,777,216 colors). Just one byte per pixel produces 256^1,600 possible images, with each possible color palette! That is 10^3,853. The full color version has 10^11,559 possible images. For this image, as for any other, changing the color of any particular pixel by a small amount has no visual effect. Although a computer vision system could immediately tell the difference, the human eye/brain cannot.

Even wholesale changes to the image, such as this shift to a lower gamma, are difficult to discern unless the two images are right next to one another. Let's consider a situation in which we watermark an image by adding one to certain pixel values, leaving the rest unchanged. There are 2^1,600, or 1.16x10⁷⁷, possible single bit-level changes in a 40x40 pixel image. If we allow adding 1, 2, or 3 to the low order bits of an arbitrary number of pixels, the number of possible changes for this two-bit-level watermark is the square of the first number, or 1.34x10¹⁵⁴, which is 13 quadrillion quadrillion times Shannon's Number. That is the number of effectively undetectable changes to an icon image that could be made. Actually, as other kinds of changes can be made, without visually detectable effect, the cluster of similar images about any given image is much, much larger.

We can try to extract what it is that makes the image
"interesting" by reducing the original image to a 2-level (1-bit) representation. It would take some tinkering to change this image so it looks more like the original, having complete outlines around the pages, for example. So even here, there is a cluster of variations on the theme.

The number of such 1-bit images is the same as the number of single-bit-level watermarks, about 10⁷⁷, and we can easily see that not all of those will be equally interesting. No matter. There is enough available complexity out there for us to keep devising new icons for the next billion years, without having examined more than a tiny fraction of the possible image space.

There is a lot of world out there. Given the level of complexity available just in a chess game on a board of 64 squares, or in a picture 40 pixels on a side, it is a wonder that anything ever repeats!