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: [email protected]
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 <[email protected]> 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: [email protected]
[mailto:[email protected]] On Behalf Of Jacques Basaldúa
Sent: Monday, January 24, 2011 2:41 PM
To: [email protected]
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
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
------------------------------------------------------------------------------
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
