What other methods have you tried? Lukasz
On Thu, Apr 2, 2009 at 17:14, <w...@swcp.com> wrote: > Isaac, > > I implemented about 6 way to track liberties, > a couple years ago, and measured the running > performance, and by far the best is also the > simplest: keep an array of liberties for each > chain, and do a simple linear search. > > This may seem slow, but it has a couple real > advantages. First, it works with the cache > to maximize locality. Second it is very simple. > > Michael Wing > >> > Many Faces also counts real liberties, and is quite fast enough. >> > >> >> > > I can confirm, with a bit of optimization, counting real liberties is >> > > only marginally slower than counting pseudo-liberties. So there's >> > > really no benefit that I can see from using pseudo liberties. >> > > >> > > Mark >> > > >> >> > > > When John Tromp and I were thinking about these things in 2007 we >> > > > decided to switch to counting real liberties instead of >> > > > pseudo-liberties. Someone (Rémi?) told us that in the end the >> > > > performance difference wasn't very large, and we verified this. >> > > > >> > > > Álvaro. >> > > > >> >> Thanks. What is a fast way to track liberties? >> >> I thought about bit arrays. Merging to groups would take O(1), counting >> takes O(1)-ish, and memory required would be small. >> >> Of course I could also use STL's "set" structure, but I found it to be >> quite slow - it implements a set using a RB-tree. This was actually the >> reason I switched to pseudo libs. >> >> -ibd. >> -- >> Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: > http://www.gmx.net/de/go/multimessenger01 >> _______________________________________________ >> computer-go mailing list >> computer-go@computer-go.org >> http://www.computer-go.org/mailman/listinfo/computer-go/ >> > > > > -- > > > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/