## Re: [neat] Re: Species stagnation

Expand Messages
• Mike, Thanks for explaining your experimental setup in more detail. I think I ve got a better handle on it now. :) I still have a few questions though. ... So
Message 1 of 26 , Apr 1, 2005
• 0 Attachment
Mike,

Thanks for explaining your experimental setup in more detail. I think
I've got a better handle on it now. :)

I still have a few questions though.

> The cat is red, the mouse is yellow. The cat has 16 inputs:
>
> 0-3: Distance to walls in U,R,D,L
> 4-7: Proximity to mouse in U,R,D,L (-1.0 for no sight)

So are all your inputs between 0 and 1? So for example, if the cat
started in the center of the grid, it's input for distance to wall
Left would be 0.5? And if the mouse were midway between the left wall
and the cat starting out the input for distance to mouse would be
0.25?

> 12-15: Measure of how long since walking on tiles in U,R,D,L

I don't understand this set of inputs.

> The cat can only see through LOS. There are five outputs of the cat:
>
> 0 - Move Up
> 1 - Move Right
> 2 - Move Down
> 3 - Move Left
> 4 - Make Sound
>
> The sounds can be ignored at this point. If no direction value is >=
> 0.9 then the cat stays put. Otherwise whichever direction value is
> highest, the cat goes that way. This is processed every game tick.

Okay, so the cat really is more like a radially symetrical robot...it
can see "behind" itself wihtout turning that way. In fact, it doesn't
need to turn at all, correct? It's got eyes in all four directions.

And it doesn't have any forward momentum. That is, it can sit still
if it wants. I would be interested to know how much time in failed
experiments, the cat spends stationary.

And if I'm understand the mouse movement in the experiments where the
mouse moves, it's moves are entirely deterministic, usually limited,
and alternated left or right. So when the mouse reaches it's fixed
number of moves, it sits still? Maybe I missed it, but how much time
do you give the cat to find the mouse?

So is a "tile" an area equivalent to the size of each actor?

> D) Mouse goes out of sight (4 tiles max). Mouse starts in an
> intersection (screenshot above) and on his first move will go out of
> sight from the cat. With a 4 move maximum you will notice that the
> mouse will never be able to turn at another intersection. The cat
> receives the direction vector of the mouse for the frame after it
> dissapeared (if he could see) but otherwise all he has is anything
> left in his memory. Obviously for this test to be successful, some
> recurrent connections must be developed.

Hmm...I'm not sure that's necessarily true, is it? If I'm
understanding correctly, on the first time step, the cat has LOS to
the mouse, then the next time step the mouse goes out of sight, either
to the right or the left. Is that correct?

So if the cat headed in that direction on step two, and reached the
intersection, the mouse would be in line of sight again, right? I
think you are saying the mouse doesn't have enough movement to get out
of LOS a second time. I'm not sure this behavior would require a
recurrent connections. The initial sight of the mouse just has to
keep it moving in that direction until it gets line of sight again,
right?

As far as I can tell, the only significant difference in behavior
desired is "go in the direction the mouse *was*" as opposed to "go in
the direction the mouse *is*". And the main difference in inputs is
that there is a constant input for mouse detection in the first ones,
and only a single blip for input before the mouse ducks out of sight
in the last. Is this correct?

I'm thinking that maybe that single blip of an input may not be enough
to drive the cat in that direction, especially with a complicated
recurrent network.

I'd be interested to see how a couple of variations might perform:

1) Clamp movement for both agents (cat and mouse) for something like
10 time steps, so that the cat is receiving direction and distance
input for the mouse for more than 1 time step. Then "let them go". I
would be interested to see if the repeated input as opposed to a
single glimpse of the mouse might make alter behavior.

2) Explicitly feed in an input for last known direction. At this
point it's not memorizing last position, but this might be a good
intermediate step between C and D. The mouse goes out of sight, but
you're still feeding a positive input for that direction. I would be
interested to know how this performs too.

Anyway, good luck no matter what you decide to do.

Derek
• Derek, Cheers for the feedback, I ll start by answering your questions. ... Yes. I use -1.0 for invalid (for ex. no mouse sighted) and 0.0 to +1.0 for valid
Message 2 of 26 , Apr 1, 2005
• 0 Attachment
Derek,

> So are all your inputs between 0 and 1?

Yes. I use -1.0 for invalid (for ex. no mouse sighted) and 0.0 to
+1.0 for valid inputs.

>> 12-15: Measure of how long since walking on tiles in U,R,D,L
>
> I don't understand this set of inputs.

These 4 inputs measure how long (relatively speaking) it has been, in
game ticks, since the cat was last on the tiles in each direction
(U,R,D,L). So at the beginning, this will have a value of -1.0 for
all four directions. As soon as the cat moves 1 tile to the right
then he has just been on the tile to his left (last time there was
tick 1, it is now tick 2) so it will have a value between 0.0 and
+1.0. The formula used is 1 - ((avg ticks since on tiles) /
current_tick_count). Thus high values represent the fact that the cat
was just there. This provides the cat with an input that he could
utilize to avoid backtracking.

> The cat doesn't need to turn at all, correct? It's got
> eyes in all four directions.

Correct.

> And if I'm understand the mouse movement in the experiments
> where the mouse moves, it's moves are entirely deterministic,
> usually limited, and alternated left or right. So when the
> mouse reaches it's fixed number of moves, it sits still? Maybe
> I missed it, but how much time do you give the cat to find
> the mouse?

The direct route to the mouse is never greater than 21 tiles of
movement (everyone moves 1 tile per tick) and so I give the cat 35 ticks.

> So is a "tile" an area equivalent to the size of each actor?

Yes.

> > D) Mouse goes out of sight (4 tiles max). Mouse starts in an
> > intersection (screenshot above) and on his first move will go
> > out of sight from the cat. With a 4 move maximum you will
> > notice that the mouse will never be able to turn at another
> > intersection. The cat receives the direction vector of the
> > mouse for the frame after it dissapeared (if he could see)
> > but otherwise all he has is anything left in his memory.
> > Obviously for this test to be successful, some recurrent
> > connections must be developed.
>
> Hmm...I'm not sure that's necessarily true, is it? If I'm
> understanding correctly, on the first time step, the cat has LOS to
> the mouse, then the next time step the mouse goes out of sight,
> either to the right or the left. Is that correct?

Yes, that's correct. A timeline, using this screenshot:
http://www.redcrocodile.net/test/nolog/CatAndMouse.jpg

Note: There are 2 tiles in between the cat and mouse.

Tick 1) Cat moves (mouse is in sight)
Tick 1) Mouse moves (mouse goes out of sight)
Tick 2) Cat cannot see the mouse. Cat moves right again, still is not
in sight of the mouse.
Tick 3) Mouse moves again.
Tick 3) If Cat moves right again, it reaches the intersection. Now
the mouse is in sight.

> I think you are saying the mouse doesn't have enough movement to
> get out of LOS a second time.

True.

> I'm not sure this behavior would require a recurrent connections.
> As far as I can tell, the only significant difference in behavior
> desired is "go in the direction the mouse *was*" as opposed to "go
> in the direction the mouse *is*".

Well, personally, that is how I would define memory. Semantics aside,
my understanding of NNs says that if all the information necessary to
achieve best fitness is not available to the agent in the current
state (i.e. it is non-Markovian) then recurrent conections are required.

> And the main difference in inputs is that there is a constant input
> for mouse detection in the first ones, and only a single blip for
> input before the mouse ducks out of sight in the last. Is this
> correct?

Yes.

> I'm thinking that maybe that single blip of an input may not be
> enough to drive the cat in that direction, especially with a
> complicated recurrent network.

As mentioned, it works great with a hand-coded fully connected
recurrent network. Even from distances across the entire map
(1,1)-(23,1), it works perfectly (mentioned again at the end).

> I'd be interested to see how a couple of variations might perform:
>
> 1) Clamp movement for both agents (cat and mouse) for something like
> 10 time steps, so that the cat is receiving direction and distance
> input for the mouse for more than 1 time step. Then "let them go".

I'm not sure what you mean by this. Could you explain in a little
more detail?

> 2) Explicitly feed in an input for last known direction. At this
> point it's not memorizing last position, but this might be a good
> intermediate step between C and D. The mouse goes out of sight,
> but you're still feeding a positive input for that direction. I
> would be interested to know how this performs too.

Yes, I would imagine that you're right in that this would help.
However, I resigned myself to only allowing the cats access to LOS
inputs from the beginning. That, in particular, is one of the aspects
that differentiates my experiments with the others that I've seen
(obstacles blocking vision) amongst the NEAT circle of publications.

-- Further update on my fully recurrent tests. As mentioned they
passed the simple scenario above (scenario D) with flying colours. I
increased the glimpse distance to the entire map and they were able to
produce 40 different solutions (not carbon copies) by G1896 (first
found at G869). For these experiments, my NEAT populations have not
come anywhere close to the fully recurrent population.

Cheers!
Mike
• ... ... Okay, gotcha. However, this set of inputs seems like it might be a little redundant. The cat is also receiving input on its absolute position
Message 3 of 26 , Apr 1, 2005
• 0 Attachment
On Apr 1, 2005 11:10 AM, gerbopel <redcrocodile@...> wrote:
>
> >> 12-15: Measure of how long since walking on tiles in U,R,D,L
> >
> > I don't understand this set of inputs.
>
> These 4 inputs measure how long (relatively speaking) it has been, in
> game ticks, since the cat was last on the tiles in each direction
> (U,R,D,L).
<snip>
>This provides the cat with an input that he could
> utilize to avoid backtracking.

Okay, gotcha. However, this set of inputs seems like it might be a
little redundant. The cat is also receiving input on its absolute
position each time step as well, right? Do the other papers use these
sorts of inputs?

> > I'm not sure this behavior would require a recurrent connections.
> > As far as I can tell, the only significant difference in behavior
> > desired is "go in the direction the mouse *was*" as opposed to "go
> > in the direction the mouse *is*".
>
> Well, personally, that is how I would define memory. Semantics aside,
> my understanding of NNs says that if all the information necessary to
> achieve best fitness is not available to the agent in the current
> state (i.e. it is non-Markovian) then recurrent conections are required.

Hmm...well, this might be an interesting discusssion to open up. That
sounds like a pretty reasonable assessment. However, if you added one
change to your domain, where the cat is always in motion, then the
intitial sight of the mouse would send him in the direction, and no
further positive feedback would be required to keep him going in that
direction, right? Then once he attains LOS on the mouse again, he
could achieve best fitness.

Of course, if you're in a domain where the agent is completely driven
by the output of the neural network, then yes, I can see how
recurrency is going to be needed to create a loop to compel it to go
in that direction without continued positive input.

> As mentioned, it works great with a hand-coded fully connected
> recurrent network. Even from distances across the entire map
> (1,1)-(23,1), it works perfectly (mentioned again at the end).

Yeah, well that would indicate that there's a problem with the NEAT
implementation you're working with, or that as Colin mentioned, you
got extremely lucky in hitting upon an architecture to solve this
particular problem, or for some reason NEAT is simply not well-suited

> > I'd be interested to see how a couple of variations might perform:
> >
> > 1) Clamp movement for both agents (cat and mouse) for something like
> > 10 time steps, so that the cat is receiving direction and distance
> > input for the mouse for more than 1 time step. Then "let them go".
>
> I'm not sure what you mean by this. Could you explain in a little
> more detail?

My thinking was basically that the cat just might not be getting
enough useful information as input upon which to act. Biologically,
the longer an agent is exposed to stimuli, the stronger the impact,
correct? If I flash a card at you for 1 second, it might be more
difficult to identify or memorize the content than if I let you study
it for 10 seconds.

I was wondering if you basically disabled movement of both agents for
the first 10 or so time steps, letting the cat see the mouse all that
time before letting them move and letting the mouse move out of sight,
that it might make a difference. I don't know.

> -- Further update on my fully recurrent tests. As mentioned they
> passed the simple scenario above (scenario D) with flying colours. I
> increased the glimpse distance to the entire map and they were able to
> produce 40 different solutions (not carbon copies) by G1896 (first
> found at G869). For these experiments, my NEAT populations have not
> come anywhere close to the fully recurrent population.

Yeah, that's odd all right. So much for my suggestions. :)

This would certainly seem to indicate either a problem with the
implementation or a shortcoming of NEAT's.

Keep us updated, and I'd be interested to see what others' thoughts are on this.

Derek
• ... I ... to ... Mike, have you tried starting NEAT with a fully recurrent population and letting it further complexify? ken
Message 4 of 26 , Apr 1, 2005
• 0 Attachment
--- In neat@yahoogroups.com, "gerbopel" <redcrocodile@h...> wrote:

> -- Further update on my fully recurrent tests. As mentioned they
> passed the simple scenario above (scenario D) with flying colours.
I
> increased the glimpse distance to the entire map and they were able
to
> produce 40 different solutions (not carbon copies) by G1896 (first
> found at G869). For these experiments, my NEAT populations have not
> come anywhere close to the fully recurrent population.
>

Mike, have you tried starting NEAT with a fully recurrent population
and letting it further complexify?

ken
• ... ... I think these inputs will be necessary for the situations when the cat has not seen the mouse yet and has no idea where to look. This could be
Message 5 of 26 , Apr 2, 2005
• 0 Attachment
>> 12-15: Measure of how long since walking on tiles in U,R,D,L
<snip>
>> This provides the cat with an input that he could
>> utilize to avoid backtracking.
>
> Okay, gotcha. However, this set of inputs seems like it might
> be a little redundant. The cat is also receiving input on its
> absolute position each time step as well, right? Do the other
> papers use these sorts of inputs?

I think these inputs will be necessary for the situations when the cat
has not seen the mouse yet and has no idea where to look. This could
be used to give him a *vague* idea of where he has been before (to
avoid checking the same corridor 1000 times).

No, I have not seen these inputs used before. But I have also not
seen a prey capture scenario with restrictions on movement and sight
like this before, so I think it could prove a beneficial, and
necessary, addition. I will be running the 'seek out' behaviour test
in the morning to see if these inputs prove useful.

I changed the way they are measured: -1.0 means no tiles in that
direction to judge (in front of a wall). 0.0 means the cat was just
there and +1.0 means the cat has not been there in a very long time.

> My thinking was basically that the cat just might not be getting
> enough useful information as input upon which to act.
> Biologically, the longer an agent is exposed to stimuli, the
> stronger the impact, correct? If I flash a card at you for 1
> second, it might be more difficult to identify or memorize the
> content than if I let you study it for 10 seconds.

> I was wondering if you basically disabled movement of both agents
> for the first 10 or so time steps, letting the cat see the mouse
> all that time before letting them move and letting the mouse move
> out of sight, that it might make a difference. I don't know.

That is a *very* interesting idea. If there is time at the end I will
go back and see if this has any affect.

Cheers,
Mike
• ... No, I hadn t thought of that! That s an interesting idea. When I give NEAT another go at the end, I ll try that. Mike
Message 6 of 26 , Apr 2, 2005
• 0 Attachment
> Mike, have you tried starting NEAT with a fully recurrent population
> and letting it further complexify?

No, I hadn't thought of that! That's an interesting idea. When I
give NEAT another go at the end, I'll try that.

Mike
• Could you separate the problem code and make it available so that I or someone else might have a go at the same problem? Using your code is the only way to be
Message 7 of 26 , Apr 2, 2005
• 0 Attachment
Could you separate the problem code and make it
available so that I or someone else might have a go at
the same problem?

Using your code is the only way to be certain that we
are solving the same problem.

Thanks,

m

Mitchell Timin
http://annevolve.sourceforge.net

__________________________________
Do you Yahoo!?
http://www.yahoo.com/r/hs
• Mitchell, When the project is wrapped up (first week in May) I will be making everything freely available: dissertation and source. Until then I m just gonna
Message 8 of 26 , Apr 3, 2005
• 0 Attachment
Mitchell,

When the project is wrapped up (first week in May) I will be making
everything freely available: dissertation and source. Until then I'm
just gonna focus on getting everything working :)

Mike
• ... Ken, I am going to give this approach a shot now but have a couple of questions for you. 1) Would you suggest that I do the normal NEAT start with just
Message 9 of 26 , Apr 4, 2005
• 0 Attachment
> Mike, have you tried starting NEAT with a fully recurrent population
> and letting it further complexify?

Ken,

I am going to give this approach a shot now but have a couple of
questions for you.

1) Would you suggest that I do the normal NEAT start with just inputs
and outputs? If so, then the only difference, of course, would be
that the outputs are all fully connected. I don't know if this is
considered recurrent, so I wanted to clarify.

2) Would you suggest that I bump up the % chance of a recurrent link
being added? At the moment I have:

New node: 1%

Cheers,
Mike
• Hi Mike, ... population ... inputs ... Yes, that s right, that is reccurent and it s what I m suggesting. My idea is this: If the task is so memory-dependant
Message 10 of 26 , Apr 6, 2005
• 0 Attachment
Hi Mike,

--- In neat@yahoogroups.com, "gerbopel" <redcrocodile@h...> wrote:
>
> > Mike, have you tried starting NEAT with a fully recurrent
population
> > and letting it further complexify?
>
> Ken,
>
> I am going to give this approach a shot now but have a couple of
> questions for you.
>
> 1) Would you suggest that I do the normal NEAT start with just
inputs
> and outputs? If so, then the only difference, of course, would be
> that the outputs are all fully connected. I don't know if this is
> considered recurrent, so I wanted to clarify.
>

Yes, that's right, that is reccurent and it's what I'm suggesting.
My idea is this: If the task is so memory-dependant that the
initial feedforward population has no possibility of making any
progress at all, it may cause initial stagnation. But if you start
it off with some memory capabilities (i.e. fully recurrent) it can
start building on that capability right away, but also complexify as
is normal in NEAT.

> 2) Would you suggest that I bump up the % chance of a recurrent
> being added? At the moment I have:
>