[Computer-go] Computing CFG distance in practice

[Aja]

Common Fate Graph (CFG) was proposed in the paper "Learning on Graphs in the Game of Go" (http://research.microsoft.com/apps/pubs/default.aspx?id=65629).

In the game of Go, Except location proximity, I think liberty proximity is also important. That is to say, it's good to play proximity to the previous move, and also good to play proximity to the liberty points of the string that contains the previous move. 

Aja
  ----- Original Message ----- 
  From: Fuming Wang 
  To: computer-go at dvandva.org 
  Sent: Tuesday, January 25, 2011 1:38 PM
  Subject: Re: [Computer-go] Computing CFG distance in practice


  how to calculate CFG distance?

  Fuming


  On Tue, Jan 25, 2011 at 3:49 AM, Brian Sheppard <sheppardco at aol.com> wrote:

    I use CFG distance only in the tree. The playout uses the concept "adjacent"
    which is trivial to compute.

    The only distance I am concerned about is the distance to the last move, and
    there are only 4 classes: distance 1,2,3, and >3. So it is cheap.

    The advantage is in semeais. Moves at CFG distance 3 are the outside
    liberties of the opponent's string.

    There was not a big difference compared to the other two heuristics. I found
    that

    - CFG is best
    - max(dx, dy) + (dx + dy)/2 is second best
    - Manhattan is third.

    Brian


    -----Original Message-----
    From: computer-go-bounces at dvandva.org
    [mailto:computer-go-bounces at dvandva.org] On Behalf Of Jacques Basaldúa
    Sent: Monday, January 24, 2011 2:41 PM
    To: computer-go at dvandva.org
    Subject: [Computer-go] Computing CFG distance in practice

    Hi,

    I got a lot of improvement recently (something you all
    did long time ago) with proximity heuristics. I am using

    Manhattan distance:
      d = max(dx, dy)

    and
      d = max(dx, dy) + (dx + dy)/2

    where dx = abs(ex - ox) and dy = abs(ey - oy)

    But many people report CFG distance to be superior.

    What do you do:

    a. Compute it in root. Then build a lookup table and
    use the LUT during playouts and tree search.

    b. Compute the shortest path from (ox, oy) to (ex, ey)
    connected by the stones on the board each time you need
    to evaluate a distance.

    I don't like a because it looks inefficient as the
    board changes a lot during the search.

    I don't like b because it looks computing intense
    unless there is some smart idea I am missing.


    Jacques.







    _______________________________________________
    Computer-go mailing list
    Computer-go at dvandva.org
    http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

    _______________________________________________
    Computer-go mailing list
    Computer-go at dvandva.org
    http://dvandva.org/cgi-bin/mailman/listinfo/computer-go





------------------------------------------------------------------------------


  _______________________________________________
  Computer-go mailing list
  Computer-go at dvandva.org
  http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20110125/122536f5/attachment.html>