[computer-go] professional game libraries for pattern harvesting
I noticed a few papers now mention Bayesian learning techniques for mining for patterns and I am curious where does one find libraries for this sort of thing are there some commercially or free game libraries to which the procedures described can be applied. Regards, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Some beginner's questions concerning go bots
Hi, I have been lurking around in this group for sometime and recently have become interested in perhaps doing some coding and data gathering for constructing a simple go bot. I have a few basic questions I was wondering if people in the group could help me answer- 1) How typically do UCT bots score simulations quickly? I am not too familiar with Chinese scoring rules. 2) How do machines define eyes analytically (mathematically) and are there approximations which are faster to calculate for more traditional or UCT designs (is this information even used for UCT bots?). 3) What sort of algorithm is used to match patterns once you have mined them from some data source? 4) And lastly how does UCT cope with ladders? Thanks in advance, Carter. Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
Thanks everyone for the responses. My go skills are somewhat limited (only 6-7kyu on KGS) so hopefully I am not belaboring the obvious. I have a few followup questions- 1) What mathematically is a seki? I know this is a local draw but can it be determined statically at some point in all cases using some sort definition without placing stones on the board (i.e. searching). I only know of three cases here- the 1 eye each case with one shared liberty. two shared liberties and the half eye situation. 2) I am guessing hash maps get quite large if they are exhaustive. i.e. (nxn)^3 can quickly become quite big. Or do they tend to be sparsely populated? 3) GTP and time management and scoring after two passes. Are these issues discussed anywhere? Do libraries like Orego and Libgo contain code that already does this which can be used as a reference? Thanks again, Carter. Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
Well I was hoping for a static definition which could be assessed with minimal calculation. The problem with a definition relying on a best move metric in my mind is that "best move" is a very difficult thing to define in go since we do not (yet) have an accurate position evaluation function. --- On Sat, 5/10/08, Evan Daniel <[EMAIL PROTECTED]> wrote: > From: Evan Daniel <[EMAIL PROTECTED]> > Subject: Re: [computer-go] Some beginner's questions concerning go bots > To: "computer-go" > Date: Saturday, May 10, 2008, 12:55 PM > On Sat, May 10, 2008 at 12:29 PM, Peter Drake > <[EMAIL PROTECTED]> wrote: > > On May 10, 2008, at 7:01 AM, Carter Cheng wrote: > > > > Thanks everyone for the responses. My go skills are > somewhat limited (only > > 6-7kyu on KGS) so hopefully I am not belaboring the > obvious. > > I have a few followup questions- > > 1) What mathematically is a seki? I know this is a > local draw but can it be > > determined statically at some point in all cases using > some sort definition > > without placing stones on the board (i.e. searching). > I only know of three > > cases here- the 1 eye each case with one shared > liberty. two shared > > liberties and the half eye situation. > > > > How about "a situation where there are neutral > points yet the best move is > > to pass"? > > Best move for both players -- in some positions and some > rulesets, > pass can be a ko threat. > > To include Japanese rulesets, where filling dame is > unimportant, you > might want to require that pass be the unique best move. > > Evan Daniel > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
Thanks for the responses. 1) I guess for this seki question I was wondering if it was as easy to define as liveness without seki. The reason I am interested in this is I am curious about absolutely correct scoring functions and whether they currently cope well with advanced seki situations or not. I have been looking at some of the cases listed on the Sensei's Library. A cursory look seems to indicate that they are very difficult to classify- and any seki classifier might need some knowledge of killing shapes. 2) You are correct Jason I transposed the symbols for some reason I actually meant 3^(n^2) but typed it in backwards. 3) Also thanks for the links. I have taken a look at some of the code. I am not sure I will be writing in Java or D and most likely will be implementing the system in something like C++. I am worried about Java's speed since it's interpreted (which still means a x2 slowdown even with the JIT and Hotspot compilation and selective inlining). D I am just not too familiar with I am wondering what advantages it brings over C++. I am primarily concerned about maturity issues. I am not trying to start a discussion on which language is "better", but those are my initial impressions. I am primarily interested in creating a very basic go bot at this point and use it for primarily data gathering. I have been curious about certain aspects of game searches and how they apply to go and how reinforcement learning works etc. I figure being a complete beginner at this it will take some time before I have any meaningful insights into how everything works to contribute anything. Regards, Carter. Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
I have looked over the language specification for D and it has alot of nice features however the maturity issue is a big one for me and unless there is a huge gain in productivity I suspect I will stick to C++. Admittedly C++ is not probably not the best language to prototype in and it would be nice to have something a bit more elegant/expressive (maybe something like SmallTalk-80/Squeak). I dont consider myself an expert C++ programmer by any means and alot of the aspects of the language I do still find a bit perplexing (I find Java easier but I do not think it's appropriate for a project which is primarily CPU/Memory bound). Even if the compilation system is reasonably mature I sometimes worry about the library support. C/C++ has alot of nice libraries for handling a wide range of potential tasks and for the most part these days they have been bashed around enough to be certain that they work(I was recently burned by this on a project where the libraries should have been labelled some hacking required despite the fact that the compiler was quite mature). Thanks everyone for all the responses hopefully I can put them to go use. Regards, Carter. Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
I am curious about the eye rule situation since I am at that stage of my implementation of the board/playout code. currently I have only implemented the basic rules of the game so that no illegal moves are possible (no superko rule) but undesirable stuff like filling your own eye spaces still are. I am curious how and when are the eye lists being calculated using the scheme described above. Also one related issue is that for certain LD shapes wont you still inadvertently fill your own eye space? Regards, Carter ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] a few more questions
Thanks for all the comments so far. Hopefully you don't mind a few more questions. 1) Do UCT bots check for atari and urgency? my understanding was that first generation Mogo did this to some extent IIRC. I am curious if anyone does this it seems like it might be important but so far I cannot think of a fast detection scheme. 2) When generating random variables for the case where the "values" of placing a stone on different points on the board are different. Are there good ways to throw and determine which point has been selected for the next move by the random player? Thanks again, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
How do L&D modules generally function? Is this discussed in the literature somewhere? The only open source L&D module I am aware of is the one in GNU-go and I am not certain how good or bad it is since my own playing strength isn't that good. I have found some papers on this topic but most do not go into much detail on how they are evaluating L&D and most just discuss performance issues and general algorithmic approaches (like proof-number-search). Regards, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
Thanks for the help with this. I suspect I will go directly for a heavy playout implementation and avoid writing some of the trickier the light playout code so I probably will be implementing this soon. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
I assume this implies that there arent any open-source basic-UCT bots which utilize the basic eye rule and a simple permute and retry scheme as described by many ppl on the group? When we speak of these sorts of bots playing at about 10kyu I assume what is meant is 10kyu at 9x9 not 19x19. --- On Wed, 5/14/08, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > From: [EMAIL PROTECTED] <[EMAIL PROTECTED]> > Subject: Re: [computer-go] 10k UCT bots > To: computer-go@computer-go.org > Date: Wednesday, May 14, 2008, 10:44 AM > > -Original Message- > > From: Jacques Basaldúa <[EMAIL PROTECTED]> > > To: computer-go@computer-go.org > > Sent: Wed, 14 May 2008 6:38 am > > Subject: Re: [computer-go] 10k UCT bots > > > > Don Dailey wrote: > > > > [EMAIL PROTECTED] wrote: > > > >> For those currently coding this up, I think > the most important thing > >>> about this playout algorithm is that it is > >> > *temporary*. You will almost certainly > be replacing it with something different and better > >> > just a little bit down the road. So you > probably don't want to worry > >> > about hair-splitting tweaks except as an > academic exercise. > > > Yes, I agree. Also my hair brained scheme of > pre-generated tables of > > > list traversal orderings was just an academic > exercise as you say. > > > But the problem is that when you do heavy playouts you > have the same > > problem except that the probabilities of the legal > moves are no longer equal. > > The problem doesn't go away but the trade-offs change > considerably. This is an interesting and relevant > discussion, but if I were trying to code up light MC > playouts for the first time, right now, I would be feeling > that this dead-simple algorithm was actually very difficult > and confusing. > > For someone in that position (and only them), my advice is > 1. Implement light playouts first. It's simple; you > will find many bugs that way; it's standardized enough > that other people will understand what you're talking > about; it's a fast way to get a basic bot; it will be a > very handy thing to have as a baseline when you test other > things. > 2. Get it working the standard way before improving it. > It's your baseline that you'll be testing > improvements against. > 3. Make it fast but don't spend excessive effort > optimizing. "Better is the enemy of good > enough." > > - Dave > Hillis___ > 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] Another beginner question: string management
I am having some difficulties deciding on a string management scheme which copes gracefully with merging groups. A first glance for me this seems like it is quite a slow operation akin to capture. The problem is how to have each stone vertex know which chain record to look up for information. I am curious how this is done in the current generation of MC bots. Is the naive way the best i.e. going through each stone and updating the pointer to the record? Regards, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Another beginner question: string management
Thanks for pointing to the existence of this document. It clarifies some things about a conventional light playout UCT design(It also answered a question about pseudo-liberties I guess they are equivalent to what I term |multi set liberty|). From the code I gather Orego (thus libEgo) does update all the pointers to the chain record. There are still a few design tradeoffs I dont quite understand such as caching adjacent vertex properties in the vertex. How much and why does this result in a speedup? Regards, Carter. --- On Fri, 5/16/08, Peter Drake <[EMAIL PROTECTED]> wrote: > From: Peter Drake <[EMAIL PROTECTED]> > Subject: Re: [computer-go] Another beginner question: string management > To: "computer-go" > Date: Friday, May 16, 2008, 4:39 PM > Carter: > > It might help to look at the Orego code. In the doc > directory, > there's a file called > Board-data-structures-explained.pdf. > > Orego's current board-handling data structures are > basically a Java > "translation" of Lukasz Lew's Library of > Effective Go Routines (EGO), > although I've gone to somewhat greater length to > explain them. If you > find C++ easier to read than Java, by all means use > Lew's code. > > Orego is here (you'll have to download and unpack the > latest .jar): > > http://www.lclark.edu/~drake/Orego.html > > Peter Drake > http://www.lclark.edu/~drake/ > > > > On May 16, 2008, at 4:29 PM, Carter Cheng wrote: > > > I am having some difficulties deciding on a string > management > > scheme which copes gracefully with merging groups. A > first glance > > for me this seems like it is quite a slow operation > akin to > > capture. The problem is how to have each stone vertex > know which > > chain record to look up for information. I am curious > how this is > > done in the current generation of MC bots. > > > > Is the naive way the best i.e. going through each > stone and > > updating the pointer to the record? > > > > Regards, > > > > Carter. > > > > > > > > ___ > > 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] Another beginner question: string management
Thanks for the help with this. I actually managed to figure most of the remaining details out on my own. I guess the chain management scheme in Orego and Libego is a bit more efficient than mine due to the lack of pointer initialization/management costs so I elected to modify my code and use the same scheme. I guess with the neighbour counts the extra cost of maintaining the data is worth it since it is used in so many contexts. There are some differences in my implementational choices so the code is slightly different (and probably suboptimal)- but I am hoping to use the code primarily to collect statistics so it doesnt have to be too fast at the moment. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] learning algorithms such as TD(lambda)- state of the art
Hi, I have been leafing through a book "Reinforcement Learning" by Sutton and Barto. The book seems to serve as a decent introductory text to some of the issues which are mentioned in parts of Sylvain Gelly's thesis. The book however, is a decade old and I curious if there are resources which discuss updates and more recent results in this and related fields where you are exploring a state space through sampling methods. I am not sure if any readers of the mailing list have looked at this- but other than the journal Machine Learning are there other good journals which explore this material in a probablistic/statistical framework? Thank again, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] batch size and impact on strength
I remember seeing this in the archive before but I forget the actual results of the experiment. Does processing simulations in groups of say 5-10 have any impact on the strength of the program? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] batch size and impact on strength
Is UCT really that good at finding the best move in alot of situations? A friend of mine pointed out that in alot of situations it would seem that there would be alot of statistical "noise" in the system. Purely random playouts from a starting position even on 9x9 may not yield alot of information using a pure UCT bot(which may be why people are resorting to opening books to improve performance). Alot of the outcomes of the playouts might be purely random or dependent on mistakes made far down the line from the move under analysis. One thing I saw mentioned in Sylvain's thesis (chapter 4) was that reasonable sequence like behavior seems to greatly improve the strength of the bot so you have to craft the pattern libraries to get this sort of behavior and combine it with a proximity style heuristic. The published materials also suggests he uses a dragon heuristic and of course inherits the atari/capture heuristic from first generation Mogo. Obviously testing is probably the only answer and this points to the heavy use of statistical techniques in both analyzing and training bots(or fitting appropriate parameters). Which leads to a question. What kinds of materials afford the correct mathematical training needed for studying board game programming in particular go? It seems to me that you need a fair amount of statistical training but what kind? I have some background in statistics but it is quite limited so I am uncertain if this would make a good hobby- or if I need to "hit the books" so to speak. Thanks again, Carter. --- On Fri, 5/23/08, Jason House <[EMAIL PROTECTED]> wrote: > From: Jason House <[EMAIL PROTECTED]> > Subject: Re: [computer-go] batch size and impact on strength > To: "computer-go" > Date: Friday, May 23, 2008, 1:47 PM > On May 23, 2008, at 4:22 PM, Magnus Persson > <[EMAIL PROTECTED]> > wrote: > > > Quoting Carter Cheng <[EMAIL PROTECTED]>: > > > >> I remember seeing this in the archive before but I > forget the > >> actual results of the experiment. Does processing > simulations in > >> groups of say 5-10 have any impact on the > strength of the program? > >> > >> Thanks in advance, > >> > >> Carter. > > > > Yes, at some point at least batch processing of > simulations will be > > inefficient. > > Every time you walk through the tree, the algorithm > prefers to go > > the best path possible to gain more information. With > each extra > > simulation in a batch there will be less and less > useful > > information. Maybe there is a tradeoff and you can get > away with > > small batches and gain something else. You have to > test and see what > > happens. > > I expect batching to help when multithreading > ___ > 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] batch size and impact on strength
I think I being was a bit unclear here. By UCT I meant the combination of UCT+Simulation. I am just curious why simulation based methods of evaluation are thus far found to be superior (are they on 19x19?) to traditional bots which have a different form of evaluation function for a given position. It would seem that simulation based methods of arriving at a scoring function for the current position (playing out to the end) might be quite inefficient especially on 19x19 where it seems to me on average the game lasts about 400-450 moves. Heavy playouts from this viewpoint are an attempt to improve the evaluation function over the uniformly random "light" playout. As for UCT itself perhaps I dont still completely understand this algorithm but is a full episode or simulation required for it's use? or are there related family of algorithms which operate on trees like UCT does but grows them asymmetrically given some confidence bounds on the values returned by the heuristical positional evaluation function? Perhaps my understanding of Mogo from the thesis is incorrect. From a certain standpoint it makes very limited usage of heuristics and seems to rely solely several published details (in the thesis): 1) UCT+simulation 2) learned pattern weights via self-play using TD(lambda). 3) Proximity heuristics. (which is something I do not quite understand on a deep level as to why it improves play). 4) RAVE knowledge recycling between trees. 5) The dragon heuristic. The first two can be viewed as online and offline learning. 3) & 5) to me incorporate some domain knowledge and 4) perhaps some but it seems to perhaps work in games which have combinatorial properties and perhaps is more broadly applicable. Obviously there are probably alot of unpublished details. Such as the use of a simple ladder search (as you indicated your program Valkyria does) and perhaps many other enhancements which we do not know about. But from Sylvain's description it seems that the amount of domain knowledge is limited and that the statistical learning procedures dominate is this a misinterpretation/misrepresentation? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] batch size and impact on strength
Thanks for the reply. 2) learned pattern weights are not learnt through > TD(lambda). RLGO is not > used in mogo. It was used a long time ago. Hand-designed > heuristics are > much more efficient (in particular after heavy > cluster-based tuning of > coefficients). I am not entirely sure what you mean here by tuning coefficients do the heuristics in question require some form of parameterization? How are these parameters tuned? > > 3) holds in mogo, and in all efficient Monte-Carlo based > techniques. This > is particularly important, as seemingly knowing the last > point if > important for a correct evaluation of a position in the > case of bounded > computational resources. By the way, this might be true for > humans, also. > I'm afraid it's difficult to find sufficiently many > human players and > situations for organizing an experiment about that :-) > This seems to be the case and I still do not really on some level understand why. Since with the chinese go rules the board should be effectively stateless (exempting ko information) all the information be contained in the the current position. Why additional information is needed i.e. an annotation of the last played move is required on some level is a mystery to me. > 4) The rave heuristic only "migrates" > informations from one node to nodes > "above" that node - never to brothers, cousins, > sons, and so on. Many > attempts have been done here and elsewhere around that > without success. > > By the way, parallelizations (both multi-core and MPI) are > *very* > efficient. The use of huge clusters could probably give > much better > results than the current limit of mogo (between 1k and 1d > on KGS with > 64 quad-cores and myrinet switch). This is obviously quite an impressive feat. However it is also on some level a bit disappointing to me that it will be sometime before we see strong desktop programs since the computational resources required is somewhat prohibitive. > > Another point which was not in the thesis of Sylvain and > which is also > central is the use of patterns in the tree. This is used > since a long time > in CrazyStone and Mango, we are currently developping this > part in MoGo, > and this is quite efficient (but involves tedious tuning of > several > parameters). > I am sure I understand the distinction here between patterns in the tree and patterns used in the heavy playouts. I guess by this you mean they are not the same thing. I am in general basically curious how tuning of parameters occurs i.e. how you fit the parameters in a given situation if things like reinforcement learning are not used (which my understanding is is sort of an automated procedure for fine tuning various parameters in the system). Regards, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Computer Olympiad registration reminder: 11 days left
I am actually relatively nearby (Hong Kong) and would like to attend but I may not have a competitive program at this time. Is it possible to attend without a program and machine? Regards, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [Fwd: Re: [Fwd: Re: [computer-go] Computer Olympiad registration reminder: 11 days left]]
Thanks Remi. Are standard accommodations being provided by the site organizers or will we have to for the most part make our own arrangements? I guess I have a few more days to decide whether or not to submit a basic program which most likely will not win any games given how stiff the competition is. Regards, Carter. --- On Mon, 6/9/08, Rémi Coulom <[EMAIL PROTECTED]> wrote: > From: Rémi Coulom <[EMAIL PROTECTED]> > Subject: [Fwd: Re: [Fwd: Re: [computer-go] Computer Olympiad registration > reminder: 11 days left]] > To: "computer-go" > Date: Monday, June 9, 2008, 1:47 AM > Some answers by the organizers. > > Rémi___ > 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] Ladders and UCT
I hope you don't mind me chiming in here. I think I asked this question quite recently on the mailing list and the reply I received from Magnus Persson (I hope I am not misquoting him) was that Valkyria adjusts the probability distribution based on a simple ladder readout which is a function which returns either success fail or unknown in order to feed this information into the playout process. --- On Mon, 6/16/08, Peter Drake <[EMAIL PROTECTED]> wrote: > From: Peter Drake <[EMAIL PROTECTED]> > Subject: Re: [computer-go] Ladders and UCT > To: "computer-go" > Date: Monday, June 16, 2008, 10:13 PM > Mark: > > Can you say more? Do you mean ALWAYS play such moves first > if they > are available, do so with some probability, or what? > > Peter Drake > http://www.lclark.edu/~drake/ > > > > On Jun 16, 2008, at 4:09 PM, Mark Boon wrote: > > > play ladder-capturing and ladder-escaping moves during > playout___ > 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] Basic question concerning the edges of the board
Hi, I have again been considering trying my hand at implementing a simple go program. The question I have pertains to checking for the edge of the board in capture situations and so on. For a modern CPU (given what limited information I have on this) the extra branches might result in pipeline stalls if I am constantly checking if values are in range. Is it best to extend the size of the board to say 21x21 to somehow avoid these sorts of checks? Or are the relative cost of these branches negligible in the scheme of things? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Basic question concerning the edges of the board
Thanks all for the replies. I am not sure I quite get the 20x21+2 idea but I will take a look back in the archives. Does anyone remember roughly when it was posted to the list? Thanks again, Carter. --- On Mon, 7/13/09, Peter Drake wrote: > From: Peter Drake > Subject: Re: [computer-go] Basic question concerning the edges of the board > To: "computer-go" > Date: Monday, July 13, 2009, 9:08 AM > As in LibEGO, if you define the > off-board points to be both black AND white, finding > captures requires fewer branches. > Peter Drakehttp://www.lclark.edu/~drake/ > > > On Jul 13, 2009, at 8:48 AM, David Fotland > wrote: > I use one dimensional arrays for speed (to > avoid a multiply by 21). > > Old Many Faces code uses arrays of 363 (361 points, pass, > and null-point). > The smallest possible arrays were required to run under 500 > KB total memory. > I avoided edge checks by having a set of small offset > arrays (with 2, 3, or > 4 offsets), chosen by the board. > > My MCTS code uses single dimension arrays with size > suggested by Mark Boon, > from Goliath, 20 * 21 + 2. This is enough to have > points off the edge on > all sides and diagonals. > > David > > -Original Message- > From: > computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] > On Behalf Of Carter Cheng > Sent: Monday, July 13, > 2009 8:36 AM > To: computer-go@computer-go.org > Subject: [computer-go] > Basic question concerning the edges of the board > > > Hi, > > I have again been > considering trying my hand at implementing a simple go > program. The question > I have pertains to checking for the edge of the > board > in capture situations and so on. > For a modern CPU (given what limited > information I have on > this) the extra branches might result in pipeline > stalls if I am > constantly checking if values are in range. Is it best to > extend the size of the > board to say 21x21 to somehow avoid these sorts of > checks? Or are the > relative cost of these branches negligible in the > scheme > of things? > > Thanks in advance, > > Carter. > > > > ___ > 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/ > > > -Inline Attachment Follows- > > ___ > 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] Basic question concerning the edges of the board
Ah alright. I will try to see if I can implement the idea from the comments thus far. Thanks everyone. I probably have a followup question. --- On Mon, 7/13/09, David Fotland wrote: > From: David Fotland > Subject: RE: [computer-go] Basic question concerning the edges of the board > To: "'computer-go'" > Date: Monday, July 13, 2009, 8:04 PM > There was computer go before this > list :) I heard this idea from Mark > sometime around 1988. > > David > > > -Original Message- > > From: computer-go-boun...@computer-go.org > [mailto:computer-go- > > boun...@computer-go.org] > On Behalf Of Carter Cheng > > Sent: Monday, July 13, 2009 10:27 AM > > To: computer-go > > Subject: Re: [computer-go] Basic question concerning > the edges of the > board > > > > > > Thanks all for the replies. I am not sure I quite get > the 20x21+2 idea but > > I will take a look back in the archives. Does anyone > remember roughly when > > it was posted to the list? > > > > Thanks again, > > > > Carter. > > > > --- On Mon, 7/13/09, Peter Drake > wrote: > > > > > From: Peter Drake > > > Subject: Re: [computer-go] Basic question > concerning the edges of the > > board > > > To: "computer-go" > > > Date: Monday, July 13, 2009, 9:08 AM > > > As in LibEGO, if you define the > > > off-board points to be both black AND white, > finding > > > captures requires fewer branches. > > > Peter Drakehttp://www.lclark.edu/~drake/ > > > > > > > > > On Jul 13, 2009, at 8:48 AM, David Fotland > > > wrote: > > > I use one dimensional arrays for speed (to > > > avoid a multiply by 21). > > > > > > Old Many Faces code uses arrays of 363 (361 > points, pass, > > > and null-point). > > > The smallest possible arrays were required to run > under 500 > > > KB total memory. > > > I avoided edge checks by having a set of small > offset > > > arrays (with 2, 3, or > > > 4 offsets), chosen by the board. > > > > > > My MCTS code uses single dimension arrays with > size > > > suggested by Mark Boon, > > > from Goliath, 20 * 21 + 2. This is enough to > have > > > points off the edge on > > > all sides and diagonals. > > > > > > David > > > > > > -Original Message- > > > From: > > > computer-go-boun...@computer-go.org > [mailto:computer-go- > > > boun...@computer-go.org] > > > On Behalf Of Carter Cheng > > > Sent: Monday, July 13, > > > 2009 8:36 AM > > > To: computer-go@computer-go.org > > > Subject: [computer-go] > > > Basic question concerning the edges of the board > > > > > > > > > Hi, > > > > > > I have again been > > > considering trying my hand at implementing a > simple go > > > program. The question > > > I have pertains to checking for the edge of the > > > board > > > in capture situations and so on. > > > For a modern CPU (given what limited > > > information I have on > > > this) the extra branches might result in > pipeline > > > stalls if I am > > > constantly checking if values are in range. Is it > best to > > > extend the size of the > > > board to say 21x21 to somehow avoid these sorts > of > > > checks? Or are the > > > relative cost of these branches negligible in > the > > > scheme > > > of things? > > > > > > Thanks in advance, > > > > > > Carter. > > > > > > > > > > > > ___ > > > 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/ > > > > > > > > > -Inline Attachment Follows- > > > > > > ___ > > > 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/
[computer-go] memory management for search trees(basic question)
This is something I have been curious about since I am somewhat new to writing code in languages which require explicit memory management (as opposed to have some sort of garbage collector do it for you). The question is how do most programs manage memory w.r.t. the search nodes? Is the memory preallocated in advance or is there some strategy to grow the space required as the nodes accumulate during a search? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] memory management for search trees(basic question)
Thanks for the replies. I will most likely be writing in C++ given the additional abstraction mechanisms and my current lack of understanding of preprocessor #define type tricks. I remember reading about Zobrist's hash functions in some old messages on the list and some papers on the GHI issue but at this point I am still just implementing the basic light playout simulation code so I haven't quite gotten here yet. I wonder concerning GHI for doing searches in go that you could in principle encode extra information into the "position" key which could be use to discriminate board positions which appear to be the same but differ in crucial ways. Thanks everyone for the help. --- On Tue, 7/14/09, Don Dailey wrote: > From: Don Dailey > Subject: Re: [computer-go] memory management for search trees(basic question) > To: "computer-go" > Date: Tuesday, July 14, 2009, 8:32 AM > There has been quite a few descriptions > on this forum about how people do this. > > I am guessing, but I think most of the authors allocate a > pool of memory and manage this themselves. Are you > writing in C? > > > In C you can declare a fixed size record (called a > struct) and just make an array of them. This is what > my program does. When I need new nodes I just use the > next ones available and a counter keeps track of where I > am. > > > It's a little more complicated if you also need to > remove nodes. I don't do this. When a new search > begins I can just start over again. > > I think there are a lot of variations of what people > do. Perhaps a better way is to use a hash table > instead of a tree. It's still a tree of course but > structured different. With a hash table a zobrist key is > used to index into a hash table. So you can build your > tree this way, again using a fixed pool of nodes or > whatever hash table method you need to. One advantage > of a hash table is that with transpositions you can resuse > information that has already been computed - but one > disadvantage is that you have to deal with Graph History > Interaction (GHI.) I think most program ignore GHI > for the most part (in a similar way that computer chess > programmers ignore the problem) but I'm not real sure on > this one. > > > You can also use malloc and free to allocate space for > nodes - but it is well known that this can be challenging > for writing bug free programs. I have found that you can > almost always avoid it and I personally only use it for top > level data structures - for instance I might allocate my > initial fixed pool of nodes this way (and so it can be user > configurable) but I won't allocate and free individual > nodes. > > > Also, if you use malloc and free you will surely see a > slowdown. > > Another option is to use the Hans Boehm garbage collector, > a library you simple link to in your C programs. It > will do the automated garbage collection for you - but I > think you will see a slowdown and I think there is a memory > overhead penality for using this as it probably needs > working space. > > > - Don > > > > On Tue, Jul 14, 2009 at 11:06 AM, > Carter Cheng > wrote: > > > > This is something I have been curious about since I am > somewhat new to writing code in languages which require > explicit memory management (as opposed to have some sort of > garbage collector do it for you). The question is how do > most programs manage memory w.r.t. the search nodes? Is the > memory preallocated in advance or is there some strategy to > grow the space required as the nodes accumulate during a > search? > > > > > Thanks in advance, > > > > Carter. > > > > > > > > ___ > > computer-go mailing list > > computer-go@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > -Inline Attachment Follows- > > ___ > 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] memory management for search trees(basic question)
I have a good number of C++ books but strangely though I use to own Meyers' first 2 books I have sort of misplaced them. Perhaps I should get a couple new copies. I will study the Boost Pool source and see what I can glean from it. The only custom allocator design I have on hand in a book is the one in Modern C++ Design. Thanks. --- On Tue, 7/14/09, Darren Cook wrote: > From: Darren Cook > Subject: Re: [computer-go] memory management for search trees(basic question) > To: "computer-go" > Date: Tuesday, July 14, 2009, 4:05 PM > > Thanks for the replies. I will > most likely be writing in C++ ... > > If you've not already, rush out and buy Effective C++ by > Scott Meyers. > Item 10 shows you a memory pool, items 1..9 and 11..50 will > also come in > useful. As will More Effective C++, and Effective STL. > > Boost has a memory pool library (*). I use > boost/detail/quick_allocator.hpp (and if you are familiar > with Boost, > the "detail/" means an unsupported library whose interface > may change > without warning) which was quickest as long as I disabled > thread support. > > If you are planning to have multiple threads share the same > memory pool > I suggest the main boost pool library (*), as I'm sure > they've taken > care of the issues, while never losing sight of > efficiency. > > Darren > > *: http://www.boost.org/doc/libs/1_39_0/libs/pool/doc/index.html > > > > -- > Darren Cook, Software Researcher/Developer > http://dcook.org/gobet/ (Shodan Go Bet - who will > win?) > http://dcook.org/mlsn/ (Multilingual open source > semantic network) > http://dcook.org/work/ (About me and my work) > http://dcook.org/blogs.html (My blogs and articles) > ___ > 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] gtp which version to implement?
Thanks everyone for the help thus far. I have been looking at the GTP protocol page and I am curious which version of the protocol I should try to implement if I want to communicate with the servers. Should I be looking at the GTP 2.0 draft version? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] gtp which version to implement?
Where can I find information on these bridging protocols or are libraries provided for this (to the 9x9 & 19x19 servers)? --- On Wed, 7/15/09, Hellwig Geisse wrote: > From: Hellwig Geisse > Subject: Re: [computer-go] gtp which version to implement? > To: "computer-go" > Date: Wednesday, July 15, 2009, 2:44 AM > On Wed, 2009-07-15 at 11:24 +0200, > Urban Hafner wrote: > > Carter Cheng wrote: > > > Thanks everyone for the help thus far. I have > been looking at the GTP > > protocol page and I am curious which version of the > protocol I should > > try to implement if I want to communicate with the > servers. Should I be > > looking at the GTP 2.0 draft version? > > > > You should implement (part of) the draft. It's widely > used nowadays. I'm > > not sure if there's any server out there that uses the > old version. > > Just to be clear on this point: GTP is not a server > protocol, but > a protocol between a controller and an engine. If you want > the > engine to connect to a server, there is still a bridge > needed, > which communicates with the engine through GTP and with the > server > through whatever protocol the server is speaking. > > Hellwig > > ___ > 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] gtp which version to implement?
Thanks all for the input. --- On Wed, 7/15/09, Don Dailey wrote: > From: Don Dailey > Subject: Re: [computer-go] gtp which version to implement? > To: "computer-go" > Date: Wednesday, July 15, 2009, 9:39 AM > > > On Wed, Jul 15, 2009 at 9:41 AM, > Carter Cheng > wrote: > > Where can I find information on these bridging protocols or > are libraries provided for this (to the 9x9 & 19x19 > servers)? > The CGOS protocol is pretty easy to decode from the cgos > client script which is written in TCL. Even if you > don't know tcl you can learn the protocol easily from > the script. > > > However, there is no need to know the CGOS protocol if your > engine speaks GTP. GTP is designed to be a universal > protocol for GO engines - if your engine knows GTP it should > be able to use all kinds of tool including GOGUI, a nice > user interface for GO programs. The cgos client > program speaks to the server in it's language and to > your program using GTP. See how simple life can be? > > > The CGOS protocol is about to change just slightly as I > will be soon upgrading the server, but an updated client > will be provided so that will require no change on your > part. (And the old CGOS prototol will still work but with > some restrictions.) > > > - Don > > > > > > --- On Wed, 7/15/09, Hellwig Geisse > wrote: > > > > > From: Hellwig Geisse > > > Subject: Re: [computer-go] gtp which version to > implement? > > > To: "computer-go" > > > Date: Wednesday, July 15, 2009, 2:44 AM > > > On Wed, 2009-07-15 at > 11:24 +0200, > > > Urban Hafner wrote: > > > > Carter Cheng wrote: > > > > > Thanks everyone for the help thus far. I > have > > > been looking at the GTP > > > > protocol page and I am curious which version of > the > > > protocol I should > > > > try to implement if I want to communicate with > the > > > servers. Should I be > > > > looking at the GTP 2.0 draft version? > > > > > > > > You should implement (part of) the draft. > It's widely > > > used nowadays. I'm > > > > not sure if there's any server out there that > uses the > > > old version. > > > > > > Just to be clear on this point: GTP is not a server > > > protocol, but > > > a protocol between a controller and an engine. If you > want > > > the > > > engine to connect to a server, there is still a > bridge > > > needed, > > > which communicates with the engine through GTP and > with the > > > server > > > through whatever protocol the server is speaking. > > > > > > Hellwig > > > > > > ___ > > > 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/ > > > > > -Inline Attachment Follows- > > ___ > 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] Erlang and computer go
I have been considering experimenting with Erlang as a means of prototyping certain aspects of a computer go program and I was curious if anyone has tried this already. How does a system like Erlang compare performance wise to writing something in say C/C++ (fastest) or Java? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Erlang and computer go
Thanks both I guess I will stick with C/C++ for now. I have looked at Scala before though not in this particular context. It looks like a pretty compelling language with some pretty nice features (true lambda functions, "argument" pattern matching among others). JVM performance does concern me however. I do have a followup question but I will make a separate topic of it. --- On Fri, 8/14/09, Vlad Dumitrescu wrote: > From: Vlad Dumitrescu > Subject: Re: [computer-go] Erlang and computer go > To: "computer-go" > Date: Friday, August 14, 2009, 1:56 PM > On Fri, Aug 14, 2009 at 22:16, Carter > Cheng > wrote: > > I have been considering experimenting with Erlang as a > means of prototyping certain aspects of a computer go > program and I was curious if anyone has tried this already. > How does a system like Erlang compare performance wise to > writing something in say C/C++ (fastest) or Java? > > Hi, > > I have started for some year ago to try to withe an Erlang > library to > play go, but got distracted by other stuff. > > Erlang has a lot of nice features, but in this particular > instance > speed isn't one of them. The main issue is that there are > no mutable > data structures, so for all processing there will be a lot > of copying. > This is somewhat simplified, of course, but the conclusion > still > holds. I don't have any hard numbers, it would depend very > much upon > the choice of data structure. > > Erlang would be good at coordinating work done by simple > and fast > slaves, written in C for example. It would be very > appropriate for a > distributed engine. The problem here is that the problem > of > synchronizing a distributed UCT tree hasn't been solvet > yet, to my > knowledge. > > regards, > Vlad > ___ > 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] representing liberties
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). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] representing liberties
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). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
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 wrote: > From: Don Dailey > Subject: Re: [computer-go] representing liberties > To: "computer-go" > Date: Friday, August 14, 2009, 2:33 PM > > > On Fri, Aug 14, 2009 at 5:13 PM, > Carter Cheng > 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 > > computer-go@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > -Inline Attachment Follows- > > ___ > 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] representing liberties
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 > 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 > wrote: > > > > > From: Don Dailey > > > Subject: Re: [computer-go] representing liberties > > > To: "computer-go" > > > Date: Friday, August 14, 2009, 2:33 PM > > > > > > > > > On Fri, Aug 14, 2009 at 5:13 PM, > > > Carter Cheng > > > 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 > > > > > > computer-go@computer-go.org > > > > > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > > > > > > > > > > > -Inline Attachment Follows- > > > > > > ___ > > > 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/ > > > > > -Inline Attachment Follows- > > ___ > 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] representing liberties
How do these link list of liberties and array of liberties variants work? Are they sorted lists/arrays? I considered bitmaps but it seemed in many ways a bit wasteful i.e. in most cases for a given group the bitmap probably is extremely sparse. Also if you are trying to identify individual bits I cannot think of any techniques to do this quickly. --- On Sat, 8/15/09, w...@swcp.com wrote: > From: w...@swcp.com > Subject: Re: [computer-go] representing liberties > To: "computer-go" > Date: Saturday, August 15, 2009, 10:54 AM > I tested bit maps in the cgbg > framework, and they perform > slower than other techniques. However, I wrote the code in > C which > does not use the built-in hardware bit tests and sets nor > use SIMD > to merge or clear sets. If you do it in assembler, bitmaps > might work > much better. > > There are various ways that bit test could be combined with > other > techniques such as linked list. However, as far as I know, > these > combinations have not been extensively explored. > > Part of the reason is that the average number of liberties > in a chain > during an insert (when running MC playouts) is only about > 1.3. > > Michael Wing > > > I've seen bit-maps mentioned many times, but is there > any evidence > > it's faster than a 'traditional' implementation? > > > > You can also use board-sized bitmaps. Merging is > a trivial OR > > > operation. > > ___ > 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/
