[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] more on dfa
From: |
Tanguy URVOY |
Subject: |
Re: [gnugo-devel] more on dfa |
Date: |
Thu, 10 Oct 2002 10:47:17 +0200 |
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
-------------------------------------
- [gnugo-devel] more on dfa, Dave Denholm, 2002/10/05
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/07
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/09
- Re: [gnugo-devel] more on dfa,
Tanguy URVOY <=
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/10
- Re: [gnugo-devel] more on dfa, Tanguy URVOY, 2002/10/11
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/11
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/12
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/12
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/14
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/19
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/11