EVOLUTIONARY PROGRAMMING, TSC, and BEAD GAMES

Jack Park
ThinkAlong Software Inc.
jackpark@thinkalong.com


Keywords

Combined simulation, gaming, qualitative model, education


Abstract

In this paper, we discuss a philosophical approach to the development of a MUVE (Multi-user Virtual Environment) in the form of a game engine that supports the exercise of educational game programs. Given a web-based approach, we propose a novel mechanism by which learners develop game-winning strategies off line, then enter the game portal ready to compete with game engines programmed by others. Our approach envisions a discovery-based system based on our program The Scholar's Companion (TSC) that permits off line development of strategies using evolutionary programming techniques. We view the outcomes of the exercise of games in such a game portal as a kind of Glass Bead Game, one in which winning moves made by contestants result in new knowledge gained by all.


Introduction

Learning environments come in all sizes and shapes, from dirt out in the back yard to mainframe computers coaching individuals. A particular learning environment that suits the model we are developing is that of a discovery-based environment. Such an environment allows new knowledge to be gained through the experiences in that environment. Generation of those experiences is a target capability we require of such an environment.

In this paper, we propose the application of an evolutionary programming environment to the search for solutions to games proposed by an entity we shall identify here as a web-based portal for the conduct of such games. Steps envisioned in the process include:

We thus propose an environment comprised of two important components: a web-based MUVE at which learners can enter competitive games, and a downloadable game development environment, itself a kind of MUVE that provides the learner with the tools necessary for personal discovery of knowledge in the form of game strategies. Virtual worlds, as the presentation layer, couple learners with the models they create.

We now sketch the learning environment, then cast it into a larger view, one in which we see the substrate of a Glass Bead Game (Hesse, 1990) evolving.


Learning Environment

We have constructed a program called...

The Scholar's Companion

(ThinkAlong, 1993) - TSC. The program implements a framework for representation of process-oriented knowledge and includes functions that allow for the manipulation of that knowledge in a variety of ways. A primary function is that of the automated construction of models when given a variety of objects and rules of behavior. For instance, at its simplest level, a child can type in simple sentences and view a graphical representation of a taxonomy of objects described in those sentences. Sentences that describe behaviors result in rules. Configure a group of objects and ask the program to build a model. The result will be a directed graph representation, called an envisionment, of the behaviors the group of objects can take.


  [Shows a series of boxes with names that represent organic structured
  subjects with relationships for...

              Living thing    Animal   Mammal     Human


                                       Reptile    Nefer

              Animal is associated with Reptiel, and Human is linked to Nefer
Figure 1 A simple taxonomy

A sketch of a graph constructed by sentences typed by the author's (then) 7-year old daughter


  [Shows elements A and B titled "Regulation1.E1" identified under A as
  "Protein kinase activated."  There is a complex structure for both A and B
  that seems to be identical, except the B rendering is more complete.  The
  meaning, purpose and conclusions are not clear without explanation, and
  example.
Figure 2 Two envisionments from a knowledge base with different initial conditions...

is Figure 1. Sentences that were entered were of the form

An animal is a living_thing. A mammal is an animal. A human is a mammal. Nefer is a particular human.

A fourteen-year-old intern spent a summer "teaching" the program about the habitat of phytoplankton and zooplankton. She added sentences that describe processes, events that would happen in that environment. The program first built a diagram of the taxonomic aspects of her environment, then it went on to build an envisionment of those processes occurring, events such as zooplankton eating phytoplankton, and so forth.

A rather more complex model has been built to model object behaviors at the molecular level (Trelease, et al, 1999). We provide a view of one of the envisionments produced in that study (Figure 2). While the diagram appears somewhat cryptic, the initial conditions for the model start at the left. Envisionment A has been annotated to reflect the semantics of each node in the graph.

We describe this model as one of a stage setting, as an application of a theatrical metaphor. Initial conditions consist of Actors on a stage, each set in some relationship with the others. Given such a stage setting, rules related to each actor on stage are then exercised. Those rules that can fire, that is, that can cause some change to the stage setting, do so. Each rule that fires creates a new node; multiple nodes connected to a single prior node indicate that multiple rules fired.

Application of a stage metaphor satisfies an intention of representing images of game play in a MUVE. Direct links between behaviors of a game engine are thus readily translated to the graphic images presented at the web site. Graph traversal over an entire envisionment can be rendered in animated scenes in the virtual environment.

Building models is itself a learning experience. The user has the task of finding a suitable way to transfer personal constructs into a form usable by the program. Transformation alone involves research and thinking. The construction of a model can result in an expectation failure, usually, a model that does not behave as expected. An expectation failure, followed by knowledge editing summarizes the primary user experience capability required of The Scholar's Companion.

A secondary capability of the program is that of performance of a sequence of mutations of knowledge supplied by the user. We tend to think of users as "teachers" since they are supplying the program with representations of their personal constructs. We view the secondary capability as one of advanced "what if" study of that knowledge. To perform such studies, the program applies an evolutionary algorithm to the mutation of objects in the closed universe supplied by the user. We discuss that algorithm next.


Evolutionary Programming


Evolutionary programming is a concept rooted in the theory of evolution as put forth by Darwin and Wallace. From the perspective of learning environments, evolution occurs in a vast ocean of cycles. Evolution of suitable sentences to teach The Scholar's Companion something new, for example, is, itself one of those cycles. Learning from the results of the programming exercise is another.

Let us consider another cycle, one deeply ensconced inside the program itself. Suppose we ask the program to use, say a random number to select some concepts the learner has taught it. Suppose another random number then chose some sort of mutation, say, composition, to perform on those concepts. For example, suppose the program has chosen to add some property, say, skin covering, taken from a reptile to a mammal. If the program presents the results of this exercise to the learner, the learner is now confronted with a concept that doesn't make sense. More learning occurs as the learner studies the change. Douglas Lenat built a program called AM (Lenat, 1983) that did just that. With a few prior concepts related to set theory, the program discovered prime numbers and a host of other uninteresting, but new to the program, concepts. Of course, it took Lenat himself reading the program's output to discover the meanings of the new concepts.

Lenat later rewrote his program, calling the new version Eurisko. Eurisko was programmed to play games. Doing so, it "learned" a few heuristics that helped it later win a warfare game, two years in a row. Lenat was made an honorary Admiral in the Travellers game fleet and not permitted to play anymore.

It is precisely this coupling of an evolutionary programming engine with strategy and other types of thinking games that is at the center of our proposal. A particular kind of game that appears to fit into the genre of the MUVE web portal is that of the Glass Bead Game.


Glass Bead Games

Hermann Hesse won a Nobel Prize for authoring the book Magister Ludi: The Glass Bead Game. The game was composed of a series of intellectual "moves" made by players under the guidance of a Game Master. The Master put forth the first move together with the rules of play. Moves made by players were then analyzed for patterns and rules for the next move were offered. The concept of a Glass Bead originated from Hesse's story. We do not use the term to mean that information is encoded in script on a glass bead; rather we use the term metaphorically to speak of the process of making moves. In our vision, a move may be comprised of directions for the next play to be interpreted by a game engine.

It turns out that Glass Bead Games have taken a life of their own on the web. It also turns out that both Eurisko, and The Scholar's Companion appear to play a kind of Bead Game internally. This is because both programs use an internal behavior cycle that reads:

That's the Glass Bead Game as expressed in a simple algorithm. In a bead game, a bead master puts forth the first move, just as a user sets the initial conditions for the construction and eventual mutation of a model. While The Scholar's Companion is playing its own variant of the game internally, its user is playing a much larger variant externally. TSC presents concepts either of the existing model as it is being built or of mutations it has created. Users then study these objects and perhaps react by changing initial conditions. In such a case, the user is a Bead Master, while TSC is one player.

Coupling Bead Game players together at a graphically rich portal will provide the stimulus for players to exercise their engines off line. Learning takes place at a variety of levels, each level behaving as, perhaps, a fractal image of a larger level.

Design goals for The Scholar's Companion center on the notion of providing a user with the opportunity to explore some domain of interest from many different views. The idea is that one can hold some concept up in the air, rotate it around, and study it from many different sides. This process starts with the "teaching" process, where the user enters new knowledge into the program. Doing so with a qualitative vocabulary, as opposed to a purely mathematical vocabulary, opens the door for users at nearly all levels of expressive capability. Indeed, the program can be programmed to respond to Icons dragged onto a workspace by very young learners. An overview visualization of the design of The Scholar's Companion is Figure 3.


    [Shows a series of boxes that seem to represent elements of Jack's
    program, The Scholar's Companion...

               Qualitative View
               Textual View
               Simulation
               Graphical
               Mathamatical View
Figure 3 Multiple views of knowledge in TSC

A variety of views, from the simple textual - sentences entered by users or rendered by the program in response to questions - to the purely mathematical view as expressed in the rendering of solutions to equations entered by the user or derived by some program. The question-answering capability of the program has been used in the conduct of classroom exercises in two high school biology courses.

In between, we find Simulation. This is the view that expands an envisionment that describes the response of process rules to a stage set by the user. What-if games can be played with The Scholar's Companion in this manner. At the same time, serious research can be conducted as well. A Ph.D. was gained by performing research using the program to help discover new process control rules for polymer curing (Abrams, 1995).

How might this environment be used? We envision an excursion into an educational game environment to be composed of several kinds of events. Consider the Grand Bead Master (Magister Ludi in the Hesse vernacular) - a web site itself, staffed by game designers. Suppose that the web site presents a first Bead, a game design complete with rules of competition. Now, consider a user, an individual who has a copy of TSC and is familiar with it. The user would be expected to begin the construction of a knowledge base, a small universe of discourse suitable for the development of a simulation that allows for off line exploration and discovery of winning strategies. This will be done off line, after the user has visited the web site. Such a user will have access to knowledge accumulated from the games of the past, archives at the portal. These links to prior art may serve as the basis for a new effort, or they may provide ideas from which the individual takes a new point of view.

The individual may run off line competitions with others, or may build a simulator that runs as an internal opponent. Analysis of the results of play may support the discovery of new heuristics that eventually lead to a winning strategy. Eventually, the individual enters the on line competition, coupling the locally trained TSC to an on line game hub, the MUVE itself. There will be others coupled to the hub and the games begin.

Conclusions

We have been developing the thread woven here with a goal to make available a program patterned after The Scholar's Companion that provides a powerful tool for learning by discovery. We believe that the development of a graphically rich MUVE environment, one that will support and animate game exercises, is an appropriate vehicle by which we might encourage learning experiences for users of all ages.

In the long run, the system we envision places content rich multiple user virtual environments firmly in the center of a web activity that encourages and contributes to the growth of knowledge in a variety of ways. It is this growth of knowledge that lays foundations for human development.


Acknowledgements

The work discussed here, indeed, the vision presented would not be possible were it not for valuable collaborations with Drs. Steven LeClair, Robert Trelease, Bill Dress, Richard Henderson, Alan Jackson, John Rose and Adam Cheyer, and with Dan Wood, Howard Liu, and Helen Park.


References

Abrams, Frances L., Process Discovery: Automated Process Development for the Control of Polymer Curing, Ph.D. dissertation, University of Dayton, Dayton Ohio, December 1995.

Hesse, Hermann, The Glass Bead Game, Henry Holt and Company, 1990.

Lenat, Douglas B., "The Role of Heuristics in Learning by Discovery: Three Case Studies," in Ryszard S. Michalski, Jaime G. Carbonell, and Tom M. Mitchell, editors, Machine Learning, an Artificial Intelligence Approach, Tioga Publishing Company, 1983.

ThinkAlong Software Inc., The Scholar's Companion Programmer's Guide, 1993. The Scholar's Companion is a registered trademark of ThinkAlong Software Inc.

Trelease, Robert B., Richard A. Henderson, Jack B. Park, "A qualitative process system for modeling NF-kB and AP-1 gene regulation in immune cell biology research," Artificial Intelligence in Medicine 17, (1999), 303-321.