Got it. Thanks! Best, Fuming
On Wed, Jan 26, 2011 at 4:51 AM, Brian Sheppard <[email protected]> wrote: > 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 <[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 >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
