ISIS
Information Science & Information Studies Program.
Computer Science
Visual Studies
72

Fall 2011 Calendar
subject to change...

ALiCE: Artificial Life,
Culture & Evolution

Simulating complexity with multiagent and evolutionary computation

30 August

Introductions...

Video: Karl Sims' "Evolved Virtual Creatures."
Video: Boston Dynamics "Big Dog."

Handout: Guide to Embarcadero C++ Builder IDE, Windows API, and C++.

We jump right in to programming!
Programming Challenge 0: The Chaos Game / Saga of the Indecisive Travellers
Building an application from scratch.
Tool palette, object inspector, Forms, PaintBoxes.
Object properties and events.
We use MouseDown to establish and display the locations of the cities...

1 September

Introduction
Videos: Karl Sims' " Panspermia"
Boston Dynamics' "Big Dog" and friends...

We continue programming...
Programming Challenge 0: The Chaos Game / Saga of the Indecisive Travellers
Insuring that your application will run on any PC (unchecking 3 RTL boxes).
We declare and define global variables.
We declare and define a function "run".
We declare and define a function "reset".
We write the principal algorithm, i.e. "how to choose a destination and travel half-way there."
We add a "Reset" button to initialize the variables and clear the screen.
We implement an array to record the "settlement pattern" produced (i.e. the number of hits on each cell).
We visualize the "settlement pattern" by pasting in the "colorRamp()" function.

Assignment for over-the-weekend:
What can we do to better understand the complex global pattern which has emerged from repitition of this simple local rule? How can we tweak or play with the application to investigate emergence?

6 September

Purchase:
12 burnable CDs.
12 clear-front envelopes for CDs.
Pen which will write on CDs.
12 sleeves for letter-size paper.
1 USB memory stick.

Programming Challenge 0: The Chaos Game / Saga of the Indecisive Travellers
Continued...
Execution of the program constructs a topographic landscape.
How would we visualize a landscape? Let's do that for our array.
What is going on that we're not seeing? Let's try color and shading.
Sonification, for aural confirmation of user input, of program execution and for revealing patterns in the topographic array. Can a fractal image be turned into a fractal musical composition?
Will sonification provide an alternative way of comprehending the pattern?

Quiz Tomorrow, Thursday...
Make sure to bring a CD or two...

8 September

Quiz today: To build an application from scratch. I'll tell you what I want you to simulate when you get here. It will be a much simpler problem than the Chaos Game. I'll need for you to burn your entire Project folder onto a CD and turn it in, in an envelope.

Programming Challenge 0: The Chaos Game / Saga of the Indecisive Travellers
Continued...
We implement:
Reverse coloring & faux shadows.
We consider:
Changing a target every now and then.
Implementing a third dimension: 3D

Drop/Add ends tomorrow...

13 September

Programming Challenge 0: The Chaos Game / Saga of the Indecisive Travellers
DUE TODAY before class
Go here for the format for the challenges.
Participant presentations (everyone)...

An introduction to Cellular Automata:

Programming Challenge 1: Cellular Automata / Conway's Game of Life
We begin building the GUI for Conway's GOL:
thisWorld[][], nextWorld[][] and initialize()

"A Full-Text Visualization of the Iraq War Logs."
Investigate the other visualizations, and for the one illustrated above keep clicking on the image
that appears on each successive URL until you get to the huge legible one.

15 September

Quiz 1 (due this coming Tuesday):
Turn this in as you would any challenge.
Write me an application that picks a card at random from a deck of 52.
It can identify the cards 3 through 10 by number, but the Ace, Deuce, Jack, King, Queen
and the suits (Hearts, Clubs, Diamonds, Spades) must be identified by name.
To output a string, simply put it in quotes (e.g. "Ace").

Programming Challenge 1: Cellular Automata / Conway's Game of Life
We continue building Conway's GOL:
run(), step(), stop(), computeNextWorld(),
copyNextWorldToThisWorld(), countNeighbors(), wrap(),
>showThisWorld(), OnMouseDown()...
Implementing parallel (cinematic) time; implementing toroidal cellular space.
Implementing the rules: computeNextWorld() and the functions it relies upon.
Speeding things up: renderChanges()

This challenge includes experimenting on Conway's world.
Specifically, I want you to characterize the ecology and ethology of the creatures in the GOL:
What is the relative proportion of different creatures spontaneously created from a random world?
How do they behave when single neighboring cells change state? What is the nature of each of those creatures?. Yes, I want you to include this information in the papers you hand in.

20 September

Quiz 1 (due this coming Tuesday):
Due at the beginning of class.

Exploring the power of Conway's world:
Is there any limit to the processes we can build in a GOL world? How about a "computer" that counts out decimal digits? What we will be looking at is a computer (a digital counter) running on a computer (the Game of Life Cellular Automaton) which is running on a computer (the PC in front of you) which is running on a computer (the computational universe we live withing, or the "Other").

Visualizing the ongoing "evolution" of Conway's worle:
Coloring "births."
Coloring "deaths."
Tracking populations growth and decline.

Given one state of a cellular automaton, for instance Conway's Game of Life, can we retrodict the previous states that gave rise to it? Can the Game of Life be used to recognize your passwords without remembering what they are? Can it serve as a "trap-door function?"

Programming Challenge 1: Cellular Automata / Conway's Game of Life
We continue optimizing the application with some minor changes:
Replacing the w() (wrap) function with a modular divide "%".
Showing "iterations" in the Edit box.
Streamlining "computeNextWorld()" by introducing the variable "livingNeighbors" and changing the function with that name to "countLivingNeighbors()".
Inserting "randomize()".
We introduce some enhanced functionality:
save() and open() functions.

22 September

Discursive Challenge 0: Cellular Automata / Conway's Game of Life
DUE TUESDAY
Does the GOL have any epistemological significance, any relevance to knowing our own world? As the GOL becomes stable and calm, are its objects static? Or are they in a continuous process of dynamic re-creation? The objects ("creatures") in the GOL are not evident in the "code;" they only "come into being" as the code is run. There is no way to predict a future state of this system other than to run the computation to its completion. Here we have a canonical example of "emergent complexity." Are the "objects" in our world, the patterns that we observe in daily life, equally emergent? These are some of the issues explored by Ed Fredkin in his article "A New Cosmogony" which is on our BLACKBOARD Course Documents page. Please reread Marvin Minsky's "Public Lecture, Nara, Japan" and "A New Cosmogony" on our BLACKBOARD pages and address the questions in this paragraph and on the first FORUM on our DISCUSSION BOARD. Have fun, but take these ideas seriously...

Mirek's Cellebration...
Under "Classroom Applications" on your desktop,
or surf the web and download it on your own computer

Programming Challenge 1: Cellular Automata / Conway's Game of Life
An afterthought:
We should reset iterations to 0 and display it after we Open a file.
We continue enhancing the application:
What tweaks would you suggest?

1. Find the intitial configuration of the world that runs the longest before it becomes stable?
   How many initial configurations are there? 2^10,000 or 2 x 10^3,010? The age of the Universe is 4.33 x 10^17 seconds.
   The fastest computer runs at 8.162 petaflops or 8.162 x 10^15 floating point operations per second.
   Running at this speed since the origin of the Universe, this machine could construct only 3.53 x 10^33 initial conditions, much less run them to completion.
2. Importing "creatures" into the world.
3. Implementing a "creature counter."
4. Can we add a "midiRamp()" function to give us an audible "image" of how the world is progressing? How would we have to scale it?
5. How might we evolve a bitmap image using a cellular automaton?

27 September

More work on Conway's Game of Life...

29 September

Programming Challenge 1: Cellular Automata / Conway's Game of Life
Classroom presentations due today!

Programming Challenge 2: Evolutionar Computation - An Introduction
An overview from the user's perspective.
An "underview" (a look "under the hood") from the programmer's perspective.

Discussion Board Forum #2: Evolutionar Computation - DUE TUESDAY
In light of today's introduction, and your readings, propose a problem which we might solve using one or more of the methods of evolutionary computation.

4 October

Video:
U-571 Bonus material:
Third screen: Capturing the U-505 (5 min)
Second screen: Britain captures the U-110 (9 min)
Second screen: Inside the Enigma with David Kahn (8 min)

Hands-On Exercise:
Working with the NEMA, a Swiss improvement on the German Enigma.

Discussion Board Forum #2: Evolutionar Computation - DUE TODAY
In-class discussion of possible ideas, to which these may be added:

1. * 3D: Example on our pages...
2. * Escape from a room: Example on our pages...
3. * Melody: Example on our pages...
4. Art: (Pixels[][], LineTo(), MoveTo(), Ellipse(), Rectangle()...
5. Unscrambling scrambled columns in an image: This might be quite interesting and dooable. One would need to import a bitmap image of a convenient size and copy its red, green and blue pixel values into an array. The in we swap columns randomly we sould end up with a scrambled image. If we handle the order of columns in the same way we handled the order if cities in the ECT we would be 80% of the way there. How would we measure fitness of each "solution" to the ordering? By measuring the degree to which the rows of colors match those of adjacent columns. This measure could include all the rows of all the columns, or we might try to limit the number of rows that determine fitness. What if we tried only one? Is one sufficient to rearrange the picture? How many does it take? If all of that worked, would it be possible to scramble all the rows and pixels of a photograph and rearrange the image?
6. Sudoku...
7. Shooting a mortar at a Ferris wheel...
8. Knight's tour in chess...
9. Crossword puzzle filler...
10. Steering through a maze...
11. Billiards, pool...
12. Positioning two creatures for the longes running GOL...
13. Balancing a pole on a railway flatcar...
14. Tweaks on the ECT...

Programming Challenge 2: Evolutionary Computation - An Introduction
Getting into the code... Let's hear some ideas on how to tweak the ECT.
"Sweet spots" in the code:
Border Crossing - lines 586-744.
Additional Constraints - lines 817-883.
Sort for shortest path - lines 483ff.
Sort for longest path - lines 510ff.

6 October

Video:
ENIGMA, Screenplay by Tom Stoppard (119 min)

Short Written Report: Alan Turing and the Enigma - DUE THURSDAY
I will leave it to each of you, individually, to write about some topic raised by the movie ENIGMA. Investigate some aspect of the cryptanalysis of the Enigma, the Polish Bomba, the British Bombe and/or the American Bombe, the machines, the methods and/or the persons involved. There are many places on the Web devoted to this story. Wikipedia contains some good articles on the British and American "Bombe," the Polish "Bomba," "Cryptanalysis of the Enigma," "Alan Turing," etc. Pick a topic, investigate it, and write a short report on paper to turn in on Thursday.

Discussion Board Forum #3: Evolutionar Computation - DUE THURSDAY
Unless you can see your way to writing a different evolutionary application, focus on the ECT. Now is the time to get into specifics. Give your discussion a title that will give others an indication of what you are trying to do. Spell out the additional variables, program code and functions you will need to make this happen. Post it...

For any evolutionary problem:

1. How would you represent the problem?
2. How would you represent a single solution?
3. How would you produce variation in inheritance?
4. How would you measure and implement fitness?

For the ECT in particular, what more can we do with what we've got? We already have:

1. Different types of places: houses, gas stations, hotels, restaurants, cities....
2. Different bounded regions: countries, swamps, ethnic areas, political regions....
3. The X and Y positions of each place so we can specify any path geometry...
4. a 3D Version but without the added features of the 2d version...

Some ideas for the ECT might include:

1. Alternating between east and west movement...
2. Penalizing for sharp turns...
3. Changing the world from bounded to a torus...
4. See item #5 for 4 October. It which includes some new thoughts.

Then read, think about and offer help with someone else's problem. You might wish to partner with someone through your discussions.

11 October

Fall Break

13 October

Programming Challenge 2: Evolutionary Computation
Work during class time...

18 October

Programming Challenge 2: Evolutionary Computation
Work during class time...

20 October

Programming Challenge 2: Evolutionary Computation
Participant presentations.

Challenge #3: Segregation/Assimilation.
Introduction

25 October

Extra-Credit and/or Course Project Suggestions:
Currency Detection...
Yellow Dot Code...

Challenge #3: Segregation/Assimilation.
Continued...
Work in class on challenge...

Version #26 has been better organized...
Introducint:
Bitmaps drawn in PhotoShop to initialize the world or to import environments.
The "cops and agitators" rioting rules.

Handout:
The STA architecture: "Elements of the Segregation/Assimilation world."
SENSE: Agents can sense, look at neighborhoods of agents and environments...
THINK: Agents can thin, but it is up to you to tell them how...
ACT: Agents can change and move...

A preliminary analysis of experiments studying the difference in outcomes between:
Natural language definitions of preference and prejudice are vague and non-specific.
We can adopt these definitions in our code:
Preference: seek neighbors like me (English)
if (neighborsLikeMe@Destination > neighborsLikeMe@Home) then move (Pseudocode)
Prejudice: flee neighbors unlike me (English)
if (neighborsUnlikeMe@Destination < neighborsUnlikeMe@Home) then move (Pseudocode)
Is there a difference in outcome? YES. Some general observations:
Empty space distributes itself as a lattice or mesh that is only one pixel thick surrounding cells consisting of clusters of agents of a single type. The less empty space, the fewer cells in that mesh or lattice. The more empty space, the more cells, until the clusters of agents are reduced to single individuals.
With two agent types the clusters of agent types form snake-like stripes.

Why does the Prejudice rule result in segregated groups separated by empty areas that are only one unit (pixel) in width?

27 October

Challenge #3: Segregation/Assimilation.
Continued...

Chase with delays. There is something happening here but it is difficult to see in the present visualization. Can you establish some specific initial conditions and/or visualizations which will make the outcome more apparent?
One solution: Create a scattering of C at the top, grading into a scattering of more M just below, grading into more Y below the M, and so on... The agents should migrate down and get congested at the bottom.
Another solution: Change the application to allow you to visuall track the movement of one individual, maybe allowing the user to place an individual of their choosing somewhere in the world, maybe enlarging a portion of the world to make tracking that agent easier.

1 November

Challenge #3: Segregation/Assimilation DUE TODAY.
Participant presentations.

The Droste Effect in CAs:
Conway's GOL running Conway's GOL?

DARPA's $50,000 Shredder Challenge:
Virtual-world clean data versus real-world dirty data.

Brian's Laetoli Walkers:
Evolving locomotion in three dimensions.

Challenge #4: Flocking (Herding, Schooling, Crowd Behvior).
Introduction...

Familiarize yourselves with the variety of User's settings for both applications.
Familiarize yourselves with the rules, how they are written and how they work:
Flocking Images 25 "sweet spot" is between lines 572 and 789.
Flocking Polygons 12 "sweet spot" is between lines 384 and 562.
Come back on Thursday with some ideas for new rules...

3 November

Challenge #4: Flocking (Herding, Schooling, Crowd Behvior).
Continued...

A technical to-do list for Flocking Images:
Use smaller images / Expand the playing field / Introduce more agent sub-variables...
Improve the 3d path visualizations by implementing Red + Cyan makes White.
Connect the dots in the path array visualizations.
Expand to fullScreen and autoRun (but there will be a problem expanding the path arrays).

A technical to-do list for Flocking Polygons:
New functions in the agentClass: setVelocity(), getVelocity(), setDirection(), getDirection().
New sub-variables for the agentClass: acquire(), divest(), memories...
New visualization of agents: uniform size vs. size as f(velocity).
New variant of existing rule: e.g. adopt a portion of NN's velocity and direction.
New coloring routine: color by iteration.

8 November

Challenge #4: Flocking (Herding, Schooling, Crowd Behvior).
Continued...

10 November

Challenge #4: Flocking (Herding, Schooling, Crowd Behvior).
Continued...

15 November

Challenge #4: Flocking (Herding, Schooling, Crowd Behvior). DUE TODAY.
Participant demonstrations...

Challenge #5: Sensors & Actuators
Introduction...

17 November

Challenge #5: Sensors & Actuators
Continued...

Written Challenge: The Computational Universe
Due the last day of class (circa 5-6 pages on paper):
In consideration of the ideas expressed:
a) in these five short articles and excerpts on our Course Documents page:

1. Non Serviam - Stanislaw Lem
2. Permutation City (excerpt) - Greg Egan
3. Rechnender Raum - Konrad Zuse
4. A Computer Scientist's View of Life, the Universe and Everything - Jurgen Schmidhuber
5. The Computerman, the Cryptographer and the Physicist - Nick Gessler
6. and...

b) in these two movies which you should rent and view (some notes are here):

1. Dark City - Alex Proyas
2. Thirteenth Floor - Josef Rusnak
3. Matrix - (great FX, but otherwise intellectually below par)

Please sympathetically* review and critique each of these with respect to a "theory of reality" which all these authors, in their own ways, are envisioning. In other words, what are all these writers attempting to express? How does each contribute to that vision? What are the implications that this "way of knowing" may have for advancing our understandings (both scientific and humanistic) of the world we find ourselves a part of?
* In other words, don't dismiss these ideas out-of-hand. Instead, work within the concepts these writers are alluding to.

22 November

Challenge #5: Sensors & Actuators
Continued...

24 November

Thanksgiving Recess...

29 November

Challenge #5: Sensors & Actuators
Continued...

1 December

Challenge #5: Sensors & Actuators
Continued...

6 December

Challenge #5: Sensors & Actuators due today.
Participant presentations.

8 December

Course Projects due today.
Participant presentations.