Re: [gnugo-devel] engine/influence.c (and DFA)

[Arend Bayer]

On 3 Sep 2002, Dave Denholm wrote:

> Hi,
>    I was just having a look at influence.c, since that is where the
> profile shows the most time being spent.
>
> Noticed something odd about the unrolled loop in accumulate_influence():
> it still has 'continue' statements in it, which means, unless I'm missing
> something obvious, the behaviour is different when the loop is unrolled or 
> not.
>
> When the loop is not unrolled, the continue means to go and do the
> next direction.
>
> But when the loop is unrolled, the same continue statement means
> abandon this queue entry entirely, and go on to the next one.

Indeed I get quite different results when I define
EXPLICIT_LOOP_UNROLLING to 0. We should fix that, but it might need some
retuning of the influence.

> - might explain why  gprof -l  only seemed to care about the first few
>  expansions of the macro ?

I also once noticed an asymmetry in the influence spreading, but never
got around to investigate it in detail.


> [ I was actually just looking to see if the   / (b*c)  could
>  be turned into a single multiply, eg  c is 1 for straight and
>  2 for diagonal, so could set invb = 1/b initially, then halve it
>  after doing the straight ones. Then just multiply by invb rather
>  than dividing by (b*c)
>
>  Oh - and ((arg_di)*(i-m) + (arg_dj)*(j-n))  is evaluated twice - don't
>  know if the compiler is smart enough to spot this, given the separation
>
>  And could store the inverse damping factors so they can be multiplied
>  rather than divided. Or store (current_strength / damping) as a loop
>  invariant...
> ]

Another idea I wanted to try out once is: Instead of spreading the
influence from the influence sources across the board, we could
at each intersection start a spiral collecting the influence sources
that contribute to this intersection, i.e. doing exacty the reverse of
what we are doing now.

This would mean we could have much better cutoff conditions; also it
would be possible to only reevaluate the points in the neighbourhood of
the move made when computing move_influence.

(If we want to implement some sort of lookahead for local fights, a
extremely fast influence evaluation would be extremely useful.)

Arend