Re: computer-go: perfect play : a new fractal algorithm

[Serge Boisse <boisse@xxxxxxxxxxxx>]

Vlad Dumitrescu wrote:
> 
> my first impression: interesting approach!

thanks, vlad.

> the big problem seems to be how to reduce the board size without losing
> importnt information. If a reduced group becomes dead (because there isn't
> enough space to make it alive), then the reduction fails...

yes, of course you will lose information. The key word is "important". My
assumption is that you will not lose important information. This is highly
dependant on the details of the reduction algorithm, which I did'nt want to dig
trough. If a threat or atari on the smaller board is an (even less important)
threat on the corresponding group on the larger board, important information is
not lost.

> one way to handle this might be using a method presented here for som months
> ago - I'm not sure I remember correctly -- building a "feature tree" where a
> string of stones or liberties becomes just a node... if the reduced board
> position has the same feature tree, then it might be close enough to the
> original one.

yes, i remember of that. But, alas, even the feature tree can not be exactly the
same in both boards. Suppose a chain has a two distinct (not adjacent) liberties
on the larger board, the corresponding chain on the smaller board may have only
one (or even none). But the similarity btw both feature trees can be computed,
and this number can give an evaluation of how "accurate" the reduction algo is,
and may be used to select the "best" choice for local reductions and guiding the
reduction process. Interesting idea.

A good working reduction algo may need to use a try and evaluate approach. One
critera is the similarities btw both boards, another can be the similarities btw
both feature trees.

> Why do you say the branching factor is reduced from 361 to 4? it is so
> directly at the 19x19 level, but you have to search the reduced boards too,
> thus there are more moves to look into before being able to choose one of
> the 4...
Of course you're right. I was a bit provocating when saying you have 361 to 4.
However, since the searching process is an exponential one, and since the number
of searches is a polynomial of degree number of subboards, the unknown beeing
the (exponential) local searches, if you reduce the exponent, even thought you
increase  the number of searches, you end up with a dramatic net gain.

> new approaches are always welcome! :-)
> /Vlad

-- 
                    ____________ 
                   / Linux now !\     ("`-/")_.-'"``-._    _
          ,,,    O \____________/   o  @ @ `; -._    )-;-,_))
         /'^'\ o°    / catch it ?\O°  (v_,)'  _  )`-.\  `---'
        ( O O )      \___________/  __.- _..-_/ / ((.'
 +---oOOo-(_)-oOOo-----------------((,.-'---((,/---------+
 |  Serge Boisse                                         |
 |  SERVICE TECHNIQUE DE LA NAVIGATION AERIENNE (STNA)   |
 |  ODS FRANCE project, http://www.stna.dgac.fr/phidias  |
 |  tel: (0)562 14 5731      mailto:boisse@xxxxxxxxxxxxxxxxx  |
 |  homepages: http://www.multimania.com/boisse          |
 |  and:       http://www.multimania.com/unitedplanet    |
 +-----------Oooo----------------------------------------+ 
     oooO   (   )
     (   )   ) /
      \ (   (_/
       \_)