Re: evolution was: [ProgSoc] Video yum-cha

[alister air <baitoven@nospam.progsoc.uts.edu.au>]

On Tue, 9 Apr 2002, Anand Kumria wrote:

> I wonder, though, how it works with evolutionary algorithms. It seems that
> they are able to start of with a large pool of untalented pieces of code
> and end up with `the best candidate'.
>
> Anyway care to explain/share the details?

It depends.  Game theory can deal with this (and does, depending on the
environment).  

One example is called the Prisoner's Dilemma.  Two people interact -
they're both arrested and charged.  The deal is that if one dobs in the
other, the dobber gets off free, the dobee gets 10 years.  If neither dob
in, they both get 2 years.  If both dob in, they both get 5 years.

What we know as the rational process would suggest you should defect - dob
in the other person.  If you do, then you'll get off free or 5 years, but
if you don't, you could get 10 years when the other person dobs you
in.  Rational decision-making would indicate that you should do what's
best for you without concern for the other decision (which you can not
know - there's no collusion allowed).

Some guy who's name escapes me developed this as a test of algorithms,
and a series of programs had to play off against each other.  Then it was
seen which strategy was the "best" in terms of minimum amount of time
served throughout repeated interactions.  The winner was amazingly simple
- it was called Tit-for-Tat.  Its first move against a new competitor was
cooperate, then it did whatever was done to it.  In ten rounds against an
"always cooperate" algorithm, they both got equal results.  In ten rounds
against an "always defect" algorithm, they were both almost equal
(Tit-for-Tat suffered slightly).  However, overall, Tit-for-Tat turned out
to be the best overall because it had the ability to punish
non-cooperation.  

This highlights one of the obvious flaws in rational decision-making (and
not just as it applies to games).  

There's more information available, but I couldn't (not trying too
hard) find the specifics of this game, except that it may have been a guy
called Alexrod.  The first place I read about this was a book called The
Origins of Virtue by Matt Ridley.

http://www.amazon.com/exec/obidos/ASIN/0140264450/102-3499592-6524931

This is just one example, but might show how the best algorithm can be
developed in a pool.  The test was done again, and this time a new
algorithm triumphed.  More about that if anyone's interested...

A.



-
You are subscribed to the progsoc mailing list. To unsubscribe, send a
message containing "unsubscribe" to progsoc-request@nospam.progsoc.uts.edu.au.
If you are having trouble, ask owner-progsoc@nospam.progsoc.uts.edu.au for help.