From: kalki33!system@lakes.trenton.sc.us
Newsgroups: talk.origins
Subject: Re: Laying a trap
Keywords: Computer program, random, mutation, chess
Date: Thu, 19 Nov 92 15:56:47 EST
Reply-To: kalki33!system@lakes.trenton.sc.us
Organization: Kalki's Infoline BBS, Aiken, SC, USA

lionel@cs.city.ac.uk (Lionel Tun) writes:

> Lets say there is a computer program which `knows' the
> legal moves of chess - lets call it ChessMover.
> ChessMover plays very poor chess because its moves are
> made at random. But it does play very fast. ChessMover
> is small, compact and extremely efficient. But it plays
> bad chess because it has not been designed with any
> chess playing algorithms at all.
> 
> Would it be possible to subject ChessMover to random
> mutations, so that eventually you evolve ChessPlayer,
> a chess program which plays very well, say at master
> level?

> For those of you who are not game fans, but more business
> oriented:
> Consider a spreadsheet program such as Lotus123 or
> QuattroPro. Lets say you have a small calculator program,
> like the toy ones which pop up in some windowing front
> ends. Would it be possible to apply random mutations to
> Calculator until it evolves into Spreadsheet?

> Please note, both Calculator and ChessMover are small (by
> today's standard) programs, lets say about 2 to 4K for the
> executable. Shreadsheet and ChessPlayer must obviously be
> of a more substantial size (I can't remember how big Lotus
> is). If you like, you can randomly modify the source code
> and compiler, rather than the executables, if you think this
> will make it less brittle. Random modification includes of
> course random additions. You might prefer the source code
> approach as the compiler will reject programs which will
> not even compile, let alone run. If you wish to modify
> the compiler, you can keep a copy of the old compiler to 
> compile it with.

These questions are testable in the following sense:

1) Design a universal Turing machine with a particular symbol set, say
the binary set {0,1}.

2) Write a simple program that works (i.e. the machine halts in a finite
number of steps).

3) Subject this program (i.e the program's bit-string) to a series of
"random" mutations that flip bits (change a "1" to a "0" or a "0" to a
"1"), or that add/delete bits at the end (or the beginning) of the
string, or that add/delete substrings, etc... (there are so many
possibilities!)

4) After each mutation, try running the mutated bit string as a program
in the universal Turing machine and observe the results. If the program
is correct (i.e. the machine eventually halts) call this an "admissible
intermediate form" and examine it further to determine just what the
mutated program is doing. If the program doesn't work (i.e. the machine
never halts) then count it as an "evolutionary dead end" and either
allow it to mutate further or discard it and start over from the most
recent admissible intermediate form.

5) If you are not sure whether the machine will eventually halt, then
attempt to dissect the code to determine if it represents a valid
algorithm or not.

6) After a number of trials (probably trillions and trillions), see if
you ever come up with the complete source code for a fantastically
complex purposeful application (designed for the Turing environment of
course, so maybe no video!).

Many additional conditions will have to be dealt with, such as:

a) the choices of starting strings, their length and bit sequence.

b) how many unsuccessful mutations are we willing to allow before we
discard a string as an evolutionary dead end?

c) how do we deal with admissible intermediate forms which, although
they are valid algorithms, do not appear to compute anything "useful"?

d) should we allow the machine itself to mutate (i.e. randomly change
its next-move function or its transition table)?

e) should there be a limit on the allowed size of a string?

f) what about programs which are self modifying? In this case, the new
string is not the result of mutation, but it has changed.

Sincerely,
Kalki Dasa



       -------------------------------------------------------
      |  Don't forget to chant:   Hare Krishna Hare Krishna   |
      |                           Krishna Krishna Hare Hare   |
      |                           Hare Rama Hare Rama         |
      |                           Rama Rama Hare Hare         |
      |                                                       |
      |   Kalki's Infoline BBS Aiken, South Carolina, USA     |
      |        (kalki33!kalki@lakes.trenton.sc.us)            |
       -------------------------------------------------------