[Computer-go] Computing CFG distance in practice

Tue Jan 25 12:51:29 PST 2011

I believe it was a suggestion of the Mogo team.

One of their papers refers to a "topological distance" defined as the
Manhattan distance but where all points on the same string are at the same
distance. it should be clear how this definition leads to the algorithm
below.

Brian

From: computer-go-bounces at dvandva.org
[mailto:computer-go-bounces at dvandva.org] On Behalf Of Fuming Wang
Sent: Tuesday, January 25, 2011 3:42 PM
To: computer-go at dvandva.org
Subject: Re: [Computer-go] Computing CFG distance in practice

Hi Brain,

Thanks for the explanation. I understand the procedure would give a more
meaningfull distance between an empty site and the last move. I went through
the original paper again, and still could not figure out how this
caluculation procedure is derived from that paper. CFG is a graph as defined
in the paper, and it is used to train some neuro-network for Go playing.
Could you or anyone point me to the place that CFG distance is first used?

Best,
Fuming

On Tue, Jan 25, 2011 at 10:41 PM, Brian Sheppard <sheppardco at aol.com> wrote:

CFG distance:

1) Start at the last move. That is the full set of points at distance 0.

2) Iterate, starting at N=1. Calculate the points at distance N by:

3) If an empty point is not at distance < N and is adjacent to a point at
distance < N, then it is at distance N.

4) If an occupied point is not at distance < N and is adjacent to a point at
distance < N, then all of the points on that string are at distance N.

5) I stop iterating at N=3. I have not checked whether there is useful
information at higher N.

Brian

From: computer-go-bounces at dvandva.org
[mailto:computer-go-bounces at dvandva.org] On Behalf Of Fuming Wang
Sent: Tuesday, January 25, 2011 5:22 AM
To: Aja; computer-go at dvandva.org

Subject: Re: [Computer-go] Computing CFG distance in practice

I think I understand what CFG is. CFG distance between two string is the
shortest distance between any stones of the two strings, is that right?

Thanks,
Fuming

On Tue, Jan 25, 2011 at 1:58 PM, Aja <ajahuang at gmail.com> wrote:

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 <mailto:fumingw85 at gmail.com>  

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

_______________________________________________
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/fddb0c20/attachment.html>