NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/ai/4386

Internet Message Format | 1992-11-19 | 4.4 KB

Xref: sparky comp.ai:4386 rec.games.programmer:4806
Newsgroups: comp.ai,comp.ai.genetic,rec.games.programmer
Path: sparky!uunet!spool.mu.edu!agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!cis.ohio-state.edu!neuron.cis.ohio-state.edu!pja
From: [e-mail] (Peter J Angeline)
Subject: Re: Games and genetic algorithms
In-Reply-To: [e-mail]'s message of Mon, 23 Nov 1992 21: 34:49 GMT
Message-ID: <[e-mail]>
Followup-To: comp.ai,comp.ai.genetic,rec.games.programmer
Originator: [e-mail]
Sender: [e-mail] (NETnews        )
Reply-To: [e-mail]
Organization: Ohio State Computer Science
References: <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]>
Date: Tue, 24 Nov 1992 05:39:43 GMT
Lines: 57

In article <[e-mail]> [e-mail] (Bruce Krulwich) writes:

>   Intuitively, does anyone really think that strategies for game playing are
>   learned in a random-permutation  evolutionary sort of way?  My intuition is
>   that people employ alot of reasoning, such as explanation, in learning new
>   strategies and in modifying old ones.

Sorry, but Genetic Algorithms are NOT random permutations. GAs are actually
similar to a typical beam search employing specific heuristics which are devoid
of specialized knowledge about the task (in most cases). The heuristics used in
typical GAs are "if two solutions in the beam are better than average at the
task then try combinations of them in the future" (i.e. crossover) and "if a
solution is better than average at solving the task then try to rearrange its
parts" (inversion) and "if a solution is better than average at solving the
task then look in its general vacinity for other good solutions" (mutation).
Of course these heuristics make assumptions about the representation of the
solutions, specifically that it makes sense to recombine their parts.  Yes the
heuristics are "weak" (as in "weak method") but that's the point.

>   Think, say, of a typical strategy in game-playing, such as the "fork" in
>   tic-tac-toe [or] chess.  It doesn't make sense to me that this would be
>   learned through random permutations, rather through a player explaining the
>   ways in which the enabled moves interact with the opponent's ability to
>   respond.

I agree, random permutations WON'T learn forking in Tic Tac Toe. But using the
heuristics of Genetic Algorithms and a lisp-like language for representation of
solutions, GLiB, a program I wrote, was able to evolve FROM SCRATCH a program
which could FORK an "expert" Tic Tac Toe player consistently! (See this year's
Cognitive Science Conference Proceedings for the paper or mail to me to ask for
instructions on how to ftp the complete paper if interested.) Just because some
technique is implemented probabilistically doesn't mean it has no power.

EBL solutions require TONS AND TONS of task specific knowledge.  Whenever you
ask sombody in EBL where this knowledge comes from they say something like "its
supplied by the programmer" or "its common sense".  But this does not _explain_
the learning!  It merely postulates a humunculus which knows what the
appropriate knowledge is to make an EBL algorithm work!  All EBL and most other
"classic" learning mechanisms do is transfer the information from one internal
medium to another, no TRUE learning is being done.  AM and EURISKO, when they
aren't using the interpretation function inside the humans that monitor the
runs, are TRUE learning algorithms. So are some forms of GAs (like mine).

If you're talking only about "deliberative" or "cognitive" learning (a dodge I
usually get when I argue as above with others) then I suggest you read
Edelman's book "Neural Darwinism" which gives a credible account of how ALL
learning is evolutionary in nature. He's a nobel laureate, so he can't be all
wrong.

-pete angeline


--
-------------------------------------------------------------------------------
Peter J. Angeline            ! Laboratory for AI Research (LAIR)
Graduate Research Assistant  ! THE Ohio State University, Columbus, Ohio 43210
ARPA: [e-mail] ! "Nature is more ingenious than we are."