Re: [glob2-devel] gradient improvement

[Nuage]

Alright, there is a possible problem. I did hope to keep it secret :P for the
sake of the performance. You can notice the experiment I did into the commented
line of the code:
//assert(listCountWrite<=size);

Now, what do we do ?

1) All parts of the code but the AI provide "clean" listedAddr. That mean that
all "gameplay" gradients are computed correctly. Here the listedAddr[size] is
big enough. Increasing its size would only decrease performance by increasing
the cache misses.

2) It's not likely to get a wrong gradient computation. To do so, all the
listedAddr[size] has to be filled. It's unlikely because the gradient propagate
as a "growing circle", and then is proportionally linear to the map size
O(sizeX+sizeY). While the listedAddr[size] has size=sizeX*sizeY, which is much
bigger.

3) At worse, if the AI provide a list which is too bad, and lead to a wrong
gradient, it will make a sub-optimal choice.

4) For an error to happen, the AI need to provide a source with high
differences. Which I don't.

5) I added some code to check how this behave. I compute the biggest size of the
queue at any moment of the gradient computation, and report it once per
gradient. Here is the result for all gradients of a game:

listCountSizeStatsOver=0
listCountSizeStats:
[    0->  255]: 9906
[  256->  511]: 4244
[  512->  767]: 6177
[  768-> 1023]: 1648
[ 1024-> 1279]: 1802
[ 1280-> 1535]:    0
[ 1536-> 1791]:    2
[ 1792-> 2047]:    3
[ 2048-> 2303]:    0
[ 2304-> 2559]:    0
[ 2560-> 2815]:    1
[ 2816-> 3071]:    1
[ 3072-> 3327]:    2
[ 3328-> 3583]:    0
[ 3584-> 3839]:    0
[ 3840-> 4095]:    0
[ 4096-> 4351]:    0
[ 4352-> 4607]:    0
[ 4608-> 4863]:   13
[ 4864-> 5119]:    0
[ 5120-> 5375]:    3
[ 5376-> 5631]:    2
[ 5632-> 5887]:    1
[ 5888-> 6143]:    3
[ 6144-> 6399]:   15
[ 6400-> 6655]:    2
[ 6656-> 6911]:    1
[ 6912-> 7167]:    4
[ 7168-> 7423]:    0
[ 7424-> 7679]:    1
[ 7680-> 7935]:    0
[ 7936-> 8191]:   13
[ 8192-> 8447]:    0
[ 8448-> 8703]:    3
[ 8704-> 8959]:    2
[ 8960-> 9215]:    1
[ 9216-> 9471]:    1
[ 9472-> 9727]:    0
[ 9728-> 9983]:   14
[ 9984->10239]:    5
[10240->10495]:    0
[10496->10751]:    1
[10752->11007]:    1
[11008->11263]:    3
[11264->11519]:    1
[11520->11775]:    0
[11776->12031]:    0
[12032->12287]:    0
[12288->12543]:    0
[12544->12799]:    0
[12800->13055]:    0
[13056->13311]:    0
[13312->13567]:    0
[13568->13823]:    0
[13824->14079]:    0
[14080->14335]:    0
[14336->14591]:    0
[14592->14847]:    0
[14848->15103]:    0
[15104->15359]:    0
[15360->15615]:    0
[15616->15871]:    0
[15872->16127]:    0
[16128->16383]:    0

The worst is 11456 over 16384. Note that it never "smash" the queue. You can
play with it by adding:
#define check_gradient_error_probability
in Map.h

If you can notice any "smash", we can add a simple argument "const size_t
listedAddrSize" which will be big enough for everything. The method caller will
use a bigger size in case it may smash, like the AI. Well, maybe you want this
to be added now anway ? Or you see another nice solution ?

See, I don't want to change the AI call, because now, it works, it's simple, and
it's powerful. I mean, "updateGlobalGradientSlow()" do what I want, and do it
nicely. It's very convenient to use it for the AI. Well, I don't mind creating a
special case for this one, if this worth it.

Nuage

ps: I added some comments here too:

Kai Antweiler wrote:
>>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.
It can actually lead to poor performance, as some fields are computed twice. If
very unlikely cases, this can lead to listedAddr "overflow", and then, gradient
computation error. As the engine only provide "clean" listedAddr, it's fine. At
worse, the AI will make bad choices.



> Imagine that the fields (x=0,y=0) (x=1,y=1) have gradient 9.
I guess you mean (x=0; y=0) and (x=1; y=0) 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.
In this 2x3 max example, we have size=6. We assume there is no wrap, this will
only be easier to prove there is a bug if any. Inside the list we have (0;0),
(1;0), (2;0) and just added (0;1), (1;1). That's an overall of 5, which is fine
yet. And just after this (0;0) is released of the list.

> 1 1 1  
> 9 9 8  
> * 

When you update this one, the corner is updated too
1 1 1
9 9 8
  *

as a result you get:
8 8 8
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.
>