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

[Dave Denholm]

Gunnar Farneback <address@hidden> writes:

> Dave wrote:
> >    I was just having a look at influence.c, since that is where the
> > profile shows the most time being spent.
> 
> On what platform and what exactly did you run? I just did a profile on
> an AMD Athlon running neurogo.tst and then the influence code doesn't
> take much time. There the pattern matching is in the top.
> 
>   %   cumulative   self              self     total           
>  time   seconds   seconds    calls   s/call   s/call  name    
>  16.05     37.36    37.36 142878688     0.00     0.00  scan_for_patterns
>   6.27     51.96    14.60 104763600     0.00     0.00  check_pattern_light
>   5.08     63.79    11.83   179092     0.00     0.00  compute_primary_domains
>   3.85     72.76     8.97 64742873     0.00     0.00  fastlib
>   3.05     79.87     7.11 30039637     0.00     0.00  do_play_move
>   2.94     86.72     6.85    97175     0.00     0.00  do_push_owl
>   2.39     92.29     5.57 31788626     0.00     0.00  hashtable_search
>   2.29     97.61     5.32 18859166     0.00     0.00  order_moves
>   2.21    102.75     5.14 117157416     0.00     0.00  neighbor_of_string
>   2.14    107.73     4.98 17859836     0.00     0.00  do_dfa_matchpat
>   2.00    112.39     4.66 17704809     0.00     0.00  assimilate_string
>   1.89    116.79     4.40 38474122     0.00     0.00  incremental_order_moves
>   1.80    120.99     4.20 30037001     0.00     0.00  undo_trymove
>   1.64    124.81     3.82 69735447     0.00     0.00  approxlib
>   1.46    128.20     3.39   157757     0.00     0.00  accumulate_influence
>   [...]
> 
> What we see here is probably that the neurogo test suite is rather owl
> intensive. For a more representative profiling one should probably
> replay a couple of entire games against varied opponents (self play
> just doesn't suffice). The most straightforward way to do that would
> be to have a GTP file simulating replay of a selection of games.
> 


Okay, I ran with --replay on an sgf I had lying around. Playing the complete
game, I do indeed see scan_for_patterns high up the list.

But I also see accumulate_influence and do_push_owl() much more prominently
than the above.


I hacked things so that --replay honours --until, and I did find that
matching does not dominate early in the game, but becomes much
more dominant later.

I guess that isn't so much of a surprise.



But one new thought... do_push_owl() just pushes state ?  But looking
at the structure, there is a lot of state to remember.

The other owl functions don't appear anywhere significant in the profile.

So what I'm thinking is : maybe the balance between saving state
and recalculating state is too far towards saving state. Maybe
if we saved less state, or spent more effort saving only what we need,
or made the owl stuff work slightly harder to get hold of its data,
then we'd get an overall speedup by making do_push_owl faster ?





To elaborate on the bit about a grid-based DFA...  what I'm currently
thinking is to operate on groups of 9 (3x3) at a time. As in the
old matcher, we make a pass over the board to generate the
composite representation at each point before doing the matching.

Then the matcher spirals round in groups of 3x3, rather than
each intersection individually.

Obviously this means that we can't have a simple table of next state based
on what is at the current (composite) cell, since there are two many
combinations. So we have to have a list of value / next-state pairs.
And we could avoid the combinatorial explosion due to [ox?] by using the same
and-compare operations as in the other grid matcher.


Given there's a list, we need to be able to backstep from one state and
continue in the previous state from where we left off. Maybe recursion,
maybe just a state array.


I have no idea off-hand what the speed / size impact would be, though.


dd
-- 
address@hidden          http://www.insignia.com