2009/8/14 David Fotland <[email protected]> > Many Faces old code does something like this. The board is an array of > group numbers. I used many single dimension arrays rather than an array of > structs, because it’s faster. >
I would have guessed that having separate arrays would impact cache in a negative way, because it's nice to do one read and have everything together in the same cache line. But there are probably many factors that could make this not such a big deal. For instance it's probably the case that there are many times you only care about 1 element in those structures, which actually would favor putting them in separate arrays. - Don > > The new UCT code does something a little simpler and faster since there is > no need to take back moves. > > > > David > > > > *From:* [email protected] [mailto: > [email protected]] *On Behalf Of *Don Dailey > *Sent:* Friday, August 14, 2009 6:17 PM > *To:* computer-go > > *Subject:* Re: [computer-go] representing liberties > > > > I'm not sure I understand your question. But I'll try to explain it a > little better. > > Basically, you keep a C structure or the equivalent which tracks each > individual chain. On your board array you put the index of that structure > (or a pointer to it.) > > The structure will look something like this: > > typedef struct > { > int color; > int stone_count; > int head_stone; > int liberty_count; > > } chain_t; > > And perhaps other crap you may want to keep. > > So lets say you have an array of these, one for each chain on the board > with room to grow. > > When you place a stone on the board, you look at the 4 neighbors to see if > this is going to be a new chain of 1, or connect to an existing chain. If > it's an existing chain, you will need to create a brand new entry, set the > stone_count to 1, the liberty count to 1, 2, 3 or 4 (by looking at the 4 > surrounding points) and set the head_stone to the location of the new > stone. the head_stone can be ANY stone in the group - it's just a way to > quickly reference one of the stones in the group. > > Your board of course will have the index of the chain_t. I start at 1 > and make zero mean empty but you could use -1 to represent empty squares if > you want to. So if the value of the board array is 5, it means it is the > 5th chain in the chain_t array and you can immediately see how many stones > are there, how many liberties etc. > > The logic for updating the liberty count is pretty basic. When you place a > stone next to an existing group, you know that group loses 1 liberty, so > you subtract 1 from ANY group of either color that touches it (there can > only be 4 at most.) But then you must check to see if the stone you just > placed created liberties for the group it belongs to. So you count the > empty points around the new stone that do not already belong to that same > group. (There is also the case where 2 chains must be merged, but we > will ignore that for now.) > > When a group is captured, you must do a bit more housekeeping. You need > to delete it's entry somewhow in the chain array and you will have to > recalculate the liberties for any enemy chain that is currently touching any > of the captured stones. This is not as hard as it seems once you work it > out. > > One way to delete the entry is to just set the stone_count to zero for > instance. You may want to "compress" the chain list from time to time but > if you make the list big enough, you will be able to complete one or more > playouts without needing to do this. You could also keep a "free list" so > that you immediately re-use entries - that's probably what I would recommend > because it's real simple and the free list will never grow very large. > > How do you unmake moves? I suggest that you don't. Instead, making a > move should either be by state copy, or if you know you will never need to > unmake a move (such as when doing fast playouts) you don't have to worry > about it. But of course you will still want to keep some original copy to > track the state of the actual game. > > So your should wrap your whole game state up into a neat little package and > operate only on those. You will be thankful if you ever decide to go with > parallel processing for instance. > > So to make a move you might have something like this in C, this is > non-object oriented version: > > int make( const position *original_state, position *new_state, > move_type mv ) > { > *new_state = *original_state; > > status = low_level_make( new_state, mv ); > return status; > } > > The "position" object is a C structure that has the entire board, chain > lists and move history. The move history can be implemented as a pointer > to previous move states. > > So in any kind of recursive search situation, you are simply passing > position states down the tree, never having to unmake a move. In the > playouts you don't even have to copy state. > > With this data structure you can also easily iterate through the chains > without having to loop over every point on the board. In fact you can > always know exactly how many chains are on the board of either color and do > something wth them if needed. Or you can quickly count the number of > stones on the board (of course if you wanted to you could keep this in a > separate counter in the position state.) > > When you make captures you will need to hit every stone. I use a recursive > flood fill type of routine to do this. I know that some programs keep > linked lists of stones - I'm not sure if that is worth the trouble and extra > space. Mabye it is. I think I figured out that you rarely have to go > through every stone, mainly in captures. > > > Ok, now my disclaimer. There are some very experienced go programmer here > and they may find this naive or silly. My reference bots do not use this, > they just do the dumb thing - a single flat array the represents the board > and the stones on it. > > > - Don > > > > > > > > > > > > > > > On Fri, Aug 14, 2009 at 6:10 PM, Carter Cheng <[email protected]> > wrote: > > So to determine where the last two liberties for a group of stones for > example is the obvious method of just doing it to have some method of > liberty counting + a exhaustive search to determine the last two liberties > for example? > > --- On Fri, 8/14/09, Don Dailey <[email protected]> wrote: > > > From: Don Dailey <[email protected]> > > Subject: Re: [computer-go] representing liberties > > To: "computer-go" <[email protected]> > > Date: Friday, August 14, 2009, 2:33 PM > > > > > > > On Fri, Aug 14, 2009 at 5:13 PM, > > Carter Cheng <[email protected]> > > wrote: > > > > I have been having difficulties selecting a good > > representation for liberty sets for strings of stones. I am > > curious how other people might be doing this. I suspect that > > for heavier playouts one would like to know not only the > > count of the liberties but also where precisely they might > > be relatively quickly(to determine if the group is in atari > > among other things). > > > > Simple is best, until you know EXACTLY what you will want > > to do and how often you will need to do it. > > > > Something pretty simple that I have used in the past is to > > track each chain and incrementally maintain the liberty > > count. > > > > > > When you plop a stone down, you have to look at only 4 > > points to see which group if any it belongs to, or if it > > connects 2 or more groups. And you can update the > > liberty counts of all affected groups very quickly. > > > > > > Where there is a capture, you must do considerably more > > work - but captures represent only a small fraction of the > > moves. Small captures are more common than large > > captures, but they require little work. > > > > > > - Don > > > > > > > > > > > > > > > > > > > > > > > > > > _______________________________________________ > > > > computer-go mailing list > > > > [email protected] > > > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > > > > > > > -----Inline Attachment Follows----- > > > > > _______________________________________________ > > computer-go mailing list > > [email protected] > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
