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/
