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!

It's only the Moon - your move

kw: book reviews, science fiction, games

I have never been much of a gamer, particularly not role-playing games (RPG's) so it paid little attention to the gaming portrayed in The Moon Maze Game by Larry Niven and Steven Barnes. So why read the book at all? you may ask. I'll read anything by Larry Niven. He is always full of interesting new ideas, and this book doesn't disappoint.

The setting is the Moon, in 2084, and not only is the Moon getting pretty well colonized, so are the L5 point and certain asteroids. Computer power and virtual reality gear are very advanced, making full-surround, live-action gaming affordable. Many effects rely on projected holography, which is still technologically far, far beyond known capabilities…but it makes for a good yarn.

On this future Moon, certain people with tons of money have contracted to convert a domed crater into a gaming arena. One of the gamers is an African prince, and when this becomes known to certain Lunar denizens, a plot is hatched to kidnap him and force his father to abdicate in favor of a democratic government. The actual kidnapping is to be carried out by a band of mercenaries who hire out to do high-profile, high-stakes kidnapping.

There are typically two ways to portray villains. One way is as ciphers with simple motive and unalloyed evil intent, black boxes that churn out evil. Another is as complex personalities made known to us by large sections of stream-of-consciousness, yet also primarily evil. Niven and Barnes take a different tack. There is a little window here and there into the thinking and motivations of the four main perpetrators, but they are portrayed with sufficient sympathy that the reader is torn, not quite willing to hate them properly. The characters of the gamers and others who find themselves embattled by the kidnapping and its aftermath add to the richness of the psychological milieu.

I don't know enough about gaming to have much of an opinion. I assume real gamers will drool over the prospect of full-immersion role play that the book offers. The game setting is a purported sequel to the fiction of H. G. Wells, particularly his Moon and Mars stories: Steampunk on steroids!

I'll leave the plot for the reader to ferret out. A number of Lunar characteristics portrayed show how the authors have thought them through. For example, taking a shower, then waiting for the water to drip off before toweling could take a long, long time. Thus, something like the strigil (a blunt, curved scraping blade used in ancient Rome) is posited to remove most of the water more quickly. The low gravity also allows muscle-powered flight using apparatus much smaller than the Gossamer Condor, and this is taken advantage of at one crucial point. So is brachiation. Tarzan might have swung through the jungle like an ape, but an actual human can only brachiate for a few swings before risking a shoulder separation. On the moon, it is almost easy. A little bit is offered about low-G fighting, but so little is actually known that the authors wisely keep it short.

In spite of my unfamiliarity with the gaming aspects, the authors explain enough (sometimes almost too much) that I could keep up. It is quite a gripping adventure.

Now, I wonder, will we really have a colony on the moon in only another 73 years? It will require another generation to arise with stars in their eyes, a confidence in our ability to conquer any barrier, and a willingness to risk that is presently almost absent among the world's peoples, particularly the American public. About a quarter of the world's population is too comfortable and yet too anxious, while the rest is too poor to imagine big things. If this doesn't change, 2084 will come and go with nobody Moon-side to dome up a crater, fill it with air, and strap on wings.

A stern chase is long

kw: games

About three hundred games ago, my standing in Spider Solitaire was 29%. I found that the calculation is truncated, but dividing the wins by the total games, it was still below 29.5% I entertained hopes of raising it to 30% or higher. Two friends have both said that whenever their cumulative percentage drops below 30%, they delete the stats and start over. I thought I'd find out if I can win at a rate sufficiently higher than 30%, to raise the average "the hard way".

As this screen shot shows, I've won 349 out of 1121 games since getting this computer, for an average of 31.13%. Calculating the marginal win rate, I've won about 35% of the past 300 games to get here.

If I continue to win at a 35% rate, I will need to play another 324 games to reach 32%, 1,047 games to reach 33%, and 3,214 games to reach 34%. I'll never reach a long-term average of 35% unless I learn to play better. I suspect that no more than 40% to 50% of Spider Solitaire games are winnable by any strategy. Some contend that all could be won with the right strategy, but this is not so: The drop of the cards in a deal can shut you out from all possible moves, and if that occurs on the last deal, the game is guaranteed a no-win. I'm pretty pleased with 31%.

Spider rating

kw: games, achievements

A few days ago, in this post, I noted that my win/loss ratio for the XP version of Spider Cell was 25.2%. The Windows 7 version may be just a tad easier, or I'm learning more tricks. This clip from the Games menu shows that I've played 939 games and won 30% of them. In precise terms, 282/939 = 0.30032, so it is just barely 30%. Ha! I'll take it!

By the way, this is for the Intermediate version, as the image shows. It is the only version I've played. I know one person who only plays the Advanced version, the one with all four suits. He says he wins a game from time to time, but well below 10%. On the other hand, I don't know anyone who plays the Beginner version the most. There is a certain level of frustration that each of us can bear, and we gravitate accordingly.

Imperfect Spider wins and losses

kw: games, statistical distributions

During the last year that I had a computer running Windows XP I kept statistics for 670 Spider Cell games. I won 169 of the games, or 25.2%. I have not yet kept any statistics for the Windows 7 version, but the program reports that I have won 29%. Perhaps this version is easier, or perhaps I am just temporarily ahead of the curve. Also, it may be that keeping the statistics interrupted the flow of play enough that I didn't play as well.

I gathered these statistics to see what the probabilities are for games of various length. The shortest possible winning game is 96 moves. Though there is no longest possible game, because you can use useless moves to inflate the numbers, I used rational rules of play to avoid making extra moves.

Of the games I won, the final tally ranged from 112 to 165, with a mean value of 140. This chart shows that the tallies are normally distributed, with a standard deviation of 11. That means that the intercept at a tally of 96 is at a standard deviation of -4.0. Thus I would expect a game in the 96 range about once per 31,600 winning games. At the rate I win, I might see such a score if I played about 120,000 games. The lowest tally I've seen is 108. That is at 2.9 sigmas, or once per 536 wins.

The statistics on losing are equally interesting. The most likely circumstance is just moving cards about and getting no suits to "complete". Generally, if you can get four suits completed, you will win, and I consider getting five completed means winning is assured, but I've had two games that had five completed suits, yet no win was possible. A statistical chart of losing games, charted by completed suits, is no surprise:

The more suits you complete, the more likely you are to be able to play longer, because typically more cards get uncovered. Note that my shortest game tallies 25 moves. There were two deals of six for which no move was possible. The shortest possible game is 0 moves, but that would require all the deals to be stonewalls, with no possible moves.

Though there is a little curvature to these distributions in line-normal space, we can estimate how likely such a situation is. Zero-deck games are nearly normally distributed with an average of 54 and a standard deviation of 13. This intersects zero at -4.15, meaning once each 60,000 zero-deck games. Such games make up about 45% of all games, so again, it would take playing about 120,000 games to have much chance of seeing a total tally near zero. The negative curvature of the line hints that this estimate may be very optimistic!

Well, I've certainly spent a lot of time gathering these data. Analyzing them has been fun. At the moment I don't expect to gather more statistics. I got different kinds of irons in the fire at present.

Cheating at crosswords

kw: observations, games, puzzles

Most days of the week, I work the puzzles in the newspaper. The main three, Sudoku, a Cryptogram, and a Crossword, increase in difficulty through the week. I can usually do the Cryptogram and the Sudoku any day of the week, though the techniques differ as the week progresses. I can usually do all the Crosswords except Saturday (I don't even try on Sunday, when they use an oversize NY Times puzzle), though in recent weeks I have often been able to complete a Saturday Crossword also.

Today I got halfway done with the Crossword and got stuck. All the key clues to the remaining sections were societal references that meant nothing to me. I guess I don't get out enough! This movie star, that 1965 Nobel prize winner, some composer. Well! I had the computer handy, so I looked a couple things up. Pretty soon, I'd gathered enough of the social clues to finish the puzzle. But, it just isn't as satisfying as finishing a puzzle by memory and wit alone.

Four-legged race

kw: holidays, games, observations

New Year's Eve there was game night at our church, an event we've carried on for about ten years. We spend from 7-8:30 pm eating a potluck dinner, then play games until nearly midnight. We stop just in time for a little prayer before the stroke of midnight. The congregation is small, so we prepare games suitable for forty or fewer people.

A favorite is Big Wind Blows, sometimes called Where the Wind Blows. The usual version starts with, say 30 people and 29 chairs, with someone standing in the middle. The person in the middle calls out, "Big Wind Blows!"

Everyone asks, "Blows where?"

Suppose the reply is, "Everyone wearing a sweater." Then only those wearing a sweater have to find a new seat and the "middle" person tries to get one. The person who fails to find a seat is now in the middle and play resumes. We can do this for an hour, easily.

A variation is to use locations, either positively or negatively. For example, the "middle" may say, "I once went to Florida." Then everyone who has visited Florida must find a new seat. Conversely, if "middle" says, "I have never been to Virginia", then only those who have not visited Virginia (even passing through) try to find new seats.

One event was the Three-Legged Race, but some of the kids decided to run in threes, with the person in the middle having both legs tied to the other kids; a Four-Legged Race. Once they figured it out, the trick was this: They decide which leg the person in the middle will move first, either right or left. Then the other two have to move their opposite leg. That way they start out coordinated. They have to follow the lead of the middle person.

Here are three of the boys practicing. Because the middle boy is the smallest, they tried simply picking him up between them and both running. It worked after a fashion, but we ruled that it violated the spirit of the game.

Once you know how to coordinate, it can be done with any number of persons tied together, but Four-Legged seems to be the most fun with the least falling down. One team of girls fell down no matter what they tried.

We also did quieter games, like 20 Questions, with Team A versus Team B, calling out alternate questions, but about a different answer for each team. You have to keep on your mental toes!