Re: [glob2-devel] gradient improvement

[Kai Antweiler]

> Currently, the method caller can put anything it want into listedAddr. 
> AICastor
> actually use it for building placement, and I guess AINicowar too. Check who 
> is
> creating it for further debugging and info.
>
> If we want to rely on the fact that listedAddr is ordered for further
> optimization, we have to fork the cases. One who can call the optimized one, 
> and
> one who can only call the less-optimized one. This would be smart actually.


It is not (only) for optimization purposes.
Theoreticly, the way it is now can lead to wrong gradients.
I didn't notice this until Simon said called it a bug.
That was reason enough for me to think it through again.
Ordering the list would not help.  The only simple constraint I see
would be to force that every field listed in listedAddr during
initialization must have the same value.


At first I thought that using listedAddr as a queue with &(size-1) and  
putting continue after if(g <= 2) instead of a return was smart. 
(And it is on average.) 
It looks like this allows more flexiblity in the initialization of
listedAddr, but theoretically this can lead to wrong gradients
nevertheless.

Imagine that the fields (x=0,y=0) (x=1,y=1) have gradient 9.
(x=0,y=1) (x=1,y=1) (x=2,y=1) have gradient 1 and are the only
fields which will not be initialized into listedAddr.
All other fields have gradient 8.
I have drawn the necessary fields to understand the point below.
The * shows which field is active.
We begin with (x=0,y=0) and put the two fields above this field
into listedAddr.  Thereby we overwrite the places of (x=0,y=0)
and (x=1,y=0) in listedAddr sience this array is full.
(x=1,y=0) will therefore never be active.
 
1 1 1  
9 9 8  
* 
 
* 
8 8 1 
9 9 8 
 
  * 
8 8 1 
9 9 8 
 
8 8 7 
9 9 8 
    * 

See the 7.  This will never change.
But this part ofthe gradient should after computation look like:

8 8 8 
9 9 8 


So either we constraint the init or we accept that the gradients
can be wrong, and mention this and its reason in the code.

We also could check during each iteration of the gradient computation
if (listCountWrite - listCountRead > size-8)
and if this case really occurs, double the size of listedAddr
copy the old list into the new one, double size and go on.
Sience this should rarely happen (really?) the overhead would be the
additional if clause.

But forcing the constraint should be beneficial for optimization.
Indead forking will be the quickest solution (nice idea), but the
unconstrainted inits have to call the modified gradient calculation
with the safety conditional.

-- 
Kai Antweiler