Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
Thanks for the documentation. I have a few questions. Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? I'll have to think more about the multi-stone suicide thing. There's definitely a few situations where that can change the life or death status of a group. How much of a speed difference do you get from the suicide thing? The documentation implies that you're not using a disjoint set for chain id tracking. I thought this was one of the large speed gains in libego. On 7/20/07, Peter Drake [EMAIL PROTECTED] wrote: What a timely thread! I've reimplemented Łukasz Lew's libego in Java for the latest edition of Orego. It includes something of an explanation of the data structures. I believe the code itself is relatively clear. The goodies are here: http://www.lclark.edu/~drake/go/ http://www.lclark.edu/%7Edrake/go/ Enjoy! Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On Jul 20, 2007, at 7:23 AM, Jason House wrote: Thanks for the documentation. I have a few questions. Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? It does also look at the diagonals; see Board.isEyelike(). I'll note this in the next version of the document. I'll have to think more about the multi-stone suicide thing. There's definitely a few situations where that can change the life or death status of a group. How much of a speed difference do you get from the suicide thing? I haven't run those experiments myself, trusting to Lew's optimizations. Perhaps he can weigh in on this. The documentation implies that you're not using a disjoint set for chain id tracking. I thought this was one of the large speed gains in libego. I'm using the same data structure as Lew. Each stone knows its chain ID number, which can be used to look up it pseudoliberty count. I'll hazard a guess that this is faster than traveling up a disjoint set tree, even with path compression. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On 7/20/07, Peter Drake [EMAIL PROTECTED] wrote: On Jul 20, 2007, at 7:23 AM, Jason House wrote: Thanks for the documentation. I have a few questions. Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? It does also look at the diagonals; see Board.isEyelike(). I'll note this in the next version of the document. I lost a game in the most recent tournament from a buggy alternative to isEyelike. I believe that it may be a bug that affects many, but I'm not really sure... That makes me especially interested in seeing how others do it and the trades they accepted for it. The documentation implies that you're not using a disjoint set for chain id tracking. I thought this was one of the large speed gains in libego. I'm using the same data structure as Lew. Each stone knows its chain ID number, which can be used to look up it pseudoliberty count. I'll hazard a guess that this is faster than traveling up a disjoint set tree, even with path compression. I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything. Merging chains together with a chain ID approach can be O(#stones) and then O(1) for everything else. Disjoint sets don't walk the tree for every lookup... the tree is flattened with each lookup. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On Jul 20, 2007, at 8:04 AM, Jason House wrote: I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything. Yes -- O(log* n) to be precise, as mentioned in my book, shameless plugData Structures and Algorithms in Java/shameless plug. Merging chains together with a chain ID approach can be O(#stones) and then O(1) for everything else. Well, it's O(#stones in smaller chain), with the smaller chain heuristically determined as the one with fewer pseudoliberties. Disjoint sets don't walk the tree for every lookup... the tree is flattened with each lookup. You still have to perform the tree-walking operation; it's just that with path compression there's *usually* only one step from a stone to the root. With the root explicitly stored, there's also no branching (if statements), which Lew asserts is very important for speed on modern processors. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On 7/20/07, Peter Drake [EMAIL PROTECTED] wrote: On Jul 20, 2007, at 8:04 AM, Jason House wrote: I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything. Yes -- O(log* n) to be precise, as mentioned in my book, shameless plugData Structures and Algorithms in Java/shameless plug. It's been a while since I was involved with theoretical analysis of disjoint sets, but I'm fairly certain that it's faster than O(log(n)) for some implementations. Do you mean something special by log*? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
Yes: log* is to log what log is to division. In other words, it's the number of times you have to take a logarithm before you get down to 1. It's an extremely slowly-growing function. It's conceivable that actual, empirical time is a better metric than asymptotic time here, because we're not really interested in what happens as the board becomes arbitrarily large. Peter Drake http://www.lclark.edu/~drake/ On Jul 20, 2007, at 8:24 AM, Jason House wrote: On 7/20/07, Peter Drake [EMAIL PROTECTED] wrote: On Jul 20, 2007, at 8:04 AM, Jason House wrote: I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything. Yes -- O(log* n) to be precise, as mentioned in my book, shameless plugData Structures and Algorithms in Java/shameless plug. It's been a while since I was involved with theoretical analysis of disjoint sets, but I'm fairly certain that it's faster than O(log (n)) for some implementations. Do you mean something special by log*? ___ 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: Fast data structures explained! (was Re: [computer-go] Go datastructures)
Peter Drake wrote: On Jul 20, 2007, at 8:04 AM, Jason House wrote: I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything. Yes -- O(log* n) to be precise, ... At the risk of being accused of serious nit-picking here, I believe Tarjan proved that the bound is actually a bit better than that, namely the inverse of the Ackermann function. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
It looks like you're right -- but I did say O (rather than THETA), so I'm also technically correct. :-) Peter Drake http://www.lclark.edu/~drake/ On Jul 20, 2007, at 9:15 AM, Richard J. Lorentz wrote: Peter Drake wrote: On Jul 20, 2007, at 8:04 AM, Jason House wrote: I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything. Yes -- O(log* n) to be precise, ... At the risk of being accused of serious nit-picking here, I believe Tarjan proved that the bound is actually a bit better than that, namely the inverse of the Ackermann function. ___ 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: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On Jul 20, 2007, at 8:04 AM, Jason House wrote: On 7/20/07, Peter Drake [EMAIL PROTECTED] wrote: On Jul 20, 2007, at 7:23 AM, Jason House wrote: Thanks for the documentation. I have a few questions. Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? It does also look at the diagonals; see Board.isEyelike(). I'll note this in the next version of the document. I lost a game in the most recent tournament from a buggy alternative to isEyelike. I believe that it may be a bug that affects many, but I'm not really sure... That makes me especially interested in seeing how others do it and the trades they accepted for it. My program disallows playing in eyes (string of empty surrounded by self) unless a neighboring stone is in atari. That catches your special-case, but is not good for saving tails (strings connected by false eyes, often found along the edge of the board). Ian___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
Jason House said: Thanks for the documentation. I have a few questions. Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? Eye detection is a tricky problem. But for immediate captures, bitmaps are fast and easy. 1) Start with bitmap of original stone; shift it up, down (assignment statements) left right , then AND each result with a bitmap of all vacant points, and if any result is nonzero, the chain is safe. 2) If not, AND each new bitmap with a bitmap of all same-color stones, then OR the results with the old . This gives a bitmap of all friendly stones adjacent to the original. 3) Replace the old bitmap with the new, and repeat the process until either a breathing space is detected or the new bitmap comes out identical with the previous one (hence there are no breathing spaces.) Forrest Curo - This email was sent using AIS WebMail. http://www.americanis.net/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On 7/20/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Jason House said: Thanks for the documentation. I have a few questions. Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? Eye detection is a tricky problem. But for immediate captures, bitmaps are fast and easy. 1) Start with bitmap of original stone; shift it up, down (assignment statements) left right , then AND each result with a bitmap of all vacant points, and if any result is nonzero, the chain is safe. 2) If not, AND each new bitmap with a bitmap of all same-color stones, then OR the results with the old . This gives a bitmap of all friendly stones adjacent to the original. 3) Replace the old bitmap with the new, and repeat the process until either a breathing space is detected or the new bitmap comes out identical with the previous one (hence there are no breathing spaces.) That's essentially the best that I came up with. Since bit board operations on 19x19 are slow, I've essentially concluded that if I have to loop like that, I'm better off with other methods. Out of curiosity, does anyone have any performance comparisons? I personally am tempted to try 7x7 go since it can fit into a single 64 bit integer... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
2007/7/20, Ian Osgood [EMAIL PROTECTED]: Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? It does also look at the diagonals; see Board.isEyelike(). I'll note this in the next version of the document. I lost a game in the most recent tournament from a buggy alternative to isEyelike. I believe that it may be a bug that affects many, but I'm not really sure... That makes me especially interested in seeing how others do it and the trades they accepted for it. My program disallows playing in eyes (string of empty surrounded by self) unless a neighboring stone is in atari. That catches your special-case, but is not good for saving tails (strings connected by false eyes, often found along the edge of the board). Do you mean oiotoshi? Andrés ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On Jul 20, 2007, at 2:25 PM, Andrés Domínguez wrote: 2007/7/20, Ian Osgood [EMAIL PROTECTED]: My program disallows playing in eyes (string of empty surrounded by self) unless a neighboring stone is in atari. That catches your special- case, but is not good for saving tails (strings connected by false eyes, often found along the edge of the board). Do you mean oiotoshi? Andrés Yes, thanks for the term. http://senseis.xmp.net/?Oiotoshi Ian___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
From: Ian Osgood [EMAIL PROTECTED] On Jul 20, 2007, at 2:25 PM, Andrés Domínguez wrote: 2007/7/20, Ian Osgood [EMAIL PROTECTED]: My program disallows playing in eyes (string of empty surrounded by self) unless a neighboring stone is in atari. That catches your special- case, but is not good for saving tails (strings connected by false eyes, often found along the edge of the board). Do you mean oiotoshi? Andrés http://senseis.xmp.net/?Oiotoshi Oitoshi appears to be a term for a situation where a group cannot be saved; it is also called connect-and-die; the group in atari will, if it connects, deprive still more stones of a liberty, putting the resultant larger group in atari. Be a better Globetrotter. Get better travel answers from someone who knows. Yahoo! Answers - Check it out. http://answers.yahoo.com/dir/?link=listsid=396545469___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fast data structures explained! (was Re: [computer-go] Go datastructures)
On Jul 20, 2007, at 12:10 PM, Jason House wrote: That's essentially the best that I came up with. Since bit board operations on 19x19 are slow... They are not necessarily slower than on smaller boards if you store only non-zero portions of your bitmaps along with the start and end row indices. The bitboard operations would be dealing with much less data, often just single rows. (Caveat: I haven't actually tried this yet.) Ian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
