[Computer-go] Computing CFG distance in practice

[Brian Sheppard]

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


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