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: [email protected] [mailto:[email protected]] On Behalf Of Fuming Wang Sent: Tuesday, January 25, 2011 3:42 PM To: [email protected] 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 <[email protected]> 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: [email protected] [mailto:[email protected]] On Behalf Of Fuming Wang Sent: Tuesday, January 25, 2011 5:22 AM To: Aja; [email protected] 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 <[email protected]> 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:[email protected]> 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 _______________________________________________ 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
