[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: computer-go <computer-go@xxxxxxxxxxxxxxx>*Subject*: Re: [computer-go] Groups, liberties, and such*From*: drd@xxxxxxx*Date*: Mon, 17 Oct 2005 13:18:42 -0400*Delivered-to*: marc.hamelin@xxxxxxxxxxxxxxxxx*Delivered-to*: computer-go@xxxxxxxxxxxxxxxxx*In-reply-to*: <200510171302.15612.drd@xxxxxxxxxxxxxxxxx>*List-archive*: <http://computer-go.org/pipermail/computer-go>*List-help*: <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=help>*List-id*: computer-go <computer-go.computer-go.org>*List-post*: <mailto:computer-go@xxxxxxxxxxxxxxxxx>*List-subscribe*: <http://hosting.midvalleyhosting.com/mailman/listinfo/computer-go>,<mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=subscribe>*List-unsubscribe*: <http://hosting.midvalleyhosting.com/mailman/listinfo/computer-go>,<mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=unsubscribe>*References*: <43501075.6090200@xxxxxxxxxxxxxxxxx> <4353C182.3000901@xxxxxxxxxxxxxxxxx><200510171302.15612.drd@xxxxxxxxxxxxxxxxx>*Reply-to*: computer-go <computer-go@xxxxxxxxxxxxxxx>*Sender*: computer-go-bounces@xxxxxxxxxxxxxxx*User-agent*: KMail/1.7.2

Woops, I just realized that my calculation is wrong. The 2 old strings may have several liberties in common. I think it is easiest just to re-calculate, the amortized time should be quite small. - Don On Monday 17 October 2005 1:02 pm, drd@xxxxxxxxxxxxxxxxx wrote: > Jason, > > When a move connects 2 strings, isn't it easy and fast to calculate > the liberty count of the newly combined string? > > new_count = old_string_A_count + old_string_B_count - 1 + LNC. > > LNC means Liberties Not in Common. For the newly placed stone (that does > the connecting), we look at the 4 neighbor points. If they are empty, > we tally 1 if they are not liberties of EITHER of the OLD strings. > This idea is easily extended for connections of 3 or 4 groups. > > When connecting 2 groups, you would have to look at 6 points at most, > the 2 possible new liberties, and the 3 possible points around these new > liberties to check if they touch the old group. > > Compared to other more complicated schemes, this is fast. What little > extra time this takes is very tiny when amortized over all the moves > your program will be making. > > Am I understanding the problem correctly or am I confused about your > requirements? > > If the new connection is also a capture, this doesn't work, but that's > a problem for any of the incremental liberty calculations, not just the > connecting ones. > > - Don > > On Monday 17 October 2005 11:21 am, Jason House wrote: > > A true liberty count is only needed for chains with only a few liberties > > (less than 4?). Chains with more liberties are generally assumed stable > > and higher order logic is required for an overall group stability. The > > exceptional case of a semai requires much more than conventional > > liberties. > > > > I think that I'll track pseudo-liberties (since it's just so darn easy), > > and calculate actual liberties only when the result can be less than > > some fixed value (initially 4). Actually I may do something as force a > > liberty calculation if the pseudo-liberties are less than 10. > > > > If a semai occurs, an exact calculation of liberties is not nearly > > enough and extra work will have to be done anyway, so I won't mind > > paying for the liberty calculation. > > > > Rémi Coulom wrote: > > > I had very similar ideas to yours when I started to write CrazyStone. I > > > started with a disjoint-set data structure, and the > > > hope that I could do all incremental updates locally, without going > > > through long chains. I gave up because of the problem of updating > > > liberties. As you wrote, it seems very difficult to incrementally > > > update liberty counts when chains are merged. So I gave up with the > > > disjoint-set data structure, and I now store a group number for each > > > stone. > > > > > > It is rather rare that long chains are merged together, so the merging > > > operation can be made very efficient by not exploring the longest > > > chain. I found that not passing through the longest chain is a very big > > > speedup in CrazyStone. But that may depend on your data structure. > > > > David Fotland wrote: > > > 1. I don't know of one. Many Faces keeps a sorted list of liberties > > > and a count of liberties for each chain. When chains are merged, the > > > sorted lists are merged (one pass through both), and the count is > > > updated during the merge. > > > > > > 2. For tactical stability, 4 liberties is enough. When I do tactical > > > look ahead I stop when a chain can be proven to have 4 liberties or > > > more. For semeai, I calculate several liberty-related values, which are > > > estimates of the number of moves it takes to capture a chain with each > > > side to move first. To compare liberties in a semeai you need > > > distinguish between shared (inside) liberties, and outside liberties, > > > and you need to compare the number of eyes in each group. There is a > > > good discussion in "The Second Book of Go". > > > > _______________________________________________ > > computer-go mailing list > > computer-go@xxxxxxxxxxxxxxxxx > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > _______________________________________________ > computer-go mailing list > computer-go@xxxxxxxxxxxxxxxxx > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list computer-go@xxxxxxxxxxxxxxxxx http://www.computer-go.org/mailman/listinfo/computer-go/

**References**:**[computer-go] Groups, liberties, and such***From:*Jason House

**Re: [computer-go] Groups, liberties, and such***From:*Jason House

**Re: [computer-go] Groups, liberties, and such***From:*drd

- Prev by Date:
**Re: [computer-go] Groups, liberties, and such** - Next by Date:
**Re: [computer-go] Groups, liberties, and such** - Previous by thread:
**Re: [computer-go] Groups, liberties, and such** - Next by thread:
**Re: [computer-go] Groups, liberties, and such** - Index(es):