Incompressible
While my main intent is to design games that are played by writing programs, I have considered a few game types that illustrate the operation of certain algorithms. Imagine enhancing any existing type of game with a scoring system based on the "originality" of the player's performance. Concretely, say that you would score fewer points for repeating the same solution every time you encounter a particular type of obstacle. The game could keep track of this by forming a statistical model of what it knows about the player's play style, and thus at each decision point it would assign a score based on how unexpected the decision was (say, oh, log 1/p). If this sounds like data compression, that's just what it is.
I imagine the data stream describing the player's actions showing up at the bottom of the screen, along with its translation into compressed data. Along with the more complex entropy coding mentioned above, simpler things like RLE and LZ77 can be used. A graphical representation of when the game last saw a backreference would be interesting. Watching a Huffman tree get built, or a range coding narrowing down, might be instructional. You might receive a bonus for getting the compressor to exceed the uncompressed data size, if you can generate a pathological dataset. Combining this scoring system with the requirement that you actually complete the level as well could prove interesting.
Many issues give me pause, however:
- What kind of data is the algorithm actually dealing with? Is it just the player's input? Analog or digital? Is it sampled every frame? Is it some higher level representation of a "move"? Perhaps taking into account the level context? Would "useless" movements be filtered out?
- If there is only a small set of symbols, say the cardinal directions, which would only require 2 bits, then it is unlikely that the game is going to achieve significant compression (at least with Huffman coding's limitations). But what more could we provide? Will the "words" of stereotyped motions be enough redundancy to give the game a fighting chance?
- How much data can we fit on the screen at once in a way that can be useful to the player?
- Should we attempt to describe the algorithms? Just watching them at work may be puzzling.
In keeping with the theme of compression, I leave this post abbreviated.