What to chose (exam)

[Frosty]

in august I'll have to attend an exam for my last year of high school
and I'm expected to bring an essay about a subject of choice

my choice was Artificial intelligence and since I've been programming for a while
(C#,C,VB & various scripting languages) I'm thinking to add some kind of
practical example of what an AI looks like.
I never programmed in LISP but I'm going to use this project as a base to learn
but I'm not sure what should the program actually do.
I won't have much time but I'd like to write something that impress them
it doesn't have to look "good" from a programmer point of view (they won't know much
about the subject) it just need to have a nice impact on the audience

P.S. I'm doing this essay mainly for myself so it doesn't have to be simple, the harder the better (with limits)

[Warren Wilkinson]

AI is kind of a nebulous topic. Basically, any algorithm that produces behavior that resembles a thing a human might do is considered AI.
Here are some ideas.

1. How about a Maze generator? Then write the A* algorithm to solve the maze?
2. How about Huffman encoding? (basically, apply a simple compression algorithm to a user supplied text file). Knowledge representation could be construed as AI.
   
3. Any form of tree-search that involves a heuristic --- for example, a Chess playing AI (I think there is a line-protocol for talking with certain GUI chess programs).
4. Neural Networks (this would be math heavy...)
   
5. You could rebuild a ZORK like game. These can be suprisingly difficult because of combinatorial explosion of options. You'll learn which choices can be computed, what can be faked, and what has to be dealt with.
6. Any sort of chat bot.
   
7. Realistic landscape (or cityscape) generation? Basically you'd just use simple subdivision (or one of many other methods) to generate a height map. Then color the various heights Blue-->Sand Brown->Green-->Mountain-Brown->Snowy peaks. That gives a simple top-down view of a landscape. It wouldn't take much to get SDL into Lisp to do the GFX.
8. Color palette generation. A lot of weird models about how the human eye works go into this. You could write an AI program that has the user select some colors, and then it tries to generate a nice palette.
9. Pattern generation. Some AI tasks try to evolve nice patterns. This could use fractals to do so.
   
10. An equation solver that 'evolves' a solution. Basically, given a proper equation -- Lisp extracts the variables, and then builds a solution where each variable is assigned a value. Then you run an evolution algorithm on it and see if you can get a reasonable result.
    
11. A general purpose problem solver. Peter Norvig wrote one of these. The basic idea is a back-trackable computation. Certain states can only be entered given certain conditions. You specify the input state, and the output one, and the program tries to find some path through the states that leads from input to output.
    
12. Text DIFF -- Given two source texts -- decide on a minimal operations to transform the first to the second.