No. Many Faces uses union find. I looked through some old literature, including Anders’ thesis. Even though we all used this algorithm it seems he didn’t mention it, probably because it seemed too obvious. I do use bitmaps for pattern matching arbitrary shaped patterns up to 8x8.
David From: computer-go-boun...@dvandva.org [mailto:computer-go-boun...@dvandva.org] On Behalf Of Peter Drake Sent: Saturday, May 24, 2014 11:05 AM To: computer-go@dvandva.org Subject: Re: [Computer-go] Bitwise-parallel surround capture David: Are you saying that Many Faces of Go uses bitmaps as its underlying board representation? (I'm in the process of rewriting Orego's board class, so I'm particularly interested in knowing if I should do it differently for speed.) On Sat, May 24, 2014 at 10:58 AM, David Fotland <fotl...@smart-games.com> wrote: The referenced union-find algorithm has been known and used by computer go programs since at least the early 80's, and I'm sure it was published before 2011. I think your implementation of union-find is a little slow. Many Faces of Go uses this algorithm, and on 9x9 got about 55k playouts per second on a much slower machine in 2008. Here is a prior discussion of bitmap performance. https://groups.google.com/forum/#!searchin/computer-go-archive/fotland$20pla <https://groups.google.com/forum/#!searchin/computer-go-archive/fotland$20playouts$20per$20second/computer-go-archive/IdZtmM1Q6Ow/Q4b1IxgdkZYJ> youts$20per$20second/computer-go-archive/IdZtmM1Q6Ow/Q4b1IxgdkZYJ A bitmap representation can be used for fast pattern matching, so there are other advantages than just performance to using it as the base representation. > -----Original Message----- > From: computer-go-boun...@dvandva.org [mailto:computer-go- > boun...@dvandva.org] On Behalf Of Cameron Browne > Sent: Saturday, May 24, 2014 2:45 AM > To: computer-go@dvandva.org > Subject: [Computer-go] Bitwise-parallel surround capture > > Hi, > > This draft paper describes a simple bitwise-parallel method for > performing surround capture: http://www.cameronius.com/research/go- > bits-1.pdf > > Before I submit it, I just wanted to check with this list that the > method is not known and already in use. > > Any general comments on the paper would also be appreciated. > > Regards, > Cameron > > _______________________________________________ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go -- Peter Drake https://sites.google.com/a/lclark.edu/drake/
_______________________________________________ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
