Hi everyone.

    I apologise  for a) being inactive in this group until now, and b) being
rather stochastic in the structure of these comments.

    On the question of how do we attract more people to the field of
co-evolution,  it may be worth a short reflection and ask why each of us was
drawn to co-evolution in the first place?  Personally my first introduction
to the subject was that I needed to solve a problem where I could not define
a quantitative objective function, and I had very little engineering insight
into how the problem may behave (as the customer was waiting, I also needed
a plausible solution quickly too).  I essentially used co-evolution as a
knowledge discovery tool.  I have since used it for evolving checkers
players, but that was more aimed at understanding the advantages/limitations
of co-evolution for knowledge discovery, rather than playing the game
itself.  My most recent work is more towards  cooperative co-evolution (my
algorithms employ a loose definition of the term though) for creating
self-adaptive dynamic systems.  I think we need to consider and understand
why *we* find the subject interesting and worthy of research before we can
attract more practitioners.  Frankly if the 'publicity material' is not
designed to hook new researchers, it does not matter where it appears.  I
found Xin's plenary at CEC really interesting this morning and he had a
large audience.  If just a few percent of those participants have been
inspired to look further, it will have helped.

   Although we have many practical algorithms, there are many difficult
fundamental issues to address in co-evolution.  Most of these have been
mentioned in previous posts, such as metrics etc.  One area that I used the
checkers work to explore, but that I have not noticed mentioned so far, is
the impact of regions of limited observability.  In checkers this phenomena
is really quite dramatic; the weights/structures relating to the pieces on
the back-rank evolve rapidly, while the central area of the board takes
longer to settle.  If evolved for long enough then the results are good (I
trained a single neuron for over 20,000 generations to get reasonable
solutions).  However weightings for the board locations when a king is
present was a different story.  Even with repeated/long runs, the king
weights were often ill evolved and could often not be truly distinguished
from random.  The problem lies in that the kings are only in play for a
relatively short fraction of a game (if at all) and so the behaviour is not
easy to observe, and hence evolve.  The general noise levels on the
aggregated evaluation function (e.g. from 10 or 15 games) may be much higher
than the average contribution from the king behaviour.  When I have applied
co-evolution to real problems (one was designing an improved target
detection system for a radar), comparing the decision variables of the best
solutions from repeated runs will quite often reveal that some parameters
are easy to evolve, but some are not, so it is reasonably simple to
establish issues with unobservable areas.  What I would like is an automated
way of making these regions more observable, but not skewing the performance
of the final algorithm in any way; for example, I tried generating checkers
boards with only kings occasionally and the evaluator then forgot how to
open the game :-(

   Best regards,

            Evan

I would have to see more detail about how you approached checkers.  But I'm
inclined to say, coming from my own bias, that you're probably adjusting
weights using some average or aggregate of the outcomes over many games or
over many configurations of the board.  Aggregates have a tendency to detect
gross features (like commonly-encountered configurations) while washing out
subtle details (like uncommonly-encountered ones).  There's a nice paper by
Ludo Pagie which discusses that point (Evolutionary Consequences of
Coevolving Targets).

One way to go about fixing that is called Pareto coevolution or, more
generally, what's been called "informative testing."  Without more details I
can only give a vague, wanky-sounding description of how you'd do this:

(1) Find/decide what's "testing" your players.  In other words, what are you
doing to a player to get information about how good it is?  How are you
ranking two players to say that one is better than the other?

(2) Find where you're averaging, maximizing, or otherwise aggregating the
info you get in (1) into some composite number which lets you rank players
(or form a delta for changing a player).  The stuff you're averaging or
aggregating form the "atomic tests."  You might, for instance, be playing
players A and B against players C and D, counting how many times A and B win
and comparing on wins.  Then C and D are the "atomic tests," and the count
is the aggregate you're forming.

(3) Create an explicit selection pressure on the atomic tests which promotes
"informative" ones.  One way to approach informativeness here is to see how
discriminatory the test information is.  Keep stuff which discriminates lots
of other players, and particularly, pay attention to whether two atomic
tests discriminate differently from one another.  If A beats C but loses to
D, and B beats D but loses to C, then C and D look equal as tests, but they
are in fact giving you different information about A and B, so on that basis
are differently informative.  You'd want to use that to incent the tests
(the opponents C and D), rather than average number of wins.

Part of the wisdom behind that line of thought is nicely laid out in Susan
Epstein's Ideal Trainer paper.  She stresses the importance of carefully
choosing opponents when testing a plyer during learning.  That paper's well
worth a read (it was in ML in 1994).  Replicating some of Arthur Samuel's
thoughts (particularly, doing some work to keep your eval function
consistent with itself, if that's what you're using to represent a player)
couldn't hurt.

So that's one approach.  Another is to muck around with how you're
representing players, but that's often domain specific.  Maybe you should
try representing your player as a neural network evaluation function using
NEAT...

Anthony

On 9/26/07, Evan Hughes <banana.l...@gmail.com> wrote: