CPSC 120: Principles of Computer Science
Fall 2002Lab 13: Genetic Algorithm / AI and Language
In today's lab, you will look briefly at two very different types of artificial intelligence. Do this lab using Internet Explorer under Windows. There are no files for you to save, and there is no need to use your Linux account. You should write a short essay for each of the two Exercises. Turn in your answers at the end of the lab.
A Genetic Algorithms Demo
The Genetic Algorithm applies ideas from biological evolution to problem solving on a computer. Evolution is a kind of "learning" in which the knowledge or abilities of a population improve over time. In this lab, you will look at a demo of the Genetic Algorithm in which a population of simulated organisms evolves over a series of generations. You can run the demo applet by clicking this button:
(For a more detailed explanation of what this applet does, see http://math.hws.edu/xJava/GA/.)
Start up the applet and let it run for a while. You'll see red "Eaters" that can move around in an environment eating green "Plants". Each Eater is very much like a Turing machine. It has an internal state which is represented by a number from 0 to 15. It can "see" the item that is directly in front of it. This item can be either a Plant, another Eater, an empty space, or a wall. At each time step, the Eater makes a move. It can move backwards, move forwards, rotate 90 degrees left, or rotate 90 degrees right. It bases its move entirely on its current internal state and on the item that it sees in front of itself. At the same time, it can change its internal state. Whenever an Eater moves onto a spot that contains a Plant, it eats the plant. At the end of each "year" (250 moves), the Eaters reproduce. Eaters that have eaten more plants have a better chance or reproducing. During the reproduction, there can be mutations in the Eater's rules. This can introduce new behaviors. There can also be genetic recombination ("sex") in which an offspring inherits its rules from two parents instead of one.
The results of all this is that the population of Eaters tends to get better at eating. Even though no individual Eater learns anything during its life, the population as a whole does seem to learn. It might even be called creative in a certain sense, because the behaviors that develop in the population were not programmed in. On the other hand, there are definite limits to what the Eaters can do. No Eater, for example, will ever be able to see what is behind it, and they will never be able to increase the number of their internal states.
Watch the applet for a number of generations. You will see that the Eaters seem to learn new behaviors (such as moving forwards) that make them better at finding and eating plants. A Statistics window shows the average number of plants eaten by each Eater in a given generation. This number will tend to increase with time, as the Eaters learn new behaviors. If you see a star next to one of these numbers, it means that that's the best average seen so far. When you see a few asterisks in a row, it's a good bet that the Eaters have "learned" something new. You can speed up the process by setting the "Speed" menu to "Fastest". At this speed, the world is not drawn, so time goes by very quickly. You can switch back to a slower speed to see how the latest generation of Eaters is behaving.
The "World Design" menu lets you change characteristics of the world. After watching the original world for a while -- and maybe playing with some of the parameters in the "World Design" menu -- set up the following "world": Start from the default settings. (If you've changed some of the settings, close the World window and open a new one.) Then, in the World Design menu:
- Change the "Plants Grow" setting to "In Rows".
- Change the "Approximate Population" to 30.
- Change the "Mutation Probability" to 0.25%.
I have found these settings to have a good probability of leading to interesting and well-defined behaviors over the long term. You can watch for a while and then maybe let it run at fastest speed while you do other things. Look back later, after a few thousand generations, to see what the Eaters have learned.
Exercise 1: What did you observe when you ran the Genetic Algorithms Demo? When you used the settings given above and let the world run for a large number of generations, what behaviors did the populations of Eaters develop? (Give some specific examples of behaviors.) Would you say that there was any real learning or creativity? Why or why not?
Meet Eliza
"Eliza" is one of the most famous programs in the history of artificial intelligence. It is a simple natural language processing program that can hold conversations with a user. The program attempts to imitate a psychologist, and it offers to help you with whatever your problem is. There have been reports of some people who found the program helpful and were sure that the program really understood them! Try it for yourself here:
In fact, Eliza is not really an AI program in the true sense at all. It looks for some key words such as "computer" in the user's input, and it can do some simple transformations of the user's input sentences. To this, it adds some randomness in its responses. There is no real attempt to represent the meaning of the user's input.
(This version of the Eliza program comes from http://chayden.net/eliza/Eliza.shtml. I also found another simple converstation applet at http://romahi.com/yazann/Mitbolel/Mitbolel.html. For a more realistic version, go to http://www.alicebot.org/ and click on the "Talk to A.L.I.C.E" link under "Features".
A Machine Translation Demo
In the essential science fiction trilogy, The Hitchhikers Guide to the Galaxy, Arthur Dent encounters the "Babel Fish", a small fish that creatures all over the galaxy stick in their ears. The Babel Fish instantly translates speech in any language. Someone with a Babel Fish in his, her, or its ear can understand any language.
In the real world, the BabelFish translation engine is an advanced machine translation system. It can be found at
The translator will attempt to translate between English and several other languages. There are two ways to use it: You can select the "Text" option and type some text into the box. Select the type of translation you want, such as "English to Chinese" or "Italian to English". Click the "Translate" button. The BabelFish translation will be shown at the top of the next page. Alternatively, you can select the "Website" option and enter the URL for a Web site, such as http://math.hws.edu/eck/cs120/. Select the type of translation you want. When you click the "Translate" button, you'll get a translation of that Web page. (If the page is very long, only part of it will be translated.) Be patient! It might take a little while to get a response.
Here are some things you can try:
- If you know one of the non-English languages that are available, try translating some text or an English Web page into that language. (This will work even for languages that use non-English alphabets, such as Chinese and Korean.)
- Try translating a Web page in some other language into English. You might want to start with the German, French, Spanish, or Italian editions of Yahoo, which you can find at http://de.yahoo.com, http://fr.yahoo.com, http://es.yahoo.com, and http://it.yahoo.com. Note that a link on a translated page will take you to another translated page.
- A classic test of machine translation is to translate something from English into another language and then back to English. Try it. Note that after the first translation, you can just cut and paste the translation into the text input box to do the reverse translation. Don't forget to change the translation type in the pop-up menu. Try this for English-to-Chinese-to-English. (A common but unlikely story has "The vodka is good, but the meat is bad" being translated into Russian and back. Supposedly, the result was "The spirit is willing, but the flesh is weak.")
Exercise 2: What is your reaction to the natural language processing abilities of the Eliza and BableFish programs? Do you think that Eliza understands you? What do your think of the current state of machine translation, as displayed by BableFish? BabelFish is immensely more complicated than Eliza. Does it understand the text it translates? How good a job does it do with translations? Comment on some of the specific translations that you found.