Re: [computer-go] Re: pseudoliberties
Just out of curiosity, how did you calculate these numbers? On 3/31/07, Gunnar Farneback [EMAIL PROTECTED] wrote: The remaining list up to 19x19 will come when the computations are done. Maximum number of pseudoliberties for a single string on square boardsizes up to 19x19: 1x1 0 2x2 2 3x3 8 4x4 14 5x5 24 6x6 37 7x7 52 8x8 70 9x9 91 10x10 114 11x11 141 12x12 169 13x13 201 14x14 234 15x15 271 16x16 310 17x17 353 18x18 397 19x19 445 Example of 445 pseudoliberties on 19x19: .O.O.O.O.O.O.O.O.O. OOO .O.O.O.O.O.O.O.O.O. OOO.O.OOO.O.O.O.OOO .O.OOO.O.OOO.O. OOO.O.O.O.O.O.O.OOO .O.O.O.O.O. OOO.O.O.O.O.OOO .O.OOO.OOO.O.O.O.O. OOO.O.O.O.O.OOO .O.O.O.O.O.O.O. O.O.O.O.O.O .O.O.OOO.OOO.O.O.OO OOO.O.O.O.O.O.O.OO. .O.OO.O OOO.O.O.O.O.O.O.OOO .O.O.O.O.O.O.O.O.O. OOO .O.O.O.O.O.O.O.O.O. /Gunnar ___ 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/
Re: [computer-go] Re: pseudoliberties
Chris wrote: Just out of curiosity, how did you calculate these numbers? Dynamic programming, along the same lines as the algorithm to count legal board positions which was discussed on this list two years ago and is described in depth in the paper linked from http://homepages.cwi.nl/~tromp/go/legal.html /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
It seems kind of dream algorithm to be able extend results for bigger board sizes. Exact knowledge is allways good anyway. So amazing, it is suitable for max pseudo liberties for one string, count of legal board positions, maybe there is other properties for board this fits or more complex issues which this algorithm could be somehow extended any studies about that? I need to study it anyway, thanks. t. harri - Original Message - From: Gunnar Farneback [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, April 01, 2007 9:22 PM Subject: Re: [computer-go] Re: pseudoliberties Chris wrote: Just out of curiosity, how did you calculate these numbers? Dynamic programming, along the same lines as the algorithm to count legal board positions which was discussed on this list two years ago and is described in depth in the paper linked from http://homepages.cwi.nl/~tromp/go/legal.html /Gunnar ___ 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/
Re: [computer-go] Re: pseudoliberties other programmable concepts
This may be an instance where bitmaps would be handy - altho expensive in terms of memory - a bitmap would require NxN bits for each string of connected stones. For each connected string, maintain a bitmap of adjacent liberties. When two strings are connected, add the two bitmaps together - this would be a bitwise logical OR operation. TV dinner still cooling? Check out Tonight's Picks on Yahoo! TV. http://tv.yahoo.com/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
After some trial and error, I got 90 * * * * * * * * * * * * *** * * * *** * * * * * * * * * * * * On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: Is 88 the maximum number of pseuoliberties a string can have on 9x9? Make that 89:-) -John ___ 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/
Re: [computer-go] Re: pseudoliberties
What's a pseudo-liberty? And how can there be more of them than there are empty intersections (81) on the board? - Original Message From: Jason House [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, March 29, 2007 1:02:01 PM Subject: Re: [computer-go] Re: pseudoliberties After some trial and error, I got 90 * * * * * * * * * * * * *** * * * *** * * * * * * * * * * * * On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: Is 88 the maximum number of pseuoliberties a string can have on 9x9? Make that 89:-) -John ___ 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/
Re: [computer-go] Re: pseudoliberties
It appears to me that at least 91 is possible: .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xxx.xxx. Weston On 3/29/07, Jason House [EMAIL PROTECTED] wrote: After some trial and error, I got 90 * * * * * * * * * * * * *** * * * *** * * * * * * * * * * * * On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: Is 88 the maximum number of pseuoliberties a string can have on 9x9? Make that 89:-) -John ___ 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/
Re: [computer-go] Re: pseudoliberties
A pseudo-liberty is a pairing of a stone in the group and an adjacent, empty intersection. On 3/29/07, Jim O'Flaherty, Jr. [EMAIL PROTECTED] wrote: What's a pseudo-liberty? And how can there be more of them than there are empty intersections (81) on the board? - Original Message From: Jason House [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, March 29, 2007 1:02:01 PM Subject: Re: [computer-go] Re: pseudoliberties After some trial and error, I got 90 * * * * * * * * * * * * *** * * * *** * * * * * * * * * * * * On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: Is 88 the maximum number of pseuoliberties a string can have on 9x9? Make that 89:-) -John ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote: It appears to me that at least 91 is possible: .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xxx.xxx. Nice! If you use O's instead like .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OOO.OOO. it looks pretty artistic, like a vase with a flower inside:-) -John ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
Weston wrote: It appears to me that at least 91 is possible: .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xxx.xxx. Congratulations, you reached the maximum. Here are the maximum number of pseudoliberties up to 13x13: 1x1 0 2x2 2 3x3 8 4x4 14 5x5 24 6x6 37 7x7 52 8x8 70 9x9 91 10x10 114 11x11 141 12x12 169 13x13 201 The remaining list up to 19x19 will come when the computations are done. An example of 201 pseudoliberties on 13x13: .O.O.O.O.O.O. O .O.O.O.O.O.O. OOO.OOO.O.OOO .O.O.O.OOO.O. O.O.O.OOO .O.O.OO.O OOO.O.O.O.OO. .O.O.O.OO OOO.O.O.OOO.O .O.O.O.O.O.O. O .O.O.O.O.O.O. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
On Thu, 2007-03-29 at 14:29 -0400, John Tromp wrote: On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote: It appears to me that at least 91 is possible: .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xxx.xxx. Nice! If you use O's instead like .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OOO.OOO. it looks pretty artistic, like a vase with a flower inside:-) If I drink a beer and cross my eyes it does! - Don -John ___ 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/
Re: [computer-go] Re: pseudoliberties
On Thu, 2007-03-29 at 11:08 -0700, Jim O'Flaherty, Jr. wrote: What's a pseudo-liberty? And how can there be more of them than there are empty intersections (81) on the board? That's why they are pseudo - they may not be real :-) Actually, a pseduo-liberty is an actual liberty, but it can be counted multiple time. Since an empty point can be surrounded by up to 4 stones, it can get counted 4 times. It's really a way to incrementally update liberties in a fast way - each stone keeps it's own count of liberties and it is summed - but of course it doesn't represent the true number of liberties since a point can get counted 2 or more times.However, if the count goes to zero, the count is correct. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote: It appears to me that at least 91 is possible: Nice! If you use O's instead like .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OOO.OOO. it looks pretty artistic, like a vase with a flower inside:-) :) It appears that you can get 92 as well, by replacing the two empty intersections along the upper edge of my diagram with a single one in the center of that edge, and placing an empty intersection on one of the other intersections along the central line of symmetry. Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
I get 144 with a simple alternating pattern: 5 .O.O.O.O. 13 4 O.O.O.O.O 16 5 .O.O.O.O. 18 4 O.O.O.O.O 16 5 .O.O.O.O. 18 4 O.O.O.O.O 16 5 .O.O.O.O. 18 4 O.O.O.O.O 16 5 .O.O.O.O. 13 41 points 144 Fewer liberty points: 41 versus 54 in your pattern, but more strings, hence more duplicate counts. Ken On Mar 29, 2007, at 11:29 AM, John Tromp wrote: .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xx.x.xx. xx.xxx.xx .xxx.xxx. Nice! If you use O's instead like .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OOO.OOO. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote: On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote: It appears to me that at least 91 is possible: Nice! If you use O's instead like .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OOO.OOO. it looks pretty artistic, like a vase with a flower inside:-) :) It appears that you can get 92 as well, by replacing the two empty intersections along the upper edge of my diagram with a single one in the center of that edge, and placing an empty intersection on one of the other intersections along the central line of symmetry. If it weren't for the fact that that central line is needed to keep everything connected:-) -john ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote: On 3/29/07, John Tromp [EMAIL PROTECTED] wrote: On 3/29/07, Weston Markham [EMAIL PROTECTED] wrote: It appears to me that at least 91 is possible: Nice! If you use O's instead like .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OO.O.OO. OO.OOO.OO .OOO.OOO. it looks pretty artistic, like a vase with a flower inside:-) :) It appears that you can get 92 as well, by replacing the two empty intersections along the upper edge of my diagram with a single one in the center of that edge, and placing an empty intersection on one of the other intersections along the central line of symmetry. If it weren't for the fact that that central line is needed to keep everything connected:-) Yes, I realized that later (as soon as I tried to draw it) but didn't bother to post anything, since Gunnar had already posted that 91 is the best possible. But thanks for pointing it out. :) Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
It's really a way to incrementally update liberties in a fast way - each stone keeps it's own count of liberties and it is summed - but of course it doesn't represent the true number of liberties since a point can get counted 2 or more times.However, if the count goes to zero, the count is correct. A count of 1 is also correct presumably, perhaps usefully. Arthur ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
On 3/29/07, Christoph Birk [EMAIL PROTECTED] wrote: On Thu, 29 Mar 2007, Jim O'Flaherty, Jr. wrote: What's a pseudo-liberty? And how can there be more of them than there are empty intersections (81) on the board? It is the sum of all stone's liberties in a group; ignoring common liberties. In other words, the number of stone-empty adjacencies. -john ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
Arthur W Cater wrote: It's really a way to incrementally update liberties in a fast way - each stone keeps it's own count of liberties and it is summed - but of course it doesn't represent the true number of liberties since a point can get counted 2 or more times.However, if the count goes to zero, the count is correct. A count of 1 is also correct presumably, perhaps usefully. Arthur Once upon a time, I did analysis of the inaccuracy of pseudo liberties. Searching quickly, I found: http://computer-go.org/pipermail/computer-go/2005-October/003839.html For any interested, I did come up with a variant of pseudo liberties that was a lot closer to real liberties. My post about local liberties is here: http://computer-go.org/pipermail/computer-go/2005-October/003852.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
Once upon a time, I did analysis of the inaccuracy of pseudo liberties. Searching quickly, I found: http://computer-go.org/pipermail/computer-go/2005-October/003839.html For any interested, I did come up with a variant of pseudo liberties that was a lot closer to real liberties. My post about local liberties is here: http://computer-go.org/pipermail/computer-go/2005-October/003852.html As far as I know, pseudo-liberties are only used for detecting a capture or detecting atari. If this method you suggest has some value beyond that, then I'm interested to learn more about it. But the message that you linked seems to leave out a lot of details. You give conclusions, but I am left wondering how to do my own open triangle tracking. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
As far as I know, pseudo-liberties are only used for detecting a
capture or detecting atari. If this method you suggest has some value
beyond that, then I'm interested to learn more about it. But the
I have a nice mathematical puzzle for you.
Fix some k, say, 81.
What is the smallest range N for which you can pick k N-bit
numbers, n_1,n_2,...n_k with the following properties:
{2*n_i, 3*n_i, 4*n_i} is disjoint from
{n_a + n_b,
n_a + n_b + n_c, n_a + 2n_b,
n_a + n_b + n_c + n_d, n_a + n_b + 2n_c, n_a + 3n_b, 2n_a + 2n_b}
(where a,b,c,d are different)
regards,
-John
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
Chris Fant wrote: Once upon a time, I did analysis of the inaccuracy of pseudo liberties. Searching quickly, I found: http://computer-go.org/pipermail/computer-go/2005-October/003839.html For any interested, I did come up with a variant of pseudo liberties that was a lot closer to real liberties. My post about local liberties is here: http://computer-go.org/pipermail/computer-go/2005-October/003852.html As far as I know, pseudo-liberties are only used for detecting a capture or detecting atari. If this method you suggest has some value beyond that, then I'm interested to learn more about it. But the message that you linked seems to leave out a lot of details. You give conclusions, but I am left wondering how to do my own open triangle tracking. Local liberties can be used for more purposes... It gives bounds on the number of liberties a chain has. The bounds are quite tight for smaller chains, and for larger chains, the liberty counts are usually high enough that an exact count isn't needed. Open triangle tracking is fairly straightforward. You can detect all newly created and destroyed open triangles by examining the 8 stones surrounding the newly placed stone. I've implemented the local liberties algorithm in HouseBot. While not the fault of the liberty tracking method, the latest HouseBot version doesn't really use it. (It stopped getting used properly in 0.4 when code was added that loops over all liberties of every chain after every move). If you're still interested in an implementation, I can look up the best source revision to look at... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: pseudoliberties
As far as I know, pseudo-liberties are only used for detecting a capture or detecting atari. If this method you suggest has some value beyond that, then I'm interested to learn more about it. But the message that you linked seems to leave out a lot of details. You give conclusions, but I am left wondering how to do my own open triangle tracking. Local liberties can be used for more purposes... It gives bounds on the number of liberties a chain has. The bounds are quite tight for smaller chains, and for larger chains, the liberty counts are usually high enough that an exact count isn't needed. Open triangle tracking is fairly straightforward. You can detect all newly created and destroyed open triangles by examining the 8 stones surrounding the newly placed stone. I've implemented the local liberties algorithm in HouseBot. While not the fault of the liberty tracking method, the latest HouseBot version doesn't really use it. (It stopped getting used properly in 0.4 when code was added that loops over all liberties of every chain after every move). If you're still interested in an implementation, I can look up the best source revision to look at... I know they CAN be used for other purposes. I'm just not aware that they ARE being used for other purposes. I am not using them for other purposes. You just confirmed that you are not using them (or local liberties) for other purposes. Perhaps someone else is. I just don't remember hearing about it. Anyone? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
