Fast data structures explained! (was Re: [computer-go] Go datastructures)
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/ Enjoy! Peter Drake http://www.lclark.edu/~drake/ On Jul 19, 2007, at 8:16 PM, Joshua Shriver wrote: Greetings, What kind of data structures do you all use for your engines, in respect to board representation and move generation. I know in chess bitboard, mailbox board[8][8], 0x88 exist all with their pro's and cons. Are there similar concepts for Go? -Josh ___ 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] didn't Samuels solve that game thirty years ago?
terry mcintyre wrote: An interesting recap of how the hype can sometimes far outpace the reality: http://www.cs.ualberta.ca/~chinook/project/legacy.html I liked this quote from Robert Nealey, which I think is applicable to go as well; By sticking to its programmed instructions, it may find an extraordinary move that a man who is gifted imaginatively may never find. It knows so much and carries its analysis to such depths that it sometimes, by the beauty of its mathematics, comes up with a truly brilliant move. This is difficult to express, but I think the machine’s complete lack of imagination is its most formidable strength! ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go datastructures
Quoting Joshua Shriver [EMAIL PROTECTED]: What kind of data structures do you all use for your engines, in respect to board representation and move generation. I know in chess bitboard, mailbox board[8][8], 0x88 exist all with their pro's and cons. Are there similar concepts for Go? I always used a 1-dimensional 25x25 = 625 integer array with 0 for black 1 for white 2 for empty and 3 for border (everything else). This way I can have a 21x21 board with 2 rows of border cells surrounding it. Looking at cells near a position p is done with p+1, p-1, p+25, p-25. For each block of stones I keep a list of the stones, liberties, and stones of the opponent colors. Valkyria also keeps track of what surrounds each empty point of the board. This slows down the representation but it makes writing higher level go knowledge code much easier. -Magnus -Magnus ___ 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)
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: [computer-go] Go datastructures
On Jul 19, 2007, at 8:16 PM, Joshua Shriver wrote: Greetings, What kind of data structures do you all use for your engines, in respect to board representation and move generation. I know in chess bitboard, mailbox board[8][8], 0x88 exist all with their pro's and cons. Are there similar concepts for Go? -Josh There is a set of pages on Sensei's Library concerning this, including essays by David Fotland and Bruce Wilcox. http://senseis.xmp.net/?ComputerGoProgramming My beginner UCT program (http://www.quirkster.com/forth/fgp.html) uses bitboards because it is very simple to express the rules of Go using bit operations. However, a mailbox board which contains references into string objects which incrementally merge, split, and track their properties (stones, liberties, neighboring enemy strings) is likely to be faster in the long run and on larger boards, though far more complicated to implement correctly. Ian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go datastructures
On 7/20/07, Ian Osgood [EMAIL PROTECTED] wrote: My beginner UCT program (http://www.quirkster.com/forth/fgp.html) uses bitboards because it is very simple to express the rules of Go using bit operations. However, a mailbox board which contains references into string objects which incrementally merge, split, and track their properties (stones, liberties, neighboring enemy strings) is likely to be faster in the long run and on larger boards, though far more complicated to implement correctly. I've thought about bit boards, but my big stumbling block is how to efficiently handle captures. I can't think of any way to detect zero-liberty chains without explicitly specifying a chain to check. Given a specific position (say the neighbor of a point played), I don't know how to look up the chains surrounding it efficiently. Have you been able to solve any of these problems? I did look at the code, but the language is sufficiently foreign to me that it's not easy to zero in on one function and know what it's doing. What language is it written in? ___ 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/
[computer-go] Neural Networks
Anyone recommend a good book on programming Neural Networks in C or C++? Been digging around the net for while and haven't come up with anything other than an encyclopedia-like definition/writeup. No examples or tutorials. Thanks! -Josh ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Neural Networks
FANN (http://leenissen.dk/fann/) is a great neural network library written in C. I don't know much about books on *programming* neural networks specifically, but I know of many great books on neural networks. I am a big fan of Bishop's Neural Networks for Pattern Recognition even if you aren't necessarily going to use them just for pattern recognition. - George On 7/20/07, Joshua Shriver [EMAIL PROTECTED] wrote: Anyone recommend a good book on programming Neural Networks in C or C++? Been digging around the net for while and haven't come up with anything other than an encyclopedia-like definition/writeup. No examples or tutorials. Thanks! -Josh ___ 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 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: [computer-go] Go datastructures
On Jul 20, 2007, at 10:58 AM, Jason House wrote: On 7/20/07, Ian Osgood [EMAIL PROTECTED] wrote: My beginner UCT program (http://www.quirkster.com/forth/fgp.html) uses bitboards because it is very simple to express the rules of Go using bit operations. However, a mailbox board which contains references into string objects which incrementally merge, split, and track their properties (stones, liberties, neighboring enemy strings) is likely to be faster in the long run and on larger boards, though far more complicated to implement correctly. I've thought about bit boards, but my big stumbling block is how to efficiently handle captures. I can't think of any way to detect zero-liberty chains without explicitly specifying a chain to check. Given a specific position (say the neighbor of a point played), I don't know how to look up the chains surrounding it efficiently. Have you been able to solve any of these problems? I make no claims about efficiency. When making a move (: makemove) I check each neighbor (: check-captures) for being captured (: ? capture). I build the chain bitmap for a neightbor stone (: string) when needed by repeated dilation (BEGIN expand) AND the bitmap of our own stones (bover-and) until it stops growing (bd-top bd-count TUCK = UNTIL). The liberty bitmap (: liberties) is then one more dilation (expand) AND the empty bitmap (empty bd-top bd-and). If that bitmap is empty (bdup liberties b0=) then we capture the string (bd-top capture), which is just removing it from the enemy bitmap (enemy bd- xor) and adding it to the empty bitmap (empty bd-or). That's a lot of work, especially toward the endgame when the groups get large, hence my comment that a higher-level incremental representation is a better way to go in the long run. I did look at the code, but the language is sufficiently foreign to me that it's not easy to zero in on one function and know what it's doing. What language is it written in? Forth, my favorite tinkering language. Like Haskell, Lisp, and Prolog it can expand your mind in unaccustomed directions. Ian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Meeting at US Go Congress
On 7/16/07, Jason House [EMAIL PROTECTED] wrote: The US Go Congress begins in less than two weeks. I have two questions: 1. If you plan to attend, which days will you be there? 2. Will you be competing? (Not with a bot) 3. Which days are most convenient for a gathering of developers? Since this event is so soon and the only definitive response I got was any day, I'm just picking what's convenient for me. I'd rather not post my cell phone number on a public, archived, mailing list. I'll give it out to anyone who wants it, but through a private e-mail. I will meet with whoever is available at the US Go Congress on July 29th at 5pm. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Meeting at US Go Congress
I realize 5pm is probably a really bad time. I picked it out of the air thinking that it'd be most convenient for those that are participating in the event. I'm now thinking that those (like me) that drive there and drive home after a short stay may want to get on the road earlier than that. I forget how far it is, but I'm 2-3 hours away. I will drive up that day and drive home that night. A meeting start time in the 12-5 window is doable for me. On 7/20/07, Jason House [EMAIL PROTECTED] wrote: On 7/16/07, Jason House [EMAIL PROTECTED] wrote: The US Go Congress begins in less than two weeks. I have two questions: 1. If you plan to attend, which days will you be there? 2. Will you be competing? (Not with a bot) 3. Which days are most convenient for a gathering of developers? Since this event is so soon and the only definitive response I got was any day, I'm just picking what's convenient for me. I'd rather not post my cell phone number on a public, archived, mailing list. I'll give it out to anyone who wants it, but through a private e-mail. I will meet with whoever is available at the US Go Congress on July 29th at 5pm. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Neural Networks
On 7/20/07, Joshua Shriver [EMAIL PROTECTED] wrote: Anyone recommend a good book on programming Neural Networks in C or C++? Been digging around the net for while and haven't come up with anything other than an encyclopedia-like definition/writeup. No examples or tutorials. There are some C programs at http://www.neural-networks-at-your-fingertips.com/ that you may find useful. [Reading this code to see what it does helped me to learn!] Software that can be downloaded from http://www.dontveter.com/nnsoft/nnsoft.html is similarly useful, as is Don Tveter's book The Pattern Recognition Basis of Artificial Intelligence, to which that software is a companion. [What I like about Tveter's book, and software, is that it seems to be written more from an engineering perspective than a theoretical one. As you have found, there is no shortage of theory, on the web, but somewhat of a dearth of practical information.] There is also a repository of free AI software (including some for neural networks) at http://www.cs.cmu.edu/Groups/AI/html/rep_info/intro.html . Also, of course, you might wish to browse the archives of the Usenet newsgroup, available at http://groups.google.com/group/comp.ai.neural-nets or from your friendly neighborhood NNTP server. The FAQ list, in particular, for that group contains a lot of good links. Hope this helps. -- Rich ___ 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: [computer-go] Neural Networks
George Dahl said: FANN (http://leenissen.dk/fann/) is a great neural network library written in C. I don't know much about books on *programming* neural networks specifically, but I know of many great books on neural networks. I am a big fan of Bishop's Neural Networks for Pattern Recognition even if you aren't necessarily going to use them just for pattern recognition. I also see a certain amount of promise in neural networks done wrong. Current notion [I'm really trying to program this, arrrgh!] A breeding population of cells, fibers, rules. Each cell has one or more fibers one or more rules. Each rule has a threshold and a masked pattern; if the cell's charge is over the threshold and its pattern matches the rule's pattern, the cell fires its pattern goes out via all fibers. [That is: The pattern a list of the cell's fibers are added to the end of a list of fibers to be processed.] Each fiber has a bit-logical operation as well as a destination cell. When a fiber is processed, its pattern and operation are applied to the destination cell's pattern. Then the fiber adds its 'signal strength' to the cell's charge; and this is checked against the thresholds of the cell's various rules, and so on... The initial patterns are, of course, bitmaps of the board. When a nonzero signal finally arrives at cell #5, one of the 1-bits is randomly selected as the move. (If that turns out illegal, the actual move is pass.) Since these cells are randomly connected (depending on the player's 'genes' plus any modifications in the course of the game)... that fibers to process list could easily blow up; what I think I'll do to damp out the overload is to add the square of (How many times has this cell fired?) to the thresholds. If I get this running, there will be a whole mess of information being processed about each position... some of it maybe even relevant. Anyway, putting together a stew of good borrowed ideas... in what I hope will be a functional way... it might be fun to watch. Forrest Curo San Diego - 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 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: [computer-go] Neural Networks
The initial patterns are, of course, bitmaps of the board. When a nonzero signal finally arrives at cell #5, one of the 1-bits is randomly selected as the move. (If that turns out illegal, the actual move is pass.) Without understanding everything about what you're doing (not even close), I'm wondering why you wouldn't pick different 1-bit when the first one you tried was illegal. And of course pass when they are all illegal. Probably you would also have some other mechanism for generating passes even in the case that they are not all illegal. ___ 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: [computer-go] Go datastructures
At 08:38 PM 7/19/2007, you wrote:
In the engine I've been working on for a week or two (I'm brand new to
computer-go)
I use:
typedef int INTERSECTION;
typedef enum { BLACK, WHITE, EMPTY } COLOR;
i used: typedef enum { BLACK, WHITE, EMPTY,OFFBOARD } COLOR; once. it
eliminated tests for array bounds inside a loop. and might be useful
in isolating groups somehow (maybe a live group of opposite color is
like off the board).
thanks
---
vice-chair http://ocjug.org/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go datastructures
I always used a 1-dimensional 25x25 = 625 integer array with 0 for black 1 for white 2 for empty and 3 for border (everything else). This way I can have a 21x21 board with 2 rows of border cells surrounding it. David Fotland, on the other hand, seems to use a 19x19 grid, and detect off-board separately. (?) This is the way I've also always done it. I get round the speed issues of off-board detection because I have a global singleton called APD (Adjacent Point Data). Its constructor caches lots of results. E.g. it has functions to turn a 0..N coord into x and y coords, functions to rotate points, functions to return the coord a certain distance away (e.g. ikken to the North, keima to the South-East). That latter function returns a special value when off-board. APD also has functions for looping (e.g. through all the adjacents, or all the diagonals, or even all the ogeima; automatically skipping over off-board), for measuring distance to nearest edge or nearest corner, and for point type (corner, edge, centre). But, still, I wonder if the N+1 x N+1 design is quicker. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go datastructures
it has functions to turn a 0..N coord into x and y coords, functions to rotate points, functions to return the coord a certain distance away (e.g. ikken to the North, keima to the South-East). Okay, I've got functions that detect a certain relation between stones--and can be linked together to specify relations between these relations, etc but When I rotate/flip the board, those relations are now in a different orientation and the same functions won't necessarily recognize them. So this would have to be done from the beginning... Whenever a new relation is generated to join two existing subpatterns, the 8 forms of each of those would need to already be included in the existing set of patterns. Would this add as much hassle to the program as I expect, or does it turn out somehow simpler? 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 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/
Re: [computer-go] Go datastructures
When we deal with patterns and their rotations/reflections, we have a canonical version that contains everything we care about, and all of the R/R patterns have pointers to the canonical. If these are being generated by some automated algorithm, we generate all of the R/R as soon as we see the new pattern. We do not consider this too difficult. Cheers, David On 20, Jul 2007, at 6:16 PM, [EMAIL PROTECTED] wrote: but When I rotate/flip the board, those relations are now in a different orientation and the same functions won't necessarily recognize them. So this would have to be done from the beginning... Whenever a new relation is generated to join two existing subpatterns, the 8 forms of each of those would need to already be included in the existing set of patterns. Would this add as much hassle to the program as I expect, or does it turn out somehow simpler? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go datastructures
I don't use functions to convert 0-n to x, y. I use arrays of constants instead. It's faster. APD.get_x(d), for instance, is doing a lookup in an array that is made by the constructor once when the program starts up. Everything is inline so it is the same. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CGOS hardware
Apparently there are more hardware issues with CGOS. The machine is down right now. So it will be a few hours before I can bring the software back up. Sorry about the problems. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Gifu Challenge was cancelled
Unfortunately, this year's Gifu Challenge was cancelled for financial difficulty. Gifu Challenge was a computer Go tournament that had been held four times since 2003. It was held in autumn season. Gifu is a prefecture name in Japan. last year's result. (there is no information about cancel) http://computer-go.softopia.or.jp/gifu2006/English/08.html CGF(Computer Go Forum) is considering alternative. Regards, Hiroshi Yamashita ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
