NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/talk/origins/14603

Internet Message Format | 1992-11-20 | 3.7 KB

Path: sparky!uunet!ulowell!m2c!jjmhome!smds!rh
From: [e-mail] (Richard Harter)
Newsgroups: talk.origins
Subject: Lionel's chess program
Keywords: Computer program, random, mutation, chess
Message-ID: <[e-mail]>
Date: 21 Nov 92 02:07:00 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Reply-To: [e-mail] (Richard Harter)
Organization: Software Maintenance & Development Systems, Inc.
Lines: 72

In article <[e-mail]> [e-mail] (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?

This is an interesting question; the answer is not immediately
obvious because it really does depend on how "chessmover" is
written and what constitutes a random mutation.  Thus, if we have
a straight forward machine language program and our mutations
consist of random insertions and deletions of bits then, regardless
of numbers of programs, the probability of ever producing a strong
chess playing program is miniscule, even on evolutionary time
scales.  I suspect this is the "trap" that Lionel has in mind.

However the genetic program for life doesn't work the same way
as a conventional Von Neumann machine.  Here is how one might
go about such a program.  The board position at any point and the
possible moves are available as data -- they correspond to the
external environment of a cell.  Chess mover has several built-in
pieces.  These are:

(a)    A "program" which is simply a string of bits.  This is fixed
    for a given instance of the program, but is alterable during
    reproduction (by mutation) or genetic exchange (prokaryotic
    sex).

(b)    A pattern matcher which matches a pattern against the data,
    i.e. against the board position and against the legal moves.
    This is analogous to enzymes.  Each pattern has a value
    associated with it which is released if the pattern matches
    the data.

(c)    A transcriber which, given a position on the "program" bit
    string, produces a pattern, following a fixed mechanical
    rule (the genetic code).

(d)    A responder which, given a value, associates with it a bit
    position on the string.

(e)    A move selector.  If a pattern matches a move that move is
    selected.  If, after a time out period passes without a move
    being selected, a random legal move is selected.

The sequence of events is as follows:  Several million instances of
the program play each other.  All programs that lose are eliminated.
Programs that draw [we will need to count reaching a maximun number
of moves as a draw] may have sex, i.e. drawing instances exchange
sections of their programs at random.  Half of these instances die.
The surviving instances reproduce, i.e. new copies are produced.
The "programs" of the new instances may mutate, i.e. the bit strings
of their "programs" can either alter at a specific bit or a substring
may be replicated or deleted.

---

In answer to Lionel's question -- a chess program written along these
lines can be expected to reach Master level.
--
Richard Harter: SMDS Inc.  Net address: [e-mail] Phone: [phone]
US Mail: SMDS Inc., PO Box 555, Concord MA 01742.    Fax: [phone]
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.