Re: [gnugo-devel] more on dfa

[Tanguy URVOY]

Hello,

Dave Denholm wrote:
> Well, I don't think the data is particularly convincing : the dfa does
> appear to be able to truncate its search before spiralling too far out.

Your test is interesting however, it shows
that pattern density fall exponentially
relatively to the deepness in the DFA.


During a game the board does not change
a lot, the spiral scan follows almost 
each time the same path in the DFA.


There are many ways to optimize the DFA:

1- use a reverse spiral and a stack to
implement an incremental scanner
as explained in the texinfo file.

2- use a non-detertministic automaton
(NFA) to save memory.
We may control the amount of determinism
in the automaton: 
 - fully deterministic: very fast and very big
 - fully non deterministic: slow but small.
We may also build on the fly
an heuristic according to the board values
to speedup the scan of the NFA.
This is a bit complicated but it should be almost 
as efficient as the DFA algorithm with a smaller automaton.

3- Use one automaton by intersection
instead of a single one.
This allow us to remove OUTBOARD values.
This would probably be better but
this is boardsize dependent and it
has to be checked.


Tanguy


> plotting column 2 shows that the number of visits falls off fairly
> rapidly with distance.
> 
>  2.5e+07 ++-----+-----+------+------+------+-----+------+------+-----+-----++
>          AAAA   +     +      +      +      +     'dfa.txt' using 1:2 + A    +
>          |                                                                  |
>          |  AA                                                              |
>    2e+07 ++                                                                ++
>          |    A                                                             |
>          |    AA                                                            |
>          |                                                                  |
>  1.5e+07 ++                                                                ++
>          |      A                                                           |
>          |      A                                                           |
>          |       A                                                          |
>    1e+07 ++       A                                                        ++
>          |        AA                                                        |
>          |          A                                                       |
>          |          AA                                                      |
>    5e+06 ++           A                                                    ++
>          |            AAAA                                                  |
>          |                AAAAAA                                            |
>          +      +     +      +  AAAAAAAAAAAAA    +      +      +     +      +
>        0 ++-----+-----+------+------+------+-AAAAAAAAAAAAAAAAAAAAAAAAAAAAA-++
>          0     10    20     30     40     50    60     70     80    90     100
> 
> plotting ($3/$5) is intended to give an average cost per pattern.
> However, it pretty much flattens off, rather than growing and then
> shrinking, as I had been hoping.
> 
>  12 ++-----+------+-------+------+------+------+------+-------+------+-----++
>     +      +      +       +      +      +  'dfa.txt' using 1:($3/$5) + A    +
>     |                   AAAAA  AAAAAAAAAAA                                  |
>  10 ++              AAAA     AAA         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA  ++
>     |   AAA   AAAAAA                                                        |
>     |     A AA                                                              |
>     |   A  A                                                                |
>   8 ++                                                                     ++
>     |  A                                                                    |
>     |                                                                       |
>   6 ++A                                                                    ++
>     |                                                                       |
>     |                                                                       |
>   4 ++                                                                     ++
>     |                                                                       |
>     |                                                                       |
>     |                                                                       |
>   2 ++                                                                     ++
>     |                                                                       |
>     +      +      +       +      +      +      +      +       +      +      +
>   0 ++-----+------+-------+------+------+------+------+-------+------+-----++
>     0     10     20      30     40     50     60     70      80     90     100
> 

-- 
-------------------------------------
Tanguy Urvoy http://www.turvoy.fr.st
-------------------------------------