[Computer-go] Computing CFG distance in practice

[Fuming Wang]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20110125/8189b4aa/attachment.html>