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:

In keeping with the theme of compression, I leave this post abbreviated.