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] 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/
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/
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: [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] Go datastructures
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/
Re: [computer-go] Go datastructures
2007/7/20, 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? Below assuming 9x9 Go. There are 2D board (i.e. board[9][9]) and 1D board (board[81]). I heard of people using guard (board[11][11]). The more important issue is representation of connected string. You need that to implement the rule. One well known representation is so-called next stone array. Scratch array to count liberties can be used. If one only wants to check the capture, so-called liberty edge which is zero if liberty is zero can be counted faster. Many different ways to implement incremental board update. Also ways to handle undo. The most usual way to handle ko seems to be to save a single point the last ko was captured. GNU Go has a comprehensive documentation of its board data structures: http://www.gnu.org/software/gnugo/gnugo_15.html -- Seo Sanghyeon ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go datastructures
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;
struct GROUP
{
INTERSECTION base;
COLOR color;
int count;
int liberties;
INTERSECTION children[5];
INTERSECTION parent;
};
struct BOARD
{
COLOR side_tm;
COLOR board[BOARD_SIZE * BOARD_SIZE];
struct GROUP group_list[BOARD_SIZE * BOARD_SIZE];
struct GROUP *group[BOARD_SIZE * BOARD_SIZE];
int group_count;
int real_group_count;
INTERSECTION empty_list[BOARD_SIZE * BOARD_SIZE];
int empty_index[BOARD_SIZE * BOARD_SIZE];
int empty_count;
};
I've just finished implementing the basic rules. I'm now working on
detecting the end of the game and scoring. I think this is a pretty
standard data structure. I do know that bitboards can be used, with
one integer usually representing a row.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
