[Computer-go] Computing CFG distance in practice

[Fuming Wang]

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 <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/20110126/f2c38750/attachment.html>